Synopsis for Probabilistic Combinatorics

Recommended Prerequisites

C11.1a Graph Theory and Part A Probability.

Overview

Probabilistic combinatorics is a very active field of mathematics, with connections to other areas such as computer science and statistical physics. Probabilistic methods are essential for the study of random discrete structures and for the analysis of algorithms, but they can also provide a powerful and beautiful approach for answering deterministic questions. The aim of this course is to introduce some fundamental probabilistic tools and present a few applications.

Learning Outcomes

The student will have developed an appreciation of probabilistic methods in discrete mathematics.

Synopsis

First-moment method, with applications to Ramsay numbers, and to graphs of high girth and high chromatic number. Second-moment method, threshold functions for random graphs. Lovasz Local Lemma, with applications to two-colourings of hyper-graphs (property B), and to Ramsay numbers. Chernoff bounds, concentration of measure, Janson's inequality. Branching processes and the phase transition in random graphs. Clique and chromatic numbers of random graphs.

1. N. Alon and J.H. Spencer, The Probabilistic Method (second edition, Wiley, 2000).

Further reading:

1. B. Bollobás, Random Graphs (second edition, CUP, 2001).
2. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, ed., Probabilistic Methods for Algorithmic Discrete Mathematics (Springer, 1998).
3. S.Janson, T. Luczak and A.Rucinski, Random Graphs (John Wiley and Sons, 2000).
4. M. Mitzenmacher and E. Upfal, Probability and Computing : Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, New York (NY), 2005).
5. M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method (Springer, 2002).
6. R. Motwani and P. Raghavan, Randomized Algorithms (CUP, 1995).