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.
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 fixed finite field.
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]