The Erdos-Rado sunflower lemma: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
 
(25 intermediate revisions by 3 users not shown)
Line 13: Line 13:
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
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>
:<math>\displaystyle f(k,r) \leq C^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.
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 <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.
 
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), 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 [http://arxiv.org/abs/1202.4196 Luczak-Mieczkowska]).
 
A family of k-sets is <I>balanced</I> (or <I>k-colored</I>) 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 <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>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>. For this function we also know that <math> g(a+b,r)\ge g(a,r)g(b,r)</math>, as shown by Abbott-Hanson in On finite Δ-systems II.
 
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. For all three functions only exponential lower bounds and factorial type upper bounds are known.
 
Denote by <math>3DES(n)</math> the largest integer such that there is a group of size <math>n</math> and a subset <math>S</math> of size <math>3DES(n)</math> without three ''disjoint equivoluminous subsets'', i.e., there is no <math>S=S_1\cup^* S_2\cup^* S_3\cup^* S_{rest}</math> such that <math>\sum_{s\in S_1} s=\sum_{s\in S_2} s=\sum_{s\in S_3} s</math>. As noticed by Alon-Shpilka-Umans, <math>{3DES(n) \choose DES(n)} / n \le g(DES(n),3)</math> holds, thus if <math>g(k,3)</math> grows exponentially, then <math>3DES(n)=O(\log n)</math>.
 
== 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)=r^k+o(r^k)</math> from Kostochka-Rödl-Talysheva (note that that paper swaps the notation for k and r).
 
{| class="wikitable"
! style="font-weight: bold; font-style: italic;" | r\k
! style="text-align: center; font-weight: normal; font-style: italic;" | 2
! style="text-align: center; font-weight: normal; font-style: italic;" | 3
! style="text-align: center; font-weight: normal; font-style: italic;" | 4
! style="text-align: center; font-weight: normal; font-style: italic;" | 5
! style="text-align: center; font-weight: normal; font-style: italic;" | 6
! style="text-align: center; font-weight: normal; font-style: italic;" | ...k
|-
| style="text-align: center; font-style: italic;" | 3
| style="text-align: right; font-weight: bold;" | 6
| style="text-align: right; font-weight: bold;" | 20
| style="text-align: right;" | 54-
| style="text-align: right;" | 160-
| style="text-align: right;" | 600-
| style="text-align: center;" | ~3.16^k
|-
| style="text-align: center; font-style: italic;" | 4
| style="text-align: right; font-weight: bold;" | 10
| style="text-align: right;" | 38-
| style="text-align: right;" | 114-
| style="text-align: right;" | 380-
| style="text-align: right;" | 1444-
| style="text-align: center;" | ~3.36^k
|-
| style="text-align: center; font-style: italic;" | 5
| style="text-align: right; font-weight: bold;" | 20
| style="text-align: right;" | 88-
| style="text-align: right;" | 400-
| style="text-align: right;" | 1760-
| style="text-align: right;" | 8000-
| style="text-align: center;" | ~4.24^k
|-
| style="text-align: center; font-style: italic;" | 6
| style="text-align: right; font-weight: bold;" | 27
| style="text-align: right;" | 146-
| style="text-align: right;" | 730-
| style="text-align: right;" | 3942-
| style="text-align: right;" | 21316-
| style="text-align: center;" | ~5.26^k
|}


