Pith. sign in

REVIEW 6 minor 21 references

Computing the permanental polynomial of $4k$-intercyclic bipartite graphs

T0 review · 0 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The permanental polynomial of every 4k-intercyclic bipartite graph equals a modified characteristic polynomial plus four times the sum of modified characteristic polynomials of its 4k-cycle-deleted subgraphs.

desk verdict Solid combinatorial formula for permanental polynomial of 4k-intercyclic bipartite graphs; proof is checkable and the result is a genuine extension of the C4k-free case. read the letter →

arxiv 2411.14238 v1 pith:NHZYVSO4 submitted 2024-11-21 math.CO cs.DM

Ravindra B. Bapat , Ranveer Singh , Hitesh Wankhede This is my paper · ORCID
classification math.COcs.DM MSC 05C3105C5005C85
keywords permanentalpolynomialcharacteristicmodified4k-intercyclicbipartitegraphC4k-freeSachssubgraphPfaffianorientationcospectralgraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a formula that computes the permanental polynomial $\pi(G,x)$ of a bipartite graph $G$ from determinant-style data, for every graph in which no two cycles whose lengths are multiples of four are vertex-disjoint. The formula is $\pi(G,x)=\varphi_p(G,x)+4\sum_{R\in C_{4k}(G)}\varphi_p(G\setminus R,x)$, where $\varphi_p$ is the modified characteristic polynomial obtained from $\det(xI-A(G))$ by changing the signs of selected coefficients. The proof counts Sachs subgraphs directly and does not use Pfaffian orientations, which apply only to a different class of bipartite graphs. For graphs with no cycle of length divisible by four, the sum is empty and the formula reduces to the known identity $\pi(G,x)=\varphi_p(G,x)$. The result matters because the permanental polynomial is a stronger graph invariant than the characteristic polynomial in practice, yet it is normally much harder to compute.

What carries the argument

The load-bearing object is the modified characteristic polynomial $\varphi_p(G,x)=\sum_{i\text{ even}}(-1)^{i/2}a_i x^{n-i}$, where $a_i$ are the coefficients of $\phi(G,x)=\det(xI-A(G))$. The mechanism that carries the argument is the Sachs coefficient expansion: the coefficients of $\phi$ and $\pi$ are signed and unsigned counts of Sachs subgraphs, so subtracting the appropriately signed characteristic coefficients cancels every Sachs subgraph containing an even number of cycles whose length is a multiple of four. The $4k$-intercyclic condition turns the surviving odd contribution into a sum over cycles, and the one-to-one correspondence between Sachs subgraphs containing a fixed cycle $R$ and Sachs subgraphs of $G\setminus R$ converts that sum into $\varphi_p(G\setminus R)$; the factor $4$ is the factor $2^{s(U)+1}$ that appears when a Sachs subgraph contains exactly one $4k$-cycle.

What would settle it

Enumerate all small 4k-intercyclic bipartite graphs, compute both sides of Theorem 2.1—the left side by direct permanent expansion and the right side from the characteristic polynomials of the cycle-deleted graphs—and compare coefficients. The first graph for which the coefficient of any $x^{n-i}$ differs would refute the theorem, and the paper's own worked example with three 4-cycles and two 8-cycles is the natural starting place.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a coefficient identity. For a bipartite graph, the difference $f(G,x)=\pi(G,x)-\varphi_p(G,x)$ expands over Sachs subgraphs—subgraphs whose components are edges or cycles—and only Sachs subgraphs containing an odd number of cycles of length divisible by four contribute. The $4k$-intercyclic hypothesis guarantees that every Sachs subgraph contains at most one such cycle, so the correction breaks into a sum over the cycles $R$ of $G$. Deleting a fixed $R$ sets up a one-to-one correspondence between Sachs subgraphs of $G$ containing $R$ and Sachs subgraphs of $G\setminus R$, and because $G\setminus R$ has no cycle of length divisible by four, its permanental polynomial is exactly its modified characteristic polynomial. The theorem $\pi(G,x)=\varphi_p(G,x)+4\sum_{R\in C_{4k}(G)}\varphi_p(G\setminus R,x)$ is the resulting identity.

Load-bearing premise

The proof relies on the defining property that no two cycles of length divisible by four are vertex-disjoint; if a Sachs subgraph could contain two such cycles, the correction term $4\sum_R\varphi_p(G\setminus R,x)$ would not count it correctly and the identity would collapse.

Editorial extensions

