Sunflower (mathematics)

A mathematical sunflower can be pictured as a flower. The kernel of the sunflower is the brown part in the middle, and each set of the sunflower is the union of a petal and the kernel.

In the mathematical fields of set theory and extremal combinatorics, a sunflower or ${\displaystyle \Delta }$-system^[1] is a collection of sets whose pairwise intersection is constant. This constant intersection is called the kernel of the sunflower.

The main research question arising in relation to sunflowers is: under what conditions does there exist a large sunflower (a sunflower with many sets) in a given collection of sets? The ${\displaystyle \Delta }$-lemma, sunflower lemma, culminating in the sunflower conjecture give successively weaker conditions which would imply the existence of a large sunflower in a given collection, with the latter being one of the most famous open problems of extremal combinatorics. ^[2]

Formal definition[]

Suppose ${\displaystyle W}$ is a set system, that is, a collection of subsets of a set ${\displaystyle U}$. The collection ${\displaystyle W}$ is a sunflower (or ${\displaystyle \Delta }$-system) if there is a subset ${\displaystyle S}$ of ${\displaystyle U}$ such that for each distinct ${\displaystyle A}$ and ${\displaystyle B}$ in ${\displaystyle W}$, we have ${\displaystyle A\cap B=S}$. In other words, a set system or collection of sets ${\displaystyle W}$ is a sunflower if the pairwise intersection of each set in ${\displaystyle W}$ is constant. Note that this intersection, ${\displaystyle S}$, may be empty; a collection of pairwise disjoint subsets is also a sunflower. Similarly, a collection of sets each containing the same elements is also trivially a sunflower.

Delta System Theorem and Sunflower Lemma[]

A basic and simple result of Erdos and Rado asserts:

Erdos-Rado ${\displaystyle \Delta }$-system theorem:

There is a function ${\displaystyle f(k,r)}$ so that every set system ${\displaystyle W}$ of sets of cardinality at most ${\displaystyle k}$ with more than ${\displaystyle f(k,r)}$ members contains a sunflower of ${\displaystyle r}$ sets.

Proof. Suppose there exists a set system ${\displaystyle W}$ such that there exists a ${\displaystyle k>0}$ and ${\displaystyle r>0}$ such that for any cardinality of the set system ${\displaystyle W}$, there is no sunflower of ${\displaystyle r}$ sets in ${\displaystyle W}$. We choose ${\displaystyle W}$ to be infinite. Since ${\displaystyle W}$ contains no sunflower of size ${\displaystyle r}$, ${\displaystyle W}$ can have at most ${\displaystyle r-1}$ pairwise disjoint subsets since ${\displaystyle r}$ disjoint subsets constitute a sunflower. Let ${\displaystyle K_{a_{0}}}$ denote the maximal set of pairwise disjoint subsets of ${\displaystyle W}$; ${\displaystyle K_{a_{0}}}$ is of cardinality at most ${\displaystyle r-1}$. It follows that each set in ${\displaystyle W}$ outside ${\displaystyle K_{a_{0}}}$ intersects with at least one set in ${\displaystyle K_{a_{0}}}$. Otherwise, suppose there was a set in ${\displaystyle W}$ outside ${\displaystyle K_{a_{0}}}$ which did not intersect any set in ${\displaystyle K}$; then it would be pairwise disjoint with each set in ${\displaystyle K}$ and hence with the ${\displaystyle r-1}$ sets in ${\displaystyle K}$, would constitute an ${\displaystyle r}$ set sunflower, contradicting the assumption.

For ${\displaystyle W}$ arbitrarily large, there is an element ${\displaystyle a_{1}}$ in the sets in ${\displaystyle K_{a_{0}}}$ such that infinitely many sets in ${\displaystyle W}$ will contain ${\displaystyle a}$ by the Inverse Pidgeonhole principle. We remove the common element from all of these sets and denote this set system by ${\displaystyle K_{a_{1}}}$. Since by assumption, there is no ${\displaystyle r}$ set sunflower, there are at most ${\displaystyle r-1}$ disjoint sets in ${\displaystyle K_{a_{1}}}$. Otherwise, those ${\displaystyle r}$ sets would form a sunflower and the intersection set of the sunflower would be ${\displaystyle {a}}$. We construct ${\displaystyle K_{a_{k}}}$ from ${\displaystyle K_{a_{k-1}}}$ by removing ${\displaystyle {a_{k}}}$ from the infinitely many sets in ${\displaystyle K_{a_{k-1}}}$ containing ${\displaystyle a_{k}}$ where ${\displaystyle a_{k}}$ is an element from the at most ${\displaystyle r-1}$ pairwise disjoint ${\displaystyle k}$-sets contained in ${\displaystyle K_{a_{k-1}}}$. ${\displaystyle K_{a_{k}}}$ is now an infinite set of empty sets, implying that there exists an infinite set of identical ${\displaystyle k}$-sets in ${\displaystyle W}$, a contradiction. This completes the proof.

