Math 261B, Probabilistic Method II, Combinatorics, Winter 2020

Time and Place: APM 2402, MWF 11:00-11:50pm
Instructor: Andrew Suk
Office: APM 6210
E-mail: asuk [@] ucsd [dot] edu
Office hours: MW 10pm.
Text: The Probabilistic Method by Alon and Spencer.
Grades Based on 2 homeworks assignments. HW 1 will be due on Feb 5th. No lecture on Monday February 5 (work on HW 1). HW 2 will be due on March 11. No lecture on Monday March 9 (work on HW 2).

Course Description: This is a continuation of Math 261A, a graduate level course on the probabilistic method. The goal of the course is to cover chapters 5, 9, 14 of the book.

Homework 1 (due Feb 5). Section 5.8 #3, 4.
Homework 2 (due March 11). Choose any (one) problem from Section 9.6.



1/6/2020: Introduction, the local lemma.
1/8/2020: Symmetric version of the local lemma, property B, and multicolored translations.
1/10/2020: Compactness argument, lower bounds for Ramsey numbers.
1/13/2020: Off-diagonal Ramsey numbers.
1/15/2020: A geometric result: decomposing k-fold coverings of R^3.
1/17/2020: The linear arboricity of graphs.
1/22/2020: Linear arboricity of graphs with high girth.
1/24/2020: Asymptotic solution to the linear arboricity conjecture.
1/27/2020: Latin transversals.
1/29/2020: Moser's fix it algorithm.
1/31/2020: Analysis of the Moser's fix it algorithm.
2/3/2020: No class.
2/5/2020: Pseudorandomness, expander mixing lemma (Verstraete). Notes.
2/7/2020: Off-diagonal Ramsey numbers (Verstraete).
2/10/2020: Cycles in graphs and large chromatic number given local constraints.
2/12/2020: Quasirandomness, quadratic residue tournaments.
2/14/2020: Upper bound for c(T_p).
2/19/2020: Quasirandomness.
2/21/2020: Quasirandom graphs, P_6 implies P_1.
2/24/2020: Szemeredi's regularity lemma, part I.
2/26/2020: Szemeredi's regularity lemma, part II.
2/28/2020: Counting lemma, triangle removal lemma, and Roth's theorem (not in the book).
3/2/2020: The Kovari-Sos-Turan theorem and dependent random choice.
3/4/2020: The greatest angle among points in R^d.
3/6/2020: VC-dimension and epsilon nets.
3/9/2020: No class.
3/11/2020: Proof of the epsilon nets theorem.
3/13/2020: Haussler's packing lemma, short edge lemma, and matchings with low stabbing number.