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

From Polymath1Wiki
Jump to: navigation, search
m (→‎Bibliography: fixed deltas)
(→‎Variants and notation: added weak sunflower section)
Line 19: Line 19:
 
== Variants and notation ==
 
== Variants and notation ==
  
−
Given a family F of sets and a set S,  the <I>star</I> of S is the subfamily of those sets in F containing S, and the <I>link</I> 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.)
+
Given a family <math>\cal F</math> of sets and a set S,  the <I>star</I> of S is the subfamily of those sets in <math>\cal F</math> containing S, and the <I>link</I> 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.
 
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.
Line 47: Line 47:
 
<B>Reduction (folklore)</B>: It is enough to prove Erdos-Rado Delta-system conjecture for the balanced case.
 
<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>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 <math>k!/k^k \cdot |\cal F|</math>.
  
 
<B>Hyperoptimistic conjecture:</B> The maximum size of a balanced collection of k-sets without a sunflower of size r is (r-1)^k.
 
<B>Hyperoptimistic conjecture:</B> The maximum size of a balanced collection of k-sets without a sunflower of size r is (r-1)^k.
  
 
<B>Disproven for <math>k=3,r=3</math></B>: 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.
 
<B>Disproven for <math>k=3,r=3</math></B>: 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.
 +
 +
A ''weak sunflower'' (''weak Delta-system'') of size <math>r</math> is a family of <math>r</math> sets, <math> A_1,\ldots,A_r</math>, such that their pairwise intersections have the same size, i.e., <math> |A_i\cap A_j|=|A_{i'}\cap A_{j'}|</math> for every <math> i\ne j</math> and <math> i'\ne j'</math>. If we denote the size of the largest family of <math>k</math>-sets without an <math>r</math>-weak sunflower by <math>g(k,r)</math>, by definition we have <math>g(k,r)\le f(k,r)</math>. Also, if we denote by <math>R_r(k)-1</math> the size of the largest complete graph whose edges can be colored with <math>r</math> colors such that there is no monochromatic clique on <math>k</math> vertices, then we have <math>g(k,r)\le R_r(k)-1</math>, as we can color the edges running between the <math>k</math>-sets of our weak sunflower-free family with the intersection sizes. Also, denote by <math>3DES(n)</math> the least integer such that given <math>3DES(n)</math> elements <math>S</math> from a group of size <math>n</math>, one can always select three disjoint equivoluminous subset of <math>S</math>, i.e., there exists <math>S=S_1\cup^* S_2\cup^* S_3\cup^* S_0</math> such that <math>\sum_{s\in S_1}=\sum_{s\in S_2}=\sum_{s\in S_3}</math>. Then if <math>2^{3DES(n)}/n></math> - to be continued...
  
 
== Small values ==
 
== Small values ==

Revision as of 08:56, 5 February 2016

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 [math]\cal F[/math] of sets and a set S, the star of S is the subfamily of those sets in [math]\cal F[/math] 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), and again consistent with Conjecture 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.

Proof: Divide the elements into d color classes at random and take only colorful sets. The expected size of the surviving colorful sets is [math]k!/k^k \cdot |\cal F|[/math].

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

Disproven for [math]k=3,r=3[/math]: 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.

A weak sunflower (weak Delta-system) of size [math]r[/math] is a family of [math]r[/math] sets, [math] A_1,\ldots,A_r[/math], such that their pairwise intersections have the same size, i.e., [math] |A_i\cap A_j|=|A_{i'}\cap A_{j'}|[/math] for every [math] i\ne j[/math] and [math] i'\ne j'[/math]. If we denote the size of the largest family of [math]k[/math]-sets without an [math]r[/math]-weak sunflower by [math]g(k,r)[/math], by definition we have [math]g(k,r)\le f(k,r)[/math]. Also, if we denote by [math]R_r(k)-1[/math] the size of the largest complete graph whose edges can be colored with [math]r[/math] colors such that there is no monochromatic clique on [math]k[/math] vertices, then we have [math]g(k,r)\le R_r(k)-1[/math], as we can color the edges running between the [math]k[/math]-sets of our weak sunflower-free family with the intersection sizes. Also, denote by [math]3DES(n)[/math] the least integer such that given [math]3DES(n)[/math] elements [math]S[/math] from a group of size [math]n[/math], one can always select three disjoint equivoluminous subset of [math]S[/math], i.e., there exists [math]S=S_1\cup^* S_2\cup^* S_3\cup^* S_0[/math] such that [math]\sum_{s\in S_1}=\sum_{s\in S_2}=\sum_{s\in S_3}[/math]. Then if [math]2^{3DES(n)}/n\gt[/math] - to be continued...

Small values

Below is a collection of known constructions for small values, taken from Abbott-Exoo. Boldface stands for matching upper bound (and best known upper bounds are planned to be added to other entries). Also note that for [math]k[/math] fixed we have [math]f(k,r)=k^r+o(k^r)[/math] from Kostochka-Rödl-Talysheva.

r\k 2 3 4 5 6 ...k
3 6 20 54- 160- 600- ~3.16^k
4 10 38- 114- 380- 1444- ~3.36^k
5 20 88- 400- 1760- 8000- ~4.24^k
6 27 146- 730- 3942- 21316- ~5.26^k

Threads

External links

Bibliography

Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!

Retrieved from "http://michaelnielsen.org/polymath1/index.php?title=The_Erdos-Rado_sunflower_lemma&oldid=9797"