Please Note: This seminar will be given in-person.
|
Probability seminar series
Nike
Sun Location: M3 3127 |
On the second Kahn-Kalai conjecture
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.
Joint work with Elchanan Mossel, Jonathan Niles-Weed, and Ilias Zadik.