betaFeedback

WorksMathematics

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

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.

Introduction

Main result

All graphs are finite and simple, with vertex set {0,…,n−1}\{0,\ldots,n-1\}. Let G=(V,E)G=(V,E) be a graph on nn vertices. Following van der Holst, Lovász and Schrijver [3 1.1], the Colin de Verdière invariant μ(G)\mu(G) is the largest corank of a real symmetric n×nn \times n matrix MM such that

  1. for i≠ji \ne j, Mij<0M_{ij} < 0 if ij∈Eij \in E and Mij=0M_{ij} = 0 if ij∉Eij \notin E, with no condition on the diagonal;

  2. MM has exactly one negative eigenvalue, of multiplicity one;

  3. (the Strong Arnold Property) no nonzero real symmetric matrix XX with Xij=0X_{ij} = 0 whenever i=ji = j or ij∈Eij \in E satisfies MX=0MX = 0.

A minor of a graph is a graph obtained from it by deleting vertices and edges and contracting edges, merging parallel edges and removing loops. Since μ\mu does not increase under taking minors [1], the graphs with μ≤k\mu\le k form a minor-closed class. An excluded minor for a minor-closed class is a graph outside the class all of whose proper minors lie in it; a graph is in the class if and only if it has no excluded minor as a minor. A graph is tt-apex if deleting at most tt vertices leaves a planar graph.

A ΔY\Delta Y-transformation replaces the three edges of a triangle by a new vertex adjacent to its three corners; a YΔY\Delta-transformation is the reverse, applied to a vertex of degree three. The Heawood family consists of the 78 graphs obtained from K7K_7 and K3,3,1,1K_{3,3,1,1} by repeated ΔY\Delta Y- and YΔY\Delta-transformations [2 §1.1]: the 20 graphs of the K7K_7 family, with 21 edges, and the 58 of the K3,3,1,1K_{3,3,1,1} family, with 22 edges.

Let G1G_1 and G2G_2 be the graphs with these edge sets:

E(G1)={04,05,06,07,15,16,17,18,1 10,26,27,28,29,37,38,39,3 10,48,49,4 10,59,5 10,6 10},\begin{aligned} E(G_1) = \{04,05,06,07,15,16,17,18,1\,10,26,27,28,29,37,38,39,3\,10,\\ 48,49,4\,10,59,5\,10,6\,10\}, \end{aligned}
E(G2)={05,06,08,09,15,18,19,1 10,26,27,28,37,39,3 10,3 11,48,49,4 10,4 11,57,5 11,6 10,6 11}.\begin{aligned} E(G_2) = \{05,06,08,09,15,18,19,1\,10,26,27,28,37,39,3\,10,3\,11,\\ 48,49,4\,10,4\,11,57,5\,11,6\,10,6\,11\}. \end{aligned}

G1G_1 has 11 vertices and 23 edges, nine of degree 4 and two of degree 5; G2G_2 has 12 vertices and 23 edges and arises from G1G_1 by a ΔY\Delta Y-transformation on the triangle {1,5,10}\{1,5,10\} (Figure 1). They are entries 90 and 332 (numbered from 0) of the list of 3028 obstructions to knotless embedding in Appendix A of Mattman and Pavelescu [8], and the graphs G2G_2 and G3G_3 of Kim and Mattman [5 §3]. Let HH be the graph G1G_1 with the edge {1,10}\{1,10\} deleted; it is 4-regular with 11 vertices and 22 edges. Mattman and Pierce found HH by a computer search, as one of two 4-regular graphs with 11 vertices and 22 edges that are not 2-apex while all their proper minors are [9 §2] (their second edge list, with labels shifted by one). Kim and Mattman call it H2H_2 and show that, up to isomorphism, HH is the only minor of G1G_1 or G2G_2 obtained by one edge deletion or contraction that is not 2-apex [5 §§3.1, 3.3].

Drawings of graphs G1 and G2