If this is right

  • For every $4k$-intercyclic bipartite graph, the permanental polynomial can be written as a linear combination of modified characteristic polynomials, so the computation needs no Pfaffian orientation and no permanent evaluation.
  • Graphs with no cycles of length divisible by four satisfy the stronger equality $\pi(G,x)=\varphi_p(G,x)$, recovering the known characterization as the empty-sum case of the theorem.
  • If the graph has only polynomially many cycles, or only $4k$-cycles of length $O(\log n)$, the formula gives a polynomial-time route to $\pi(G,x)$ because those cycle lists can be generated efficiently.
  • The identity can be used to design families of $4k$-intercyclic bipartite graphs with a prescribed correction polynomial $f(G,x)$; inside each such family, two graphs are cospectral exactly when they are per-cospectral.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the same cancellation argument should apply to the difference between a permanent-style and a determinant-style polynomial whenever every Sachs subgraph contains at most one cycle from a prescribed distinguished family; the coefficient $4$ is specific to cycles of length divisible by four in bipartite graphs.
  • The formula also suggests a hierarchy of corrections for graphs that violate the condition: Sachs subgraphs with three, five, or more distinguished cycles would generate further terms, as the odd-cardinality condition in Lemma 2.2 indicates.
  • The cost of the formula is dominated by listing $4k$-cycles, so the real algorithmic question opened by the paper is how quickly those cycles can be enumerated in large sparse graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The manuscript defines a modified characteristic polynomial φp(G,x) = Σ_{i even} (−1)^{i/2} a_i x^{n−i} for bipartite G and the difference polynomial f(G,x) = π(G,x) − φp(G,x). It then proves (Theorem 2.1) that if G is a 4k-intercyclic bipartite graph, i.e., one in which the deletion of the vertices of any 4k-cycle leaves a C4k-free graph, then π(G,x) = φp(G,x) + 4 Σ_{R∈C4k(G)} φp(G\R,x). The proof uses the Sachs coefficient formulas (1.1), a lemma computing f_i in terms of Sachs subgraphs with an odd number of 4k-cycles, and a one-to-one correspondence between Sachs subgraphs of G containing a fixed cycle R and Sachs subgraphs of G\R. The paper also reformulates the Zhang–Li Pfaffian-orientation theorem, derives Borowiecki's C4k-free characterization as a corollary, gives a worked example, and discusses applications to constructing cospectral/per-cospectral pairs.

Significance. If correct, Theorem 2.1 extends determinant-based computation of the permanental polynomial to a class of bipartite graphs that may contain K2,3 and hence lies outside the Pfaffian-orientation class of Zhang and Li; the example in Section 2 demonstrates this. The proof is elementary and self-contained: the coefficient computation in Lemma 2.2 is sound, the use of 4k-intercyclicity to guarantee that every Sachs subgraph contains at most one 4k-cycle is correct, and the bijection of Sachs subgraphs is valid because G\R is C4k-free. The paper is honest about the complexity of listing 4k-cycles and does not overclaim the scope of the formula relative to prior work.

minor comments (6)
  1. [Section 2, proof of Theorem 2.1] The last sentence of the proof, 'the application of this expression to it leads to π(G\R,x)=φp(G\R,x)', creates an appearance of circularity because the expression is exactly the identity being proved. The intended argument is legitimate, but it should be stated directly: since G\R is C4k-free, Lemma 2.2 gives f(G\R,x)=0, and therefore π(G\R,x)=φp(G\R,x).
  2. [Section 1, proof of Theorem 1.5] The inference 'by Proposition 1.1, G is bipartite' is imprecise: Proposition 1.1 requires both a_k and b_k to vanish for odd k, whereas the argument establishes only b_k=0. The conclusion is nevertheless true because all Sachs contributions to b_k are positive, so b_k=0 for all odd k rules out odd cycles; please add a sentence making this explicit.
  3. [Throughout, especially Theorem 2.1] The notation C4k(G) is overloaded because k is also the variable in '4k-intercyclic'. In the statement of Theorem 2.1, C4k(G) denotes the set of all cycles whose length is divisible by 4, not the set of cycles of one fixed length; please define this explicitly, for instance with a symbol such as C_{4Z}(G).
  4. [Section 2, complexity paragraph] The claim that 'all cycles of length up to log n can be found in polynomial time using the color coding method' is not justified as written: the number of cycles of length O(log n) can be superpolynomial, and color-coding is typically a detection technique rather than an enumeration technique. Please qualify the statement, for example by using output-sensitive listing or by explicitly bounding the number of cycles.
  5. [Section 2, definition of Gp] The sentence 'corresponding to p, we define a class of 4k-intercyclic bipartite graphs Gp = {G | f(G,x)=p}' is imprecise because f is defined for every bipartite graph, not only for 4k-intercyclic ones; the set-builder description should be restricted to 4k-intercyclic bipartite graphs.
  6. [Section 2, Example 2.3] Example 2.3 refers to Figure 1, but the figure is not reproduced in the arXiv text, so the reader cannot independently verify the listed cycles and subgraphs; the final version should include the figure or otherwise specify the graph.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main identity is derived from coefficient formulas, and the subgraph step is independently justified.

