|
|
| Line 1: |
Line 1: |
| == The problem ==
| | Unlike prior Polymath projects, the main wiki pages for this project will not be hosted here, but rather at [http://gowers.tiddlyspace.com this tiddlywiki]. |
| | |
| 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://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summer-holidays/ What I did in my summer holidays], Timothy Gowers, Oct 24, 2013. ''Inactive'' |
| | | * [http://gowers.wordpress.com/2013/11/03/dbd1-initial-post DBD1 - initial post], Timothy Gowers, Nov 3, 2013. ''inactive'' |
| == Bibliography ==
| | * [http://gowers.wordpress.com/2014/01/09/dbd2-success-of-a-kind/ DBD2 - success of a kind], Timothy Gowers, Jan 9, 2014. <B>Active</B> |
| | |
| 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.
| |
Unlike prior Polymath projects, the main wiki pages for this project will not be hosted here, but rather at this tiddlywiki.
Threads
