Jerusalem Mathematics Colloquium
Thursday, 11th January 2001, 4:00 pm
Mathematics Bldg., lecture hall 2
The Jerusalem Mathematics Colloquium is happy to host the first of a series
of three Erdos Memorial Lectures given by Professor Joel Spencer.
Professor Joel Spencer
"The Probabilistic Method"
The Probabilistic Method is a lasting legacy of the late
Paul Erdös. We give two examples - both problems
first formulated by Erdös 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 vantagepoint, 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. Erdös
showed this may always be done if m < 2^(n-1), we give a recent
argument of Srinivasan and Radhukrishnan that extends this to
m < c.2^n.sqrt(n/ln n). 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 --> oo. We want an
asymptotic packing, a subfamily of ~ N/k disjoint sets.
Erdös and Hanani conjectured such a packing exists (in an
important special case of asymptotic designs) and this conjecture
was shown by Rödl. We give a recent simple proof of the speaker
that analyzes the random greedy algorithm.
Coffee, Cookies at the faculty lounge at 3:30.
The other two lectures in the series will be both held 10-12:
January 15th "The Phase Transition for Random Graphs"
January 17th "The Strange Logic of Random Graphs"
List of talks, 2000-01
List of talks, 1998-99
List of talks, 1997-98