2026-09-10T09:45:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27755 2026-09-09T12:19:37Z ddc:004 open_access

Almost All Graphs Are Vertex-Minor Universal Ascoli, Ruben Frederickson, Bryce Frederickson, Sarah McFarland, Caleb Post, Logan vertex-minors random graphs quantum networks graph states 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ruben Ascoli and Bryce Frederickson and Sarah Frederickson and Caleb McFarland and Logan Post 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.38 urn:nbn:de:0030-drops-277559 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.38 eng https://creativecommons.org/licenses/by/4.0/legalcode