Return to Colloquia & Seminar listing
On the second Kahn-Kalai conjecture
ProbabilitySpeaker: | Nike Sun, MIT |
Location: | MSB 2112 |
Start time: | Tue, Apr 4 2023, 1:10PM |
For a graph $H = H_n$, the critical probability $p_c(H)$ is the value of $p$ such that an Erdos-Renyi graph $G(n,p)$ includes a copy of $H$ with chance 1/2. The "second Kahn-Kalai conjecture," which remains open, posits that $p_c(H)$ is equivalent up to a logarithmic factor to a subgraph expectation threshold. We show that $p_c(H)$ is equivalent up to a logarithmic factor to a modified subgraph expectation threshold, thus proving a weak version of the second Kahn-Kalai conjecture. This gives a simplification of the fractional Kahn-Kalai result of Frankston, Kahn, Narayanan, and Park (2019) in the special case of graph inclusion properties. The main technical ingredient is the spread lemma of Alweiss, Lovett, Wu, and Zhang (2019). Separately, we also present a new proof of the spread lemma from a Bayesian inference perspective.