pith. sign in

arxiv: 2606.00653 · v1 · pith:RKHNOHJBnew · submitted 2026-05-30 · 🧮 math.CO

Combinatorial interpretations of Tutte polynomials at the point (2,-1)

Yu Chen , Xian'an Jin , Tianlong Ma This is my paper

Pith reviewed 2026-06-28 18:37 UTC · model grok-4.3

classification 🧮 math.CO
keywords Tutte polynomialspanning forestspermutationsalternating permutationscombinatorial interpretationsgraph enumerationcomplete graphs
0
0 comments X

The pith

The Tutte polynomial T_G(2,-1) equals the number of even-left spanning forests of G and the number of odd G-partitionable permutations.

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

The paper defines two new families of combinatorial objects on a connected graph G: even-left spanning forests and odd G-partitionable permutations. It proves that the number of objects in each family equals the evaluation of the graph's Tutte polynomial at the point (2,-1). For the complete graph K_n the same evaluation counts the alternating permutations on n+1 elements; the equality is shown both by a recurrence and by an explicit bijection.

Core claim

For any simple connected graph G, T_G(2,-1) equals the number of even-left spanning forests of G and also equals the number of odd G-partitionable permutations. When G is the complete graph K_n, T_{K_n}(2,-1) equals the number of alternating permutations on the set {1,2,…,n+1}.

What carries the argument

Even-left spanning forests and odd G-partitionable permutations, the two newly defined objects whose enumeration is shown to match the algebraic value T_G(2,-1).

If this is right

  • The number of even-left spanning forests in any connected graph equals T_G(2,-1).
  • The number of odd G-partitionable permutations in any connected graph equals T_G(2,-1).
  • For the complete graph K_n the number of alternating permutations on n+1 letters equals T_{K_n}(2,-1).
  • The same number admits both a recurrence proof and an explicit bijection proof when G is complete.

Where Pith is reading between the lines

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

  • The explicit bijection between alternating permutations and one of the new objects on K_n may transfer known recurrence or generating-function properties of alternating permutations to the other combinatorial count.
  • The recurrence relation derived for complete graphs may be adaptable to other recursively defined graph families.

Load-bearing premise

The newly introduced even-left spanning forests and odd G-partitionable permutations are assumed to be well-defined objects whose counts exactly equal the algebraic evaluation at (2,-1) with no further restrictions.

What would settle it

For the cycle graph C_4 compute the algebraic value of T_{C_4}(2,-1), then enumerate the even-left spanning forests of C_4 by hand and check whether the two integers coincide.

Figures

Figures reproduced from arXiv: 2606.00653 by Tianlong Ma, Xian'an Jin, Yu Chen.

Figure 1
Figure 1. Figure 1: G 1 2 4 3 F1 1 2 4 3 F2 1 2 4 3 F3 1 2 4 3 F4 1 2 4 3 F5 1 2 4 3 F6 1 2 4 3 F7 1 2 4 3 F8 1 2 4 3 F9 1 2 4 3 F10 1 2 4 3 F11 1 2 4 3 F12 1 2 4 3 F13 1 2 4 3 F14 1 2 4 3 F15 1 2 4 3 F16 1 2 4 3 F17 1 2 4 3 F18 1 2 4 3 F19 1 2 4 3 F20 1 2 4 3 F21 1 2 4 3 F22 1 2 4 3 F23 1 2 4 3 F24 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: All the spanning forests of G (Black forests are even-left, while red and green forests are not and each adjacent pair is the two sides of the involution ψG). We now present the proof of Theorem 1.1. Proof of Theorem 1.1. Note that |NF | is even when F ∈ FG. Therefore, by Lemmas 2.6 and 2.7, we have TG(2, −1) = X F ∈FG (−1)|NF | 8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: Among them, Fi with 13 ≤ i ≤ 22 are not even-left spanning forests, while all the others are even-left. Moreover, we have ψG(F13) = F14, ψG(F15) = F16, ψG(F17) = F18, ψG(F19) = F20, ψG(F21) = F22 and TG(2, −1) = 14. These verify Theorem 1.1. 3. Odd G-partitionable permutations When working with permutations of a finite ordered set (X, <), it is often convenient to record a permutation σ simply by listing i… view at source ↗
read the original abstract

Let $G$ be a simple connected graph, and let $T_{G}(x,y)$ be the Tutte polynomial of $G$. Motivated by the works in \cite{Ma}, we, in this paper, introduce the even-left spanning forests of $G$ and odd $G$-partitionable permutations, and show that $T_{G}(2,-1)$ is equal to both the number of even-left spanning forests of $G$ and the number of odd $G$-partitionable permutations. In particular, for a complete graph $K_n$, we prove that $T_{K_{n}}(2,-1)$ is the number of alternating permutations on $\{1,2,\dots,n+1\}$, using two distinct techniques: a recurrence relation and an explicit bijection construction.

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 claims that for a simple connected graph G, the Tutte polynomial T_G(2,-1) equals both the number of even-left spanning forests of G and the number of odd G-partitionable permutations. For the complete graph K_n it further claims this value equals the number of alternating permutations on {1,2,…,n+1}, established via an independent recurrence relation together with an explicit bijection.

