21-737 Probabilistic Combinatorics

This course covers the probabilistic method for combinatorics in detail and introduces randomized algorithms and the theory of random graphs.

Methods covered include the second moment method, the Lov\'asz local lemma, correlation inequalities, martingale's and tight concentration, Janson's inequality, branching processes, coupling and the differential equations method for discrete random processes. Objects studied include the configuration model for random regular graphs, Markov chains, and the phase transition in the Erd\H{o}s-R\'enyi random graph.

Course Instructor:

Tom Bohman
Wean Hall 6105
tbohman@math.cmu.edu
Office Hours: Wednesday 3:00-4:30 or by appointment


Course Information

Sample midterm questions.


Homework 1

Homework 2

Homework 3

Homework 4

Homework 5


Week 1:

Weeks 2,3:

Week 4:

Week 5:

Week 6:

Week 7:

Week 8: spring break.

Week 9:

Week 10:

Week 11:

Week 12:

Week 13:

Week 14:

<


Possible presentation papers:

N. Alon, M. Krivelevich, B. Sudakov, Finding a large hidden clique in a random graph. Random Structures Algorithms 13 (1998), 457-466.

D. Achlioptas and C. Moore, The Asymptotic Order of the k-SAT Threshold, Proc. Foundations of Computer Science (FOCS) 2002.

Y. Azar, A. Broder, A. Karlin, and E. Upfal, Balanced allocations, SIAM J. on Computing, 29, (2000), 180-200.

G. Brightwell and P. Winkler, Maximum hitting time for random walks on graphs. Random Structures & Algorithms 1 (1990), 263-276.

A. Ferber, Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs. Electronic Journal of Combinatorics 22 (2015), Paper 1.61

A. Frieze, Loose Hamilton cycles in random 3-uniform hypergraphs. Electron. J. Combin. 17 (2010), no. 1, Note 28.

Svante Janson, The probability that a random multigraph is simple. Combinatorics Probability and Computing 18 (2009), 205-225.

J. Kim, V. Vu, Concentration of multivariate polynomials and its applications. Combinatorica 20 (2000), 417-434.

M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities, Random Structures and Algorithms 7 (1995), 145-155.

A Nachmias, Y. Peres, The critical random graph, with martingales, Israel Journal of Math, 176 (2010) 29-43.

A Nachmias, Y. Peres, Component sizes of the random graph outside the scaling window , Latin American Journal of Probability and Mathematical Statistics (ALEA), 3, 133-142 (2007).

B. Reed and B. Sudakov, Asymptotically the list colouring constants are 1, J. Combinatorial Theory Ser. B 86 (2002), 27-37.

O. Riordan, The k-core and branching processes. Combinatorics, Probability, and Computing, 17 (2008), 111-136.

A. Rucinski and N. Wormald, Random graph processes with degree restrictions, Combinatorics, Probability and Computing 1 (1992) 169-180.

J. Spencer Asymptotic Packing via A Branching Process Random Structures and Algorithms, 7 (1995,) 167-172

J. Spencer and N. Wormald, Birth control for giants , Combinatorica 27 (2007), 587-628.