| 1 | Introduction to the probabilistic method. Ramsey number lower bounds (union bound, alternation, Lovász local lemma). Sperner’s theorem. | |
| 2 | Bollobás’s two families theorem. Erdős-Ko-Rado theorem. 2-colorable hypergraphs (property B). Linearity of expectations: sum-free sets. | |
| 3 | Linearity of expectations: Ramsey multiplicities, Turán’s theorem, crossing number inequality, balancing vectors. | |
| 4 | Linearity of expectations: deterministically balancing vectors, unbalancing lights, dense sphere packings in high dimensions. | |
| 5 | Alteration method: dominating sets, Heilbronn triangle problem, high girth and high chromatic number, random greedy coloring (2-coloring hypergraphs). | Problem set 1 due |
| 6 | Second moment method: concentration and thresholds for subgraphs in a random graph. | |
| 7 | Second moment method: clique number, number of prime divisors (Hardy-Ramanujan, Erdős-Kac), multidimensional Szemerédi theorem in the primes. | |
| 8 | Second moment method: distinct sums, Weierstrass approximation theorem. Chernoff bound: discrepancy. | |
| 9 | Chernoff bound: Counterexample to Hajós conjecture. Local lemma: coloring hypergraphs. | |
| 10 | Local lemma: proof and algorithm. | |
| 11 | Local lemma: large independent sets with structure, directed cycles of lengths divisible by k, linear arboricity conjecture. | Problem set 2 due |
| 12 | Local lemma: linear arboricity conjecture lopsided LLL. | |
| 13 | Local lemma: Latin transversals. Correlation inequalities: Harris-FKG inequality. | |
| 14 | Janson’s inequalities: statement and proof, probability that a random graph is triangle-free. | |
| 15 | Janson’s inequalities: lower tail, chromatic number of G(n, 1/2). | Problem set 3 due |
| 16 | Martingale concentration: Azuma’s inequality, concentration of chromatic number of dense random graph. | |
| 17 | Martingale concentration: 4-point concentration of chromatic number of sparse random graphs, application to clique number of random graph. | |
| 18 | Concentration of measure, Johnson-Lindenstrauss lemma. | |
| 19 | Talagrand inequality: concentration of convex Lipschitz functions, convex distance, top eigenvalue of a random graph. | Problem set 4 due |
| 20 | Talagrand inequality: certifiable functions, longest increasing subsequence of a random permutation. Entropy method. | |
| 21 | Entropy method: coin-weighing, Bregman’s theorem, Shearer’s inequality, triangle-intersecting families. | |
| 22 | Entropy method: the number of independent sets in a regular graph, Sidorenko’s conjecture for trees. | |
| 23 | More on Sidorenko’s conjecture. Occupancy method: the number of independent sets in a regular graph. | |
| 24 | Occupancy method: further applications to independent sets and colorings. | |
| 25 | Triangles and equations: a trailer for 18.217 Graph Theory and Additive Combinatorics. | Problem set 5 due |
