The bounded-degree spanning graph threshold conjecture

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

pn2/(Δ+1)(logn)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.

Sources & referencesView supporting material

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.