Speaker:  Joel Spencer, Courant Institute

Title: The Probabilistic Method

Abstract:
The Probabilistic Method is a lasting legacy of the late
Paul Erdos.  We give two examples - both problems
first formulated by Erdos in the 1960s with new
results in the last few years and both with substantial
open questions.  Further in both examples we take a
Computer Science vantage point, creating a probabilistic
algorithm to create the object (coloring, packing respectively)
and showing that with positive probability the created object
has the desired properties.


 Given m sets each of size n (with an
arbitrary intersection pattern) we want to color the underlying
vertices Red and Blue so that no set is monochromatic.  Erdos
showed this may always be done if m< 2n-1, we give a recent
argument of Srinivasan and Radhukrishnan that extends this to
m < c2n(n/ln n)1/2.  One first colors randomly and then 
recolors the blemishes with a clever random sequential algorithm.

  In a universe of size N we have a family
of sets, each of size k, such that each vertex is in D sets
and any two vertices have only o(D) common sets.  Asymptotics
are for fixed k with N,D$\rightarrow\infty$.  We want an
asymptotic packing, a subfamily of $\sim N/k$ disjoint sets.
Erdos and Hanani conjectured such a packing exists (in an
important special case of asymptotic designs) and this conjecture
was shown by Rodl.  We give a recent simple proof of the speaker
that analyzes the random greedy algorithm.