## [ 582D - Probabilistic Combinatorics]

### Lecturer: Thomas Rothvoss

• 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: This is a math graduate topics course on probabilistic combinatorics. A detailed syllabus can be found here.
• 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
• Lecture notes are available here

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

1. Monday, Jan 7: First day of class. Intro to the probabilistic method. Ramsey Theory.
2. Wednesday, Jan 9: Ch 1.2 "Balancing lights" and Ch 1.3 "On the number of disjoint pairs"
3. Friday, Jan 11: Chapter 1.4 "Graphs with high chromatic number and high girth". Started with Chapter 1.5
4. Monday, Jan 13: Cont. of Chapter 1.5 "The Roedl Nibble"
5. Wednesday, Jan 15: Cont. of Chapter 1.5 "The Roedl Nibble"
6. Friday, Jan 17: Finished Chapter 1.5 "The Roedl Nibble". Started with Chapter 1.6 "Independent Sets in Locally Sparse Graphs"
7. Monday, Jan 21: HOLIDAY - NO LECTURE
8. Wednesday, Jan 23: Finished Ch 1.6. Started with Ch 2.1 "Chernov bounds"
9. Friday, Jan 25: Martingale concentration, Freedman's Inequality
10. Monday, Jan 28: Application of Martingales
11. Wednesday, Jan 30: Talagrand's Inequality
12. Friday, Feb 1: Talagrand's Inequality
13. Monday, Feb 4: CLASS CANCELLED DUE TO SNOW
14. Wednesday, Feb 6: The Lovasz Local Lemma
15. Friday, Feb 8: CLASS CANCELLED DUE TO SNOW
16. Monday, Feb 11: CLASS CANCELLED DUE TO SNOW (Reading homework: The Constructive Lovasz Local Lemma)
17. Wednesday, Feb 13: Chapter 4, Point Line Incidences
18. Friday, Feb 15: Chapter 4, The Crossing Number Theorem
19. Monday, Feb 18: NO CLASS. PRESIDENT'S DAY
20. Wednesday, Feb 20: VC dim
21. Friday, Feb 22: VC dim and epsilon-net Theorem
22. Monday, Feb 25: Dual VC dim
23. Wednesday, Feb 27: Proof of Hamiltonian Cycle for low VC dim set system
24. Friday, Mar 1: Finished discrepancy and VC dim. Motivation Szemeredi Regularity Lemma
25. Monday, Mar 4: Szemeredi Regularity lemma
26. Wednesday, Mar 6: Application of Szemeredi regularity lemma
27. Friday, Mar 8: Intro to KLP-Theorem

### Corrected typos in lecture notes]

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