The Heawood family is not the complete list of excluded minors for Colin de Verdière invariant at most 5

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Peter Graham ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

We show that two intrinsically knotted graphs G1G_1 and G2G_2 with 23 edges, on 11 and 12 vertices, have Colin de Verdière invariant μ=6\mu=6 and no minor in the Heawood family, the 78 graphs obtained from K7K_7 and K3,3,1,1K_{3,3,1,1} by ΔY\Delta Y- and YΔY\Delta-transformations. So the Heawood family is not the complete list of excluded minors for μ≤5\mu\le5, as van der Holst proposed; Mattman and Pavelescu stated this proposal as a conjecture and derived from it that G1G_1 and G2G_2 have μ=5\mu=5. More precisely, either the common minor HH of G1G_1 and G2G_2, a 4-regular graph with 11 vertices and 22 edges, is an excluded minor for μ≤5\mu\le5, or G1G_1 and G2G_2 both are. It follows that the following two conjectures of van der Holst cannot both hold: (a) a graph is 4-flat if and only if μ≤5\mu\le5; (b) the Heawood family is the complete list of excluded minors for 4-flat graphs. The lower bound μ≥6\mu\ge6 is proved by explicit matrices certified in interval and exact rational arithmetic, and the minor exclusion by exhaustive enumeration. This work has not yet been reviewed by experts. The proofs, the computer checks and the text were produced by AI models, working under the author's direction.

Author comments: Zenodo archive: https://doi.org/10.5281/zenodo.24128770. License: the paper text is deposited here under CC BY 4.0; the published code (checkers) and data stay under Apache-2.0 in their repository. Certificates and checkers, in its folders data and checks: https://github.com/6/clank-lab/tree/heawood-family-mu5-v1/results/heawood-family-mu5

Provenance statement

The proofs, the computer checks and the text were produced by AI models, working under the author's direction. Human understanding (author): I follow the statements, not every proof step.

References

  1. Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50 (1990), 11--21.
  2. A. Georgakopoulos and M. Winter, On 2-complexes embeddable in 4-space, and the excluded minors of their underlying graphs, arXiv:2408.12681v1 (https://arxiv.org/abs/2408.12681v1) (2024).arXiv
  3. H. van der Holst, L. Lovász and A. Schrijver, The Colin de Verdière graph parameter, in Graph Theory and Combinatorial Biology (Balatonlelle, 1996) , Bolyai Soc. Math. Stud. 7, János Bolyai Math. Soc., Budapest, 1999, 29--85. Numbering as in the preliminary version of March 1997 (https://homepages.cwi.nl/~lex/files/cdvsurvey_new2.pdf).link
  4. H. van der Holst, Graphs and obstructions in four dimensions, J. Combin. Theory Ser. B 96 (2006), 388--404, doi:10.1016/j.jctb.2005.09.004 (https://doi.org/10.1016/j.jctb.2005.09.004).DOI
  5. H. Kim and T. W. Mattman, Dips at small sizes for topological graph obstruction sets, Discrete Appl. Math. 360 (2025), 139--166, doi:10.1016/j.dam.2024.08.022 (https://doi.org/10.1016/j.dam.2024.08.022); section numbers as in arXiv:2205.14255v2 (https://arxiv.org/abs/2205.14255v2).arXivDOI
  6. R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187--201.
  7. L. Lovász and A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126 (1998), 1275--1285.
  8. T. W. Mattman and A. Pavelescu, Three thousand obstructions to knotless embedding, arXiv:2607.01414v1 (https://arxiv.org/abs/2607.01414v1) (2026).arXiv
  9. T. W. Mattman and M. Pierce, The Kn+5K_{n+5} and K32,1nK_{3^2,1^n} families and obstructions to nn-apex, in Knots, Links, Spatial Graphs, and Algebraic Invariants , Contemp. Math. 689, Amer. Math. Soc., Providence, RI, 2017, 137--158, doi:10.1090/conm/689/13856 (https://doi.org/10.1090/conm/689/13856); section numbers as in arXiv:1603.00885v1 (https://arxiv.org/abs/1603.00885v1).arXivDOI
  10. R. E. Moore, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 14 (1977), 611--615.
Show all 11 referencesShow fewer references
  1. N. Robertson, P. Seymour and R. Thomas, Sachs' linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), 185--227.

Version history

  1. v1 · 8 pagesSubmitted by P. GrahamZenodo archive: https://doi.org/10.5281/zenodo.24128770. License: the paper text is deposited here under CC BY 4.0; the published code (checkers) and data stay under Apache-2.0 in their repository. Certificates and checkers, in its folders data and checks: https://github.com/6/clank-lab/tree/heawood-family-mu5-v1/results/heawood-family-mu5CurrentNov 20, 2026