OctoInformBeta

The second Kahn–Kalai conjecture with an edge-count bound

Let n≥2n\ge2 be an integer and let HH be a finite simple graph with at most nn vertices and h≥1h\ge1 edges. The random graph G(n,p)G(n,p) on {1,…,n}\{1,\ldots,n\} includes each edge independently with probability p∈[0,1]p\in[0,1]. For finite simple graphs GG and FF, let N(G,F)N(G,F) count the subgraphs of GG isomorphic to FF, allowing additional edges between their vertices. The containment threshold is pc(n,H)=inf⁡{p∈[0,1]:ℙ(N(G(n,p),H)>0)≥12}p_{\mathrm c}(n,H)=\inf\{p\in[0,1]:\mathbb P(N(G(n,p),H)>0)\ge\tfrac12\}. The graph expectation threshold is pE(n,H)=inf⁡{p∈[0,1]:𝔼N(G(n,p),F)≥12 for every subgraph F⊆H}p_{\mathrm E}(n,H)=\inf\{p\in[0,1]:\mathbb E N(G(n,p),F)\ge\tfrac12\text{ for every subgraph }F\subseteq H\}. The problem is to bound the containment threshold in terms of the graph expectation threshold uniformly as HH varies with nn.

Kahn and Kalai conjectured that pc(n,H)=O(pE(n,H)log⁡2n)p_{\mathrm c}(n,H)=O(p_{\mathrm E}(n,H)\log_2 n) uniformly over HH. Dubroff, Kahn, and Park proved the general bound pc(n,H)=O(pE(n,H)(log⁡2n)3)p_{\mathrm c}(n,H)=O(p_{\mathrm E}(n,H)(\log_2 n)^3). Tran improved this to pc(n,H)=O(pE(n,H)(log⁡2(2h))2)p_{\mathrm c}(n,H)=O(p_{\mathrm E}(n,H)(\log_2(2h))^2).

The preprint proves pc(n,H)≤min⁡{1,2048exp⁡(50)pE(n,H)(1+log⁡2h)}p_{\mathrm c}(n,H)\le\min\{1,2048\exp(50)p_{\mathrm E}(n,H)(1+\log_2 h)\}. It also proves pc(n,H)≤6144exp⁡(50)pE(n,H)log⁡2np_{\mathrm c}(n,H)\le6144\exp(50)p_{\mathrm E}(n,H)\log_2 n.

The Lean library GraphThreshold formalizes these threshold bounds. Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its statement there. Where a statement differs from the preprint’s, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only to the order and names of the results.