Deterministic quadratic-size vertex-minor-universal graphs

Problem

Does there exist an absolute constant \(C>0\) and a deterministic algorithm that, for each integer \(k\geq2\) supplied in unary, runs in time \(k^{O(1)}\) and outputs a \(k\)-vertex-minor-universal graph with at most \(Ck^2\) vertices? The output is a finite simple labelled graph \(G_k=(V_k,E_k)\). Write \(H\leq_{\mathrm{vm}}G_k\) when \(H\) is obtainable by local complementations and vertex deletions that preserve the labels of surviving vertices; local complementation toggles edges between distinct neighbors of a vertex. Universality requires every graph on every prescribed \(k\)-element subset of \(V_k\) to be obtainable, as in Eq. (1):

\begin{equation} \begin{gathered} k\leq|V_k|\leq Ck^2,\\ \forall S\subseteq V_k\text{ with }|S|=k,\quad \forall E_H\subseteq\{\{u,v\}:u,v\in S,\ u\neq v\},\\ (S,E_H)\leq_{\mathrm{vm}}G_k. \end{gathered} \tag{1} \end{equation}

Source

This is a precise algorithmic formulation of the first open question in Section 5, p. 36:15 of Cautrès et al., which asks for deterministic cubic or quadratic constructions of vertex-minor-universal graphs [CCM+24]. The unary input and polynomial-time requirement make explicit the efficient-construction target; the present question selects the quadratic-size case.

Progress

Reports do not certify correctness or automatically change the problem's status. Progress policy.

For an \(n\)-vertex \(k\)-vertex-minor-universal graph, counting local-Clifford classes (Proposition 5 and its proof) obtainable by Pauli measurements gives

\begin{equation} 3^{n-k}\geq2^{(k^2-5k)/2-1}, \qquad n\geq k+\frac{k^2-5k-2}{2\log_2 3} =\Omega(k^2). \tag{2} \end{equation}

Equation (2) shows that quadratic order is necessary, irrespective of construction time. [CMP23]
Theorem 8 of Cautrès et al. establishes that, for every real \(\alpha>2\) and all sufficiently large \(k\), there exists a \(k\)-vertex-minor-universal graph satisfying

\begin{equation} |V_k|\leq\alpha k^2. \tag{3} \end{equation}

By Eq. (3), the optimal asymptotic order is already known existentially. [CCM+24]
For a prime power \(q\), let \(B_q\) be the bipartite incidence graph between points and lines of the projective plane over the field with \(q\) elements; the explicit construction in Theorem 19 satisfies

\begin{equation} |V(B_q)|=2(q^2+q+1), \qquad 7k^2-16\leq4q \quad\Longrightarrow\quad B_q\text{ is }k\text{-vertex-minor universal}. \tag{4} \end{equation}

In Eq. (4), choosing \(q=\Theta(k^2)\) gives a deterministic polynomial-time construction with \(O(k^4)\) vertices; the authors explicitly ask for cubic or quadratic deterministic constructions in their conclusion. [CCM+24]
Ascoli and coauthors improve (Theorem 1.1) the random-graph guarantee: writing \(\mathbb G(n,p)\) for the distribution in which each possible edge appears independently with probability \(p\), and defining \(c_0:=1/(2\log_2(4/3))\), for every fixed \(\eta>0\) one has, asymptotically as \(k\to\infty\),

\begin{equation} n\geq(1+\eta)c_0k^2 \quad\Longrightarrow\quad \Pr_{G\sim\mathbb G(n,1/2)} [G\text{ is }k\text{-vertex-minor universal}] \geq1-2^{-(1+o(1))\eta k^2/2}. \tag{5} \end{equation}

Equation (5) gives efficient random generation with high success probability, not a guaranteed deterministic construction. [AFF+26]
Chao and Xu’s Theorem 1.3 (version 3, May 2026) proves the following random-graph guarantee: for sufficiently large \(n\), with \(s:=\min(p,1-p)\),

\begin{equation} \begin{gathered} s\geq\frac{100\log n}{\sqrt n}, \\ k\leq\frac{s\sqrt n}{100} \\ \Longrightarrow\quad \Pr_{G\sim\mathbb G(n,p)} [G\text{ is }k\text{-vertex-minor universal}] \geq1-2^{-s^2n/100}. \end{gathered} \tag{6} \end{equation}

Beyond the regime in Eq. (6), Theorem 1.4 and its proof in Appendix A complete the sparse and dense regimes. The authors attribute this complementary argument to an internal OpenAI model, communicated by Mehtaab Sawhney. Neither probabilistic result supplies the deterministic quadratic-size family asked for here. The logarithm in the hypothesis follows the source, which does not specify its base. [CX26]

Comment

No deterministic polynomial-time construction with \(O(k^2)\) vertices was found in the public literature checked through 9 September 2026; the unresolved gap is between quadratic probabilistic existence and quartic efficient deterministic constructions. Exhaustive finite search can eventually find a quadratic-size graph, but that observation does not meet the polynomial-time requirement, and the resolved random-graph conjecture must not be relabelled as this open construction problem. The status audit used public primary sources and later-work searches; it is not an exhaustive citation-index audit. The related Pauli-pairability question asks only for perfect matchings on prescribed terminals, rather than all graphs, and does not require an efficient deterministic construction.

References

[CMP23]: N. Claudet, M. Mhalla, and S. Perdrix, “Small \(k\)-Pairable States,” arXiv preprint (2023).DOI arXiv
[CCM+24]: M. Cautrès, N. Claudet, M. Mhalla, S. Perdrix, V. Savin, and S. Thomassé, “Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems,” in 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), 36:1–36:18 (2024).DOI arXiv
[AFF+26]: R. Ascoli, B. Frederickson, S. Frederickson, C. McFarland, and L. Post, “Almost All Graphs Are Vertex-Minor Universal,” arXiv preprint (2026), version 2; accepted for RANDOM 2026.DOI arXiv
[CX26]: T.-W. Chao and Z. Xu, “Vertex-Minor Universality of a Random Graph,” arXiv preprint (2026), version 3, 5 May 2026.DOI arXiv

Deterministic quadratic-size vertex-minor-universal graphs

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems