Kahn–Kalai threshold conjecture for graph appearances

About 20 years old · traced to

Let GG be a graph, and write v(G)v(G) and e(G)e(G) for its numbers of vertices and edges. For a subgraph F⊆GF\subseteq G, define pE(G)p_E(G) to be the smallest pp such that

v(F)!∣Aut⁡(F)∣pe(F)≥1\frac{v(F)!}{|\operatorname{Aut}(F)|}p^{e(F)}\geq 1

for every F⊆GF\subseteq G. A threshold function for a sequence of graphs {Gn}\{G_n\} is a function th(Gn){\rm th}(G_n) such that, for the random graph G(n,p(n))G(n,p(n)), the appearance probability tends to one when p(n)/th(Gn)→∞p(n)/{\rm th}(G_n)\to\infty and tends to zero when p(n)/th(Gn)→0p(n)/{\rm th}(G_n)\to 0. Kahn–Kalai threshold conjecture. There is a universal constant KK such that, for every sequence {Gn}\{G_n\}, a threshold function for the appearance of {Gn}\{G_n\} in G(n,p)G(n,p) is at most

pE(Gn)log⁡∣v(Gn)∣.p_E(G_n)\log |v(G_n)|.

This conjecture proposes that the first-moment obstruction determines thresholds up to a logarithmic factor, uniformly over all graph sequences. It was proposed by Kahn and Kalai; the supplied text gives no resolution status.

References

Primary source

Yu Chen, Jie Han and Haoran Luo, “On the thresholds of degenerate hypergraphs”, arXiv:2411.18596 (2024).

Additional references

5 papers in this index state this conjecture (2006–2024). The statement above is taken from the most recent of them; the others are arXiv:1910.13433, arXiv:1702.02648, arXiv:1612.06026, arXiv:math/0603218.

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 0

No solutions have been posted yet.