The second Kahn–Kalai conjecture for graph-containment thresholds

From papers

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,pH)=1/2.\mathbb{P}(G_{n,p}\supseteq H)=1/2.

Define the expectation threshold by

pE(H)=pE(n,H)=min{p:EpXI1/2 IH}.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)logvH.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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Additional 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.

Solutions 0

No solutions have been posted yet.