The Heawood family is not the complete list of excluded minors for 4-flat graphs

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.GT — Geometric Topology

Contributed by Peter Graham ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

A graph is 4-flat if the complex obtained by filling every simple cycle with a separate disk embeds piecewise linearly in four-dimensional space. The Heawood family consists of 78 graphs obtained from K7K_7 and K3,3,1,1K_{3,3,1,1} by triangle–star and star–triangle transformations. Van der Holst proved that these graphs are not 4-flat; Georgakopoulos and Winter completed the proof that all 78 are excluded minors and conjectured that there are no other excluded minors for 4-flatness. We show that the known eleven-vertex, twenty-two-edge graph HH is not 4-flat and has no Heawood-family minor, resolving the completeness question negatively. Mattman and Pierce found by computer search that every proper minor of HH is 2-apex; this implies that HH itself is a further excluded minor. Mattman and Pierce found HH, subsequently studied by Kim and Mattman. An earlier paper by the author proved that its one-edge extension G1G_1 has Colin de Verdière invariant 6 and no Heawood-family minor. This made 4-flatness completeness incompatible with van der Holst's proposed equivalence between 4-flatness and invariant at most 5. The new step is an explicit mod-two deleted-product cycle with invariant one. Van der Holst and Pendavingh's obstruction theorem therefore excludes an even map, and hence an embedding, of a cycle subcomplex of HH into four-dimensional space. Two separately written exact implementations evaluate the certificate, using moment-curve intersections and the recursive cellular invariant, respectively. 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.24146253. Paper text license: CC BY 4.0. The published code and data are governed by the licenses in the tagged release. Release archive folders: checks, data.

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. 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
  2. P. Graham, The Heawood family is not the complete list of excluded minors for Colin de Verdière invariant at most 5, heawood-family-mu5 , version 1 (2026), doi:10.5281/zenodo.24128771 (https://doi.org/10.5281/zenodo.24128771).DOI
  3. 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 refer to arXiv:2205.14255v2 (https://arxiv.org/abs/2205.14255v2).arXivDOI
  4. T. W. Mattman and A. Pavelescu, Three thousand obstructions to knotless embedding, arXiv:2607.01414v1 (https://arxiv.org/abs/2607.01414v1) (2026).arXiv
  5. 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., 2017, 137--158, doi:10.1090/conm/689/13856 (https://doi.org/10.1090/conm/689/13856). Section numbers refer to arXiv:1603.00885v1 (https://arxiv.org/abs/1603.00885v1).arXivDOI
  6. V. Kaluža and M. Tancer, Even maps, the Colin de Verdière number and representations of graphs, arXiv:1907.05055v2 (https://arxiv.org/abs/1907.05055v2) (2020). All page and proposition references use this version.arXiv
  7. J. Matoušek, M. Tancer and U. Wagner, Hardness of embedding simplicial complexes in Rd\R^d, J. Eur. Math. Soc. 13 (2011), 259--295, doi:10.4171/JEMS/252 (https://doi.org/10.4171/JEMS/252).DOI
  8. H. van der Holst, L. Lovász and A. Schrijver, The Colin de Verdière graph parameter, in Graph Theory and Combinatorial Biology , Bolyai Soc. Math. Stud. 7 (1999), 29--85, open text (https://ir.cwi.nl/pub/1257/1257D.pdf).link
  9. 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
  10. H. van der Holst and R. A. Pendavingh, On a graph property generalizing planarity and flatness, Combinatorica 29 (2009), 337--361, doi:10.1007/s00493-009-2219-6 (https://doi.org/10.1007/s00493-009-2219-6). Lemma 12, Theorem 18 and section numbers refer to the author manuscript dated April 26, 2008 (https://www.researchgate.net/publication/220441340_On_a_graph_property_generalizing_planarity_and_flatness).DOI

Version history

  1. v1 · 9 pagesSubmitted by P. GrahamZenodo archive: https://doi.org/10.5281/zenodo.24146253. Paper text license: CC BY 4.0. The published code and data are governed by the licenses in the tagged release. Release archive folders: checks, data.CurrentNov 21, 2026