Universal bounded-degree graph conjecture

Let H(n,Δ)\mathcal H(n,\Delta) be the family of all graphs on nn vertices with maximum degree Δ\Delta. A graph GG is F\mathcal F-universal if it contains every member of a graph family F\mathcal F. Let Gn,pG_{n,p} be the binomial random graph.

Universal bounded-degree graph conjecture. Let ΔN\Delta\in\mathbb N and p=ω(n1log1/Δn)2Δ+1p=\omega\left(n^{-1}\log^{1/\Delta}n\right)^{\frac{2}{\Delta+1}}. Then, with high probability, Gn,pG_{n,p} is H(n,Δ)\mathcal H(n,\Delta)-universal.

This strengthens the preceding embedding conjecture by requiring one random graph to contain every graph on nn vertices of maximum degree at most Δ\Delta. The proposed density is motivated by the conjectured worst case of KΔ+1K_{\Delta+1}-factors, but the statement remains open in the source.

Sources & referencesView supporting material

Primary source

Asaf Ferber, Kyle Luh and Oanh Nguyen, “Embedding large graphs into a random graph”, arXiv:1606.05923 (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.