Almost all graphs are vertex-minor universal

• URL: http://arxiv.org/abs/2602.09049v1
• Date: Fri, 06 Feb 2026 20:59:33 GMT
• Title: Almost all graphs are vertex-minor universal
• Authors: Ruben Ascoli, Bryce Frederickson, Sarah Frederickson, Caleb McFarland, Logan Post,
• Abstract summary: We prove that the uniformly random graph $Gsim mathrmvm(k)$ is $(sqrt n)$-vertex-minor universal with high probability.<n>This has direct implications for quantum communications networks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 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 $Ω(k^2) \leq R_{\mathrm{vm}}(k) \leq 2^k - 1$.

Related papers

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Preparing graph states forbidding a vertex-minor [1.864621482724548]
  Measurement based quantum computing is preformed by adding non-Clifford measurements to a prepared stabilizer states.<n>Every stabilizer state is local-Clifford equivalent to a graph state, so we may focus on graph states $leftvert G rightrangle$.<n>We obtain significantly improved bounds when $G$ is contained within certain proper classes of graphs.
  arXiv  Detail & Related papers  (2025-03-31T23:25:35Z)
• Vertex-minor universal graphs for generating entangled quantum subsystems [3.1758167940451987]
  We study the notion of $k$-stabilizer universal quantum state, that is, an $n$-qubit quantum state, such that it is possible to induce any stabilizer state on any $k$ qubits. These states generalize the notion of $k$-pairable states introduced by Bravyi et al., and can be studied from a perspective using graph states and $k$-vertex-minor universal graphs.
  arXiv  Detail & Related papers  (2024-02-09T09:17:19Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Small k-pairable states [0.9208007322096533]
  Bravyi et al. introduced a family of $k-pairable $n$-qubit states, where $n$ grows exponentially with $k$. We present a family of $k$-pairable $n$-qubit graph states, where $n$ is in $k$, namely $nO(k3ln3k)$. We establish the existence of $k$-vertex-minor-universal graphs of order $O(k4 ln k)$.
  arXiv  Detail & Related papers  (2023-09-18T17:26:27Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems [0.0]
  We prove that the continuous-time quantum walk (CTQW) -- with Hamiltonian $H=gamma L$ -- does not depend on the graph $G$. We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices.
  arXiv  Detail & Related papers  (2022-02-28T14:33:44Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  We describe an implicit sparsity-inducing mechanism based on over a family of kernels. As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.
  arXiv  Detail & Related papers  (2021-10-12T09:36:41Z)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  We show that the exponential dependence on the dimension dimension $d in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved. This is the first formal limitation proven about fast multipole methods.
  arXiv  Detail & Related papers  (2020-11-04T18:35:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.