The Erdos-Rado sunflower lemma

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

• 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.