Razborov’s Theorem

by

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 \{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.

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 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]