Figure 1. Left, G1G_1; deleting the dashed edge {1,10}\{1,10\} gives HH. Right, G2G_2, obtained from G1G_1 by a ΔY\Delta Y-transformation on the thick triangle {1,5,10}\{1,5,10\}; the new vertex is 7 and the thick edges are its three edges. Vertices of G2G_2 carry their labels in G2G_2. Drawn by checks/figure.py from data/graphs.g6, which also checks the drawing.

Theorem 1. μ(G1)=μ(G2)=6\mu(G_1)=\mu(G_2)=6, and neither G1G_1 nor G2G_2 has a minor in the Heawood family.

Corollary 2. The Heawood family is not the complete list of excluded minors for the class of graphs with μ≤5\mu\le5. More precisely, if μ(H)=6\mu(H) = 6 then HH is an excluded minor for μ≤5\mu\le5, and otherwise G1G_1 and G2G_2 both are; in either case none of them is in the Heawood family.

The lower bound μ≥6\mu\ge6 rests on two certificates, one explicit matrix for each graph, checked in exact rational and interval arithmetic, and the minor exclusion on an exhaustive enumeration (§ 6). The upper bound μ≤6\mu\le6 and the identification of the excluded minor are short arguments from known facts.

Background

Colin de Verdière proved that μ\mu is minor-monotone and that μ(G)≤3\mu(G) \le3 exactly when GG is planar [1]; see [3 Theorem 2.4 and 1.4]. Lovász and Schrijver [7] and Robertson, Seymour and Thomas [11] showed that μ(G)≤4\mu(G) \le4 exactly when GG is linklessly embeddable, that is, embeddable in R3\mathbb{R}^3 with no two disjoint cycles linked, so the excluded minors for μ≤4\mu\le4 are those for linkless embedding, the Petersen family [3 1.4]. As Georgakopoulos and Winter point out, the Petersen and Heawood families are both obtained from the Kuratowski graphs K5K_5 and K3,3K_{3,3} “by forming suspensions, and then ΔY\Delta Y- and YΔY \Delta-transformations” [2 §1.1]; this analogy makes the Heawood family the natural candidate for μ≤5\mu\le5.

Van der Holst introduced 4-flat graphs [4]: in the words of Georgakopoulos and Winter, “a graph GG is 4-flat if every 2-dimensional regular CW complex having GG as its 1-skeleton can be (piecewise linearly) embedded into R4\mathbb{R}^4” [2 §1]. Van der Holst proved that for every graph GG of the Heawood family the complex obtained from GG by attaching a disk to each cycle does not embed in R4\mathbb{R}^4 [4], so these graphs are not 4-flat. Two of van der Holst’s conjectures concern us, as Georgakopoulos and Winter record them: (a) a graph is 4-flat if and only if μ≤5\mu\le5 [4 Conjecture 3], [2, Conjecture 1.4]; and (b) the Heawood family is the complete list of excluded minors for 4-flat graphs, the second statement of [2 Conjecture 1.1], which by their footnote 1 combines (a) with van der Holst’s conjecture that the Heawood graphs are the excluded minors for μ≤5\mu\le5 [4 §4]. Georgakopoulos and Winter prove that each Heawood graph is an excluded minor for 4-flat graphs [2 Theorem 6.1] and note that all Heawood graphs have μ=6\mu= 6 [2 §1.1].

A graph is intrinsically knotted if every embedding of it in R3\mathbb{R}^3 contains a knotted cycle, and minor-minimal intrinsically knotted (MMIK) if moreover no proper minor is intrinsically knotted; the MMIK graphs are the excluded minors for knotless embedding. Mattman and Pavelescu state the classification for μ\mu directly: “Conjecture 4 ([vdH]). The graphs in the K7K_7 and K3,3,1,1K_{3,3,1,1} families are the obstructions to μ≤5\mu\le5” [8 p. 3]. Assuming it, they list the MMIK graphs with μ≥6\mu\ge6 through 24 edges, noting that “the MMIK graphs GG in our list are 3-apex” [8 §3]. Of the three MMIK graphs with 23 edges, found by Kim and Mattman [5], they write that “they do not have a minor in the K7K_7 family. By van der Holst’s conjecture these three have μ=5\mu= 5” [8 §3]. Theorem 1 shows that two of them, G1G_1 and G2G_2, have μ=6\mu= 6.

What is new

The new step is the lower bound μ(Gi)≥6\mu(G_i) \ge6. A corank-6 matrix with the sign pattern of GiG_i has to satisfy one polynomial equation for each non-adjacent pair of vertices, and it must also have the Strong Arnold Property; such matrices are found numerically and then certified rigorously. Minor exclusion and the upper bound are routine, and the non-2-apex minors of GiG_i follow from the work of Mattman and Pierce [9] and of Kim and Mattman [5] cited above; we recheck them (Lemma 8). Corollary 2 has the following consequence for 4-flat graphs.

Corollary 3. Conjectures (a) and (b) of § 1.2 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.

Proof. If (a) holds, the two classes coincide and so have the same excluded minors; by Corollary 2 these include a graph outside the Heawood family, so (b) fails.

We do not decide which of (a) and (b) fails, whether G1G_1 is 4-flat, or the value of μ(H)\mu(H). The third 23-edge graph of [8 §3], entry 24 of its Appendix A, is not treated here.

Proof overview

For the lower bound we exhibit, for each G∈{G1,G2}G \in\{G_1,G_2\}, a matrix MM satisfying (i)–(iii) with corank 6. We split the vertices into a set SS of six vertices and the rest TT, choose the T×TT \times T block CC and most of the S×TS \times T block BB as explicit rationals, and set the S×SS \times S block to A=BC−1BTA = BC^{-1}B^{\mathsf{T}}. Then the corank of MM is at least 6 automatically (Lemma 4), and (ii) reduces to an inertia statement about CC. The pattern condition (i) on AA asks that (BC−1BT)ij=0(BC^{-1}B^{\mathsf{T}})_{ij} = 0 for each non-adjacent pair i,j∈Si,j \in S; we leave exactly as many entries of BB free as there are such pairs and solve this square polynomial system numerically. Krawczyk’s test proves that an exact solution lies in a box of radius 10−4010^{-40} around the numerical one (Lemma 5); the remaining sign conditions hold on the whole box; and the Strong Arnold Property, an injectivity statement, is proved at the box center with a margin that survives the perturbation to the exact solution (Lemma 6).

For minor exclusion, every Heawood graph has at least 21 edges and GiG_i has 23, so a Heawood minor would arise from at most two deletions or contractions (Lemma 7), and these are enumerated.

Certificates for μ≥6\mu\ge6

Order the vertices so that SS comes first and write

M=(ABBTC),∣S∣=6, ∣T∣=n−6.M = \begin{pmatrix} A & B \\ B^{\mathsf{T}} & C \end{pmatrix}, \qquad|S| = 6,\ |T| = n - 6.

Lemma 4. If CC is invertible and A=BC−1BTA = BC^{-1}B^{\mathsf{T}}, then MM has the eigenvalue 0 with multiplicity 6 plus that of CC, and MM has as many negative and as many positive eigenvalues as CC.

Proof. With P=(I0C−1BTI)P = \begin{pmatrix} I & 0 \\ C^{-1}B^{\mathsf{T}} & I \end{pmatrix} one has M=PT(000C)PM = P^{\mathsf{T}}\begin{pmatrix} 0 & 0 \\ 0 & C \end{pmatrix}P, and PP is invertible. Sylvester’s law of inertia gives the claim.