full rationale

The central claim (Theorem 2.1) is not assumed anywhere. Lemma 2.2 is obtained directly from the standard Sachs coefficient formulas (1.1): since cycles in bipartite graphs are either 4k-cycles or (4k+2)-cycles, the difference f_i = b_i - (-1)^{i/2}a_i collapses to a sum over Sachs subgraphs containing an odd number of 4k-cycles. The proof of Theorem 2.1 then uses only the defining property of 4k-intercyclic graphs—every Sachs subgraph has at most one 4k-cycle—and a vertex-disjoint-cycle counting argument to derive f(G,x) = 4 Σ_R π(G\R,x). The only sentence that could be misread as self-application is "Since G\R is C4k-free, the application of this expression to it leads to π(G\R, x) = ϕp(G\R, x)"; this is not circular because applying Equation (1.3) to G\R gives π(G\R)=ϕp(G\R)+f(G\R), and Lemma 2.2 gives f(G\R)=0 when G\R has no 4k-cycles. No parameters are fitted, no prediction is a renamed input, and the cited Borowiecki result is independent external work, not a self-citation chain. The proof could be more explicit about the induction or the direct use of Lemma 2.2 at the last line, but the mathematical content is self-contained.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted. The proof uses only the standard Sachs coefficient formulas (Eq. 1.1), the parity classification of cycles in bipartite graphs, and the definitional property of 4k-intercyclic graphs. No new objects are postulated, so the ledger is short.

assumptions (3)
  • standard math Sachs coefficient formulas: a_i = Σ (-1)^{p(U)} 2^{c(U)} and b_i = (-1)^i Σ 2^{c(U)} over Sachs subgraphs.
    Invoked in Eq. 1.1 and used throughout Lemma 2.2; cited to [16] and [14]. The main proof is entirely built on this interpretation.
  • standard math Every cycle in a bipartite graph has even length, so each cycle component of a Sachs subgraph is either a 4k-cycle or a (4k+2)-cycle.
    Used in Lemma 2.2 to classify cycle components and to relate the parity of component count to i/2 plus the number of 4k-cycles.
  • domain assumption C4k-free graphs are vacuously 4k-intercyclic.
    Used when applying the derived expression to G\R; a graph with no 4k-cycles has no two vertex-disjoint 4k-cycles, so the theorem's framework applies.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computing the permanental polynomial of $4k$-intercyclic bipartite graphs." pith.science (2026). https://pith.science/paper/NHZYVSO4

@misc{pith2026241114238,
  author       = {Pith},
  title        = {Pith review of: Computing the permanental polynomial of $4k$-intercyclic bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NHZYVSO4}},
  note         = {Machine review of arXiv:2411.14238}
}
abstract

Let $G$ be a bipartite graph with adjacency matrix $A(G)$. The characteristic polynomial $\phi(G,x)=\det(xI-A(G))$ and the permanental polynomial $\pi(G,x) = \text{per}(xI-A(G))$ are both graph invariants used to distinguish graphs. For bipartite graphs, we define the modified characteristic polynomial, which is obtained by changing the signs of some of the coefficients of $\phi(G,x)$. For $4k$-intercyclic bipartite graphs, i.e., those for which the removal of any $4k$-cycle results in a $C_{4k}$-free graph, we provide an expression for $\pi(G,x)$ in terms of the modified characteristic polynomial of the graph and its subgraphs. Our approach is purely combinatorial in contrast to the Pfaffian orientation method found in the literature to compute the permanental polynomial.

Figures

Figures reproduced from arXiv: 2411.14238 by the authors.

