The Sunflower Lemma

Section 1.2 The Sunflower Lemma

In the previous section, we proved that, if the cardinality of \(\mathcal{F}\subseteq \binom{[n]}{k}\) is large enough, then it is always possible to find two sets in \(\mathcal{F}\) with empty intersection. In this section, our aim will be to find a large subcollection of \(\mathcal{F}\) such that any pair of sets in this subcollection have the same intersection (which may or may not be empty). This leads us to the following definition.

“Sunflower.”

Definition 1.2.1.

For \(p\geq2\text{,}\) a sunflower with \(p\) petals is a collection \(\{F_1,\dots,F_p\}\) of \(p\) sets such that, for any \(1\leq i \lt j\leq p\) and \(1\leq i' \lt j'\leq p\text{,}\)

\begin{equation*} F_i\cap F_j = F_{i'}\cap F_{j'}\text{.} \end{equation*}

That is, all pairs of distinct sets in the collection have a same intersection. The core of the sunflower is defined to be the intersection of any two sets in the sunflower; i.e. the set \(F_1\cap F_2\text{.}\)

Sunflowers are sometimes called \(\Delta\)-systems in the literature. The following result of Erdős and Rado [98] implies that any large enough collection of sets of fixed cardinality contains a sunflower.

Figure 1.2.2. Two sunflowers. The one on the left has a core \(S\) of cardinality three and eight petals. The one on the right has an empty core and four petals. You can think of it as a sunflower that has had all of its petals plucked off.

Theorem 1.2.3. Sunflower Lemma [98].

For \(k\geq1\text{,}\) if \(\mathcal{F}\subseteq \binom{\mathbb{N}}{k}\) such that \(|\mathcal{F}|> k!(p-1)^k\text{,}\) then \(\mathcal{F}\) contains a sunflower with \(p\) petals.

Proof.

We proceed by induction on \(k\text{.}\) In the case \(k=1\text{,}\) we have that \(\mathcal{F}\) is a collection of at least \(p\) distinct single-element sets, and so any \(p\) of them form a sunflower with core \(\emptyset\text{.}\)

Now, suppose that \(k\geq2\text{.}\) Let \(\mathcal{A} = \{A_1,\dots,A_t\}\) be a maximal collection of pairwise disjoint elements of \(\mathcal{F}\text{.}\) If \(t\geq p\text{,}\) then we are done, as the sets in \(\mathcal{A}\) form a sunflower with core \(\emptyset\text{.}\) So, we assume that \(t\leq p-1\text{.}\) Define

\begin{equation*} X:=\bigcup_{i=1}^tA_i\text{.} \end{equation*}

Since every set in \(\mathcal{F}\) has cardinality \(k\) and \(t\leq p-1\text{,}\) we have that \(|X|\leq (p-1)k\text{.}\) By maximality of \(\mathcal{A}\text{,}\) every element of \(\mathcal{F}\) intersects \(X\text{.}\) Therefore, by the Pigeonhole Principle, there is a point \(x\in X\) which is contained in at least

\begin{equation*} \frac{|\mathcal{F}|}{|X|} > \frac{k!(p-1)^k}{(p-1)k}=(k-1)!(p-1)^{k-1} \end{equation*}

sets of \(\mathcal{F}\text{.}\) Consider the system

\begin{equation*} \mathcal{F}':= \{F\setminus \{x\}: F\in \mathcal{F}\text{ and } x\in F\}\text{.} \end{equation*}

Then \(\mathcal{F}'\) is a collection of more than \((k-1)!(p-1)^{k-1}\) sets of cardinality \(k-1\text{;}\) therefore, it has a sunflower with \(p\) petals by the induction hypothesis. Adding the element \(x\) back into each set of this sunflower gives us a sunflower with \(p\) petals in \(\mathcal{F}\text{.}\)

One interesting thing to mention is that, unlike the Erdős–Ko–Rado Theorem in the previous section (and many other results covered in these notes), the Sunflower Lemma is not tight. That is, for most values of \(k\) and \(p\text{,}\) there does not exist a collection \(\mathcal{F}\subseteq \binom{\mathbb{N}}{k}\) with \(|\mathcal{F}|= k!(p-1)^k\) such that \(\mathcal{F}\) does not contain a sunflower with \(p\) petals. In Exercise 19, we describe a lower bound construction which is rather far from matching the upper bound in Theorem 1.2.3.

Here is are a couple of YouTube videos related to the Sunflower Lemma:

Prev Top Next