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

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 UV(G)U\subseteq V(G) of size kk, every graph on UU is a vertex-minor of GG. Here, GG(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),p1/2,p=\omega(1/\sqrt{n}),\qquad p\leqslant 1/2,

and GG(n,p)G\sim G(n,p) or GG(n,1p)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.

Sources & referencesView supporting material

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.