# The Sunflower Lemma

A sunflower is a family of p sets $\{P_1,P_2,\dots,P_p\}$, 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 $M=(p-1)^{l}l!$ 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 $(p-1)^l$.

Exercise : Construct a family of $(p-1)^l$ 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.

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 $C^{l}$ 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]

## 5 thoughts on “The Sunflower Lemma”

1. Andrei Lopatenko |

A modification of the sunflower lemma was used by Andreev to prove the exponential bounds for monotone circuits (mentioned in Stasys Jukna “Extremal combinatorics”)

2. Andrei Lopatenko |

Andreev A. E. On the method of obtaining effective lower bounds on monotone complexity, Algebra i Logica, 26:1, 3-26 (Russian, 1987)

• kintali |

Thanks Andrei. I will look at this paper.

3. Vineet |

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/

4. vzn |

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