MATH Seminar
| Title: Random graphs and Suprema of stochastic processes |
|---|
| Colloquium: Combinatorics |
| Speaker: Huy Pham of Stanford University |
| Contact: Liana Yepremyan, liana.yepremyan@emory.edu |
| Date: 2023-03-20 at 4:00PM |
| Venue: Atwood 215 |
| Download Flyer |
| Abstract: The threshold phenomenon is a central direction of study in probabilistic combinatorics, particularly the study of random graphs, and in theoretical computer science. The threshold of an increasing graph property (or more generally an increasing boolean function) is the density at which a random graph (or a random set) transitions from unlikely satisfying to likely satisfying the property (or the function). 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 Johansson, Keevash, and 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 and connections to sparse regularity 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 stochastic processes. |
See All Seminars