2022/09/07 by Elchanan Mossel, Jonathan Niles‐Weed, Mossel, Elchanan +5 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2209.03326
openalex publication_date 2022/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For any given graph H, we are interested in pcrit(H), the minimal p such that the Erdős-Rényi graph G(n,p) contains a copy of H with probability at least 1/2. Kahn and Kalai (2007) conjectured that pcrit(H) is given up to a logarithmic factor by a simpler "subgraph expectation threshold" pE(H), which is the minimal p such that for every subgraph H'⊆ H, the Erdős-Rényi graph G(n,p) contains in expectation at least 1/2 copies of H'. It is trivial that pE(H) ≤ pcrit(H), and the so-called "second Kahn-Kalai conjecture" states that pcrit(H) \lesssim pE(H) log e(H) where e(H) is the number of edges in H. In this article, we present a natural modification pE, new(H) of the Kahn--Kalai subgraph expectation threshold, which we show is sandwiched between pE(H) and pcrit(H). The new definition pE, new(H) is based on the simple observation that if G(n,p) contains a copy of H and H contains many copies of H', then G(n,p) must also contain many copies of H'. We then show that pcrit(H) \lesssim pE, new(H) log e(H), thus proving a modification of the second Kahn--Kalai conjecture. The bound follows by a direct application of the set-theoretic "spread" property, which led to recent breakthroughs in the sunflower conjecture by Alweiss, Lovett, Wu and Zhang and the first fractional Kahn--Kalai conjecture by Frankston, Kahn, Narayanan and Park.