In this seminar, we shall present and discuss a variety of important results and developments in the areas of extremal and probabilistic combinatorics that are not normally covered in the standard courses on combinatorics and graph theory.

Students registering for the seminar are expected to possess working knowledge of basic graph theory notions and be familiar with basic concepts of discrete probability.

Below is a tentative list of topics to be discussed and presented during the seminar. Topics that have already been reserved are highlighted in light gray.

1. Algorithmic version of the Local Lemma
   R. Moser, G. Tardos, A Constructive Proof of the General Lovász Local Lemma, J. ACM 57 (2010), Art. 11, 15 pp. (article | arXiv)
2. The emergence of the giant component in G(n,p)
   M. Krivelevich, B. Sudakov, The phase transition in random graphs: a simple proof, Random Structures Algorithms 43 (2013), 131–138. (article | arXiv)
3. Enumerating graphs without a cycle of length four
   D. J. Kleitman, K. J. Wilson, On the number of graphs without 4-cycles, Discrete Math. 41 (1982), 167–172. (article)
4. Embedding large trees in expanding graphs
   J. Friedman, N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), 71–76. (article)
   P. E. Haxell, Tree embeddings, J. Graph Theory 36 (2001), 121–130. (article)
5. Forbidden patterns in permutations and the Stanley–Wilf Conjecture
   A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley–Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), 153–160. (article)
   J. Fox, Stanley–Wilf limits are typically exponential, Adv. Math., to appear (arXiv)
6. The Turán problem for even cycles
   J. A. Bondy, M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory Ser. B 16 (1974), 97–105. (article)
   O. Pikhurko, A note on the Turán function of even cycles, Proc. Amer. Math. Soc. 140 (2012), 3687–3692. (article)
   B. Bukh, Z. Jiang, A bound on the number of edges in graphs without an even cycle, preprint. (arXiv)
7. Random algebraic constructions I
   B. Bukh, Random algebraic construction of extremal graphs, preprint. (arXiv)
8. Random algebraic constructions II
   D. Conlon, Graphs with few paths of prescribed length between any two vertices, preprint. (arXiv)
9. Pseudo-randomness in graphs
   F. R. K. Chung, R. L. Graham, R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345–362. (article)
10. An analogue of Turán's theorem in pseudo-random graphs
    B. Sudakov, T. Szabó, V. H. Vu, A generalization of Turán's theorem, J. Graph Theory 49 (2005), 187–195. (article)
11. The triangle-free process
    P. Erdős, S. Suen, P. Winkler, On the size of a random maximal graph, Random Structures Algorithms 6 (1995), 309–318. (article)
12. The Erdős–Simonovits Conjecture (aka Sidorenko's conjecture)
    D. Conlon, J. Fox, B. Sudakov, An approximate version of Sidorenko's conjecture, Geom. Funct. Anal. 20 (2010), 1354–1366. (article | arXiv)
13. The polynomial method in discrete geometry
    L. Guth, N. H. Katz, Algebraic methods in discrete analogs of the Kakeya problem, Adv. Math. 225 (2010), 2828–2839. (article | arXiv)
14. Edge-disjoint Hamilton cycles in random graphs
    A. Frieze, M. Krivelevich On two Hamilton cycle problems in random graphs, Israel J. Math. 166 (2008), 221–224. (article)