On the Second Kahn–Kalai Conjecture
share
For any given graph H, we are interested in p_crit(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 p_crit(H) is given up to a logarithmic factor by a simpler "subgraph expectation threshold" p_E(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 p_E(H) ≤ p_crit(H), and the so-called "second Kahn-Kalai conjecture" states that p_crit(H) ≲ p_E(H) log e(H) where e(H) is the number of edges in H. In this article, we present a natural modification p_E, new(H) of the Kahn–Kalai subgraph expectation threshold, which we show is sandwiched between p_E(H) and p_crit(H). The new definition p_E, 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 p_crit(H) ≲ p_E, 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.
READ FULL TEXT
