Ascoli–Frederickson–Frederickson–McFarland–Post vertex-minor universality conjecture

Less than 1 year old · traced to

Let G(n,p)G(n,p) denote the Erdős–Rényi random graph on nn vertices, and say that a graph GG is kk-vertex-minor universal if, for every vertex subset U⊆V(G)U\subseteq V(G) of size kk, every graph on UU is a vertex-minor of GG. Here, G∼G(n,p)G\sim G(n,p) means that each edge is present independently with probability pp.

Vertex-minor universality conjecture. If

p=ω(1/n),p⩽1/2,p=\omega(1/\sqrt{n}),\qquad p\leqslant 1/2,

and G∼G(n,p)G\sim G(n,p) or G∼G(n,1−p)G\sim G(n,1-p), then, with high probability, GG is kk-vertex-minor universal for some

k=Ω(pn).k=\Omega(p\sqrt{n}).

This conjecture extends the known result for G(n,1/2)G(n,1/2), where almost all graphs are O(n)O(\sqrt{n})-vertex-minor universal, and predicts the corresponding scale for sparse and complementary random graphs. The source gives no resolution of the conjecture.

References

Primary source

Ting-Wei Chao and Zixuan Xu, “Vertex-minor universality of a random graph”, arXiv:2603.13600 (2026).

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.