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.

Copyright © 2001 UBC Mathematics Department