Matching works

1 work

math.CO — Combinatorics

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

Contributed by Peter Graham

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

Primarily AI-generated textHuman understanding: some parts4-flat graphsColin de Verdière invariantHeawood familyexcluded minorsintrinsically knotted graphs
Nov 20, 20268 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations