On the Second Kahn-Kalai Conjecture

          @misc{ scivideos_22600,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22600},
            author = {},
            keywords = {},
            language = {en},
            title = {On the Second Kahn-Kalai Conjecture},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22600 see, \url{https://scivideos.org/simons-institute/22600}}
          }
          

Abstract

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