← All problems

The second Kahn–Kalai conjecture for graph-containment thresholds

3 years old · documented by

For a graph HH, let pc(H)=pc(n,H)p_c(H)=p_c(n,H) be the unique pp such that

P(Gn,p⊇H)=1/2.\mathbb{P}(G_{n,p}\supseteq H)=1/2.

Define the expectation threshold by

pE(H)=pE(n,H)=min⁡{p:EpXI≥1/2 ∀I⊆H}.p_{\mathbb E}(H)=p_{\mathbb E}(n,H)=\min\{p:\mathbb{E}_pX_I\geq 1/2\ \forall I\subseteq H\}.

The second Kahn–Kalai conjecture. There is a fixed KK such that for any graph HH,

pc(H)<KpE(H)log⁡vH.p_c(H)<Kp_{\mathbb E}(H)\log v_H.

This conjecture asks whether the graph-containment threshold is bounded by a logarithmic factor times the expectation threshold. It was the starting point for the cited work on thresholds, but the general assertion remains open.

References

3 papers in this index state this conjecture (2022–2025). The statement above is taken from the most recent of them; the others are arXiv:2508.14269, arXiv:2209.03326.

Source: Quentin Dubroff, Jeff Kahn and Jinyoung Park, “On the "second" Kahn–Kalai Conjecture: cliques, cycles, and trees”, arXiv:2510.02005 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. Claims that for every n>=2 and finite simple graph H with at most n vertices and h>=1 edges, its containment threshold is at most a universal constant times its subgraph expectation threshold times 1+log2(h), as in the second Kahn–Kalai conjecture.See full solutionHide full solution

Claimed by OpenAI.

Claims that for every n>=2 and finite simple graph H with at most n vertices and h>=1 edges, its containment threshold is at most a universal constant times its subgraph expectation threshold times 1+log2(h), as in the second Kahn–Kalai conjecture.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-second-Kahn-Kalai-conjecture-September-24-2026/paper.pdf

For H with v_H>=2 and h>=1, h<=v_H(v_H-1)/2, hence 1+log_2 h <= C_0 log v_H for a universal constant C_0. This gives the target vertex-logarithm comparison after enlarging its universal constant, uniformly for all host sizes n>=v_H. Edgeless or single-vertex targets are excluded from this claim.

  • OpenAI-176-01-The-second-Kahn-Kalai-conjecture.pdf382,191 bytesOpen