The Heawood family is not the complete list of excluded minors for Colin de Verdière invariant at most 5
Version 1 / Nov 20, 2026 / CC BY 4.0
Abstract
We show that two intrinsically knotted graphs and with 23 edges, on 11 and 12 vertices, have Colin de Verdière invariant and no minor in the Heawood family, the 78 graphs obtained from and by - and -transformations. So the Heawood family is not the complete list of excluded minors for , as van der Holst proposed; Mattman and Pavelescu stated this proposal as a conjecture and derived from it that and have . More precisely, either the common minor of and , a 4-regular graph with 11 vertices and 22 edges, is an excluded minor for , or and 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 ; (b) the Heawood family is the complete list of excluded minors for 4-flat graphs. The lower bound 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.
Provenance statement
References
- 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.
- 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
- 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
- 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
- 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
- R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187--201.
- 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.
- T. W. Mattman and A. Pavelescu, Three thousand obstructions to knotless embedding, arXiv:2607.01414v1 (https://arxiv.org/abs/2607.01414v1) (2026).arXiv
- T. W. Mattman and M. Pierce, The and families and obstructions to -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
- 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
- N. Robertson, P. Seymour and R. Thomas, Sachs' linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), 185--227.
Version history
- 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