Skip to main content

Counterexamples to coefficient conjectures for plane Penrose polynomials

2026-11-18

← All publications

Research publication

Counterexamples to coefficient conjectures for plane Penrose polynomials

Preprint

Original date
Authors
Yair Lavi

Topics

  • Combinatorics
  • Graph theory
  • Graph polynomials
  • Planar graphs

External publication links

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

Paper

This browser cannot display the PDF inline. Open the PDF in a new tab.