Erdős & Rado (1960, p. 86) proved the sunflower lemma, which states that ${\displaystyle f(k,r)\leq k!(r-1)^{k+1}}$. That is, if ${\displaystyle k}$ and ${\displaystyle r}$ are positive integers, then a set system ${\displaystyle W}$ of cardinality greater or equal to ${\displaystyle k!(r-1)^{k+1}}$ of sets of cardinality at most ${\displaystyle k}$ contains a sunflower with at least ${\displaystyle r}$ sets. The proof of the Erdos-Rado Delta-system theorem may be adapted for finite ${\displaystyle W}$ to prove the lemma, in particular, by observing that the total number of elements in the sets of the maximal pairwise disjoint sets in ${\displaystyle K_{a_{0}}}$, ${\displaystyle K_{a_{1}}}$,...,${\displaystyle K_{a_{k-1}}}$, ${\displaystyle K_{a_{k}}}$ are ${\displaystyle (r-1)k}$, ${\displaystyle (r-1)(k-1)}$,..., ${\displaystyle r}$ respectively, and that the size of ${\displaystyle K_{a_{i}}}$ can be chosen to be at least ${\displaystyle K_{a_{i-1}}/[(r-1)(k-i)]}$.

The following gives a direct inductive proof of the Erdos-Rado sunflower lemma.

Proof. Clearly ${\displaystyle f(0,r)\leq r-1}$ since if every set is the empty set, then any ${\displaystyle r}$ size set of empty sets is an ${\displaystyle r}$ set sunflower as ${\displaystyle r}$ identical sets is an ${\displaystyle r}$ set sunflower. ${\displaystyle F}$ which contains sets of size ${\displaystyle k+1}$ either has a subset ${\displaystyle K}$ of pairwise disjoint ${\displaystyle k-}$sets of size greater or equal to ${\displaystyle r}$ which would constitute an ${\displaystyle r}$ set sunflower and we are done or it contains a disjoint set of size at most ${\displaystyle r-1}$ containing at most ${\displaystyle (r-1)(k+1)}$ distinct elements. Hence there exists in the latter case an element of the pairwise disjoint sets in ${\displaystyle K}$ that is contained in ${\displaystyle |F|/(r-1)(k+1)}$sets of ${\displaystyle F}$. This follows because of the following trivial lemma where Σ${\displaystyle (C)}$ denotes the summation of elements in the set ${\displaystyle C}$:

Lemma 1. Suppose ${\displaystyle A=(a_{1},....,a_{n})}$ are positive integers for ${\displaystyle n>0}$ and Σ${\displaystyle (A)=m}$. Then for every ${\displaystyle k}$ such that ${\displaystyle n\geq k>0}$, there is a ${\displaystyle k}$ element subset of ${\displaystyle A}$, ${\displaystyle B}$, such that Σ${\displaystyle (B)\geq m/k}$.

Hence if ${\displaystyle |F|\geq (r-1)(k+1)f(k,r)}$, where ${\displaystyle f(k,r)}$ is well-defined by the induction hypothesis, then ${\displaystyle F}$ contains an ${\displaystyle r}$ set sunflower of size ${\displaystyle k+1}$sets. Hence, ${\displaystyle f(k+1,r)\leq f(k,r)(r-1)(k+1)}$ and the theorem follows.

^[3]}}

Applications of the Sunflower Lemma[]

The sunflower lemma has numerous applications in theoretical computer science. For example, in 1986, Razborov used the sunflower lemma to prove that the Clique language required ${\displaystyle n^{log(n)}}$ (superpolynomial) size monotone circuits, a breakthrough result in circuit complexity theory at the time. Håstad, Jukna, and Pudlák used it to prove lower bounds on depth-${\displaystyle 3}$ ${\displaystyle AC_{0}}$ circuits. It has also been applied in the parameterized complexity of the hitting set problem, to design fixed-parameter tractable algorithms for finding small sets of elements that contain at least one element from a given family of sets.^[4]

Erdős-Rado Sunflower Conjecture[]

