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 S₁,…,S_k such that any two have the same pairwise intersection, i.e., for all 1 ≤ i < j ≤ k, S_i∩S_j=S₁∩S₂. 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.