pith. sign in

arxiv: 2606.03166 · v1 · pith:3OEX5VDEnew · submitted 2026-06-02 · 🧮 math.CO

Recurrence and coefficient inequality for the partial Petrial polynomial of graphs

Ruiqing Feng , Xia Guo , Qi Yan This is my paper

Pith reviewed 2026-06-28 09:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords partial Petrial polynomialrecurrence relationcoefficient inequalitylocal complementationedge pivotinggraftsribbon graphs
0
0 comments X

The pith

The partial Petrial polynomial satisfies a three-term recurrence that forces its lowest coefficient to be at most its highest, with equality only for edgeless graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a recurrence that writes the partial Petrial polynomial of any graph as the sum of three polynomials on graphs obtained from an arbitrary edge by local complementation, edge pivoting, and deletion. This recurrence extends an earlier leaf-reduction formula to edges of any degree. The authors then use the relation to compare the extreme coefficients and establish that the coefficient of lowest degree is always less than or equal to the coefficient of highest degree. Equality occurs precisely when the graph contains no edges at all.

Core claim

The partial Petrial polynomial of a graph obeys a three-term recurrence under local complementation and edge pivoting on an arbitrary edge; this relation implies that the lowest-degree coefficient is at most the highest-degree coefficient, with equality if and only if the graph has no edges.

What carries the argument

The three-term recurrence obtained by reducing the partial Petrial polynomial (defined via the rank-generating function of an adjacency matrix) under local complementation and edge pivoting on any edge.

If this is right

  • The recurrence supplies an algorithmic way to evaluate the polynomial by repeated edge reductions.
  • The coefficient comparison holds for every graph, including those with positive-degree vertices.
  • Edgeless graphs are the only ones for which the two extreme coefficients coincide.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The recurrence may permit inductive proofs of other coefficient properties or evaluations at specific points.
  • Similar reductions could be sought for related polynomials on the same class of graphs.

Load-bearing premise

The polynomial admits a reduction under local complementation and edge pivoting that yields the stated three-term recurrence for every edge.

What would settle it

Any graph with at least one edge in which the lowest-degree coefficient strictly exceeds the highest-degree coefficient, or any graph with edges in which the two coefficients are equal.

Figures

Figures reproduced from arXiv: 2606.03166 by Qi Yan, Ruiqing Feng, Xia Guo.