The entries of BB on non-edges are 0. On the edges between SS and TT, all but qq entries are fixed negative rationals and the remaining qq are unknowns u=(u1,…,uq)u = (u_1,\ldots,u_q), where qq is the number of non-adjacent pairs in SS. For each such pair i<ji < j let fij(u)=biC−1bjTf_{ij}(u) = b_iC^{-1}b_j^{\mathsf{T}}, where bib_i is the row of BB indexed by ii. Write f=(fij):Rq→Rqf = (f_{ij}): \mathbb{R}^q \to\mathbb{R}^q and JJ for its Jacobian matrix.

The following is Krawczyk’s test [6] in the form of Moore [10], with inclusion in the interior, which makes the choice of YY free.

Lemma 5. Let X⊂RqX \subset\mathbb{R}^q be a box with sides of positive lengths w1,…,wqw_1,\ldots,w_q, let y∈Xy \in X, let YY be a real q×qq \times q matrix, and let J\mathcal{J} be an interval matrix containing J(x)J(x) for every x∈Xx \in X. If the interval vector K=y−Yf(y)+(I−YJ)(X−y)K = y - Yf(y) + (I - Y\mathcal{J})(X-y) lies in the interior of XX, then ff has a zero in XX.

Proof. Let J∈JJ \in\mathcal{J} and D=I−YJD = I - YJ. The interval vector KK contains y−Yf(y)+Ddy - Yf(y) + Dd for every d∈X−yd \in X - y, and as dd ranges over this box the kk-th coordinate of DdDd ranges over an interval of length ∑j∣Dkj∣wj\sum_j |D_{kj}|w_j. Since KK lies in the interior of XX, this is less than wkw_k for every kk. So DD has norm less than 11 for the norm max⁡k∣vk∣/wk\max_k |v_k|/w_k on Rn\mathbb{R}^n, and YJ=I−DYJ = I - D and hence YY are invertible. For x∈Xx \in X, f(x)=f(y)+Jˉ(x−y)f(x) = f(y) + \bar{J}(x-y), where Jˉ\bar{J} is the average of JJ along the segment from yy to xx; it lies in J\mathcal{J} because interval matrices are convex. So g(x)=x−Yf(x)=y−Yf(y)+(I−YJˉ)(x−y)g(x) = x - Yf(x) = y - Yf(y) + (I - Y\bar{J})(x-y) lies in K⊂XK \subset X. By Brouwer’s fixed-point theorem gg has a fixed point x∗x^*, and Yf(x∗)=0Yf(x^*) = 0 gives f(x∗)=0f(x^*) = 0. □

Here yy is a point near the center of XX, YY a floating-point approximation of J(y)−1J(y)^{-1}, and f(y)f(y) and J\mathcal{J} are enclosed in interval arithmetic.

Lemma 6. Let WW be the space of real symmetric matrices XX with Xij=0X_{ij} = 0 whenever i=ji = j or ij∈Eij \in E, with coordinates xij=Xijx_{ij} = X_{ij} for the non-edges i<ji < j, so that ∥X∥F=2∣x∣\lVert X\rVert_F = \sqrt{2}\lvert x\rvert. Suppose that ∥M0X∥F≥ε∣x∣\lVert M_0X\rVert_F \ge\sqrt{\varepsilon}\lvert x\rvert for all X∈WX \in W, for some ε>0\varepsilon> 0. If ∥M−M0∥F<ε/2\lVert M-M_0\rVert_F < \sqrt{\varepsilon}/2, then MM has the Strong Arnold Property.

Proof. For nonzero X∈WX \in W, ∥MX∥F≥∥M0X∥F−∥M−M0∥F∥X∥F>ε∣x∣−22ε∣x∣>0\lVert MX\rVert_F \ge\lVert M_0X\rVert_F - \lVert M-M_0\rVert_F\lVert X\rVert_F > \sqrt{\varepsilon}\lvert x\rvert- \frac{\sqrt{2}}{2}\sqrt{\varepsilon}\lvert x\rvert> 0. □