The sunflower conjecture is one of several variations of the conjecture of Erdős & Rado (1960, p. 86) that for each ${\displaystyle r>2}$, ${\displaystyle f(k,r)\leq C^{k}}$ for some constant ${\displaystyle C>0}$ depending only on ${\displaystyle r}$. The conjecture remains wide open even for fixed low values of ${\displaystyle r}$; for example ${\displaystyle r=3}$; it is not known whether ${\displaystyle f(k,3)\leq C^{k}}$ for some ${\displaystyle C>0}$. It is known that ${\displaystyle 10^{.5k}\leq f(k,3)}$. ^[5] A 2021 paper by Alweiss, Lovett, Wu, and Zhang gives the best progress towards the conjecture, proving that ${\displaystyle f(k,r)\leq C^{k}}$ for ${\displaystyle C=(\log k)^{1+o(1)}(r-1)}$.^[6][7] A month after the release of the first version of their paper, Rao sharpened the bound to ${\displaystyle C=(\log k)(r-1)}$.

Analogue for infinite collections of sets[]

A version of the ${\displaystyle \Delta }$-lemma which is essentially equivalent to the Erdos-Rado ${\displaystyle \Delta }$-system theorem states that a countable collection of k-sets contains a countably infinite sunflower or ${\displaystyle \Delta }$-system.

The ${\displaystyle \Delta }$-lemma states that every uncountable collection of finite sets contains an uncountable ${\displaystyle \Delta }$-system.

The ${\displaystyle \Delta }$-lemma is a combinatorial set-theoretic tool used in proofs to impose an upper bound on the size of a collection of pairwise incompatible elements in a forcing poset. It may for example be used as one of the ingredients in a proof showing that it is consistent with Zermelo–Fraenkel set theory that the continuum hypothesis does not hold. It was introduced by Shanin (1946).

If ${\displaystyle W}$ is an ${\displaystyle \omega _{2}}$-sized collection of countable subsets of ${\displaystyle \omega _{2}}$, and if the continuum hypothesis holds, then there is an ${\displaystyle \omega _{2}}$-sized ${\displaystyle \Delta }$-subsystem. Let ${\displaystyle \langle A_{\alpha }:\alpha <\omega _{2}\rangle }$ enumerate ${\displaystyle W}$. For ${\displaystyle \operatorname {cf} (\alpha )=\omega _{1}}$, let ${\displaystyle f(\alpha )=\sup(A_{\alpha }\cap \alpha )}$. By Fodor's lemma, fix ${\displaystyle S}$ stationary in ${\displaystyle \omega _{2}}$ such that ${\displaystyle f}$ is constantly equal to ${\displaystyle \beta }$ on ${\displaystyle S}$. Build ${\displaystyle S'\subseteq S}$ of cardinality ${\displaystyle \omega _{2}}$ such that whenever ${\displaystyle i<j}$ are in ${\displaystyle S'}$ then ${\displaystyle A_{i}\subseteq j}$. Using the continuum hypothesis, there are only ${\displaystyle \omega _{1}}$-many countable subsets of ${\displaystyle \beta }$, so by further thinning we may stabilize the kernel.

See also[]

• Cap set

References[]

• Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (June 2020), "Improved bounds for the sunflower lemma", Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, pp. 624–630, arXiv:1908.08483, doi:10.1145/3357713.3384234, ISBN 978-1-4503-6979-4
• Deza, M.; Frankl, P. (1981), "Every large set of equidistant (0,+1,–1)-vectors forms a sunflower", Combinatorica, 1 (3): 225–231, doi:10.1007/BF02579328, ISSN 0209-9683, MR 0637827
• Erdős, Paul; Rado, R. (1960), "Intersection theorems for systems of sets", Journal of the London Mathematical Society, Second Series, 35 (1): 85–90, doi:10.1112/jlms/s1-35.1.85, ISSN 0024-6107, MR 0111692
• Flum, Jörg; Grohe, Martin (2006), "A Kernelization of Hitting Set", Parameterized Complexity Theory, EATCS Ser. Texts in Theoretical Computer Science, Springer, pp. 210–212, doi:10.1007/3-540-29953-X, MR 2238686
• Jech, Thomas (2003), Set Theory, Springer
• Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs, North-Holland, ISBN 978-0-444-85401-8
• Shanin, N. A. (1946), "A theorem from the general theory of sets", C. R. (Doklady) Acad. Sci. URSS, New Series, 53: 399–400
• Tao, Terence (2020), The sunflower lemma via Shannon entropy, What's new (personal blog)

External links[]

• Thiemann, René. The Sunflower Lemma of Erdős and Rado (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)

Notes[]