Barcelona Graduate School of Mathematics
Random Structures and the Probabilistic
Method
Fall 2013
Tue-Thu 17h-19h, Room 005, FME, UPC
Instructors:
Gábor Lugosi,
Elitza Maneva,
and Oriol Serra
Plan of the course
Thu September 29: Presentation.
Introduction to the probabilistic method
Tue October 1:
The second moment method and beyond
Thu October 3:
Lovász Local Lemma
Tue October 8:
Chernoff bounds, discrepancy
Thu October 10: Entropy compression
Tue October 15:
Random graphs: introduction, different models
Thu October 17:
Random graphs: copies of small subgraphs
Tue October 22:
Random graphs: connectivity
Thu October 24:
Random graphs: birth of the giant component
Tue October 29:
Association inequalities, Chernoff bounds, Johnson-Lindenstrauss lemma
Thu October 31:
Inequalities: Efron-Stein, Azuma, Janson
Tue November 5:
Random graphs: clique number and chromatic number
Thu November 7:
Entropy and Shannon's theorem
Tue November 12:
Introduction to finite Markov Chains;
Exercises
Thu November 14:
Random walks on graphs and an application to SAT
Tue November 19: Coupling (LPW Chapter 5);
Exercises
Thu November 21: Special Lecture: Random dependent
choice (Benny Sudakov, ETH, Zurich)
Tue November 26: Special lecture: Random dependent
choice (Benny Sudakov, ETH Zurich)
Thu November 28:
Spectral gap, flows and expansion
Tue December 3: Computational
complexity of counting and sampling
Thu December 5: Coupling
from the past
Tue December 10:
Special
Lecture: Graph coloring and the probabilistic method (Bruce Reed, McGill Univ, Montreal)
Notes and exercises.
Thu December 12: Special Lecture: Graph coloring and the probabilistic method (Bruce Reed, McGill
Univ., Montreal)
Tue December 17: Review session
Thu December 19: Final
exam
References
Alon N., Spencer J.H. The probabilistic
method, Wiley 2008
B. Bollobás, Random graphs, Cambridge
2001
Levin, D.A, Peres Y., Wilmer E.L. Markov
Chains and Mixing Times,
(PDF)
E. M. Palmer, Graphical Evolution, Wiley, 1985.
S. Janson, T. Luczak, A. Rucinski, Random graphs, Wiley 2000.