Counterexamples to coefficient conjectures for plane Penrose polynomials
2026-11-18
Research publication
Counterexamples to coefficient conjectures for plane Penrose polynomials
Preprint
- Original date
- Authors
- Yair Lavi
- Combinatorics
- Graph theory
- Graph polynomials
- Planar graphs
Abstract
We give counterexamples to coefficient-sign alternation and coefficient nonvanishing for the plane Penrose polynomial \(P_H(q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{c_H(A)}\). Here \(H\) is a graph embedded in the sphere, and \(c_H(A)\) counts boundary components after replacing vertices by disks and edges by bands and half-twisting the bands in \(A\). 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 \(160\), 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-\(k\) vertex of the first two examples by a \(k\)-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.
Supplementary material
A standalone exact verifier for the three polynomials, their plane embeddings, the triangle-replacement identity and the minor-minimality of the ten-vertex graph’s cycle matroid (Python 3.10 or later, standard library only), with its saved output and instructions. It is archived on Zenodo together with the paper as doi:10.5281/zenodo.24351582.
SHA-256 of the archive: 7130de37328e4098afd42418fb50751f682e5e1fd5bcd6a511f77a1b99cf825b