The bounded-degree spanning graph threshold conjecture

At least 8 years old · documented by

Fix a constant Δ\Delta, and let H=(Hn)H=(H_n) be a sequence of graphs with maximum degree Δ(H)≤Δ\Delta(H)\le \Delta and at most nn vertices, v(H)≤nv(H)\le n.

Bounded-degree spanning graph threshold conjecture. The random graph G(n,p)G(n,p) almost surely contains HH whenever

p⋅n2/(Δ+1)(log⁡n)1/(Δ+12)→∞.p\cdot\frac{n^{2/(\Delta+1)}}{(\log n)^{1/\binom{\Delta+1}{2}}}\to\infty.

Equivalently, the conjectured threshold is the threshold for a KΔ+1K_{\Delta+1}-factor. The source says this optimum is widely believed and gives no resolution.

References

Primary source

Julia Böttcher, “Large-scale structures in random graphs”, arXiv:1702.02648 (2017).

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.