Figure 1
Figure 1. Figure 1: The edge pivot operation: edges between the three sets [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the auxiliary graphs G0 u,v and G1 u,v. Lemma 12 ([12]). Let G be a simple graph and uv ∈ E(G). Then AG ∗ {u, v} = AG∧uv. Lemma 13. Let G be a simple graph and uv ∈ E(G). Set W = V (G)\{u, v}. Let p, q ∈ GF(2)W be column vectors satisfying: for all x ∈ W, px = 1 if and only if x is adjacent to u in G, and qx = 1 if and only if x is adjacent to v in G. Then, for every Q ⊆ W, A [PITH_FULL_IM… view at source ↗
read the original abstract

The partial Petrial polynomial of a ribbon graph, introduced by Gross, Mansour and Tucker, enumerates partial Petrials by Euler genus. Recently, Deng, Jin and Yan defined an analogue for grafts and showed that it can be expressed as a rank-generating function of an adjacency matrix. In this paper we first prove a recurrence relation that reduces the partial Petrial polynomial of a graph with respect to an arbitrary edge, expressing it as a sum of three terms involving graphs obtained by local complementation and edge pivoting. This recurrence extends the known leaf-reduction formula to vertices of any positive degree. Second, using this recurrence we compare the lowest and highest degree coefficients of the polynomial. We prove that the lowest coefficient is always at most the highest coefficient, and that equality holds if and only if the graph has no edges.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves a three-term recurrence for the partial Petrial polynomial of a graft (defined via the rank-generating function of its adjacency matrix) that holds for an arbitrary edge and is obtained by local complementation and edge pivoting; this extends the known leaf-reduction formula. It then applies the recurrence inductively to show that the lowest-degree coefficient is at most the highest-degree coefficient, with equality if and only if the graph is edgeless.

Significance. If the proofs are correct, the recurrence supplies a practical reduction tool for arbitrary edges and enables inductive arguments on the polynomial, while the coefficient comparison gives a clean combinatorial characterization of edgeless graphs. The work directly extends the matrix-based definition of Deng, Jin and Yan and the ribbon-graph polynomial of Gross, Mansour and Tucker; the explicit case analysis on adjacency-matrix entries for the non-leaf case is a concrete strength.

minor comments (2)
  1. The introduction should explicitly restate the rank-generating-function definition of the partial Petrial polynomial (currently only referenced) before stating the recurrence, to make the manuscript self-contained for readers unfamiliar with Deng-Jin-Yan.
  2. In the statement of the recurrence (presumably Theorem 3.1 or equivalent), the three resulting graphs obtained by local complementation and pivoting should be labeled with a uniform notation (e.g., G^e, G_e, etc.) that is used consistently in the subsequent inductive proof of the coefficient inequality.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript. The report correctly summarizes the main results: the three-term recurrence obtained via local complementation and edge pivoting, and the coefficient comparison characterizing edgeless graphs. We are pleased that the referee views the explicit case analysis and the extension of the leaf-reduction formula as strengths.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript defines the partial Petrial polynomial via the rank-generating function of the adjacency matrix of the graft (external prior definition). It then derives the three-term recurrence explicitly from this matrix definition by direct computation on adjacency-matrix entries under local complementation and edge pivoting. The coefficient inequality is obtained by induction on the recurrence, with the equality case verified by separate explicit check on edgeless graphs. No equation reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation chain; the derivation chain is self-contained against the matrix definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the prior definition of the partial Petrial polynomial for grafts and on the standard behavior of local complementation and edge pivoting in graph theory.

axioms (1)
  • domain assumption The partial Petrial polynomial of a graft is given by the rank-generating function of an adjacency matrix (Deng, Jin and Yan).
    The recurrence and coefficient comparison are derived from this definition.

pith-pipeline@v0.9.1-grok · 5664 in / 1092 out tokens · 25864 ms · 2026-06-28T09:43:57.048335+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 2 linked inside Pith

  1. [1]

    Arratia, B

    R. Arratia, B. Bollobás, G.B. Sorkin, The interlace polynomial: a new graph polynomial, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2000, pp. 237– 245

    2000

  2. [2]

    Arratia, B

    R. Arratia, B. Bollobás, G.B. Sorkin, The interlace polynomial of a graph,J. Combin. Theory Ser. B92 (2004) 199–233

    2004

  3. [3]

    Bollobás, O

    B. Bollobás, O. Riordan, A polynomial of graphs on surfaces,Math. Ann.323 (2002) 81–96

    2002

  4. [4]

    Bouchet, Graphic presentations of isotropic systems,J

    A. Bouchet, Graphic presentations of isotropic systems,J. Combin. The- ory Ser. B45 (1988) 58–76

    1988

  5. [5]

    Bouchet, Multimatroids

    A. Bouchet, Multimatroids. III. Tightness and fundamental graphs,Eu- ropean J. Combin.22 (2001) 657–677

    2001

  6. [6]

    Q. Deng, X. Jin, Q. Yan, Partial-twuality polynomials of matrices, arXiv:2604.12433, 2026

    Pith/arXiv arXiv 2026

  7. [7]

    Ellis-Monaghan, I

    J.A. Ellis-Monaghan, I. Moffatt, Twisted duality for embedded graphs, Trans. Amer. Math. Soc.364 (2012) 1529–1569

    2012

  8. [8]

    R. Feng, Q. Yan, X. Zheng, Characterizing circle graphs with binomial partial Petrial polynomials,Discrete Appl. Math.382 (2026) 411–416

    2026

  9. [9]

    Gross, T

    J.L. Gross, T. Mansour, T.W. Tucker, Partial duality for ribbon graphs, II: Partial-twuality polynomials and monodromy computations,Euro- pean J. Combin.95 (2021) 103329. 14

    2021

  10. [10]

    Kotzig, Eulerian lines in finite 4-valent graphs and their transforma- tions, Theory of Graphs , Academic Press, New York, 1968, pp

    A. Kotzig, Eulerian lines in finite 4-valent graphs and their transforma- tions, Theory of Graphs , Academic Press, New York, 1968, pp. 219–230

    1968

  11. [11]

    I.Moffatt, Delta-matroidsforgraphtheorists, SurveysinCombinatorics, 2019, London Math. Soc. Lecture Note Ser., vol. 456, Cambridge Univ. Press, Cambridge, 2019, pp. 167–220

    2019

  12. [12]

    Moffatt, From matrix pivots to graphs in surfaces: Exploring com- binatorics through partial duals, European Congress of Mathematics, EMS Press, Berlin, 2023, pp

    I. Moffatt, From matrix pivots to graphs in surfaces: Exploring com- binatorics through partial duals, European Congress of Mathematics, EMS Press, Berlin, 2023, pp. 825–856

    2023

  13. [13]

    Wilson, Operators over regular maps,Pacific J

    S.E. Wilson, Operators over regular maps,Pacific J. Math.81 (1979) 559–568

    1979

  14. [14]

    Q. Yan, X. Jin, Partial-twuality polynomials of delta-matroids,Adv. Appl. Math.153 (2024) 102623

    2024

  15. [15]

    Q. Yan, Y. Li, Partial Petrial polynomials for complete graphs and paths,Discrete Appl. Math.375 (2025) 281–289

    2025

  16. [16]

    X.Yu, R.Hao, J.Liu, Z.Li, PartialPetrialpolynomialsofribbongraphs, arXiv:2604.21942, 2026. 15

    Pith/arXiv arXiv 2026