Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Richard Rado (1906-1989)

Expand Messages
  • 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
    Message 1 of 1 , Apr 27 3:28 AM
    • 0 Attachment
      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

    Your message has been successfully submitted and would be delivered to recipients shortly.