# Sunflower (mathematics)

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.

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.

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, and the Erdős-Rado 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 identical. 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.

## Sunflower lemma and conjecture

The study of sunflowers generally focuses on when set systems contain sunflowers, in particular, when a set system is sufficiently large to necessarily contain a sunflower.

Specifically, researchers analyze the function ${\displaystyle f(k,r)}$  for nonnegative integers ${\displaystyle k,r}$ , which is defined to be the smallest nonnegative integer ${\displaystyle n}$  such that, for any set system ${\displaystyle W}$  such that every set ${\displaystyle S\in W}$  has cardinality at most ${\displaystyle k}$ , if ${\displaystyle W}$  has more than ${\displaystyle n}$  sets, then ${\displaystyle W}$  contains a sunflower of ${\displaystyle r}$  sets. Though it is not clear that such an ${\displaystyle n}$  must exist, a basic and simple result of Erdős and Rado, the Delta System Theorem, indicates that it does.

For each ${\displaystyle k>0}$ , ${\displaystyle r>0}$  is an integer ${\displaystyle f(k,r)}$  such that a set system ${\displaystyle F}$  of ${\displaystyle k}$ -sets is of cardinality greater than ${\displaystyle f(k,r)}$ , then ${\displaystyle F}$  contains a sunflower of size ${\displaystyle r}$ .

In the literature, ${\displaystyle W}$  is often assumed to be a set rather than a collection, so any set can appear in ${\displaystyle W}$  at most once. By adding dummy elements, it suffices to only consider set systems ${\displaystyle W}$  such that every set in ${\displaystyle W}$  has cardinality ${\displaystyle k}$ , so often the sunflower lemma is equivalently phrased as holding for "${\displaystyle k}$ -uniform" set systems.[3]

### Sunflower lemma

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 ${\displaystyle k!(r-1)^{k+1}}$  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 .

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)}$ .

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)\leq k(r-1)f(k-1,r).}$

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}$ . 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=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]

## 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.[9]

## Analogue for infinite collections of sets

A version of the ${\displaystyle \Delta }$ -lemma which is essentially equivalent to the Erdős-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  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.