betaFeedback

WorksMathematics

Counterexamples to coefficient conjectures for plane Penrose polynomials

Abstract

We give counterexamples to coefficient-sign alternation and coefficient nonvanishing for the plane Penrose polynomial PH(q)=∑A⊆E(H)(−1)∣A∣qcH(A)P_H(q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{c_H(A)}. Here HH is a graph embedded in the sphere, and cH(A)c_H(A) counts boundary components after replacing vertices by disks and edges by bands and half-twisting the bands in AA. Weak alternation means that coefficients, read in descending powers from a positive leading coefficient, are alternately nonnegative and nonpositive. We construct a simple bridgeless plane graph on ten vertices whose Penrose polynomial is monic of degree eight and has linear coefficient 160160, contrary to weak alternation. A bridgeless plane multigraph on eleven vertices has zero linear coefficient. We also give a simple bridgeless cubic example on twelve vertices, where cubic means that every vertex has degree three; its linear and quadratic coefficients both have the wrong signs. These examples answer Aigner's questions on coefficient nonvanishing and sign alternation negatively. Replacing each degree-kk vertex of the first two examples by a kk-cycle, with the incident edges attached in their embedding order, gives counterexamples to both coefficient conjectures of Kauffman, Silver and Williams. A known triangle-replacement identity gives infinite families, and connected sums give arbitrarily many vanishing initial coefficients for the Penrose–Kauffman polynomial. The cycle matroid of the ten-vertex example is an explicit planar minor-minimal obstruction to coefficient alternation, answering Aigner's question about minor-minimal binary-matroid obstructions negatively.

Introduction

The Penrose polynomial has its origins in Penrose’s tensor approach to graph coloring [8]. A plane graph is a finite graph embedded in the sphere. Following Aigner, call it normal if it is 2-connected and any two distinct faces share at most one boundary edge; 2-connected means that there are at least three vertices and deleting any one vertex leaves a connected graph. For a normal plane graph HH with ff faces, write PH(q)=∑i=1faiqiP_H(q)=\sum_{i=1}^{f}a_iq^i. In this setting Aigner’s questions [1 Problems 1–2], restated in our notation, are as follows.

Problem 1 asks whether ai≠0a_i\ne0 for every 1≤i≤f1\le i\le f; in particular, whether a1≠0a_1\ne0, with the stronger proposed inequality (−1)f−1a1>0(-1)^{f-1}a_1>0.

Problem 2 asks whether the coefficients weakly alternate, (−1)f−iai≥0(-1)^{f-i}a_i\ge0 for every 1≤i≤f1\le i\le f. It also asks whether PH(−1)≠0P_H(-1)\ne0, with the stronger proposed inequality (−1)fPH(−1)>0(-1)^fP_H(-1)>0.

The Eulerian case was proved by Aigner [1 Corollary 5]; his survey also records the series-parallel and outerplanar cases, citing Mielke’s thesis [2 pp. 65–66]. The graph terminology is recalled in Section 2.1. The motivation includes the Four Color Theorem: for a connected bridgeless plane graph, weak coefficient alternation implies four-face-colorability, meaning that faces sharing an edge receive different colors from a set of four [A, Corollary 11]; [A00, Theorem 16]. Further background appears in [3].

For a cubic graph GG, in which every vertex has degree three, a perfect matching MM is a set of edges meeting every vertex exactly once. The Penrose–Kauffman polynomial PKG,M(q)\mathrm{PK}_{G,M}(q), at a positive integer qq, counts colorings of the edges outside MM with qq named colors: the two colors at each vertex must be distinct, and the unordered pairs at the two ends of every matching edge must agree. Section 2.3 gives the polynomial construction. Kauffman, Silver and Williams (KSW) conjecture, for every connected cubic plane graph GG with specified perfect matching MM, that (1) the linear coefficient of PKG,M\mathrm{PK}_{G,M} is nonzero and (2) its coefficients weakly alternate [7 Section 8, p. 24].

We begin with two explicit normal plane graphs. The tetragonal trapezohedron G10G_{10} violates both weak alternation and the proposed strict sign of the linear coefficient.1 Splitting one of its two degree-four vertices gives ZZ, whose zero linear coefficient refutes both nonvanishing assertions. Their cycle expansions, defined in Section 2.3, refute KSW Conjectures (2) and (1), respectively. We then give a full treatment of the twelve-vertex cubic graph H0H_0, obtained by splitting both degree-four vertices of G10G_{10}. Its ordinary Penrose polynomial violates weak alternation in both the linear and quadratic coefficients, as well as the proposed strict linear sign, so the failure persists even for simple bridgeless cubic plane graphs. All three families satisfy (−1)fPH(−1)>0(-1)^fP_H(-1)>0, as shown in Section 7.

Sections 3–4 construct G10G_{10} and ZZ and prove their polynomial formulas by exact reproducible calculations. Section 5 applies the known triangle-replacement identity [5 Theorem 4.1, equation (4.5)] to obtain infinite families. Section 6 gives the cubic example H0H_0 and its entire cubic family. Section 7 records the conjecture consequences, connected sums with arbitrarily many initial zero coefficients, and the planar minor-minimality of the cycle matroid M(G10)M(G_{10}), defined below, which answers Aigner’s classification question [2 p. 66] negatively. These results do not contradict the Four Color Theorem and supply no new proof of it.

Preliminaries

Ribbon surfaces and coefficient signs

A plane graph means a finite graph embedded in the sphere. A graph is simple if it has no loops or parallel edges, cubic if every vertex has degree three, and bridgeless if deleting any edge preserves its number of connected components. The graphs constructed below are connected and loopless; ZZ has two parallel edges. We use the definition of normality from Section 1. The dual H∗H^* has one vertex for each face of HH, and one edge crossing each edge of HH and joining its two incident faces.

A graph is Eulerian if every vertex degree is even. A graph minor is obtained by edge deletions, vertex deletions, and edge contractions. The graph K4K_4 is the complete graph on four vertices; series-parallel graphs have no K4K_4 minor. An outerplanar graph admits an embedding with every vertex on one face boundary.

Replace the vertices of a plane graph HH by disjoint disks and its edges by narrow bands attached in the embedding’s cyclic order. This gives a compact surface with boundary, called a ribbon neighborhood. For A⊆E(H)A \subseteq E(H), insert one half twist in each band indexed by AA, leaving all attaching orders fixed. Let cH(A)c_H(A) be the number of boundary components of the resulting surface. We use the ribbon-surface expression of Ellis-Monaghan–Moffatt [6 Proposition 5.1], which for plane graphs gives Aigner’s Penrose polynomial [1]:

PH(q)=∑A⊆E(H)(−1)∣A∣qcH(A).(1)P_H(q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{c_H(A)}. \tag*{(1)}

For a polynomial P(q)=∑k=0dakqkP(q)=\sum_{k=0}^{d}a_kq^k with ad>0a_d>0, weak sign alternation means

(−1)d−kak≥0(0≤k≤d).(2)(-1)^{d-k}a_k\geq0 \qquad(0\leq k\leq d). \tag*{(2)}

We write [qk]P(q)[q^k]P(q) for the coefficient of qkq^k in P(q)P(q).

Aigner indexes the signs from the number of faces. In all three base examples the degree equals that number, so there is no indexing ambiguity. The constant term in (1) is zero; the nonvanishing question concerns the coefficients of q,…,qdq,\ldots,q^d.

The binary-Laplacian formula

Work over the field F2={0,1}\mathbb{F}_2=\{0,1\}, with addition and multiplication modulo two. Let TT be a finite loopless multigraph on dd vertices. For an edge e=uve=uv, let beb_e have a one in positions u,vu,v and zero elsewhere. Define

LA=∑e∈AbebeT,r(A)=rank⁡F2LA,FT(q)=∑A⊆E(T)(−1)∣A∣qd−r(A).(3)L_A=\sum_{e\in A}b_eb_e^{\mathsf{T}},\qquad r(A)=\operatorname{rank}_{\mathbb{F}_2}L_A,\qquad F_T(q)=\sum_{A\subseteq E(T)}(-1)^{|A|}q^{d-r(A)}. \tag*{(3)}

Each edge toggles its two off-diagonal entries and the two corresponding diagonal entries. Parallel edges are separate elements of E(T)E(T) and contribute separately to this sum.

We recall the binary-matroid definitions needed both for the formula and for the final consequence. A binary matroid N=(E,C)\mathcal{N}=(E,C) is specified by a finite set EE and a subspace C⊆F2EC\subseteq\mathbb{F}_2^E, its cycle space. The support of a vector is the set of its nonzero coordinates. The nonempty supports of vectors in CC that are minimal under inclusion are the circuits. The dual N∗\mathcal{N}^* has cycle space C⊥C^\perp, the orthogonal complement for the usual mod-two dot product. An element is a coloop if it belongs to no circuit; a matroid is bridgeless if it has no coloops. Deleting an element restricts to cycles with zero in that coordinate and then removes the coordinate; contracting it projects all cycles onto the remaining coordinates. A matroid minor is obtained by a sequence of these operations.

For a graph HH, its cycle matroid M(H)M(H) has the even-degree edge subsets as its binary cycle space, with addition given by symmetric difference. A matroid is graphic if it is a graph’s cycle matroid, and planar if that graph can be chosen planar. For A⊆EA\subseteq E, let x∣Ax|_A denote the vector equal to xx on AA and zero elsewhere. Set

BN(A)={x∈C:x∣A∈C⊥},QN(q)=∑A⊆E(−1)∣A∣qdim⁡BN(A).(4)B_{\mathcal{N}}(A)=\{x\in C:x|_A\in C^\perp\},\qquad Q_{\mathcal{N}}(q)=\sum_{A\subseteq E}(-1)^{|A|}q^{\dim B_{\mathcal{N}}(A)}. \tag*{(4)}

We use the binary-matroid Penrose polynomial of Aigner and Mielke [4], in the cycle-space form recorded in [2 equation (4.5)]. The letter QQ distinguishes its normalization from the graph polynomial.

Proposition 1 (Binary-Laplacian formula). Let c(T)c(T) be the number of connected components of the loopless multigraph TT. Then

FT(q)=qc(T)QM∗(T)(q).(5)F_T(q)=q^{c(T)}Q_{M^*(T)}(q). \tag*{(5)}

If T=H∗T=H^* for a connected bridgeless plane graph HH, then PH(q)=FT(q)=qQM(H)(q)P_H(q)=F_T(q)=qQ_{M(H)}(q).

The boundary-count identity underlying the plane-graph formula is known [9 Theorem 1.1] and is used in the proofs of [7 Proposition 6.2 and Theorem 6.3]. We recall a short derivation from Aigner’s characterization [1 Proposition 1].

Proof. Let DD be the vertex-edge incidence matrix of TT over F2\mathbb{F}_2, whose columns are the beb_e. The cycle space of M∗(T)M^*(T) is the cut space im⁡DT\operatorname{im}D^{\mathsf{T}}, and its orthogonal complement is ker⁡D\ker D. For x=DTyx=D^{\mathsf{T}}y, the condition x∣A∈ker⁡Dx|_A\in\ker D is exactly LAy=0L_Ay=0. The map y↦DTyy\mapsto D^{\mathsf{T}}y has kernel of dimension c(T)c(T), consisting of vectors constant on each component. Since DTy=0D^{\mathsf{T}}y=0 implies beTy=0b_e^{\mathsf{T}}y=0 for every edge ee, it also implies LAy=0L_Ay=0. Thus ker⁡DT⊆ker⁡LA\ker D^{\mathsf{T}}\subseteq\ker L_A. The restricted map DT:ker⁡LA→BM∗(T)(A)D^{\mathsf{T}}:\ker L_A\to B_{M^*(T)}(A) is surjective and has kernel of dimension c(T)c(T). Rank-nullity now gives dim⁡BM∗(T)(A)=d−r(A)−c(T)\dim B_{M^*(T)}(A)=d-r(A)-c(T), proving the first identity. For a connected plane graph HH, plane duality gives M(H)=M∗(H∗)M(H)=M^*(H^*), and the closed paths in Aigner’s construction can be identified with ribbon boundaries. For every A⊆E(H)A\subseteq E(H), his closed paths with changing set AA correspond to the boundary components of the ribbon surface twisted along AA: both follow the face-boundary pairing at edges outside AA and the crossing pairing at edges in AA [1 Section 2]; [6 proof of Proposition 5.1]. Thus his path count is cH(A)c_H(A) for each AA. Aigner’s boundary-count identity then gives dim⁡BM(H)(A)=cH(A)−1\dim B_{M(H)}(A)=c_H(A)-1. Substitution into (1) and (4) proves the remaining identities. □\square

If TT is simple, only the empty subset has LA=0L_A=0, because the off-diagonal entries record the selected edges. Hence FTF_T is monic of degree dd. Also LA1=0L_A\mathbf{1}=0, so r(A)≤d−1r(A)\le d-1. For normal plane graphs this recovers [1 Corollary 3]; the corresponding PK statement is [7 Proposition 6.2]. For comparison, a graph on two vertices with two parallel edges has FT(q)=2q2−2qF_T(q)=2q^2-2q.

Cycle expansion and the Penrose–Kauffman polynomial

A perfect matching MM of a cubic graph GG is a set of edges meeting each vertex exactly once. A Tait nn-coloring of (G,M)(G,M) assigns one of nn named colors to every edge outside MM, so that the two colors at each vertex are distinct and the unordered pairs at the two ends of every matching edge agree. The Penrose–Kauffman polynomial PKG,M(q)PK_{G,M}(q) counts these colorings at every positive integer q=nq=n [7 Definition 3.1].

To see that this is a polynomial with integer coefficients, define a state to be a choice, at each matching edge, of one of the two bijections between the pairs of incident nonmatching edges. The two local pairings are shown in Figure 1. Following the pairings gives closed circuits. A state is uncolorable if the two local strands selected by the pairing at some matching edge belong to the same circuit. Otherwise its component graph is the simple graph with one vertex per circuit, with two vertices adjacent when the circuits meet at a matching edge. A proper coloring assigns different colors to adjacent vertices; its counting polynomial is the chromatic polynomial. Summing these chromatic polynomials over the colorable states counts every Tait coloring once, since distinct colors determine a unique compatible pairing at each matching edge [7 Theorem 3.4]. Uncolorable states contribute zero. A related expansion for plane Penrose polynomials is given in [6 Theorem 7.2].

Figure 1. Local matching and band rules. In (a), the central matching edge is uncolored and its endpoints have the same unordered pair of distinct incident colors. Panels (b) and (c) show the two possible pairings of the four nonmatching strands incident with the matching edge in (a). These correspond respectively to an untwisted band and a half-twisted band. The labels ℓ1,ℓ2,r1,r2\ell_1,\ell_2,r_1,r_2 correspond respectively to the upper-left, lower-left, upper-right and lower-right strands in (a). For the displayed colors i≠ji \ne j, only pairing (c) joins strands of equal color. The crossing in (c) is not a graph vertex.

For a loopless plane graph HH of minimum degree at least three, let its cycle expansion (also called truncation) ΔH\Delta H be the graph obtained by replacing each vertex of degree kk by a kk-cycle and attaching its incident edges in cyclic order. The original edges form a perfect matching MHM_H, and ΔH\Delta H is a cubic plane graph. Thus degree-three vertices become triangles and degree-four vertices become quadrilaterals.

Proposition 2 (Identity for cycle expansion). For every connected loopless plane graph HH of minimum degree at least three,

PH(q)=PKΔH,MH(q).(6)P_H(q)=P_{K_{\Delta H,M_H}}(q). \tag*{(6)}

Identity (6) is stated in [7 Section 4], where the cycle expansion is called a blow-up; the same construction is used in [5 Section 1]. We give a direct proof from the ribbon sum (1).

Proof. At a positive integer q=nq=n, expand each term in (1) by assigning a color to each boundary circuit. Regroup by fixed colors on the corner arcs, the portions of the vertex-disk boundaries between consecutive edge bands. The corner arcs around a degree-kk vertex of HH correspond to the edges of its replacement kk-cycle in ΔH\Delta H. The band of an original edge ee corresponds to the matching edge ee in MHM_H; the two corner arcs at either end correspond to the two nonmatching edges incident with that endpoint. For each such coloring, the signed sum factors over the edge bands: a local pairing is compatible when joined ends have the same color, and the untwisted and twisted pairings have weights +1+1 and −1-1. If all four ends at a band have the same color, both pairings are compatible and their local contribution is 1−1=01-1=0. These assignments therefore cancel.

Every surviving compatible assignment has two distinct colors at every band and exactly one compatible pairing there. Its unordered pairs at the two ends agree, precisely the Tait-coloring rule for (ΔH,MH)(\Delta H,M_H). Its total sign is positive: each twisted pairing is a crossing between two differently colored closed curves in the sphere. For each pair of colors, the total number of crossings is even, because closed mod-two cycles on the sphere have zero intersection number. Summing over color pairs makes the number of selected twists even. For every positive integer nn, the sum therefore counts the Tait nn-colorings. Equality at all positive integers proves the polynomial identity. □

The first two counterexamples

Construct G10G_{10} from the cycle c0c1⋯c7c0c_0c_1\cdots c_7c_0. Put a vertex NN inside the cycle and join it to c0,c2,c4,c6c_0,c_2,c_4,c_6; put a vertex SS outside and join it to c1,c3,c5,c7c_1,c_3,c_5,c_7. We call NN and SS the two hubs. This is the tetragonal trapezohedron graph, shown in Figure 2. The construction specifies its sphere embedding.

Figure 2. The two plane graphs. The left panel shows G10G_{10}, and the right panel shows the split hub and the two parallel edges of ZZ. The cycle labels agree in both panels.

It is simple and connected, has eight degree-three vertices and two degree-four vertices, and has sixteen edges and eight quadrilateral faces. Every edge lies on a cycle, so it is bridgeless.

To obtain ZZ, split NN into N1N_1, N2N_2, keeping N1N_1 adjacent to c0c_0, c2c_2 and N2N_2 adjacent to c4c_4, c6c_6, and join N1N_1, N2N_2 by two parallel edges bounding a digon. All other edges and their embedding are unchanged. This connected graph has eleven vertices, eighteen edges, and nine faces: six quadrilaterals, two pentagons and the digon. Its vertices have degrees three or four, and every edge again lies on a cycle. Both graphs are 2-connected: deleting a hub leaves the cycle connected, and deleting a cycle vertex leaves a path to which every remaining hub is attached. Their duals described below are simple, so both graphs are normal.

Theorem 1. The graphs just constructed have Penrose polynomials

PG10(q)=q8−16q7+114q6−432q5+857q4−744q3+60q2+160q,(7)P_{G_{10}}(q) = q^{8} - 16q^{7} + 114q^{6} - 432q^{5} + 857q^{4} - 744q^{3} + 60q^{2} + 160q, \tag*{(7)}

and

PZ(q)=q9−18q8+150q7−708q6+1973q5−3178q4+2700q3−920q2.(8)P_Z(q) = q^{9} - 18q^{8} + 150q^{7} - 708q^{6} + 1973q^{5} - 3178q^{4} + 2700q^{3} - 920q^{2}. \tag*{(8)}

Thus PG10P_{G_{10}} fails weak sign alternation, and [q]PZ(q)=0[q]P_Z(q) = 0.

The calculation proving (7)–(8) is given next. Both dual graphs are simple. The dual T=G10∗T = G_{10}^{*} is the square antiprism: on vertices 0,…,70, \ldots, 7, its edges are the unordered pairs {i,i+1}\{i, i+1\} and {i,i+2}\{i, i+2\}, with indices modulo eight. Explicitly, for i=0,1,2,3i = 0, 1, 2, 3, label the face Nc2ic2i+1c2i+2Nc_{2i}c_{2i+1}c_{2i+2} by 2i+12i + 1 and the face Sc2i+1c2i+2c2i+3Sc_{2i+1}c_{2i+2}c_{2i+3} by 2i+22i + 2, taking all numerical labels modulo eight. Then Z∗Z^{*} is obtained from TT by adding vertex 88 and edges 3838, 7878. The two pentagons retain labels 33, 77, and the new digon receives label 88. These descriptions also give the input for the short calculation in Appendix § 8.

Proof of Theorem and independent checks

For the graph TT in (3), define Br(T)=(−1)r[qd−r]FT(q)B_r(T)=(-1)^r[q^{d-r}]F_T(q), setting Br(T)=0B_r(T)=0 outside 0≤r≤d0\le r\le d. These numbers remove the expected alternating signs: weak alternation is equivalent to Br(T)≥0B_r(T)\ge0 for every rr. The rank formula gives

Br(T)=#{A:r(A)=r, ∣A∣≡r(mod2)}−#{A:r(A)=r, ∣A∣≢r(mod2)}.(9)\begin{aligned} B_r(T)={}&\#\{A:r(A)=r,\ |A|\equiv r\pmod{2}\}\\ &-\#\{A:r(A)=r,\ |A|\not\equiv r\pmod{2}\}. \tag*{(9)} \end{aligned}

Proof of Theorem 1. By Proposition 1, the required coefficients are given by binary-Laplacian ranks. Table 1 records all 2162^{16} subsets for G10∗G_{10}^{*} and all 2182^{18} subsets for Z∗Z^{*}. The even and odd columns count subsets of the given rank by the parity of ∣A∣|A|, so Br=(−1)r(even−odd)B_r=(-1)^r(\text{even}-\text{odd}) by (9). The dash denotes a rank outside the range for G10∗G_{10}^{*}.

rank rrG10∗G_{10}^{*}: evenoddBrB_rZ∗Z^{*}: evenoddBrB_r
0101101
10161601818
21301611416616150
3232664432272980708
425451688857432523521973
56504724874411424146023178
613148130886035236325362700
71020810048−160-1604928050200920
8———30368303680

Table 1. Exact edge-subset counts by binary-Laplacian rank and edge-count parity for G10∗G_{10}^{*} and Z∗Z^{*}; Br=(−1)r(even−odd)B_r=(-1)^r(\text{even}-\text{odd}).

Taking even minus odd as the coefficient of qd−rq^{d-r} proves (7)–(8). For G10G_{10}, degree eight requires a nonpositive linear coefficient, whereas that coefficient is 160. For ZZ, the equally sized even and odd classes with one boundary component cancel. Appendix A exhausts every edge subset and computes these counts in exact integers. Thus B7(G10∗)=−160B_7(G_{10}^{*})=-160 exhibits failure of weak alternation, whereas B8(Z∗)=0B_8(Z^{*})=0 records the vanishing linear coefficient.

Independent checks

The supplement, described under Supplementary material, contains the verification program (verify.py), reproduction instructions (README.md), and exact output with the program SHA-256 (verification.json). The program verify.py reconstructs the embeddings from the cycle-and-hubs description, checks the sphere and duals, and obtains both polynomials by three computations: the binary-Laplacian sum, direct tracing of twisted-ribbon boundary components in (1), and set partitions of the corner arcs in Proposition 2. The last calculation enumerates color classes of the 32 or 36 nonmatching edges of the cycle expansion. A partition into mm nonempty classes has (q)m=q(q−1)⋯(q−m+1)(q)_m=q(q-1)\cdots(q-m+1) assignments of distinct named colors. This gives the general falling-factorial expansion of [7 equation (8.2)]. Processing arcs in a fixed order and assigning either an existing class or the next unused class enumerates each partition once; the local pair constraints reject incompatible assignments. Our enumerated counts give

PG10(q)=8(q)3+48(q)4+88(q)5+44(q)6+12(q)7+(q)8,P_{G_{10}}(q) = 8(q)_3 + 48(q)_4 + 88(q)_5 + 44(q)_6 + 12(q)_7 + (q)_8,
PZ(q)=24(q)3+184(q)4+404(q)5+300(q)6+108(q)7+18(q)8+(q)9.(10)P_Z(q) = 24(q)_3 + 184(q)_4 + 404(q)_5 + 300(q)_6 + 108(q)_7 + 18(q)_8 + (q)_9. \tag*{(10)}

Since [q](q)m=(−1)m−1(m−1)![q](q)_m = (-1)^{m-1}(m-1)!, the coefficient formula [7 Corollary 8.4] gives the direct checks

[q]PG10=16−288+2112−5280+8640−5040=160,[q]P_{G_{10}} = 16 - 288 + 2112 - 5280 + 8640 - 5040 = 160,
[q]PZ=48−1104+9696−36000+77760−90720+40320=0.[q]P_Z = 48 - 1104 + 9696 - 36000 + 77760 - 90720 + 40320 = 0.

For each graph, the coefficient of (q)m(q)_m in (10) is the count eme_m of colorings up to renaming in [7 equation (8.2)]. The number of colorings using all mm named colors is cm=m!emc_m = m!e_m, as used in [7 Corollary 8.4]. Direct enumeration of color partitions provides an independent check of the rank calculation. The supplement also checks numerical evaluations from Aigner’s formulas, the dual cancellation for triangle replacement on a nine-edge test graph, and the matroid-minimality calculation below. Its README gives a standalone reproduction command and explains the exact outputs. All these calculations use integer arithmetic.

Triangle replacement and infinite families

We call replacing one degree-three vertex by a triangle, with the incident edges attached in their embedding order, a triangle replacement. The following is its dual form. Let TT be a finite simple plane graph with a triangular face abcabc, and form T′T' by placing a new vertex vv inside that face and joining it to aa, bb, cc. We give a short algebraic proof of the known recurrence [5 Theorem 4.1, equation (4.5)]. For a selected edge set A′⊆E(T′)A' \subseteq E(T'), write A=A′∩E(T)A = A' \cap E(T) and J={x∈{a,b,c}:vx∈A′}J = \{x \in\{a,b,c\} : vx \in A'\}, the set of selected neighbors of vv.

Lemma 1 (Triangle recurrence). In this setting,

FT′(q)=(q−2)FT(q),Br(T′)=Br(T)+2Br−1(T),(11)F_{T'}(q) = (q - 2)F_T(q), \qquad B_r(T') = B_r(T) + 2B_{r-1}(T), \tag*{(11)}

where missing coefficient indices have value zero.

Proof. We pair terms in the full sum indexed by (A,J)(A,J), allowing the old subset AA to change. Choose aa as a distinguished vertex. The following pairing cancels all terms except those with J=∅,{b},{c}J = \varnothing, \{b\}, \{c\}:

  • If ∣J∣=2|J| = 2, toggle the old edge joining the two vertices in JJ.

  • If J={a,b,c}J = \{a,b,c\}, change JJ to {a}\{a\} and toggle all three old triangle edges; reverse this rule when J={a}J = \{a\}.

Every rule is its own inverse and reverses the edge-count parity. The second rule changes two spokes and three old edges. We check that both preserve binary rank.

For ∣J∣=2|J| = 2, let L=LA′L = L_{A'} be the binary Laplacian of the selected edge set A′A' in T′T', let eve_v be the coordinate vector at vv, and put z=Levz = Le_v. The vector zz has ones exactly at the two selected neighbors. Since vv has two selected incident edges, Lvv=0L_{vv} = 0 over F2\mathbb{F}_2, so zTev=Lvv=0z^{\mathsf{T}}e_v = L_{vv} = 0. Toggling the edge between those neighbors changes LL to L+zzTL + zz^{\mathsf{T}}, and

L+zzT=L(I+evzT),(I+evzT)2=I.L + zz^{\mathsf{T}} = L(I + e_v z^{\mathsf{T}}), \qquad(I + e_v z^{\mathsf{T}})^2 = I.

The right factor is invertible, proving rank preservation.

For odd ∣J∣|J|, put coordinate vv first, let ss be the neighbor indicator, and use the diagonal entry 1 as a pivot. The resulting Schur complement is LA+diag⁡(s)+ssTL_A+\operatorname{diag}(s)+ss^{\mathsf{T}}. For J={a}J=\{a\} the last two terms cancel. For J={a,b,c}J=\{a,b,c\} they are the binary Laplacian of the old triangle. Toggling that triangle makes the two pivoted matrices identical. Both full matrices have rank one more than this Schur complement.

The unpaired choices are J=∅,{b},{c}J=\varnothing,\{b\},\{c\}. For an old subset of rank rr, the empty choice has rank rr on d+1d+1 vertices and contributes qq times its old monomial. Each remaining singleton has rank r+1r+1 and the opposite edge-count sign, hence contributes minus its old monomial. Their sum is (q−2)(q-2) times the old contribution. Comparing coefficients, with the degree increased by one, gives the second identity in (11).

The same argument proves (11) for any finite loopless multigraph TT containing a triangle abcabc, with T′T' obtained by adjoining a new vertex joined once to each of a,b,ca,b,c. If parallel edges occur, fix one edge for each side of the triangle and use those edges in the toggles. Planarity and the facial condition are needed only for the dual interpretation as triangle replacement.

Let HH be either G10G_{10} or ZZ. For an integer t≥0t\ge0, write H(t)H^{(t)} for any graph obtained by tt successive triangle replacements. At each step any degree-three vertex may be chosen, including one created by an earlier replacement. In each base graph a degree-three vertex meets three distinct faces. Dually, its replacement inserts a vertex into a triangular face, preserving simplicity of the dual and the sphere embedding. The new degree-three vertices also have triangular dual faces, so this argument applies at every step. The replacement also preserves 2-connectedness: after deleting any one vertex, paths through the replaced vertex can be routed through the surviving triangle. Thus the resulting graphs remain normal and bridgeless; those starting from G10G_{10} remain simple.

Each replacement adds two vertices, three edges and one face. Equation (11) therefore gives

PH(t)(q)=(q−2)tPH(q),deg⁡PG10(t)=8+t,deg⁡PZ(t)=9+t.(12)P_{H^{(t)}}(q)=(q-2)^tP_H(q),\qquad\deg P_{G_{10}^{(t)}}=8+t,\qquad\deg P_{Z^{(t)}}=9+t. \tag*{(12)}

In particular,

(−1)7+t[q]PG10(t)(q)=−160⋅2t<0,[q]PZ(t)(q)=0.(13)(-1)^{7+t}[q]P_{G_{10}^{(t)}}(q)=-160\cdot2^t<0,\qquad[q]P_{Z^{(t)}}(q)=0. \tag*{(13)}

To see this directly from the coefficient recurrence, let TT have dd vertices. Its constant coefficient Bd(T)B_d(T) is zero, since every LAL_A has the all-ones vector in its kernel. Equation (11) gives Bd(T′)=2Bd−1(T)B_d(T')=2B_{d-1}(T): the sign-adjusted linear coefficient doubles at each replacement. Starting from −160-160 and 0 gives (13).

The cubic counterexample and its family

The first two base graphs have degree-four vertices. We now construct a simple cubic example for the ordinary Penrose polynomial. Starting from G10G_{10}, split NN into adjacent vertices N1,N2N_1,N_2, with N1N_1 joined to c0,c2c_0,c_2 and N2N_2 to c4,c6c_4,c_6. Split SS into adjacent vertices S1,S2S_1,S_2, with S1S_1 joined to c1,c3c_1,c_3 and S2S_2 to c5,c7c_5,c_7. Each split uses a single joining edge and inherits the plane embedding. Denote the resulting graph by H0H_0; see Figure 3.

The graph has twelve vertices, eighteen edges and eight faces: four quadrilaterals and four pentagons. Every vertex has degree three, and the edge list has no loops or parallel edges. Deleting a cycle vertex leaves a path with both split hub pairs attached; deleting a hub vertex leaves the original cycle and all other hubs attached. Thus H0H_0 is 2-connected and bridgeless. Its dual T0T_0 is obtained from the labelled square antiprism of § 3 by adding edges {3,7}\{3,7\} and {0,4}\{0,4\}. The first splits the northern square face of the dual and the second the southern square face. The dual is simple, so H0H_0 is normal.

Theorem 2 (A cubic counterexample and an infinite cubic family). The graph H0H_0 has Penrose polynomial

Figure 3. The cubic plane graph H0H_0. Both hubs of G10G_{10} are split into adjacent pairs, each joined by a single edge. The cycle labels are the same as in Figure 2.

PH0(q)=q8−18q7+162q6−753q5+1692q4−1452q3−208q2+576q.(14)P_{H_0}(q) = q^8 - 18q^7 + 162q^6 - 753q^5 + 1692q^4 - 1452q^3 - 208q^2 + 576q. \tag*{(14)}

For every integer t≥0t \ge0, let HtH_t be any graph obtained from H0H_0 by tt successive triangle replacements. Then HtH_t is normal, simple, connected, bridgeless and cubic, with 12+2t12 + 2t vertices, 18+3t18 + 3t edges and 8+t8 + t faces, and

PHt(q)=(q−2)tPH0(q).(15)P_{H_t}(q) = (q - 2)^t P_{H_0}(q). \tag*{(15)}

Its linear and quadratic coefficients both have the wrong signs:

(−1)7+t[q]PHt(q)=−576⋅2t<0,(16)(-1)^{7+t}[q]P_{H_t}(q) = -576 \cdot2^t < 0, \tag*{(16)}
(−1)6+t[q2]PHt(q)=−(208+288t)2t<0.(-1)^{6+t}[q^2]P_{H_t}(q) = -(208 + 288t)2^t < 0.

Proof. Apply Proposition 1 to the dual T0T_0 just specified. Table 2, computed by the exhaustive integer calculation in Appendix § 8, gives (14).

rank rrevenoddBr(T0)B_r(T_0)
0101
101818
219230162
rank rrevenoddBr(T0)B_r(T_0)
35911344753
4720455121692
524700261521452
65406454272−208-208
74432043744−576-576

Table 2. Exact edge-subset counts for T0=H0∗T_0 = H_0^*; all 2182^{18} subsets are included, and Br=(−1)r(even−odd)B_r = (-1)^r(\text{even} - \text{odd}).

The construction and the preservation argument in § 5 prove the graph properties at every step. Each replacement adds two vertices, three edges and one face and preserves degree three. Lemma 1 gives (15). Put ℓt=(−1)7+t[q]PHt\ell_t=(-1)^{7+t}[q]P_{H_t} and st=(−1)6+t[q2]PHts_t=(-1)^{6+t}[q^2]P_{H_t}. The coefficient recurrence in (11) gives ℓt+1=2ℓt\ell_{t+1}=2\ell_t and st+1=2st+ℓts_{t+1}=2s_t+\ell_t, with ℓ0=−576\ell_0=-576 and s0=−208s_0=-208. Induction gives (16). □\square

The supplement reconstructs this embedding and verifies (14) by the same three computations used for G10G_{10} and ZZ. The color-class enumeration gives the further check

PH0(q)=3(q)3+93(q)4+207(q)5+50(q)6+10(q)7+(q)8.P_{H_0}(q)=3(q)_3+93(q)_4+207(q)_5+50(q)_6+10(q)_7+(q)_8.

A proper edge three-coloring assigns one of three named colors to each edge, with different colors on edges sharing a vertex. Direct enumeration gives eighteen such colorings of H0H_0. Triangle replacement preserves this number: the three external edge colors at a replacement triangle must be distinct, and then each internal edge has the color missing at its two endpoints. Indeed, for each color, counting its incidences at the three triangle vertices forces an odd number of external edges of that color; hence there is exactly one of each. This gives a bijection with colorings before replacement. Consequently every HtH_t has eighteen proper edge three-colorings.

The evaluations PH0(3)=18P_{H_0}(3)=18 and PH0(−2)=73728=(−4)6⋅18P_{H_0}(-2)=73728=(-4)^6\cdot18 agree with the standard cubic formulas [1 Corollaries 8 and 10]. More generally, (15) gives PHt(3)=18P_{H_t}(3)=18 and PHt(−2)=(−4)6+t⋅18P_{H_t}(-2)=(-4)^{6+t}\cdot18. The value at −1-1 is recorded with those of the other two families in § 7.

Thus weak alternation and the proposed strict linear sign fail even for the ordinary Penrose polynomial of simple bridgeless cubic plane graphs. Since [q]PH0=576≠0[q]P_{H_0}=576\ne0, this example does not refute linear nonvanishing.

Consequences for the coefficient conjectures

The graphs G10(t)G_{10}^{(t)} answer Aigner’s weak-alternation question and his proposed strict sign for the linear coefficient negatively [1 Problems 1–2]. The graphs Z(t)Z^{(t)} answer both his linear-nonvanishing question and his question whether every coefficient from the linear through the leading term is nonzero negatively. The polynomial of ZZ itself does satisfy weak alternation; its purpose here is the distinct nonvanishing conclusion.

The graphs ΔG10(t)\Delta G_{10}^{(t)} and ΔZ(t)\Delta Z^{(t)} are simple, connected, bridgeless cubic plane graphs on 32+6t32+6t and 36+6t36+6t vertices, respectively, with the specified perfect matchings. Propositions 1–2 and (13) refute [7 Conjecture (2)] and [7 Conjecture (1)], respectively. The replacement cycles have length at least three, and each original edge joins different cycles, so the expansions are simple. Each new cycle edge lies on its replacement cycle; a cycle containing an original edge lifts to a cycle in the expansion. This proves bridgelessness.

The ordinary families G10(t)G_{10}^{(t)} and Z(t)Z^{(t)} retain degree-four vertices and are not cubic; Theorem 2 supplies the separate cubic ordinary-Penrose family. Every Z(t)Z^{(t)} retains its digon. This family therefore does not settle coefficient nonvanishing for the ordinary Penrose polynomial of simple normal plane graphs, or for the associated diagrams without bigons. The simple bridgeless cubic expansions ΔZ(t)\Delta Z^{(t)} already refute nonvanishing for the matching-dependent polynomial PKG,MP_{KG,M}.

The diagram associated with (ΔG10,MG10)(\Delta G_{10},M_{G_{10}}) lies in the class of [7 Theorem 6.6]. In the construction of [7 Section 4], contract each matching edge to a crossing to obtain the medial projection, whose vertices correspond to edges of G10G_{10} and whose arcs join consecutive edges around its vertices. The associated crossing choices make the diagram alternating. A diagram is reduced if no crossing is isolated from the remainder by a simple closed curve through that crossing, and prime if any simple closed curve meeting the projection transversely twice bounds a disk containing only an arc on at least one side. Because G10G_{10} is 2-connected, each vertex occurs only once on the boundary of each incident face. A two-edge cut in its medial projection would admit a separating simple closed curve crossing precisely the two cut edges once each. Between crossings, the curve lies in one vertex region and one face region, so the cut edges would represent distinct corners of the same vertex in the same face, a contradiction. A separating vertex would also yield a two-edge cut: in a connected 4-regular graph, every component left after deleting a vertex meets it in a positive even number of edges. Thus the diagram is reduced and prime. Its regions have lengths given by vertex degrees and face lengths of G10G_{10}, namely three or four, so it has no bigon regions. Weak alternation fails even for this diagram class.

The diagrams associated with (ΔHt,MHt)(\Delta H_t,M_{H_t}), t≥0t \ge0, also belong to this class. Each HtH_t is simple, cubic and 2-connected, so the same connectivity argument applies, vertex regions have length three and face regions have length at least three. By (6) and (16), weak alternation fails in both the linear and quadratic coefficients throughout this family.

All three base graphs have odd-degree vertices, so these examples do not contradict the Eulerian result [1 Corollary 5]. Their values at −1-1 are PG10(−1)=2064P_{G_{10}}(-1)=2064, PZ(−1)=−9648P_Z(-1)=-9648, and PH0(−1)=3294P_{H_0}(-1)=3294. For a base graph HH with fHf_H faces, successive triangle replacements give

(−1)fH+tPH(t)(−1)=3t(−1)fHPH(−1).(17)(-1)^{f_H+t}P_{H(t)}(-1)=3^t(-1)^{f_H}P_H(-1). \tag*{(17)}

The three resulting values are 2064⋅3t2064\cdot3^t, 9648⋅3t9648\cdot3^t, and 3294⋅3t3294\cdot3^t, respectively, all positive. All three families satisfy the sign-at-minus-one inequality proposed in [1 Problem 2].

There is also an arbitrarily long block of initial zero coefficients for the Penrose–Kauffman polynomial. A connected sum of diagrams cuts one arc in each and joins the ends across the two diagrams. Take s≥1s \ge1 copies of the diagram associated with (ΔZ,MZ)(\Delta Z,M_Z) and iterate precisely the joining of [7 Definition 3.6, Figure 7(c)]. Let (Γs,Ms)(\Gamma_s,M_s) be the corresponding connected cubic plane graph with its specified matching. Then [7 Proposition 3.7(3)] gives

PΓs,Ms(q)=PZ(q)sqs−1=qs+1(−920+qR(q))s,R(q)∈Z[q].(18)P_{\Gamma_s,M_s}(q)=\frac{P_Z(q)^s}{q^{s-1}}=q^{s+1}(-920+qR(q))^s,\qquad R(q)\in\mathbb{Z}[q]. \tag*{(18)}

Thus the coefficients of q,…,qsq,\ldots,q^s vanish, and the coefficient of qs+1q^{s+1} is (−920)s≠0(-920)^s\ne0. This realizes the conditional consequence already noted in [7 p. 25].

An explicit planar matroid obstruction

Dividing a nonzero graph polynomial by qq decreases its degree and every nonzero exponent by one, preserving the difference between degree and exponent in (2): (d−1)−(k−1)=d−k(d-1)-(k-1)=d-k. By (5), QM(G10)Q_{M(G_{10})} has degree seven and constant coefficient 160, whereas weak alternation requires a non-positive constant coefficient. Aigner asks whether F7∗F_7^*, M(Pet)M(\mathrm{Pet}), and M∗(K5)M^*(K_5) are the only bridgeless minor-minimal binary matroids whose Penrose polynomials have non-alternating coefficients [A00, p. 66]. A positive answer would imply the Four Color Theorem. Theorem 3 answers this question negatively by providing a planar minor-minimal obstruction. Here F7F_7 is the Fano matroid whose cycle space is the kernel of the 3-by-7 matrix with all nonzero vectors of F23\mathbb{F}_2^3 as columns. The Petersen graph Pet⁡\operatorname{Pet} has vertices uiu_i, viv_i for ii modulo five and edges uiui+1u_i u_{i+1}, uiviu_i v_i, and vivi+2v_i v_{i+2}. The graph K5K_5 is complete on five vertices.

Theorem 3 (Planar minor-minimal obstruction; computer-assisted). The 16-element planar matroid M(G10)M(G_{10}) fails weak coefficient alternation, and every proper bridgeless minor has strictly alternating coefficients. Thus M(G10)M(G_{10}) is a planar minor-minimal obstruction to coefficient alternation, distinct from all three examples listed by Aigner, none of which is planar.

Here minimality is within the bridgeless class. Strict alternation requires strict inequalities for every coefficient of QQ, including its constant term. Minor-minimality holds for both strict and weak alternation: QM(G10)Q_{M(G_{10})} fails weak alternation, whereas every proper bridgeless minor satisfies strict alternation. As in Aigner’s list, we regard the zero polynomial QF7∗=0Q_{F_7^*}=0 as non-alternating.

Proof. It remains to verify minimality and the nonplanarity of the listed examples. Distinctness already follows from their sizes: M(G10)M(G_{10}) has sixteen elements, whereas F7∗F_7^*, M(Pet⁡)M(\operatorname{Pet}), and M∗(K5)M^*(K_5) have seven, fifteen and ten, respectively. Since M(G10)=M∗(T)M(G_{10})=M^*(T) for the square antiprism TT, its bridgeless minors are the matroids M∗(U)M^*(U) of loopless graph minors UU of TT. Contracted edges partition V(T)V(T) into connected blocks. Contract each block, delete the resulting loops, and retain any selection of edges between blocks. This describes every loopless minor, including disconnected ones and the empty matroid.

A class of k≥1k\geq1 parallel edges contributes 2k−12^{k-1} times the contribution of a single edge to (3): its even and odd subsets each number 2k−12^{k-1} and give, respectively, the zero and single-edge binary-Laplacian contributions. Let U‾\overline{U} retain all vertices and one edge from each parallel class, and put p=∣E(U)∣−∣E(U‾)∣≥0p=|E(U)|-|E(\overline{U})|\geq0. Then FU(q)=2pFU‾(q)F_U(q)=2^pF_{\overline{U}}(q). Since c(U)=c(U‾)c(U)=c(\overline{U}), also QM∗(U)=2pQM∗(U‾)Q_{M^*(U)}=2^pQ_{M^*(\overline{U})}. Thus simplification preserves both strict and weak alternation. In the plane-graph setting this is [7 Theorem 6.3], the dual form of [1 Corollary 2]. It suffices to examine every spanning subgraph RR of each simple quotient and test QM∗(R)=FR/qc(R)Q_{M^*(R)}=F_R/q^{c(R)}.

The supplement performs this finite exhaustive calculation. For each quotient with edge set EE, start with the signed nullity monomial (−1)∣A∣qd−r(A)(-1)^{|A|}q^{d-r(A)} at every A⊆EA\subseteq E. For each edge ee, add the entry for R∖{e}R\setminus\{e\} to that for RR whenever e∈Re\in R. After all edges have been processed, the entry at RR is exactly FRF_R. Removing the factor qc(R)q^{c(R)} and testing all coefficients gives strict alternation in every case except the original full square antiprism. Only the partition into singleton blocks can retain sixteen distinct edges, so this exception is precisely M(G10)M(G_{10}) itself. The enumeration covers 1,511 partitions into connected blocks, 151 distinct labelled simple quotients, and 624,339 pairs consisting of a partition and a spanning subgraph of its simple quotient. The last count retains partition multiplicity; repeated labelled quotients are evaluated once. For each partition, we label its blocks 0, 1, . . . in increasing order of their least vertex; quotients are identified only when their resulting labelled vertex and edge sets agree. These are not counts of nonisomorphic matroids. This proves minimality.

None of Aigner’s three matroids is planar. By Whitney’s planarity criterion [10 Theorem 29], the dual of a graph’s cycle matroid is graphic if and only if the graph is planar. If M(Pet⁡)M(\operatorname{Pet}) admitted a planar graph representation, its dual would be graphic; Whitney’s criterion would imply that Pet⁡\operatorname{Pet} itself is planar, a contradiction. The same criterion makes M∗(K5)M^*(K_5) nongraphic because K5K_5 is nonplanar. Also F7∗F_7^* is nongraphic: its cycle space has dimension three, every nonzero vector has support of size four, and every two elements belong to a common circuit. A graphic representation would therefore be connected after removing isolated vertices, with seven edges and five vertices.

Its circuits force it to be simple and triangle-free, whereas such a graph on five vertices has at most six edges. Every minor of a planar matroid is planar, so none of these three matroids can be a minor of M(G10)M(G_{10}). □\square

The Petersen example is not minor-minimal, contrary to its description in [2 p. 66]. Contract the outer edge e=u0u1e = u_0u_1 in the labelling above. The resulting graph is bridgeless, and an exact cycle-space calculation in the supplement gives

QM(Pet)/e(q)=q6−14q5+84q4−235q3+248q2+12q−96.(19)Q_{M(\mathrm{Pet})/e}(q) = q^{6} - 14q^{5} + 84q^{4} - 235q^{3} + 248q^{2} + 12q - 96. \tag*{(19)}

Its positive linear coefficient and negative constant coefficient violate weak alternation. Thus a proper bridgeless minor of M(Pet)M(\mathrm{Pet}) already fails.

The matroid M(G10)M(G_{10}) does not contradict Tutte’s tangential 2-block conjecture in the formulation of [2 equation (5.3)], since

QM(G10)(4)=PG10(4)/4=336≠0.(20)Q_{M(G_{10})}(4) = P_{G_{10}}(4)/4 = 336 \ne0. \tag*{(20)}

A complete calculation of the rank tables

The following program requires Python 3.10 or later and uses only integers and the standard library. Bits encode vectors over F2\mathbb{F}_2. The pivot dictionary stores independent rows with distinct highest set bits; each XOR is elementary row reduction. Every subset is visited once, and the four toggled entries per selected edge are exactly its binary-Laplacian contribution. The three edge lists are exactly the duals specified in Sections 3 and 6. The same exhaustive calculation gives Tables 1 and 2.

edges = sorted({tuple(sorted((i, (i+s) % 8)))
                for i in range(8) for s in (1, 2)})
for name, n, es in [("G10", 8, edges),
                    ("Z", 9, edges + [(3, 8), (7, 8)]),
                    ("H0", 8, edges + [(3, 7), (0, 4)])]:
    counts = [[0, 0] for _ in range(n)]
    for mask in range(1 << len(es)):
        rows = [0] * n
        for j, (a, b) in enumerate(es):
            if (mask >> j) & 1:
                pair = (1 << a) | (1 << b)
                rows[a] ^= pair
                rows[b] ^= pair
        pivots = {}
        for row in rows:
            while row:
                lead = row.bit_length() - 1
                if lead in pivots:
                    row ^= pivots[lead]
                else:
                    pivots[lead] = row
                    break
        counts[len(pivots)][mask.bit_count() & 1] += 1
    assert sum(map(sum, counts)) == 1 << len(es)
    print(name)
    for r, (even, odd) in enumerate(counts):
        print(r, even, odd, (-1)**r * (even - odd))

Supplementary material

The supplement contains a standalone exact verifier requiring Python 3.10 or later and only the standard library, together with its saved output and a README. The supplement, supplement-v7.tar.gz, is archived together with this paper on Zenodo at https://doi.org/10.5281/zenodo.24351582.

Acknowledgments

The proofs in this paper were developed by OpenAI’s GPT models (Sol and Astra) and Anthropic’s Claude Fable models under the author’s guidance. The author has reviewed the resulting proof arguments. The author takes full responsibility for the contents of this paper.

References

  1. [1]M. Aigner, The Penrose polynomial of a plane graph, Mathematische Annalen 307 (1997), 173–189. doi:10.1007/s002080050030. Author preprint A-96-12 (1996). Item numbering follows the linked author preprint.DOI
  2. [2]M. Aigner, Die Ideen von Penrose zum 4-Farbenproblem, Jahresbericht der Deutschen Mathematiker-Vereinigung 102 (2000), 43–68. Journal scan.
  3. [3]M. Aigner, The Penrose polynomial of graphs and matroids, in J. W. P. Hirschfeld (ed.), Surveys in Combinatorics, 2001, London Mathematical Society Lecture Note Series 288, Cambridge University Press (2001), 11–46. doi:10.1017/CBO9780511721328.004.DOI
  4. [4]M. Aigner and H. Mielke, The Penrose polynomial of binary matroids, Monatshefte für Mathematik 131 (2000), 1–13. doi:10.1007/s006050070020.DOI
  5. [5]S. Baldridge and B. McCarty, New relations for the Penrose polynomial, arXiv: 2606.06643v1, 4 June 2026.arxiv.org/abs/2606.06643
  6. [6]J. A. Ellis-Monaghan and I. Moffatt, A Penrose polynomial for embedded graphs, European Journal of Combinatorics 34 (2013), 424–445. doi:10.1016/j.ejc.2012.06.009; arXiv: 1106.5279v3. Item numbering follows arXiv v3.
  7. [7]L. H. Kauffman, D. S. Silver and S. G. Williams, The Penrose-Kauffman Polynomial, arXiv: 2604.16635v1, 17 April 2026.arxiv.org/abs/2604.16635
  8. [8]R. Penrose, Applications of Negative Dimensional Tensors, in D. J. A. Welsh (ed.), Combinatorial Mathematics and its Applications, Academic Press (1971), 221–244.
  9. [9]D. S. Silver and S. G. Williams, On the component number of links from plane graphs, Journal of Knot Theory and Its Ramifications 24 (2015), 1520002. doi:10.1142/S0218216515200023. arXiv:1408.6815.DOI
  10. [10]H. Whitney, Non-separable and planar graphs, Transactions of the American Mathematical Society 34 (1932), 339–362. doi:10.1090/S0002-9947-1932-1501641-2.DOI

Paper details

vlnc:W_5qzh3pjf
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

OpenAI GPT (Sol), OpenAI GPT (Astra), Anthropic Claude Fable

View statement
Looking for related papers…
Contents