Math 261A, Probabilistic Method, Combinatorics, Fall 2019

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 Oct 30th. No lecture on Monday October 28 (work on HW 1). HW 2 will be due on December 4. No lecture on Monday Dec 2 (work on HW 2).

Course Description: This is a graduate level introduction course to the probabilistic method, a powerful tool used in extremal combinatorics. The goal of the course will be to cover the first 4 chapters of the book.

Homework 1: Section 1.7: #2, 10. Section 2.7: #1, 2. Section 3.7 #2. Due October 30. Solutions.
Homework 2: Section 3.7 #3. Section 4.8 #1, 5. Due December 4. Solutions.

9/27/2019: Introduction, Ramsey numbers.
9/30/2019: Tournaments with the S_k property, dominating sets.
10/2/2019: Property B, (k,l)-systems.
10/4/2019: Sum-free subsets, Disjoint pairs in set systems.
10/7/2019: Graph containers and list coloring.
10/9/2019: List coloring and Erdos-Ko-Rado.
10/11/2019: Linearity of expectation, Hamiltonian paths in tournaments, splitting graphs, crossing k-sets.
10/14/2019: Applications in Ramsey theory, bipartite Ramsey numbers, balancing vectors.
10/16/2019: Unbalancing lights, greedy algorithms for splitting graphs.
10/18/2019: Bregman's theorem.
10/21/2019: Alterations, Ramsey numbers, independent sets.
10/23/2019: Combinatorial geometry, Heilbronn's conjecture.
10/25/2019: Packing, Greedy coloring.
10/28/2019: No class.
10/30/2019: Packing, high girth high chromatic number.
11/1/2019: Variance, Markov and Chebyshev's inequality.
11/4/2019: almost all integers in [n] have ~ lnln(n) prime factors.
11/6/2019: Random graphs, threshold functions, upper bounds on the variance.
11/8/2019: Threshold functions of balanced graphs.
11/13/2019: Counting copies of balanced graphs in G(n,p).
11/15/2019: Clique number of G(n,1/2).
11/18/2019: Distinct sums.
11/20/2019: Designs and the Rodl nibble.
11/22/2019: Rodle nibble.
11/25/2019: Rodle nibble.
11/27/2019: Hamiltonian paths.
12/02/2019: No class.
12/04/2019: Crossing numbers, incidences, sums and products.
12/06/2019: Turan's theorem, Triangle free graphs have large independence number.

Winter 2020: Math 261B.