The hypothesis on M0M_0 says that the Gram matrix of the linear map X↦M0XX \mapsto M_0X on WW, in the coordinates xx, minus εI\varepsilon I is positive definite; for a rational M0M_0 this is an exact computation.

Proof of μ(Gi)≥6\mu(G_i) \ge6. For G1G_1 take S={1,2,3,4,5,10}S = \{1,2,3,4,5,10\}, which spans five edges, so q=10q = 10; for G2G_2 take S={3,5,6,8,9,10}S = \{3,5,6,8,9,10\}, which spans three edges, so q=12q = 12. The certificate files give CC, the fixed entries of BB, and a rational point cc; let XX be the box of radius 10−4010^{-40} about cc in every coordinate. The following are verified.

  1. CC has the pattern (i) of the subgraph induced by TT; the fixed entries of BB are negative; every edge between SS and TT carries a fixed entry or an unknown, and every non-edge the entry 00.

  1. The test of Lemma 5 succeeds on XX, so there is u∗∈Xu^* \in X with f(u∗)=0f(u^*) = 0.

  1. On all of XX, each unknown is negative and (BC−1BT)ij<0(BC^{-1}B^{\mathsf{T}})_{ij} < 0 for each edge ijij inside SS.

  1. CC is invertible with exactly one negative eigenvalue: its characteristic polynomial has rational coefficients and only real roots, so Descartes’ rule of signs counts its positive and negative roots exactly. The inertia is (1,0,4)(1,0,4) for G1G_1 and (1,0,5)(1,0,5) for G2G_2.

  1. For M0M_0 the matrix built from cc and ε=10−6\varepsilon= 10^{-6}, the hypothesis of Lemma 6 holds, and ∥M−M0∥F\lVert M-M_0\rVert_F is at most 1.6×10−381.6 \times10^{-38} for every MM built from a point of XX.

Let M∗M^* be the matrix built from u∗u^*. By (1)–(3) it satisfies (i), since A=BC−1BTA = BC^{-1}B^{\mathsf{T}} vanishes on the non-adjacent pairs in SS by f(u∗)=0f(u^*) = 0. By (4) and Lemma 4 it has corank exactly 66 and one negative eigenvalue, which is (ii). By (5) and Lemma 6 it satisfies (iii). Hence μ(Gi)≥6\mu(G_i) \ge6. □

Excluding Heawood minors

Lemma 7. Let GG have mm edges and let FF be a minor of GG with at least m−km-k edges. Then FF is obtained from GG by at most kk edge deletions and edge contractions followed by deleting isolated vertices.

Proof. A minor is obtained by deleting and contracting edges and deleting vertices. Deleting a vertex of positive degree can be replaced by deleting its edges and then the isolated vertex. Every deletion or contraction of an edge lowers the number of edges by at least one, and deleting an isolated vertex does not change it. So at most kk edge operations occur, and since isolated vertices take part in no edge operation, their deletions can be postponed to the end.

Proof that GiG_i has no Heawood minor. Every Heawood graph has 21 or 22 edges and no isolated vertex. By Lemma 7 with k=2k = 2, a Heawood minor of GiG_i would be isomorphic to a graph obtained from GiG_i by at most two edge deletions or contractions, with isolated vertices removed and parallel edges merged, that has at least 21 edges. The bound of 21 edges loses no Heawood graph; it excludes some graphs, since contracting an edge of a triangle removes two edges. Up to isomorphism there are 354 graphs with at least 21 edges obtained in this way from G1G_1 and 455 from G2G_2, and none is isomorphic to a graph of the Heawood family.

The family itself is regenerated from K7K_7 and K3,3,1,1K_{3,3,1,1} by closing under ΔY\Delta Y and under those YΔY\Delta-transformations whose result is simple; this gives 20 graphs with 21 edges and 58 with 22 edges, the counts of [2 §1.1] and [8 §3].

Proofs of Theorem 1 and Corollary 2

