Almost all graphs are vertex-minor universal

Ruben Ascoli, Bryce Frederickson, Sarah Frederickson, Caleb McFarland, Logan Post

arXivarxiv/2602.09049Feb 6, 2026quant-phscore 0

Answering a question of Claudet, we prove that the uniformly random graph $G\sim \mathbb G(n, 1/2)$ is $Ω(\sqrt n)$-vertex-minor universal with high probability. That is, for some constant $α\approx 0.911$, any graph on any $α\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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.09049
curl -X POST /api/v1/records/arxiv/2602.09049/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.09049/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'