# 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. 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. 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. 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/