Ascoli–Frederickson–Frederickson–McFarland–Post vertex-minor universality conjecture
Ascoli–Frederickson–Frederickson–McFarland–Post vertex-minor universality conjecture
Let denote the Erdős–Rényi random graph on vertices, and say that a graph is -vertex-minor universal if, for every vertex subset of size , every graph on is a vertex-minor of . Here, means that each edge is present independently with probability .
Vertex-minor universality conjecture. If
and or , then, with high probability, is -vertex-minor universal for some
This conjecture extends the known result for , where almost all graphs are -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.