Departmental Colloquium
Huy Tuan Pham
Stanford
The Kahn-Kalai conjecture, Talagrand’s selector process conjecture, and sunflowers
Abstract: The threshold of an increasing graph property is the density at which a random graph transitions from unlikely satisfying to likely satisfying the property. Kahn and Kalai conjectured that this threshold is always within a logarithmic factor of the expectation threshold, a natural lower bound to the threshold which is often much easier to compute. In probabilistic combinatorics and random graph theory, the Kahn—Kalai conjecture directly implies a number of difficult results, such as Shamir’s problem on hypergraph matchings, or the threshold for containing a bounded degree spanning tree. I will discuss recent joint work with Jinyoung Park that resolves the Kahn—Kalai conjecture. Our proof of the Kahn—Kalai conjecture is closely related to the resolution (in joint work with Jinyoung Park) of a conjecture of Talagrand on extreme events of suprema of certain stochastic processes driven by sparse Bernoulli random variables (known as selector processes), and a question of Talagrand on suprema of general positive empirical processes. Given recent advances on chaining and the resolution of the (generalized) Bernoulli conjecture, these results give the first steps towards Talagrand’s last ``Unfulfilled dreams’’ in the study of suprema of general empirical processes. These problems turn out to be intimately related to the sunflower conjecture, an important open problem in extremal combinatorics which has surprising connections to theoretical computer science. Time permitting, I will discuss the connections to sunflowers in various settings.
Friday November 4, 2022 at 3:00 PM in 636 SEO