EVENT DETAILS AND ABSTRACT

Title: Random graphs and Suprema of stochastic processes
Speaker: Huy Tuan Pham
Speaker Info: Stanford University
Brief Description:
Special Note:
Abstract:

Sparse random graphs are central objects in probability and combinatorics. An important aspect of random graphs that has been extensively studied is the threshold phenomenon. 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 joint work with Jinyoung Park that resolves the Kahn—Kalai conjecture. I will also discuss recent joint work with Vishesh Jain that resolves a conjecture of Luria and Simkin on the threshold for containment of Latin squares and Steiner triple systems, and joint work with Ashwin Sah, Mehtaab Sawhney, Michael Simkin on thresholds in robust settings. Zooming into finer details of random graphs beyond the threshold phenomenon, I will touch on nonlinear large deviation results for subgraph counts obtained in joint work with Nicholas Cook and Amir Dembo.

Interestingly, the proof of the Kahn—Kalai conjecture is closely related to our resolution 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. These conjectures play an important role in generalizing the study of suprema of stochastic processes beyond the Gaussian case, and 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.