Computational Complexity

Thursday, April 27, 2006

 
Richard Rado (1906-1989)

Posted by Lance

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.

5:26 AM #

1.  Anonymous says:  
   
   Actually, there's a simpler proof of Razborov's theorem, without using the Sunflower thm:
   
   "Symmetric Approximation Arguments for Monotone Lower Bounds without Sunflowers (1997)"
   
   http://citeseer.ist.psu.edu/rd/43448601%2C505735%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/25920/ftp:zSzzSzftp.nada.kth.sezSzpubzSzdocumentszSzTheoryzSzChrister-BergzSzapprox.pdf/berg97symmetric.pdf
   

   6:26 AM, April 27, 2006