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

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

*MMD, 5/29/98*