Sunday, June 25

MS2
Probabilistic Combinatorics: Part I

10:00 AM - 12:30 PM
Room: Cornett A120

For Part II, see MS7

Probabilistic Combinatorics is an interface between Probability and Discrete Mathematics. Initiated by P. Erdos over fifty years ago, it has now become one of the fastest developing areas in discrete mathematics, with fascinating applications to many other important areas, such as Theoretical Computer Science. This minisymposium will focus on all the main research topics of Probabilistic Combinatorics, including the application of probability to solve combinatorial problems, the study of random combinatorial objects and the investigation of randomized algorithms.

One aim of the minisymposium is simply to foster interaction between researchers in these fields, discuss recent progress and communicate new results and ideas. We also intend to use this forum to make the main state-of-the-art probabilistic techniques available to a broader audience.

Organizer: Benjamin Sudakov
Princeton University

10:00-10:25 Independent Transversals in Locally Sparse Graphs

Benjamin Sudakov and Po-Shen Loh, Princeton University

10:30-10:55 Extremal Subgraphs of Random Graphs

Angelika Steger, Institute of Theoretical Computer Science, ETH, Zürich, Switzerland; Graham Brightwell, London School of Economics, United Kingdom; Konstantinos Panagiotou, ETH Zürich, Switzerland

11:00-11:25 Graph Colouring via the Probabilistic Method

Bruce Reed, McGill University, Canada

11:30-11:55 On the Chromatic Number of Random Graphs with a Fixed Degree Sequence

Michael Krivelevich, Tel Aviv University, Israel; Alan Frieze, Carnegie Mellon University; Clifford D. Smyth, Massachusetts Institute of Technology

12:00-12:25 Propp's Derandomized Walk Machine

Joel Spencer, Courant Institute of Mathematical Sciences, New York University