Figure 1
Figure 1. Example of a 4k-intercyclic bipartite graph. In 1985, Borowiecki proved the following. Theorem 1.2. [5] Let G be a bipartite graph with the spectrum {λ1, λ2, . . . , λn}. Then, G is C4k-free if and only if its per-spectrum is {iλ1, iλ2, . . . , iλn}. 1 By inspecting the proof of this theorem, we notice that a bipartite graph G is C4k-free if and only if π(G, x) = ϕp(G, x) (see Corollary 2.4). As a result, the perman… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Manindra Agrawal, Determinant versus permanent, in Proceedings of the 25th Interna- tional Congress of Mathematicians, ICM 2006, volume 3, 985–997 (2006)

    work page 2006

  2. [2]

    Noga Alon, Raphael Yuster, and Uri Zwick, Color-coding, Journal of the ACM (JACM) 42 (1995) 844–856

    work page 1995

  3. [3]

    Aho and John E

    Alfred V. Aho and John E. Hopcroft, The design and analysis of computer algorithms , Pearson Education India (1974)

    work page 1974

  4. [4]

    Etienne Birmel´ e, Rui Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto,Optimal listing of cycles and st-paths in undirected graphs, in Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algo- rithms, 1884–1896 (2013)

    work page 2013

  5. [5]

    Mieczyslaw Borowiecki, On spectrum and per-spectrum of graphs , Publ. Inst. Math.(Beograd) 38 (1985) 31–33

    work page 1985

  6. [6]

    Cvetkovi´ c, Michael Doob, and Horst Sachs,Spectra of graphs: theory and application, Academic press (1979)

    Dragoˇ s M. Cvetkovi´ c, Michael Doob, and Horst Sachs,Spectra of graphs: theory and application, Academic press (1979)

    work page 1979

  7. [7]

    Radu Curticapean, A full complexity dichotomy for immanant families , in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 1770–1783 (2021)

    work page 2021

  8. [8]

    Matthias Dehmer, Frank Emmert-Streib, Bo Hu, Yongtang Shi, Monica Stefu, and Shailesh Tripathi, Highly unique network descriptors based on the roots of the perma- nental polynomial, Information Sciences 408 (2017) 176–181

    work page 2017

Show all 21 references
  1. [9]

    Anna Galluccio and Martin Loebl, On the theory of Pfaffian orientations. I. Perfect matchings and permanents , the Electronic Journal of Combinatorics (1999) R6–R6

    1999

  2. [10]

    Bruno Grenet, An upper bound for the permanent versus determinant problem , Theory of Computing (2011)

    2011

  3. [11]

    42 Bapat et al./ American Journal of Combinatorics 3 (2024) 35–43

    Wei Li, Shunyi Liu, Tingzeng Wu, and Heping Zhang, On the permanental polynomials of graphs, Graph Polynomials (2016) 101–121, Chapman and Hall/CRC. 42 Bapat et al./ American Journal of Combinatorics 3 (2024) 35–43

    2016

  4. [12]

    Shunyi Liu and Jinjun Ren, Enumeration of copermanental graphs , arXiv preprint arXiv:1411.0184 (2014)

    2014 arXiv

  5. [13]

    William McCuaig, P´ olya’s permanent problem, the Electronic Journal of Combinatorics (2004) R79–R79

    2004

  6. [14]

    Rebman, and William Watkins, Permanental polynomials of graphs, Linear Algebra and Its Applications 38 (1981) 273–288

    Russell Merris, Kenneth R. Rebman, and William Watkins, Permanental polynomials of graphs, Linear Algebra and Its Applications 38 (1981) 273–288

    1981

  7. [15]

    Gy¨ orgy P´ olya,Aufgabe 424, Archiv der Mathematik und Physik 20 (1913) 271

    1913

  8. [16]

    Horst Sachs, Beziehungen zwischen den in einem Graphen enthaltenen Kreisen und seinem charakteristischen Polynom , Publ. Math. Debrecen 11 (1964) 119–134

    1964

  9. [17]

    Van Dam and Willem H

    Edwin R. Van Dam and Willem H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra and its applications 373 (2003) 241–272

    2003

  10. [18]

    Valiant, The complexity of computing the permanent , Theoretical computer science 8 (1979) 189–201

    Leslie G. Valiant, The complexity of computing the permanent , Theoretical computer science 8 (1979) 189–201

    1979

  11. [19]

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou, New bounds for matrix multiplication: from alpha to omega , in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3792–3835 (2024)

    2024

  12. [20]

    Weigen Yan and Fuji Zhang, On the permanental polynomials of some graphs , Journal of Mathematical Chemistry 35 (2004) 175–188

    2004

  13. [21]

    Contact Information Ravindra B

    Heping Zhang and Wei Li, Computing the permanental polynomials of bipartite graphs by Pfaffian orientation , Discrete Applied Mathematics 160 (2012) 2069–2074. Contact Information Ravindra B. Bapat Indian Statistical Institute, rbb@isid.ac.in New Delhi 110016, India. https://o...

    2012

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.