Discretized Borel Determinacy and P=NP: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== The problem == | |||
A <I>sunflower</I> (a.k.a. <I>Delta-system</I>) of size <math>r</math> is a family of sets <math>A_1, A_2, \dots, A_r</math> such that every element that belongs to more than one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that | |||
:<B>Erdos-Rado Delta-system theorem</B>: There is a function <math>f(k,r)</math> so that every family <math>\cal F</math> of <math>k</math>-sets with more than <math>f(k,r)</math> members contains a sunflower of size <math>r</math>. | |||
(We denote by <math>f(k,r)</math> the smallest integer that suffices for the assertion of the theorem to be true.) The simple proof giving <math>f(k,r)\le k! (r-1)^k</math> can be found [https://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/ here]. | |||
The best known general upper bound on <math>f(k,r)</math> (in the regime where <math>r</math> is bounded and <math>k</math> is large) is | |||
:<math>\displaystyle f(k,r) \leq D(r,\alpha) k! \left( \frac{(\log\log\log k)^2}{\alpha \log\log k} \right)^k</math> | |||
for any <math>\alpha < 1</math>, and some <math>D(r,\alpha)</math> depending on <math>r,\alpha</math>, proven by Kostkocha from 1996. The objective of this project is to improve this bound, ideally to obtain the Erdos-Rado conjecture | |||
:<math>\displaystyle f(k,r) \leq C(r)^k </math> | |||
for some <math>C(r)</math> depending on <math>k</math>. This is known for <math>r=1,2</math> but remains open for larger r. | |||
== Threads == | == Threads == | ||
* [ | * [https://gilkalai.wordpress.com/2015/11/03/polymath10-the-erdos-rado-delta-system-conjecture Polymath10: The Erdos Rado Delta System Conjecture], Gil Kalai, Nov 2, 2015. <B>Active</B> | ||
* [ | |||
* [http:// | == Bibliography == | ||
Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome! | |||
* Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389 | |||
* [https://www.math.uni-bielefeld.de/ahlswede/homepage/public/114.pdf The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets], R. Ahlswede, L. Khachatrian, Journal of Combinatorial Theory, Series A 76, 121-�138 (1996). | |||
* [http://arxiv.org/abs/1205.6847 On the Maximum Number of Edges in a Hypergraph with Given Matching Number], P. Frankl | |||
* An intersection theorem for systems of sets, A. V. Kostochka, Random Structures and Algorithms, 9(1996), 213-221. | |||
* [http://www.math.uiuc.edu/~kostochk/docs/2000/survey3.pdf Extremal problems on <math>\Delta</math>-systems], A. V. Kostochka | |||
* [http://arxiv.org/abs/1202.4196 On Erdos' extremal problem on matchings in hypergraphs], T. Luczak, K. Mieczkowska | |||
* Intersection theorems for systems of sets, J. H. Spencer, Canad. Math. Bull. 20 (1977), 249-254. | |||
Revision as of 09:37, 3 November 2015
The problem
A sunflower (a.k.a. Delta-system) of size [math]\displaystyle{ r }[/math] is a family of sets [math]\displaystyle{ A_1, A_2, \dots, A_r }[/math] such that every element that belongs to more than one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that
- Erdos-Rado Delta-system theorem: There is a function [math]\displaystyle{ f(k,r) }[/math] so that every family [math]\displaystyle{ \cal F }[/math] of [math]\displaystyle{ k }[/math]-sets with more than [math]\displaystyle{ f(k,r) }[/math] members contains a sunflower of size [math]\displaystyle{ r }[/math].
(We denote by [math]\displaystyle{ f(k,r) }[/math] the smallest integer that suffices for the assertion of the theorem to be true.) The simple proof giving [math]\displaystyle{ f(k,r)\le k! (r-1)^k }[/math] can be found here.
The best known general upper bound on [math]\displaystyle{ f(k,r) }[/math] (in the regime where [math]\displaystyle{ r }[/math] is bounded and [math]\displaystyle{ k }[/math] is large) is
- [math]\displaystyle{ \displaystyle f(k,r) \leq D(r,\alpha) k! \left( \frac{(\log\log\log k)^2}{\alpha \log\log k} \right)^k }[/math]
for any [math]\displaystyle{ \alpha \lt 1 }[/math], and some [math]\displaystyle{ D(r,\alpha) }[/math] depending on [math]\displaystyle{ r,\alpha }[/math], proven by Kostkocha from 1996. The objective of this project is to improve this bound, ideally to obtain the Erdos-Rado conjecture
- [math]\displaystyle{ \displaystyle f(k,r) \leq C(r)^k }[/math]
for some [math]\displaystyle{ C(r) }[/math] depending on [math]\displaystyle{ k }[/math]. This is known for [math]\displaystyle{ r=1,2 }[/math] but remains open for larger r.
Threads
- Polymath10: The Erdos Rado Delta System Conjecture, Gil Kalai, Nov 2, 2015. Active
Bibliography
Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!
- Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389
- The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets, R. Ahlswede, L. Khachatrian, Journal of Combinatorial Theory, Series A 76, 121-�138 (1996).
- On the Maximum Number of Edges in a Hypergraph with Given Matching Number, P. Frankl
- An intersection theorem for systems of sets, A. V. Kostochka, Random Structures and Algorithms, 9(1996), 213-221.
- Extremal problems on [math]\displaystyle{ \Delta }[/math]-systems, A. V. Kostochka
- On Erdos' extremal problem on matchings in hypergraphs, T. Luczak, K. Mieczkowska
- Intersection theorems for systems of sets, J. H. Spencer, Canad. Math. Bull. 20 (1977), 249-254.
