Small vertex-minor universal graphs: an order-15 witness at k=5, the exact vertex-minor deficit of an extremal order-14 graph, and the first values over 𝔽ₚ
Abstract
A graph G is k-vertex-minor universal if every graph on every k of its vertices is a vertex-minor of G. Let ν(k) be the least order of such a graph; the first three values are ν(2)=3, ν(3)=6, ν(4)=10, and at k=5 the best published bound is ν(5) ≤ 17, from the Paley graph of order 17. We exhibit a 5-vertex-minor universal graph of order 15, so ν(5) ≤ 15, together with a covering family of 8880 explicit local-complementation words that certifies it over all 3 075 072 (subset, target) cells. We then analyse the extremal end of order 14. For the published extremal (14,2¹⁴,6) self-dual additive GF(4) code with graph6 string MAa_OKrD]UlV|r}~?, we determine its vertex-minor deficit exactly, and unconditionally: 2 050 036 of the 2 050 048 cells are realised, by 7233 explicit words, and the remaining twelve are realised by no sequence of local complementations at all. All twelve missing targets are labellings of 2K₂ ∪ K₁, which is a local-complementation fixed point. The negative half rests on a blocking criterion, read off the graph-state code and proved here from scratch, which also shows that the Paley graph of order 13 and eight extremal order-13 candidates are not 5-vertex-minor universal. The second half of the paper opens a new axis. Replacing graphs by symmetric zero-diagonal matrices over 𝔽ₚ and local complementation by the two operations of Bahramgiri and Beigi, we define k-vertex-minor universality for qudit graph states and write νₚ(k) for the corresponding minimal order. We prove νₚ(2)=3 for every p with 𝔽ₚ a domain, uniformly in p and with no computation; we prove ν₃(3)=6 with the all-ones 6-cycle as witness, 6 ≤ ν₃(4) ≤ 10 with the all-ones Petersen graph, and 5 ≤ ν₅(3) ≤ 6. The same 6-cycle is the k=3 witness at p=2,3,5 and the same Petersen graph the k=4 witness at p=2,3, which raises the question whether νₚ(k) depends on p at all. Every theorem and proposition below is formally verified in Lean 4; the computations reported alongside them are flagged, where they occur, as lying outside that development.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 2 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
2eccc7807a5392f73e961a51ab4d0f41dd0122d9805556306fa12b1d7fc7f520
Claim ledger
Stated results
vmu-01routine2026-08-23
The minimal order of a 2-vertex-minor universal graph is 3
vmu-02routine2026-08-23
The minimal order of a 3-vertex-minor universal graph is 6
vmu-03known data2026-08-23
k = 4: the source's order-10 'wheel' C₁0(1,5), the Petersen graph, and Paley(13) are 4-vertex-minor universal; no graph of order <= 6 is
vmu-04candidate2026-08-23
There is a 5-vertex-minor universal graph of order 15: the minimal order of a 5-vertex-minor universal graph is at most 15, against the source's 17
vmu-05known data2026-08-23
The Paley graph of order 17 is 5-vertex-minor universal
vmu-06routine2026-08-23
Negative controls: C₅ is not 3-VMU and C₆ is not 4-VMU, each with the failing target named; four ways the certificate checker rejects; the Lean encoding cross-checked against the C search tool
vmu-07routine2026-08-23
The two certificate bridges, kernel-only
vmu-08routine2026-08-23
The largest independent set over a local-complementation orbit is n minus a minimum rank, checked against the orbit at every labelled graph of order ≤ 6
vmu-09known data2026-08-23
αₗoc(Paley(13)) = 4: the empty graph on 5 vertices is not a vertex-minor of the Paley graph of order 13
vmu-10routine2026-08-23
Negative controls for the orbit-independence invariant
vmu-11candidate2026-08-23
A 5-subset that no sequence of local complementations can empty, for eight extremal order-13 candidates and for Paley(13) — the per-subset half of the complete order-13 sweep
vmu-12routine2026-08-23
The array-defined graphs are graphs, and ofCode is onto the graphs: every symmetric loop-free n-row bitmask array is ofCode n c for some c < 2^C(n,2), which upgrades the family's exhaustive lower bounds from decoded codes to all graphs
vmu-13measurement2026-08-23
Frontier at k = 5, order 14: the witness hunt is negative, the best known order-14 graph misses 12 of the 2 050 048 (5-subset, target) cells, and every missing cell is a matching target
This ledger entry is reported in prose and is not bound to a Lean theorem.vmu-14candidate2026-08-28
The order-14 record graph MAa_OKrD]UlV|r? misses exactly twelve of the 2 050 048 cells, all twelve labellings of 2K₂ ∪ K₁ — in particular 2K₂ ∪ K₁ on S = 1,2,5,6,11 with edges 1,5, 2,6 is not a vertex-minor of it
vmu-15candidate2026-08-28
2 050 036 of the 2 050 048 cells of the order-14 record graph are vertex-minors, by 7 233 explicit local-complementation words: deficit ≤ 12 with no bridge lemma, and the vertex-minor set on S = 1,2,5,6,11 determined exactly
vmu-16routine2026-08-30
Local complementation acts on the graph-state code by an explicit coordinatewise map, and hence a line assignment blocks a vertex-minor: the family's negative half as a kernel-clean criterion that imports nothing
vmu-17candidate2026-08-30
The order-14 record graph MAa_OKrD]UlV|r? is not 5-vertex-minor universal, and deficit = 12 holds exactly — both halves unconditional
vmu-18known data2026-08-30
The Paley graph of order 13 is not 5-vertex-minor universal, as a kernel theorem with no unformalized lemma
vmu-19candidate2026-08-30
None of the eight extremal order-13 candidates is 5-vertex-minor universal; the criterion agrees with Thirteen.blockedFirst on sixteen graphs in the kernel, and is exact over every labelled graph of orders 5, 6 and 7
vmu-20routine2026-08-30
Negative controls for the code criterion
vmu-21routine2026-08-30
The Fₚ layer: Bahramgiri-Beigi's generalized local complementation and local scaling on qudit label matrices, qudit vertex-minors, and the two certificate bridges
vmu-22candidate2026-08-30
The minimal order of a 2-vertex-minor universal Fₚ graph is 3, for every p in which Fₚ has no zero divisors – both halves, uniform in p, with no computation
vmu-23candidate2026-08-30
The minimal order of a 3-vertex-minor universal qutrit graph is 6, witnessed by the 6-cycle with all labels 1
vmu-24candidate2026-08-30
6 <= (minimal order of a 4-vertex-minor universal qutrit graph) <= 10: the Petersen graph with all labels 1 is 4-vertex-minor universal over F₃, and no qutrit label matrix of order 4 or 5 is
vmu-25candidate2026-08-30
5 <= (minimal order of a 3-vertex-minor universal F₅ graph) <= 6, the upper half by the same all-ones 6-cycle; the value is 6, the order-5 sweep being computed but parked outside the kernel
vmu-26routine2026-08-30
Negative controls for the qudit layer: the p = 2 reproduction of both published qubit values, the encoding cross-check against this family's qubit development, six checker rejections, and the qutrit C₅'s named missed target
vmu-27routine2026-08-30
ofCode is onto the Fₚ label matrices: base-p digit extraction for the induced codes, so every qudit lower bound is a statement about all label matrices and not about a code enumeration
vmu-28candidate2026-09-02
The all-ones 6-cycle is 3-vertex-minor universal over Z/m for every modulus m >= 2, prime or not: one witness, one kernel proof, no computation
vmu-29routine2026-09-02
No Fₚ label matrix of order n is n-vertex-minor universal, for every n >= 2 and every modulus in which Fₚ has no zero divisors
vmu-30candidate2026-09-02
No Fₚ label matrix of order 4 is 3-vertex-minor universal, for every modulus in which Fₚ has no zero divisors, by the orbit-invariance of the 2x2 block determinant and of isolatedness
vmu-31routine2026-09-02
Negative controls for the uniform k = 3 column: universality is not automatic, the witness matters, the degree cannot be raised, and both hypotheses are non-vacuous
vmu-32candidate2026-09-02
5 <= (minimal order of a 3-vertex-minor universal Fₚ label matrix) <= 6 for every modulus p >= 2 in which Fₚ has no zero divisors, with the same witness at every one of them; and = 6 at p = 3 from the order-5 table alone
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Source: arXiv:2511.22271, Nathan Claudet, *Local Equivalences of Graph States* (PhD thesis, Université de Lorraine, defended 17 November 2025; arXiv v1 27 Nov 2025, v2 21 Jul 2026), Chapter 7, "Vertex-minor universal graphs". The asymptotic half of that chapter is published as Cautrès–Claudet–Mhalla–Perdrix–Savin–Thomassé, *Vertex-minor universal graphs for generating entangled quantum subsystems*, ICALP 2024 (arXiv:2402.06260); the small-graph section this family works on appears only in the thesis.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7