Kahn–Kalai threshold conjecture for graph appearances
Kahn–Kalai threshold conjecture for graph appearances
Let be a graph, and write and for its numbers of vertices and edges. For a subgraph , define to be the smallest such that
for every . A threshold function for a sequence of graphs is a function such that, for the random graph , the appearance probability tends to one when and tends to zero when . Kahn–Kalai threshold conjecture. There is a universal constant such that, for every sequence , a threshold function for the appearance of in is at most
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.