Monday, July 13

The Probabilistic Method

3:30 PM-5:30 PM
Room: Sidney Smith 2118

The probabilistic method is a powerful technique, pioneered by Paul Erdös in the 1950s. In recent years, the probabilistic method has yielded some of the most important results in discrete mathematics, perhaps most notably in the fields of graph coloring and Ramsey Theory. The probabilistic method is particularly elegant when it yields a solution to a problem whose statement does not indicate that it has any relation to probability whatsoever. In this session, the speakers will present several results of this type. Thus, while the proofs are all probabilistic, the theorems are drawn from the realms of mainstream graph theory, and so this session is intended to appeal to a much broader audience than simply those who are frequently involved with probabilistic aspects of discrete math. To further facilitate this goal, some of the presentations will provide an introduction to the probabilistic method for the nonspecialist.

Organizer: Michael S. O. Molloy
University of Toronto, Canada
3:30 Graph Coloring with the Probabilistic Method
Michael S. O. Molloy, Organizer
4:00 Coloring Graphs with Sparse Neighborhoods
Noga Alon, Tel-Aviv University, Israel; Michael Krivelevich, Institute for Advanced Study, Princeton; and Benny Sudakov, Tel-Aviv University, Israel
4:30 On the Average Size of Independent Sets in Triangle-Free Graphs
James B. Shearer, IBM T. J. Watson Research Center
5:00 Packing and Covering: A Probabilistic Approach
Raphael Yuster, Tel Aviv University, Israel
Program Program Overview Program-at-a-Glance Program Updates Speaker Index Registration Hotel Transportation

MMD, 5/29/98