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]
A modification of the sunflower lemma was used by Andreev to prove the exponential bounds for monotone circuits (mentioned in Stasys Jukna “Extremal combinatorics”)
Andreev A. E. On the method of obtaining effective lower bounds on monotone complexity, Algebra i Logica, 26:1, 3-26 (Russian, 1987)
Thanks Andrei. I will look at this paper.
Hello Shiva,
Munro et. al. use the lemma to show an information-theoretic lower bound on the number of bits to be read for a space-efficient code. “Integer Representation and Counting in the Bit Probe Model”. This is in the conference version only as it wasn’t reproduced in the journal version. http://www.springerlink.com/content/c20040k70k368212/
there is some improved sunflower lemmas by rossman in his recent paper on circuit lower bounds and noga alon has a new paper linking them to the complexity of matrix multiplication! see also detailed material on sunflowers, cstheory stackexchange