Proof of Theorem 1. § 3 and § 4 give μ(Gi)≥6\mu(G_i) \ge6 and the absence of Heawood minors. For the upper bound, deleting a vertex lowers μ\mu by at most one [3 Theorem 2.7] and planar graphs have μ≤3\mu\le3 [3 1.4], so a graph that becomes planar after deleting tt vertices has μ≤t+3\mu\le t + 3. Deleting {0,1,2}\{0, 1, 2\} leaves a planar graph in both G1G_1 and G2G_2, so μ(Gi)≤6\mu(G_i) \le6.

By the same bound a 2-apex graph has μ≤5\mu\le5, and every minor of a 2-apex graph is 2-apex: if G−XG - X is planar with ∣X∣≤2|X| \le2, deleting an edge or vertex keeps this, contracting an edge avoiding XX contracts it in G−XG - X, and contracting an edge uvuv with u∈Xu \in X into a vertex ww gives a graph in which deleting ww and X∖{u,v}X \setminus\{u,v\} leaves G−(X∪{v})G - (X \cup\{v\}). A graph is 2-apex if and only if the graph obtained by removing its isolated vertices is, since isolated vertices do not affect planarity.

Lemma 8. Up to isomorphism, the minors of G1G_1 that are not 2-apex are G1G_1 and HH, and the minors of G2G_2 that are not 2-apex are G2G_2 and HH.

Proof. For a graph FF write F∘F^\circ for FF with its isolated vertices removed. Starting from GiG_i, apply every single edge deletion and contraction, remove isolated vertices, keep the results that are not 2-apex, and repeat. The search finds, up to isomorphism, exactly GiG_i and HH; for G2G_2 the second graph has 11 vertices and 22 edges and is isomorphic to HH.

Let FF be a minor of GiG_i that is not 2-apex. First, F∘F^\circ is isomorphic to a graph found by the search. Indeed, by Lemma 7 there are graphs Gi=F0,F1,…,FrG_i = F_0, F_1, \ldots, F_r, each obtained from the previous one by an edge deletion or contraction, with Fj∘=F∘F_j^\circ= F^\circ. Each FjF_j has FF as a minor, so it is not 2-apex, and neither is Fj∘F_j^\circ; and Fj+1∘F_{j+1}^\circ is obtained from Fj∘F_j^\circ by one edge deletion or contraction followed by removing isolated vertices. By induction on jj the search reaches every Fj∘F_j^\circ. So F∘F^\circ is isomorphic to GiG_i or HH, and FF has at least 22 edges. Second, FF has no isolated vertex. By Lemma 7 with k=1k = 1, FF is obtained from GiG_i by at most one edge deletion or contraction followed by deleting isolated vertices. The minimum degree of G1G_1 is 4 and that of G2G_2 is 3, and deleting or contracting one edge lowers no degree by more than one, except that the vertex formed by contracting uvuv has degree at least max⁡(deg⁡u,deg⁡v)−1\max(\deg u, \deg v) - 1. So the graph before the last step has minimum degree at least 2, there is nothing to delete, and F=F∘F = F^\circ.

Proof of Corollary 2. Let i∈{1,2}i \in\{1,2\}. Since μ(Gi)=6\mu(G_i)=6 and the class μ≤5\mu\le5 is closed under minors, GiG_i has a minor OO that is an excluded minor for μ≤5\mu\le5. Then OO is not 2-apex, so by Lemma 8 it is isomorphic to GiG_i or HH. If μ(H)=6\mu(H)=6, the proper minors of HH are 2-apex by Lemma 8, so HH is an excluded minor. If μ(H)≤5\mu(H)\le5, every proper minor of GiG_i is HH, a minor of HH or 2-apex, so GiG_i is an excluded minor, for i=1i=1 and i=2i=2. These graphs are minors of G1G_1 or G2G_2, so by Theorem 1 none of them lies in the Heawood family.

Computational verification

