DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.38

Almost All Graphs Are Vertex-Minor Universal

Authors: Ruben Ascoli, Bryce Frederickson, Sarah Frederickson, Caleb McFarland, and Logan Post

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

Answering a question of Claudet, we prove that the uniformly random graph G∼ 𝔾(n, 1/2) is Ω(√n)-vertex-minor universal with high probability. That is, for some constant α≈ 0.911, any graph on any α√ n specified vertices of G can be obtained as a vertex-minor of G. This has direct implications for quantum communications networks: an n-vertex k-vertex-minor universal graph corresponds to an n-qubit k-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any k qubits using only local operations and classical communications. We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number R_{vm}(k) to be the smallest value n such that every n-vertex graph contains an independent set of size k as a vertex-minor. Supported by our main result, we conjecture that R_{vm}(k) is polynomial in k. We prove Ω(k²) ≤ R_{vm}(k) ≤ 2^k - 1.

Cite as

Ruben Ascoli, Bryce Frederickson, Sarah Frederickson, Caleb McFarland, and Logan Post. Almost All Graphs Are Vertex-Minor Universal. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ascoli_et_al:LIPIcs.APPROX/RANDOM.2026.38,
  author =	{Ascoli, Ruben and Frederickson, Bryce and Frederickson, Sarah and McFarland, Caleb and Post, Logan},
  title =	{{Almost All Graphs Are Vertex-Minor Universal}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.38},
  URN =		{urn:nbn:de:0030-drops-277559},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.38},
  annote =	{Keywords: vertex-minors, random graphs, quantum networks, graph states}
}

Search Results

Documents authored by Frederickson, Sarah

Almost All Graphs Are Vertex-Minor Universal

Abstract

Cite as

Thanks for your feedback!

Could not send message