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.