Methods covered include the second moment method, the R\"odl nibble, 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, the phase transition in the Erd\H{o}s-R\'enyi random graph, and the Barab\'asi-Albert preferential attachment model.

- Tony Johansson, Minimum-cost matching in a regular bipartite graph with random costs.

Friday, April 24

- Zilin Jiang, Component sizes of the random graph outside the scaling window.

Monday, April 27

- Dabeen Lee, Integer feasibility of random polytopes.

Wednesday, April 29

- Vijay Bhattiprolu, Asymptotically the list colouring constants are 1.

Friday, May 1

- Joe Briggs, The critical random graph, with martingales

Week 2: Second moment method. See Alon and Spencer Sections 4.5 Clique Number and 4.6 Distinct Sums.

Week 3: Second moment method. Satisfiability threshold for random 2-SAT. See Chvatal and Reed: Mick gets some (the odds are on his side), FOCS, 1992, pp. 620--627.

Week 4: Lovasz Local Lemma (and linear arboricity). Alon and Spencer: Sections 5.1, 5.2, 5.5

Week 5: The Moser-Tardos Local Lemma Algorithm. See Moser and Trados: A constructive proof of the general LovĂˇsz Local Lemma, Journal of the ACM 57 (2010) (2) Art. 11, 15pp. Also see some notes written by Joel Spencer.

Week 6: Janson's Inequality. See Alon and Spencer Section 8.1-8.3. Diameter of a random graph.

Week 7: Martingales and tight concentration. See Alon and Spencer 7.1-7.4.

Week 8: An Introduction to Dynamic Concentration

Week 9: Branching processes and the giant component. See Janson, Luczak and Rucinski Section 5.2

Week 10: Applictaions of Dynamic concentration. Giant Component Triangle Free Process

Week 11: Introduction to finite markov chains. See Chapters 1, 2 of Levin, Peres, and Wilmer.

Week 12: Markov chain monte carlo and mixing. See Chapters 3, 4, 5 of Levin, Peres, and Wilmer.

Week 13: Path coupling. See Chapter 14 of Levin, Peres, and Wilmer.

Week 14,15: Student presentations.

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.

T. Bohman, A. Frieze and E. Lubetzky, A note on the random greedy triangle-packing algorithm , Journal of Combinatorics, 1 (2010), 477-488.

Svante Janson, The probability that a random multigraph is simple. Combin. Probab. Comput. 18 (2009), 205-225.

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.

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.