Title: The Kahn—Kalai conjecture and Talagrand’s selector process conjecture
Speaker: Huy T. Pham (Stanford University)
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.