Significance. If the stated equalities hold, the work supplies two new enumerative interpretations of a specific Tutte evaluation and recovers the known count of alternating permutations for complete graphs by two independent methods (recurrence and bijection). Such direct combinatorial models for T_G(2,-1) could be useful for further study of the polynomial’s evaluations.

minor comments (2)
  1. [Abstract] The abstract introduces the terms “even-left spanning forests” and “odd G-partitionable permutations” without definitions or references to their location in the text; the manuscript should place clear, self-contained definitions of these objects in an early section (e.g., §2) before any enumeration claims.
  2. [Abstract] The citation \cite{Ma} is used to motivate the work but is not expanded in the provided abstract; the bibliography entry and any discussion of how the present constructions relate to prior results should be checked for completeness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript and for acknowledging the potential utility of the new combinatorial interpretations for T_G(2,-1). The report lists no specific major comments, and the recommendation is listed as 'uncertain' without further elaboration. We address this below.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces new objects (even-left spanning forests, odd G-partitionable permutations) and proves they count T_G(2,-1); the K_n case uses an independent recurrence plus explicit bijection to alternating permutations. No equations reduce by construction to inputs, no fitted parameters are renamed as predictions, and the cited motivation in \{Ma\} is not load-bearing for the central enumerative claims. The derivation chain is self-contained against external combinatorial verification.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of the Tutte polynomial and of graphs; the new objects are introduced by definition rather than derived from prior axioms.

axioms (1)
  • standard math The Tutte polynomial T_G(x,y) is well-defined for any simple connected graph G via its standard deletion-contraction recurrence or rank-nullity formulation.
    Invoked implicitly when equating the polynomial evaluation to the new counts.

pith-pipeline@v0.9.1-grok · 5661 in / 1319 out tokens · 18825 ms · 2026-06-28T18:37:17.008502+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

17 extracted references

  1. [1]

    J. S. Beissinger, On external activity and inversions in trees,J. Combin. Theory Ser. B33 (1982), no. 1, 87–92

    1982

  2. [2]

    Donaghey, Alternating permutations and binary increasing trees,J

    R. Donaghey, Alternating permutations and binary increasing trees,J. Combina- torial Theory Ser. A18 (1975), 141–148

    1975

  3. [3]

    Gioan, Enumerating degree sequences in digraphs and a cycle-cocycle reversing system,European J

    E. Gioan, Enumerating degree sequences in digraphs and a cycle-cocycle reversing system,European J. Combin.28 (2007), no. 4, 1351–1366

    2007

  4. [4]

    A. J. Goodall et al., On the evaluation of the Tutte polynomial at the points(1,−1) and(2,−1),Ann. Comb.17 (2013), no. 2, 311–332

    2013

  5. [5]

    I. P. Goulden, D. M. Jackson, Combinatorial enumeration, Wiley, Chichester, 1983

    1983

  6. [6]

    I. M. Gessel, Aq-analog of the exponential formula,Discrete Math.40 (1982), no. 1, 69–80

    1982

  7. [7]

    I. M. Gessel, B. E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions,Electron. J. Combin.3 (1996), no. 2, Research Paper 9, approx. 36 pp

    1996

  8. [8]

    Greene, T

    C. Greene, T. Zaslavsky, On the interpretation of Whitney numbers through ar- rangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs,Trans. Amer. Math. Soc.280 (1983), no. 1, 97–126

    1983

  9. [9]

    A. G. Kuznetsov, I. Pak, A. Postnikov, Increasing trees and alternating permuta- tions,Russian Math. Surveys49 (1994), no. 6, 79–114

    1994

  10. [10]

    D. N. Kostić, C. H. Yan, Multiparking functions, graph searching, and the Tutte polynomial,Adv. in Appl. Math.40 (2008), no. 1, 73–97

    2008

  11. [11]

    Merino, The number of 0-1-2 increasing trees as two different evaluations of the Tutte polynomial of a complete graph,Electron

    C. Merino, The number of 0-1-2 increasing trees as two different evaluations of the Tutte polynomial of a complete graph,Electron. J. Combin.15 (2008), no. 1, Note 28, 5 pp

    2008

  12. [12]

    Ma, Y.-N

    J. Ma, Y.-N. Yeh, Combinatorial interpretations forTG(1,−1),J. Graph Theory 69 (2012), no. 3, 341–348

    2012

  13. [13]

    Martin, Remarkable valuation of the dichromatic polynomial of planar multi- graphs,J

    P. Martin, Remarkable valuation of the dichromatic polynomial of planar multi- graphs,J. Combin. Theory Ser. B24 (1978), no. 3, 318–324

    1978

  14. [14]

    Perian, B

    Q. Perian, B. Xu, A. L. Zhang, Counting the nontrivial equivalence classes ofSn under{1234,3412}-pattern-replacement,J. Integer Seq.23 (2020), no. 10, Art. 20.10.2, 16 pp. 16

    2020

  15. [15]

    Rosenstiehl, R

    P. Rosenstiehl, R. C. Read, On the principal edge tripartition of a graph,Ann. Discrete Math.3 (1978), 195–226

    1978

  16. [16]

    R. P. Stanley, Acyclic orientations of graphs,Discrete Math.5 (1973), 171–178

    1973

  17. [17]

    Tutte, A contribution to the theory of chromatic polynomials,Canad

    W. Tutte, A contribution to the theory of chromatic polynomials,Canad. J. Math. 6 (1954) 80–91. 17

    1954