Almost all graphs are vertex-minor universal

Abstract

Answering a question of Claudet, we prove that the uniformly random graph $G\sim \mathbb{G}(n,1/2)$ is $\hat{I}\text{c◯}(\sqrt{n})$-vertex-minor universal with high probability. That is, for some constant $\hat{I}\pm \approx 0.911$, any graph on any $\hat{I}\pm \sqrt{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_{\mathrm{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_{\mathrm{vm}}(k)$ is polynomial in $k$. We prove $\hat{I}\text{c◯}(k^2)\le R_{\mathrm{vm}}(k)\le 2^k-1$.

33 pages