Mathematics Colloquium

The threshold phenomenon is a central direction of investigation in the study of random graphs. 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. I will discuss recent joint work with Jinyoung Park that resolves the Kahn-Kalai conjecture.

Interestingly, our proof of the Kahn-Kalai conjecture is closely related to the resolution of a conjecture of Talagrand on 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. These conjectures play an important role in generalizing the study of suprema of stochastic processes beyond the Gaussian case. Given recent advances on chaining and the resolution of the (generalized) Bernoulli conjecture, our results give the first steps towards Talagrand's last ``Unfulfilled dreams'' in the study of suprema of general empirical processes.