Kahn–Kalai threshold conjecture for graph appearances

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 FGF\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 FGF\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)logv(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.

Sources & referencesView supporting material

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.