## [ 582D - Probabilistic Combinatorics]

### Lecturer: Thomas Rothvoss

- Office: Padelford C-440

- Office hours:
Monday 1:30pm-2:30pm and Wednesday 1:30pm-2:30pm

- Email: rothvoss@uw.edu

### Course information

- Class schedule:
**MWF 12:30 - 1:20pm**in**PDL C401**

**Description**:

**Prerequisites**: A good understanding of probability and combinatorics.

**Required Work:**

- Your grade will be based on homework assignments. Homeworks are due weekly on Fridays in class. The problems will be posted at the latest after the Monday lecture of the week in which the homework is due.
- NO EXAMS
- Detailed lecture notes will be provided

### Homework

**Homework 1, due Friday, Jan 18, in class.**Solve exercises 1.1, 1.4 and 1.5 in the lecture notes

**Homework 2, due Friday, Jan 25, in class.**

Solve exercises 1.3, 1.7, 1.8 in the lecture notes (for 1.8 see updated lecture notes)**Homework 3, due Friday, Feb 1, in class.**

Solve exercises 2.1, 2.3, 2.8.

**Remark.**For exercise 2.3 it makes sense to wait for the Monday lecture.**Homework 4, due Friday,****Feb 8, in class.**

Please solve Exercises 2.7 and 2.9 in the lecture notes. Please use the updated lecture notes from Feb 1.**Homework 5, due Friday, Feb****15, in class.**

Please solve Exercises 3.2 and 3.5 in the lecture notes. Please use the updated lecture notes from Feb 8 (there was a typo in Ex 3.2: t-regular -> t-uniform).**Homework 6, due Friday, Feb****22, in class.**

Please solve Exercises 4.1, 4.2 and 4.5 in the lecture notes (for 4.5 see the updated lecture notes from Feb 15).**Homework 7, due Friday, Mar 1 in class.**

Please solve Ex 5.1, 5.2 and 5.4 in the lecture notes.**Homework 8, due Friday, Mar 8 in class.**

Please solve Ex 3.3 (back in the LLL chapter) and Ex 5.3.**Homework 9 (last homework), due Friday, Mar 15 in class.**

Please solve Ex 6.1 and Ex 6.3 in the lecture notes.

### Course calendar

- Monday, Jan 7: First day of class. Intro to the probabilistic method. Ramsey Theory.
- Wednesday, Jan 9: Ch 1.2 "Balancing lights" and Ch 1.3 "On
the number of disjoint pairs"

- Friday, Jan 11: Chapter 1.4 "Graphs with high chromatic number and high girth". Started with Chapter 1.5
- Monday, Jan 13: Cont. of Chapter 1.5 "The Roedl Nibble"
- Wednesday, Jan 15: Cont. of Chapter 1.5 "The Roedl Nibble"
- Friday, Jan 17: Finished Chapter 1.5 "The Roedl Nibble". Started with Chapter 1.6 "Independent Sets in Locally Sparse Graphs"
- Monday, Jan 21: HOLIDAY - NO LECTURE
- Wednesday, Jan 23: Finished Ch 1.6. Started with Ch 2.1 "Chernov bounds"
- Friday, Jan 25: Martingale concentration, Freedman's Inequality
- Monday, Jan 28: Application of Martingales

- Wednesday, Jan 30: Talagrand's Inequality
- Friday, Feb 1: Talagrand's Inequality
- Monday, Feb 4: CLASS CANCELLED DUE TO SNOW

- Wednesday, Feb 6: The Lovasz Local Lemma
- Friday, Feb 8: CLASS CANCELLED DUE TO SNOW

- Monday, Feb 11: CLASS CANCELLED DUE TO SNOW (Reading homework: The Constructive Lovasz Local Lemma)
- Wednesday, Feb 13: Chapter 4, Point Line Incidences
- Friday, Feb 15: Chapter 4, The Crossing Number Theorem
- Monday, Feb 18: NO CLASS. PRESIDENT'S DAY
- Wednesday, Feb 20: VC dim

- Friday, Feb 22: VC dim and epsilon-net Theorem

- Monday, Feb 25: Dual VC dim
- Wednesday, Feb 27: Proof of Hamiltonian Cycle for low VC
dim set system

- Friday, Mar 1: Finished discrepancy and VC dim. Motivation Szemeredi Regularity Lemma
- Monday, Mar 4: Szemeredi Regularity lemma

- Wednesday, Mar 6: Application of Szemeredi regularity
lemma

- Friday, Mar 8: Intro to KLP-Theorem

### Corrected typos in lecture notes]

- Chapter 1.5 - The Roedl Nibble: I fixed a bunch of typos, made the theorem statement more clear and added a footnote non Chebychev's inequality, variance and covariance
- Added exercise 1.8
- Chapter 2.4: Talagrand inequality was two-sided.

- Added exercise 2.8
- Removed bracket in Exercise 2.1
- Ch 2.5 Talagrand inequality. Several typos: X' should be \bar{X}, some X should be \bar{X} and some X_n should be -X_n
- Ch 3, LLL: k-regular -> k-uniform
- Ch 2.2.1 Application of Martingales: I added a justification by X_0,...,X_n is a Martingale
- Ch 2.4. There was a 1 / mu_n(A) missing at (*)
- Ch 3: Clarified definition of dependency graph and added extra remarks.
- Exercise 2.9: E[Y] -> E[f(Y)]
- Theorem 3.3: the independency graph -> a dependency graph
- Exercise 3.2: t-regular -> t-uniform
- Chapter 5 on VC dim: added details for bounds on shatter
function Phi_d(m). Added details for reduction from Spanning
Tree to Hamiltonian Cycle. Added definition incidence
matrix. Added details for other calculations.