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