[ 582D - Probabilistic Combinatorics]

Lecturer: Thomas Rothvoss

Course information

Homework


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
  2. Added exercise 1.8
  3. Chapter 2.4: Talagrand inequality was two-sided.
  4. Added exercise 2.8
  5. Removed bracket in Exercise 2.1
  6. 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
  7. Ch 3, LLL: k-regular -> k-uniform 
  8. Ch 2.2.1 Application of Martingales: I added a justification by X_0,...,X_n is a Martingale
  9. Ch 2.4. There was a 1 / mu_n(A) missing at (*)
  10. Ch 3: Clarified definition of dependency graph and added extra remarks.
  11. Exercise 2.9: E[Y] -> E[f(Y)]
  12. Theorem 3.3: the independency graph -> a dependency graph
  13. Exercise 3.2: t-regular -> t-uniform
  14. 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.