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.
March 8
Introduction; presentation of topics
March 15
The emergence of the giant component in G(n,p)
March 22
Embedding large trees in expanding graphs
March 29
The polynomial method in discrete geometry
April 12
Random algebraic constructions I
April 19
The Turán problem for even cycles
May 10
Forbidden patterns in permutations and the Stanley–Wilf Conjecture
May 17
Random algebraic constructions II
May 31
The Erdős–Simonovits Conjecture (aka Sidorenko's conjecture)
June 7
The trianglefree process
June 14
Pseudorandomness in graphs
June 21
Triangle removal lemma
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.

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)

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)

Enumerating graphs without a cycle of length four
D. J. Kleitman, K. J. Wilson, On the number of graphs without 4cycles, Discrete Math. 41 (1982), 167–172. (article)

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)

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)

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)

Random algebraic constructions I
B. Bukh, Random algebraic construction of extremal graphs, preprint. (arXiv)

Random algebraic constructions II
D. Conlon, Graphs with few paths of prescribed length between any two vertices, preprint. (arXiv)

Pseudorandomness in graphs
F. R. K. Chung, R. L. Graham, R. M. Wilson, Quasirandom graphs, Combinatorica 9 (1989), 345–362. (article)

An analogue of Turán's theorem in pseudorandom graphs
B. Sudakov, T. Szabó, V. H. Vu, A generalization of Turán's theorem, J. Graph Theory 49 (2005), 187–195. (article)

The trianglefree process
P. Erdős, S. Suen, P. Winkler, On the size of a random maximal graph, Random Structures Algorithms 6 (1995), 309–318. (article)

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)

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)

Edgedisjoint 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)