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

(added small values) |
(→Variants and notation) |
||

(9 intermediate revisions by 2 users not shown) | |||

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>. 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 == | == Small values == | ||

Line 61: | Line 67: | ||

{| class="wikitable" | {| class="wikitable" | ||

! style="font-weight: bold; font-style: italic;" | r\k | ! style="font-weight: bold; font-style: italic;" | r\k | ||

− | ! style="text-align: center; font-style: italic;" | 2 | + | ! style="text-align: center; font-weight: normal; font-style: italic;" | 2 |

− | ! style="text-align: center; font-style: italic;" | 3 | + | ! style="text-align: center; font-weight: normal; font-style: italic;" | 3 |

− | ! style="text-align: center; font-style: italic;" | 4 | + | ! style="text-align: center; font-weight: normal; font-style: italic;" | 4 |

− | ! style="text-align: center; font-style: italic;" | 5 | + | ! style="text-align: center; font-weight: normal; font-style: italic;" | 5 |

− | ! style="text-align: center; font-style: italic;" | 6 | + | ! style="text-align: center; font-weight: normal; font-style: italic;" | 6 |

− | ! style="text-align: center; font-weight: | + | ! style="text-align: center; font-weight: normal; font-style: italic;" | ...k |

|- | |- | ||

| style="text-align: center; font-style: italic;" | 3 | | style="text-align: center; font-style: italic;" | 3 | ||

Line 100: | Line 106: | ||

| style="text-align: center;" | ~5.26^k | | 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. <I>Inactive</I> | * [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. <B>Active</B> | + | * [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> | ||

== External links == | == External links == | ||

Line 115: | 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! | ||

− | * On set systems not containing delta systems, H. L. Abbott and G. Exoo, Graphs and Combinatorics 8 (1992), 1–9. | + | * [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. |

− | * On finite | + | * [http://www.sciencedirect.com/science/article/pii/0012365X74901034 On finite Δ-systems], H. L. Abbott and D. Hanson, Discrete Math. 8 (1974), 1-12. |

− | * Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389. | + | * [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 | * [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). | ||

− | * [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 | + | * [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://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 | + | * [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. | * 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 11:58, 5 February 2016

## Contents

## 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]. 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)=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

- Polymath10: The Erdos Rado Delta System Conjecture, Gil Kalai, Nov 2, 2015.
*Inactive* - Polymath10, Post 2: Homological Approach, Gil Kalai, Nov 10, 2015.
*Inactive* - Polymath 10 Post 3: How are we doing?, Gil Kalai, Dec 8, 2015.
*Inactive* - Polymath10-post 4: Back to the drawing board?, Gil Kalai, Jan 31, 2016.
**Active**

## External links

- Erdos-Ko-Rado theorem (Wikipedia article)
- Sunflower (mathematics) (Wikipedia article)
- 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!

- On set systems not containing delta systems, H. L. Abbott and G. Exoo, Graphs and Combinatorics 8 (1992), 1–9.
- On finite Δ-systems, H. L. Abbott and D. Hanson, Discrete Math. 8 (1974), 1-12.
- On finite Δ-systems II, H. L. Abbott and D. Hanson, Discrete Math. 17 (1977), 121-126.
- Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389.
- Hodge theory for combinatorial geometries, Karim Adiprasito, June Huh, and Erick Katz
- 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 Sunflowers and Matrix Multiplication, N. Alon, A. Shpilka, C. Umans, Computational Complexity 22 (2013), 219-243.
- On set systems without weak 3-Δ-subsystems, M. Axenovich, D. Fon-Der-Flaassb, A. Kostochka, Discrete Math. 138 (1995), 57-62.
- 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.
- Intersection theorems for systems of sets, P. Erdős, R. Rado, Journal of the London Mathematical Society, Second Series 35 (1960), 85–90.
- 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 Δ-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.
- 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.