[Computational Complexity] Richard Rado (1906-1989)
Tomorrow marks the hundredth anniversary of the birth of combinatorialist Richard Rado. Rado is the second most famous mathematician born on April 28, 1906 so we will celebrate him a day early.
In complexity Rado is best known for the Erdös-Rado Sunflower Lemma. A sunflower is a collection of sets S1,…,Sk such that any two have the same pairwise intersection, i.e., for all 1 ≤ i < j ≤ k, Si∩Sj=S1∩S2. A Venn diagram of these sets would look like a sunflower.
The sunflower lemma states that given any collection of m distinct sets of cardinality s with m>s!(k-1)s, there is a subcollection of size k that forms a sunflower. The size of the universe plays no role in the statement of the lemma.
The proof is a nice induction once you figure out the right variable to induct on. Try it yourself or read it here.
The sunflower lemma has played a major role in many results in computational complexity, most notably in Razborov's proof that clique does not have small monotone circuits.
Posted by Lance to Computational Complexity at 4/27/2006 05:26:00 AM