Return to Colloquia & Seminar listing
On the second Kahn-Kalai conjecture and statistical connections
Probability| Speaker: | Ilias Zadik, MIT |
| Location: | MSB 2112 |
| Start time: | Fri, Oct 28 2022, 1:10PM |
For a given graph H we are interested in the critical threshold p so that a sample from the Erdos-Renyi random graph contains a copy of H with high probability. Kahn and Kalai in 2006 conjectured that it should be given (up to a logarithm) by the minimum p so that in expectation all subgraphs H’ of H appear in the random graph.
In this work, we will present a proof of a modified version of this conjecture. Our proof is based on a powerful “spread lemma”, which played a key role in recent breakthroughs (a) on the Erdos-Rado sunflower conjecture (which enjoys many TCS applications) and (b) the fractional Kahn-Kalai conjecture. Time permitting, we will discuss also a new proof of the spread lemma using Bayesian inference tools.
Joint work with Elchanan Mossel, Jonathan Niles-Weed and Nike Sun.