Almost All Graphs Are Vertex-Minor Universal

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.