Recent developments in probabilistic combinatorics: New synergies
- Time: everyday Jan 6 to Jan 10, 2025, offline at IBS headquarter B332.
Online: 9:00-10:30am (Beijing), 10:00-11:30am (Seoul). - Zoom: 981 0186 8315, PW: 250106
Recent developments in probabilistic combinatorics have brought about synergistic interactions across multiple disciplines, including extremal combinatorics, probability theory and theoretical computer science. This mini-course aims to give an introduction to some of these developments and interactions.
In the first part of the mini-course, we will discuss the Kahn-Kalai conjecture on thresholds and expectation thresholds and its close relation to Talagrand’s selector process conjecture in probability theory. We will also touch on several subsequent developments of the proof technique in extremal combinatorics, probability theory and theoretical computer science.
The Kahn-Kalai conjecture opens up a new avenue on thresholds of interesting properties in random graph models. Yet, while it relates thresholds to the expectation thresholds, estimation of the latter remains a highly challenging task in general. Recent developments have found close connections between this task and previous fundamental developments in extremal combinatorics, such as the regularity method. In the second part of the mini-course, I will briefly overview classical aspects of the regularity method before discussing its new applications to thresholds and other problems in probabilistic combinatorics.
- 1/6 Lecture 1: Thresholds and expectation thresholds, the Kahn-Kalai conjecture. Tablet note
- 1/7 Lecture 2: Talagrand’s (sharp) selector process conjecture, minimum fragments and proof of the Kahn-Kalai conjecture. Tablet note
- 1/8 Lecture 3: Minimum fragments and applications: spread and smooth spread families, sunflowers and sunflowers in set systems with bounded VC dimension, and rounding fractional covers via the sharp selector process conjecture. Tablet note
- 1/9 Lecture 4: Synergies of extremal and probabilistic combinatorics: robust thresholds and perturbed random graphs from the Kahn-Kalai conjecture and the random blow-up lemma. Tablet note
- 1/10 Lecture 5: The matching lemma and derivations of some results on robust thresholds and perturbed random graphs. Tablet note
