The Erdos-Rado Sunflower Lemma
A sunflower is a collection of sets such that all pairs have the same intersections. The sets are called petals, and the intersection is called the core of the sunflower. More precisely, we say a collection of non-empty sets \(S_1, \ldots, S_k\) is a sunflower of size \(k\) with core \(Y\) if \(S_i \cap S_j = Y\) for all \(i\neq j\). The core could be empty, which means all the petals are disjoint.
The Sunflower Lemma (Erdos and Rado).
Let \(\mathcal{S} = \{S_1, \ldots, S_m\}\) be a collection of sets such that each \(S_i\) has cardinality at most \(l\) and \(m > l! (k-1)^l\) for some \(k\), then \(\mathcal{S}\) contains a sunflower of size \(k\).
The proof is by induction on the cardinality \(l\) of the sets. When \(l=1\), the singleton sets form a sunflower with the empty core.
For \(l >1\), find a maximal sub-collection \(\mathcal{D}\) of \(\mathcal{S}\) with disjoint sets. If this sub-collection \(\mathcal{D}\) has size at least \(k\), then it is a desirable sunflower (with the empty core). Otherwise, we consider the union of all sets within \(\mathcal{D}\), which has cardinality at most \(l\cdot(k-1)\). This union set intersects with every set in \(\mathcal{S}\). Then there must be one element which is contained in at least \(m/[l(k-1)] > (l-1)! (k-1)^{l-1}\) sets of \(\mathcal{S}\). If we remove that single element from all such sets, then by the induction hypothesis, there is a sunflower of size \(k\). Adding back the single element still gives a sunflower. This ends the proof.
The sunflower lemma finds many applications in theoretical computer science, for example, Razborov’s lower bound for CLIQUE against monotone circuits.