Abstract

For a given graph H we are interested in the critical value of p so that a sample of an Erdos-Renyi 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 G(n,p).

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 the recent breakthroughs on the sunflower conjecture and the proof of the fractional Kahn-Kali conjecture. Time permitting, we will discuss a new proof of the spread lemma using Bayesian inference tools.

This is joint work with Elchanan Mossel, Jonathan Niles-Weed and Nike Sun