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.
Overview
Syllabus
- Large Bipartite Subgraph
- Lower Bounds to Ramsey Numbers
- Extremal Set Theory: Sperner's Theorem
- Extremal Set Theory: Intersecting Families
- Linearity of Expectations
- Independent Sets and Turán's Theorem
- Crossing Number Inequality
- Markov, Chebyshev, and Chernoff
- Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)
- Threshold for a Random Graph to Contain a Triangle
- Existence of Graphs with High Girth and High Chromatic Number
Taught by
Prof. Yufei Zhao
