Colloquium
3:00 p.m., Friday
Math 100
Joel Spencer
Courant Institute, New York University
Erdos' Magic
The Probabilistic Method is a lasting legacy of the late Paul Erdos.
A randomized algorithm (in modern language) is described and
it is shown that with positive probability that algorithm produces
an object (coloring, graph, tournament, partition, whatever) with
the desired property. Thus, the Magic, the object absolutely must
exist. We examine problems first studied by Erdos in the 1960s,
including modern day improvements and conjectures.
|