On the Second Kahn--Kalai Conjecture

For any given graph $H$, we are interested in $p_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}}(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\mathrm{/}2$. Kahn and Kalai (2007) conjectured that $p_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}}(H)$ is given up to a logarithmic factor by a simpler “subgraph expectation threshold” $p_{\mathrm{E}}(H)$, which is the minimal $p$ such that for every subgraph $H^{\mathrm{\prime }}\subseteq H$, the Erdős-Rényi graph $G(n,p)$ contains \emph{in expectation} at least $1\mathrm{/}2$ copies of $H^{\mathrm{\prime }}$. It is trivial that $p_{\mathrm{E}}(H)\le p_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}}(H)$, and the so-called “second Kahn-Kalai conjecture” states that $p_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}}(H)\lesssim p_{\mathrm{E}}(H)\log e(H)$ where $e(H)$ is the number of edges in $H$. In this article, we present a natural modification $p_{\mathrm{E},\mathrm{n}\mathrm{e}\mathrm{w}}(H)$ of the Kahn–Kalai subgraph expectation threshold, which we show is sandwiched between $p_{\mathrm{E}}(H)$ and $p_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}}(H)$. The new definition $p_{\mathrm{E},\mathrm{n}\mathrm{e}\mathrm{w}}(H)$ is based on the simple observation that if $G(n,p)$ contains a copy of $H$ and $H$ contains \emph{many} copies of $H^{\mathrm{\prime }}$, then $G(n,p)$ must also contain \emph{many} copies of $H^{\mathrm{\prime }}$. We then show that $p_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}}(H)\lesssim p_{\mathrm{E},\mathrm{n}\mathrm{e}\mathrm{w}}(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.