The certificates and programs are in the folders data and checks of the published files (linked below the title). The certificate for GiG_i lists its graph, the split (S,T)(S,T), the rational block CC, the fixed entries of BB, the positions of the unknowns and the rational center cc. The checker reads only the certificate. It recomputes the non-adjacent pairs in SS from the graph; runs the test of Lemma 5 at 300 bits in interval arithmetic, with C−1C^{-1} enclosed from exact rationals; checks the signs of items (1) and (3) over the box; computes the characteristic polynomial of CC exactly; and verifies the Gram condition of Lemma 6 exactly, bounding ∥M−M0∥F\lVert M-M_0\rVert_F over the box. A second checker, written separately from a description of the format, repeats these steps with different methods: Krawczyk’s test in exact rational arithmetic using the constant Hessian of the quadratic system ff, inertia by an LDLTLDL^{\mathsf{T}} factorization and by Descartes’ rule, and the Strong Arnold Property in two formulations, each with a Weyl perturbation bound. Both checkers accept both certificates, and each rejects its own suite of deliberately corrupted certificates, listed in the checker documentation.

The Heawood family is generated by two separate programs, which agree on the 78 graphs and the split 20 + 58. Minor exclusion is checked twice: by the enumeration of Lemma 7 with isomorphism tests, and by a search for branch sets of each Heawood graph in GiG_i, cross-checked by deletion and contraction; both find the Heawood minors of three planted control graphs. The 3-apex and 2-apex statements, the minimum degrees used in Lemma 8 and Figure 1 are checked by the same programs. The whole check takes about half a minute on one core. The numerical search that produced the matrices is not part of the proof.

The graphs and certificates in graph6

In the graph6 format, G1G_1 is J?bFF`wNA{?, G2G_2 is K?BD@jguAsBo and HH is J?bFF`wN?{?. In G1G_1 the split is S={1,2,3,4,5,10}S = \{1, 2, 3, 4, 5, 10\}, T={0,6,7,8,9}T = \{0, 6, 7, 8, 9\}, and the ten unknowns are entries of BB on edges between SS and TT; in G2G_2 it is S={3,5,6,8,9,10}S = \{3, 5, 6, 8, 9, 10\}, T={0,1,2,4,7,11}T = \{0, 1, 2, 4, 7, 11\}, with twelve unknowns. The graph G2G_2 also arises from G1G_1 by a ΔY\Delta Y-transformation on the triangle {1,6,10}\{1, 6, 10\}. Deleting any of 105 vertex triples of G1G_1, and any of 130 of G2G_2, leaves a planar graph.

References

  1. [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.DOI
  2. [2]A. Georgakopoulos and M. Winter, On 2-complexes embeddable in 4-space, and the excluded minors of their underlying graphs, arXiv:2408.12681v1 (2024).arxiv.org/abs/2408.12681
  3. [3]H. van der Holst, L. Lovász and A. Schrijver, The Colin de Verdière graph parameter, in Graph Theory and Combinatorial Biology (Balatonelle, 1996), Bolyai Soc. Math. Stud. 7, János Bolyai Math. Soc., Budapest, 1999, 29–85. Numbering as in the preliminary version of March 1997.
  4. [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.DOI
  5. [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; section numbers as in arXiv:2205.14255v2.DOI
  6. [6]R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187–201.DOI
  7. [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.DOI
  8. [8]T. W. Mattman and A. Pavelescu, Three thousand obstructions to knotless embedding, arXiv:2607.01414v1 (2026).arxiv.org/abs/2607.01414
  9. [9]T. W. Mattman and M. Pierce, The Kₙ₊₅ and K₃₂,₁ⁿ families and obstructions to n-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; section numbers as in arXiv:1603.00885v1.
  10. [10]R. E. Moore, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 14 (1977), 611–615.DOI
  11. [11]N. Robertson, P. Seymour and R. Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), 185–227.

Paper details

vlnc:W_zqqhrzjj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI models (from OpenAI and Anthropic)

View statement
Looking for related papers…
Contents