# 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

(NYU)

"The Probabilistic Method"

** Abstract: **
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