Sunflower (mathematics)

Erdős & Rado (1960, p. 86) proved the sunflower lemma, which states that[4]

${\displaystyle f(k,r)\leq k!(r-1)^{k}.}$

That is, if ${\displaystyle k}$ and ${\displaystyle r}$ are positive integers, then a set system ${\displaystyle W}$ of cardinality greater than or equal to ${\displaystyle k!(r-1)^{k}}$ of sets of cardinality ${\displaystyle k}$ contains a sunflower with at least ${\displaystyle r}$ sets.

The Erdős-Rado sunflower lemma can be proved directly through induction. First, ${\displaystyle f(1,r)\leq r-1}$, since the set system ${\displaystyle W}$ must be a collection of distinct sets of size one, and so ${\displaystyle r}$ of these sets make a sunflower. In the general case, suppose ${\displaystyle W}$ has no sunflower with ${\displaystyle r}$ sets. Then consider ${\displaystyle A_{1},A_{2},\ldots ,A_{t}\in W}$ to be a maximal collection of pairwise disjoint sets (that is, ${\displaystyle A_{i}\cap A_{j}}$ is the empty set unless ${\displaystyle i=j}$, and every set in ${\displaystyle W}$ intersects with some ${\displaystyle A_{i}}$). Because we assumed that ${\displaystyle W}$ had no sunflower of size ${\displaystyle r}$, and a collection of pairwise disjoint sets is a sunflower, ${\displaystyle t<r}$.

Let ${\displaystyle A=A_{1}\cup A_{2}\cup \cdots \cup A_{t}}$. Since each ${\displaystyle A_{i}}$ has cardinality ${\displaystyle k}$, the cardinality of ${\displaystyle A}$ is bounded by ${\displaystyle kt\leq k(r-1)}$. Define ${\displaystyle W_{a}}$ for some ${\displaystyle a\in A}$ to be

${\displaystyle W_{a}=\{S\setminus \{a\}\mid a\in S,\,S\in W\}.}$

Then ${\displaystyle W_{a}}$ is a set system, like ${\displaystyle W}$, except that every element of ${\displaystyle W_{a}}$ has ${\displaystyle k-1}$ elements. Furthermore, every sunflower of ${\displaystyle W_{a}}$ corresponds to a sunflower of ${\displaystyle W}$, simply by adding back ${\displaystyle a}$ to every set. This means that, by our assumption that ${\displaystyle W}$ has no sunflower of size ${\displaystyle r}$, the size of ${\displaystyle W_{a}}$ must be bounded by ${\displaystyle f(k-1,r)-1}$.

Since every set ${\displaystyle S\in W}$ intersects with one of the ${\displaystyle A_{i}}$'s, it intersects with ${\displaystyle A}$, and so it corresponds to at least one of the sets in a ${\displaystyle W_{a}}$:

${\displaystyle |W|\leq \sum _{a\in A}|W_{a}|\leq |A|(f(k-1,r)-1)\leq k(r-1)f(k-1,r)-|A|\leq k(r-1)f(k-1,r)-1.}$

Hence, if ${\displaystyle |W|\geq k(r-1)f(k-1,r)}$, then ${\displaystyle W}$ contains an ${\displaystyle r}$ set sunflower of size ${\displaystyle k}$ sets. Hence, ${\displaystyle f(k,r)\leq k(r-1)f(k-1,r)}$ and the theorem follows.[2]

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}$. [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=O(r^{3}\log(k)\log \log(k))}$.[6][7] A month after the release of the first version of their paper, Rao sharpened the bound to ${\displaystyle C=O(r\log(rk))}$;[8] the current best-known bound is ${\displaystyle C=O(r\log k)}$.[9]

Erdős and Rado proved the following lower bound on ${\displaystyle f(k,r)}$. It is equal to the statement that the original sunflower lemma is optimal in ${\displaystyle r}$.

Theorem. ${\displaystyle (r-1)^{k}\leq f(k,r).}$

Proof. For ${\displaystyle k=1}$ a set of ${\displaystyle r-1}$ sequence of distinct elements is not a sunflower. Let ${\displaystyle h(k-1,r)}$ denote the size of the largest set of ${\displaystyle k-1}$-sets with no ${\displaystyle r}$ sunflower. Let ${\displaystyle H}$ be such a set. Take an additional set of ${\displaystyle r-1}$ elements and add one element to each set in one of ${\displaystyle r-1}$ disjoint copies of ${\displaystyle H}$. Take the union of the ${\displaystyle r-1}$ disjoint copies with the elements added and denote this set ${\displaystyle H^{*}}$. The copies of ${\displaystyle H}$ with an element added form an ${\displaystyle r-1}$ partition of ${\displaystyle H^{*}}$. We have that,${\displaystyle (r-1)|H|\leq |H^{*}|}$. ${\displaystyle H^{*}}$ is sunflower free since any selection of ${\displaystyle r}$ sets if in one of the disjoint partitions is sunflower free by assumption of H being sunflower free. Otherwise, if ${\displaystyle r}$ sets are selected from across multiple sets of the partition, then two must be selected from one partition since there are only ${\displaystyle r-1}$ partitions. This implies that at least two sets and not all the sets will have an element in common. Hence this is not a sunflower of ${\displaystyle r}$ sets.

A stronger result is the following theorem:

Theorem. ${\displaystyle f(a+b,r)\geq (f(a,r)-1)(f(b,r)-1)}$

Proof. Let ${\displaystyle F}$ and ${\displaystyle F^{*}}$ be two sunflower free families. For each set ${\displaystyle A}$ in F, append every set in ${\displaystyle F^{*}}$ to ${\displaystyle A}$ to produce ${\displaystyle |F^{*}|}$ many sets. Denote this family of sets ${\displaystyle F_{A}}$. Take the union of ${\displaystyle F_{A}}$ over all ${\displaystyle A}$ in ${\displaystyle F}$. This produces a family of ${\displaystyle |F^{*}||F|}$ sets which is sunflower free.

It is also known that ${\displaystyle 10^{.5k}\leq f(k,3)}$.