The Sunflower Lemma

Today’s post is about the Sunflower Lemma (a.k.a the Erdos-Rado Lemma). I learnt about Sunflower Lemma while reading Razborov’s Theorem from Papadimitriou’s computational complexity book.

A sunflower is a family of p sets , called petals, each of cardinality at most l, such that all pairs of sets in the family have the same intersection, called the core of the sunflower.

The Sunflower Lemma : Let Z be a family of more than nonempty sets, each of cardinality l or less. Then Z must contain a sunflower.

Exercise : Prove the Sunflower Lemma

The best known lower bound on M is .

Exercise : Construct a family of   nonempty sets that does not have a sunflower.

We develop counterparts

of the Sunflower Lemma for distributive lattices, graphic matroids, and matroids

representable over a xed nite eld.

Sunflower lemma plays a crucial role in Razborov’s theorem [Razborov’85]. [McKenna’05] generalized the Sunflower Lemma for distributive lattices, graphic matroids, and matroids representable over a fixed finite field.

I am not aware of other applications of Sunflower Lemma. If you know any, please leave a comment.

Open problems :

• Improve the upper/lower bound on M.
• Erdos and Rado conjectured that “For every fixed p there is a constant C = C(p) such that a family of more than nonempty sets, each of cardinality l or less has a sunflower”. This conjecture is still open. It is open even for p=3.

References :

• [Razborov’85] A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357.
• [McKenna’05] Geoffrey McKenna, Sunflowers in Lattices, The Electronic Journal of Combinatorics Vol.12 2005 [pdf]