Sunflower lemma

Remarks

The proof is by induction on $k$. Take a maximal subfamily of pairwise disjoint sets. If it has at least $p$ members, they form a sunflower with empty core. Otherwise their union $U$ has at most $(p - 1) k$ elements and meets every set of $\mathcal{F}$, so some $x \in U$ lies in more than $(k-1)! \, (p-1)^{k-1}$ sets. Remove $x$ from these sets and apply the induction hypothesis to get a sunflower, then add $x$ back to its core.

Example: for $k = 1$ and $p = 3$, a family of $3$ distinct one-element sets is a sunflower with empty core, and $3 > 1! \cdot 2^1$. The result is due to Erdős and Rado, who conjectured that $k! \, (p-1)^k$ can be replaced by $C_p^k$ for a constant $C_p$ that depends only on $p$; this is open. In 2019 Alweiss, Lovett, Wu and Zhang improved the bound to $(C p \log k \log \log k)^k$ for an absolute constant $C$, and later work lowered it to $(C p \log k)^k$.

Going deeper

For a student

The sunflower lemma is a basic tool in extremal set theory and in theoretical computer science, for example in lower bounds for monotone circuits. Its proof is a typical Ramsey-type argument: either many sets are disjoint, or many share an element, and then one recurses. It belongs to the circle of results of Ramsey theory, where a large structure always contains an orderly part.