On the "second" Kahn--Kalai Conjecture

Abstract

We make progress on a conjecture of Kahn and Kalai, the original (stronger but less general) version of what became known as the ``Kahn-Kalai Conjecture" (KKC; now a theorem of Park and Pham). This ``second" KKC concerns the threshold, $p_c(H)$, for $G_{n,p}$ to contain a copy of a given graph $H$, predicting $p_c(H)=O(p_{\mathbb{E}}(H)\log n)$, where $p_{\mathbb{E}}$ is an easy lower bound on $p_c$. What we actually show is $p_{\mathbb{E}}^{\ast }(H)=O(p_{\mathbb{E}}(H){\log }^{2}n)$, where $p_{\mathbb{E}}^{\ast }$, the fractional expectation threshold, is a larger lower bound suggested by Talagrand. When combined with Talagrand's fractional relaxation of the KKC (now a theorem of Frankston, Kahn, Narayanan and Park), this gives $p_c(H)=O(p_{\mathbb{E}}(H){\log }^{3}n)$. (The second KKC would follow similarly if one could remove the log factors from the above bound on $p_{\mathbb{E}}^{\ast }$.)

14 pages