Difference between revisions of "The Erdos-Rado sunflower lemma"

From Polymath1Wiki
Jump to: navigation, search
(The problem)
(The problem)
Line 15: Line 15:
 
:<math>\displaystyle f(k,r) \leq C^k </math>
 
:<math>\displaystyle f(k,r) \leq C^k </math>
  
for some <math>C=C(r)</math> depending on <math>r</math> only.  This is known for <math>r=1,2</math> but remains open for larger r.
+
for some <math>C=C(r)</math> depending on <math>r</math> only.  This is known for <math>r=1,2</math>(indeed we have <math>f(k,r)=1</math> in those cases) but remains open for larger r.
 +
 
 +
== Variants and notation ==
 +
 
 +
Given a family F of sets and a set S,  the star of S is the subfamily of those sets in F containing S, and the link of S is obtained from the star of S by deleting the elements of S from every set in the star. (We use the terms link and star because we do want to consider eventually hypergraphs as geometric/topological objects.)
 +
 
 +
We can restate the delta system problem as follows: f(k,r) is the maximum size of a family of k-sets such that the link of every set A does not contain r pairwise disjoint sets.
 +
 
 +
Let f(k,r;m,n) denote the largest cardinality of a family of k-sets from {1,2,…,n} such that that the link of every set A of size at most m-1  does not contain r pairwise disjoint sets.  Thus f(k,r) = f(k,r;k,n) for n large enough. 
 +
 
 +
:<B>Conjecture 1</B>: <math>f(k,r;m,n) \leq C_r^k n^{k-m}</math> for some <math>C_r</math> depending only on r.
 +
 
 +
This conjecture implies the Erdos-Ko-Rado conjecture (set m=k).  The [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdos-Ko-Rado theorem] asserts that
 +
 
 +
:<math>f(k,2;1,n) = \binom{n-1}{k-1}</math> (1)
 +
 
 +
when <math>n \geq 2k</math>, which is consistent with Conjecture 1.  More generally, Erdos, Ko, and Rado showed
 +
 
 +
:<math>f(k,2;m,n) = \binom{n-m}{k-m}</math>
 +
 
 +
when <math>n</math> is sufficiently large depending on k,m.  The case of smaller n was treated by several authors culminating in the work of [https://www.math.uni-bielefeld.de/ahlswede/homepage/public/114.pdf Ahlswede and Khachatrian].
 +
 
 +
Erdos conjectured that
 +
 
 +
:<math>f(k,r;1,n) = \max( \binom{rk-1}{k}, \binom{n}{k} - \binom{n-r}{k} )</math>
 +
 
 +
for <math>n \geq rk</math>, generalising (1).  This was established for k=2 by Erdos and Gallai, and for r=3 by Frankl (building on work by [http://arxiv.org/abs/1202.4196 Luczak-Mieczkowska]).
 +
 
 +
A family of k-sets is balanced (or k-colored) if it is possible to color the elements with k colors so that every set in the family is colorful.
 +
 
 +
<B>Reduction (folklore)</B>: It is enough to prove Erdos-Rado Delta-system conjecture for the balanced case.
 +
 
 +
<B?Proof</B>: Divide the elements into d color classes at random and take only colorful sets. The expected size of the surviving colorful sets is k!/k^k|F|.
 +
 
 +
<B>Hyperoptimistic conjecture:</B> The maximum size of a balanced collection of k-sets without a sunflower of size r is (r-1)^k.
 +
 
 +
Disproven for k=3,r=3: set <math>|V_1|=|V_2|=|V_3|=3<math> and use ijk to denote the 3-set consisting of the i^th element of V_1, j^th element of V_2, and k^th element of V_3.  Then 000, 001, 010, 011, 100, 101, 112, 122, 212 is a balanced family of 9 3-sets without a 3-sunflower.
  
 
== Threads ==
 
== Threads ==

Revision as of 09:40, 6 November 2015

The problem

A sunflower (a.k.a. Delta-system) 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

Erdos-Rado Delta-system theorem: 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 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 \lt 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^k [/math]

for some [math]C=C(r)[/math] depending on [math]r[/math] only. This is known for [math]r=1,2[/math](indeed we have [math]f(k,r)=1[/math] in those cases) but remains open for larger r.

Variants and notation

Given a family F of sets and a set S, the star of S is the subfamily of those sets in F containing S, and the link of S is obtained from the star of S by deleting the elements of S from every set in the star. (We use the terms link and star because we do want to consider eventually hypergraphs as geometric/topological objects.)

We can restate the delta system problem as follows: f(k,r) is the maximum size of a family of k-sets such that the link of every set A does not contain r pairwise disjoint sets.

Let f(k,r;m,n) denote the largest cardinality of a family of k-sets from {1,2,…,n} such that that the link of every set A of size at most m-1 does not contain r pairwise disjoint sets. Thus f(k,r) = f(k,r;k,n) for n large enough.

Conjecture 1: [math]f(k,r;m,n) \leq C_r^k n^{k-m}[/math] for some [math]C_r[/math] depending only on r.

This conjecture implies the Erdos-Ko-Rado conjecture (set m=k). The Erdos-Ko-Rado theorem asserts that

[math]f(k,2;1,n) = \binom{n-1}{k-1}[/math] (1)

when [math]n \geq 2k[/math], which is consistent with Conjecture 1. More generally, Erdos, Ko, and Rado showed

[math]f(k,2;m,n) = \binom{n-m}{k-m}[/math]

when [math]n[/math] is sufficiently large depending on k,m. The case of smaller n was treated by several authors culminating in the work of Ahlswede and Khachatrian.

Erdos conjectured that

[math]f(k,r;1,n) = \max( \binom{rk-1}{k}, \binom{n}{k} - \binom{n-r}{k} )[/math]

for [math]n \geq rk[/math], generalising (1). This was established for k=2 by Erdos and Gallai, and for r=3 by Frankl (building on work by Luczak-Mieczkowska).

A family of k-sets is balanced (or k-colored) if it is possible to color the elements with k colors so that every set in the family is colorful.

Reduction (folklore): It is enough to prove Erdos-Rado Delta-system conjecture for the balanced case.

<B?Proof</B>: Divide the elements into d color classes at random and take only colorful sets. The expected size of the surviving colorful sets is k!/k^k|F|.

Hyperoptimistic conjecture: The maximum size of a balanced collection of k-sets without a sunflower of size r is (r-1)^k.

Disproven for k=3,r=3: set [math]|V_1|=|V_2|=|V_3|=3\ltmath\gt and use ijk to denote the 3-set consisting of the i^th element of V_1, j^th element of V_2, and k^th element of V_3. Then 000, 001, 010, 011, 100, 101, 112, 122, 212 is a balanced family of 9 3-sets without a 3-sunflower. == 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. \ltB\gtActive\lt/B\gt == External links == * [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower (mathematics)] (Wikipedia article) * [http://mathoverflow.net/questions/163689/what-is-the-best-lower-bound-for-3-sunflowers What is the best lower bound for 3-sunflowers?] (Mathoverflow) == 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://renyi.hu/~p_erdos/1960-04.pdf Intersection theorems for systems of sets], P. Erdős, R. Rado, Journal of the London Mathematical Society, Second Series 35 (1960), 85–90. * [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 \ltmath\gt\Delta[/math]-systems], A. V. Kostochka