== 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>
* [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.  <I>Inactive</I>
* [https://gilkalai.wordpress.com/2015/11/11/polymath10-post-2-homological-approach/ Polymath10, Post 2: Homological Approach], Gil Kalai, Nov 10, 2015. <I>Inactive</I>
* [https://gilkalai.wordpress.com/2015/12/08/polymath-10-post-3-how-are-we-doing/ Polymath 10 Post 3: How are we doing?], Gil Kalai, Dec 8, 2015. <I>Inactive</I>
* [https://gilkalai.wordpress.com/2016/01/31/polymath10-post-4-back-to-the-drawing-board/ Polymath10-post 4: Back to the drawing board?], Gil Kalai, Jan 31, 2016. <B>Active</B>


== Wikipedia links ==
== External links ==


* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower (mathematics)]
* [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdos-Ko-Rado theorem] (Wikipedia article)
* [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 ==
== Bibliography ==
Line 29: Line 124:
Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!
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
* [http://anothersample.net/on-set-systems-not-containing-delta-systems On set systems not containing delta systems], H. L. Abbott and G. Exoo, Graphs and Combinatorics 8 (1992), 1–9.
* [http://www.sciencedirect.com/science/article/pii/0012365X74901034 On finite Δ-systems], H. L. Abbott and D. Hanson, Discrete Math. 8 (1974), 1-12.
* [http://www.sciencedirect.com/science/article/pii/0012365X7790139X On finite Δ-systems II], H. L. Abbott and D. Hanson, Discrete Math. 17 (1977), 121-126.
* [http://www.sciencedirect.com/science/article/pii/0097316572901033 Intersection theorems for systems of sets], H. L. Abbott, D. Hanson, and N. Sauer,  J. Comb. Th. Ser. A 12 (1972), 381–389.
* [http://arxiv.org/abs/1511.02888  Hodge theory for combinatorial geometries], Karim Adiprasito, June Huh, and Erick Katz
* [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).
* [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).
* Intersection theorems for systems of sets, P. Erdős, R. Rado,ournal of the London Mathematical Society, Second Series 35 (1960), 85–90.  
* [http://users.cms.caltech.edu/~umans/papers/ASU11-final.pdf On Sunflowers and Matrix Multiplication], N. Alon, A. Shpilka, C. Umans, Computational Complexity 22 (2013), 219-243.
* [http://www.sciencedirect.com/science/article/pii/0012365X9400185L On set systems without weak 3-Δ-subsystems], M. Axenovich, D. Fon-Der-Flaassb, A. Kostochka, Discrete Math. 138 (1995), 57-62.
* [http://www.renyi.hu/~p_erdos/1961-07.pdf Intersection theorems for systems of finite sets], P. Erdős, C. Ko, R. Rado, The Quarterly Journal of Mathematics. Oxford. Second Series 12 (1961), 313–320.
* [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
* [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://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.300.1783&rep=rep1&type=pdf 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://www.math.uiuc.edu/~kostochk/docs/2000/survey3.pdf Extremal problems on Δ-systems], A. V. Kostochka
* On Systems of Small Sets with No Large Δ-Subsystems, A. V. Kostochka, V. Rödl, and L. A. Talysheva, Comb. Probab. Comput. 8 (1999), 265-268.
* [http://arxiv.org/abs/1202.4196 On Erdos' extremal problem on matchings in hypergraphs], T. Luczak, K. Mieczkowska
* [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.
* Intersection theorems for systems of sets,  J. H. Spencer, Canad. Math. Bull. 20 (1977), 249-254.

Latest revision as of 13:26, 29 July 2020

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^k }[/math]

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

Variants and notation

Given a family [math]\displaystyle{ \cal F }[/math] of sets and a set S, the star of S is the subfamily of those sets in [math]\displaystyle{ \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]\displaystyle{ f(k,r;m,n) \leq C_r^k n^{k-m} }[/math] for some [math]\displaystyle{ 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]\displaystyle{ f(k,2;1,n) = \binom{n-1}{k-1} }[/math] (1)

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

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

when [math]\displaystyle{ 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]\displaystyle{ f(k,r;1,n) = \max( \binom{rk-1}{k}, \binom{n}{k} - \binom{n-r}{k} ) }[/math]

for [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ k=3,r=3 }[/math]: set [math]\displaystyle{ |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]\displaystyle{ r }[/math] is a family of [math]\displaystyle{ r }[/math] sets, [math]\displaystyle{ A_1,\ldots,A_r }[/math], such that their pairwise intersections have the same size, i.e., [math]\displaystyle{ |A_i\cap A_j|=|A_{i'}\cap A_{j'}| }[/math] for every [math]\displaystyle{ i\ne j }[/math] and [math]\displaystyle{ i'\ne j' }[/math]. If we denote the size of the largest family of [math]\displaystyle{ k }[/math]-sets without an [math]\displaystyle{ r }[/math]-weak sunflower by [math]\displaystyle{ g(k,r) }[/math], by definition we have [math]\displaystyle{ g(k,r)\le f(k,r) }[/math]. For this function we also know that [math]\displaystyle{ g(a+b,r)\ge g(a,r)g(b,r) }[/math], as shown by Abbott-Hanson in On finite Δ-systems II.

Also, if we denote by [math]\displaystyle{ R_r(k)-1 }[/math] the size of the largest complete graph whose edges can be colored with [math]\displaystyle{ r }[/math] colors such that there is no monochromatic clique on [math]\displaystyle{ k }[/math] vertices, then we have [math]\displaystyle{ g(k,r)\le R_r(k)-1 }[/math], as we can color the edges running between the [math]\displaystyle{ k }[/math]-sets of our weak sunflower-free family with the intersection sizes. For all three functions only exponential lower bounds and factorial type upper bounds are known.

Denote by [math]\displaystyle{ 3DES(n) }[/math] the largest integer such that there is a group of size [math]\displaystyle{ n }[/math] and a subset [math]\displaystyle{ S }[/math] of size [math]\displaystyle{ 3DES(n) }[/math] without three disjoint equivoluminous subsets, i.e., there is no [math]\displaystyle{ S=S_1\cup^* S_2\cup^* S_3\cup^* S_{rest} }[/math] such that [math]\displaystyle{ \sum_{s\in S_1} s=\sum_{s\in S_2} s=\sum_{s\in S_3} s }[/math]. As noticed by Alon-Shpilka-Umans, [math]\displaystyle{ {3DES(n) \choose DES(n)} / n \le g(DES(n),3) }[/math] holds, thus if [math]\displaystyle{ g(k,3) }[/math] grows exponentially, then [math]\displaystyle{ 3DES(n)=O(\log n) }[/math].

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]\displaystyle{ k }[/math] fixed we have [math]\displaystyle{ f(k,r)=r^k+o(r^k) }[/math] from Kostochka-Rödl-Talysheva (note that that paper swaps the notation for k and r).

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!