Monday, July 13

MS9
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.

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