**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.