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