The second Kahn–Kalai conjecture for graph-containment thresholds
For a graph , let be the unique such that
Define the expectation threshold by
The second Kahn–Kalai conjecture. There is a fixed such that for any graph ,
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
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 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
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.pdfOpen