Catalog

Probabilistic Methods in Combinatorics

Mathematics MIT CC BY-NC-SA 4.0 11 lectures

This course is a graduate-level introduction to the probabilistic methods, a fundamental and powerful technique in combinatorics and theoretical computer science. The essence of the approach is to show that some combinatorial object exists and prove that a certain random construction works with positive probability. The course focuses on methodology as well as combinatorial applications.

Syllabus

  1. 1 Large Bipartite Subgraph
  2. 2 Lower Bounds to Ramsey Numbers
  3. 3 Extremal Set Theory: Sperner's Theorem
  4. 4 Extremal Set Theory: Intersecting Families
  5. 5 Linearity of Expectations
  6. 6 Independent Sets and Turán's Theorem
  7. 7 Crossing Number Inequality
  8. 8 Markov, Chebyshev, and Chernoff
  9. 9 Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)
  10. 10 Threshold for a Random Graph to Contain a Triangle
  11. 11 Existence of Graphs with High Girth and High Chromatic Number

Course materials