Matching works

1 work

math.CO — Combinatorics

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

Contributed by Peter Graham

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.

Primarily AI-generated textHuman understanding: some parts4-flat graphsColin de Verdière invariantGeorgakopoulos–Winter conjectureHeawood familydeleted productexcluded minors
Nov 21, 20269 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations