pith. sign in

arxiv: 2604.04489 · v1 · submitted 2026-04-06 · 🧮 math.CO

Immanantal polynomials of the linear combination matrices of graphs

Xiangshuai Dong , Tingzeng Wu This is my paper

Pith reviewed 2026-05-10 20:23 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5015A15
keywords immanantal polynomialslinear combination matricesdegree matrixadjacency matrixcombinatorial interpretationvertex orientationimmanantsgraph matrices
0
0 comments X

The pith

Immanantal polynomials of linear combinations of a graph's degree and adjacency matrices have coefficients that count oriented vertex structures, with bounds that solve Merris's open problem.

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

The paper examines immanantal polynomials of matrices formed as arbitrary linear combinations of the degree matrix D and adjacency matrix A of an undirected graph. Using a vertex-orientation technique that works for general graphs, it supplies an explicit combinatorial reading of every coefficient in these polynomials and determines tight bounds on their magnitudes. The bounds recover earlier coefficient results of Chan and Lam that were limited to trees and to bipartite graphs. The same development answers an open question of Merris about the immanantal coefficients. The authors further generalize the classical Frobenius-König theorem and Laplace expansion to immanants, then apply the generalizations to locate roots and to obtain explicit formulas for the first six coefficients of the hook immanantal polynomial on several standard graph matrices.

Core claim

For any undirected graph the immanantal polynomial of a linear combination matrix formed from its degree and adjacency matrices admits a combinatorial interpretation of its coefficients via vertex orientations; the coefficients are bounded in size by expressions involving the number of such orientations, the bounds encompass prior results on trees and bipartite graphs, and the framework solves the open problem posed by Merris on these polynomials.

What carries the argument

vertex-orientation technique that assigns combinatorial meaning to the coefficients of immanantal polynomials of linear combination matrices

If this is right

  • The coefficient bounds recover the earlier results of Chan and Lam for trees and for bipartite graphs.
  • The open problem posed by Merris receives a complete solution.
  • The star degree of any graph is a lower bound on the multiplicity of a certain root of its immanantal polynomial.
  • Two regular graphs share the same hook immanantal polynomial if and only if they satisfy a stated necessary and sufficient condition on their parameters.
  • Explicit formulas are obtained for the first six coefficients of the hook immanantal polynomial for several families of graph matrices.

Where Pith is reading between the lines

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

  • The vertex-orientation counting may yield polynomial-time procedures for evaluating certain immanants on graphs of bounded tree-width.
  • The generalized expansion theorems could be applied to immanants of other linear combinations such as the Laplacian or normalized adjacency matrix.
  • The root-multiplicity bound suggests a way to locate eigenvalues of immanantal polynomials for graphs with known star-degree sequences.

Load-bearing premise

The vertex-orientation technique and the generalized Frobenius-König and Laplace expansions apply without additional restrictions to arbitrary undirected graphs and to any chosen linear combination of the degree and adjacency matrices.

What would settle it

A specific graph G, scalars alpha and beta, and an immanant index lambda for which the number of vertex-oriented substructures counted by the formula differs from the actual coefficient of the immanantal polynomial of alpha D(G) + beta A(G), or for which a coefficient violates one of the stated bounds.

read the original abstract

In this paper, we focus on the study of immanantal polynomials for linear combination matrices composed of the degree matrix and adjacency matrix of a graph. First, applying the concept of vertex orientation for general graphs, we provide a combinatorial interpretation of the coefficients of the immanantal polynomials for the linear combination matrices of graphs, and we also characterize the bounds of these coefficients. These bounds implicitly encompass the existing results of Chan and Lam on trees and bipartite graphs. Furthermore, we give a solution to the open problem posed by Merris. Second, we characterize the first six coefficients of the hook immanantal polynomial. And the necessary and sufficient condition under which the linear combination matrices of two regular graphs have the same hook immanantal polynomial is proved. Third, we generalize the Frobenius--K\"onig theorem and the Laplace expansion theorem to immanants. Using these two theorems, we show that the star degree of a graph is always a lower bound for the multiplicity of a certain root of the immanantal polynomial of its linear combination matrix. Finally, we derive formulas for the first six coefficients of the hook immanantal polynomial for several important graph matrices.

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

3 major / 2 minor

Summary. The paper studies immanantal polynomials of linear combination matrices M = αD + βA of undirected graphs. It claims a combinatorial interpretation of all coefficients via a vertex-orientation technique on general graphs, derives bounds on those coefficients that subsume prior results for trees and bipartite graphs, solves an open problem of Merris, characterizes the first six coefficients of the hook immanantal polynomial together with a necessary-and-sufficient condition for two regular graphs to share the same hook immanantal polynomial, generalizes the Frobenius–König and Laplace expansion theorems to immanants, proves that the star degree of a graph lower-bounds the multiplicity of a certain root, and supplies explicit formulas for the first six hook-immanant coefficients of several standard graph matrices.

Significance. If the vertex-orientation interpretation and the generalized expansion theorems are valid for arbitrary α, β and general graphs, the work would constitute a substantial advance in algebraic graph theory by extending combinatorial descriptions of immanants beyond the special cases treated by Chan–Lam and by resolving Merris’ open problem. The explicit coefficient formulas and the star-degree multiplicity bound would also supply concrete, checkable predictions for further study.

major comments (3)
  1. [combinatorial interpretation section (first main result)] The central combinatorial interpretation (first part of the abstract and the corresponding section) relies on vertex orientation to assign signs and count objects whose weighted products recover the immanant expansion of det_χ(M). However, the diagonal entries of M arise solely from the degree matrix D and carry no incident edges; the manuscript does not specify how these diagonal contributions are encoded in the orientation rule or whether they introduce additional sign factors or zero patterns when α ≠ 0. This detail is load-bearing for the claim that the interpretation holds for arbitrary linear combinations on general graphs.
  2. [bounds and Merris problem section] The claimed solution to Merris’ open problem and the bounds that “implicitly encompass” Chan–Lam results are stated to follow from the same orientation technique. If the diagonal-handling issue above is unresolved, both the solution and the generality of the bounds rest on an incomplete foundation; a concrete counter-example or explicit rule for the diagonal terms is required before these claims can be accepted.
  3. [generalized theorems and multiplicity bound] The generalization of the Frobenius–König theorem and Laplace expansion (third part) is used to prove the star-degree multiplicity lower bound. The proof sketch in the abstract does not indicate whether the generalized statements impose extra hypotheses on the immanant character χ or on the support of M that would restrict applicability to the linear-combination matrices under study.
minor comments (2)
  1. [abstract and introduction] Notation for the linear combination matrix (αD + βA or similar) should be fixed once at the beginning and used consistently; the abstract employs both “linear combination matrices” and “its linear combination matrix” without a single defining equation.
  2. [bounds section] The statement that the bounds “implicitly encompass” prior results would be strengthened by an explicit corollary or remark showing how the new bounds specialize to the Chan–Lam statements for trees and bipartite graphs.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below with clarifications and indicate planned revisions to improve the manuscript.

read point-by-point responses

  1. Referee: [combinatorial interpretation section (first main result)] The central combinatorial interpretation (first part of the abstract and the corresponding section) relies on vertex orientation to assign signs and count objects whose weighted products recover the immanant expansion of det_χ(M). However, the diagonal entries of M arise solely from the degree matrix D and carry no incident edges; the manuscript does not specify how these diagonal contributions are encoded in the orientation rule or whether they introduce additional sign factors or zero patterns when α ≠ 0. This detail is load-bearing for the claim that the interpretation holds for arbitrary linear combinations on general graphs.

    Authors: We acknowledge that an explicit description of the diagonal handling would strengthen the presentation. In the vertex-orientation framework, each diagonal contribution α deg(v) is treated as a fixed positive weight factor attached to vertex v with no associated edge or orientation choice, hence carrying a positive sign and introducing no additional zeros or sign changes. This is consistent with the matrix support and holds for arbitrary α, β. We will add a dedicated paragraph with a small illustrative example (e.g., K_2 with α=1, β=1) to the combinatorial interpretation section. revision: yes

  2. Referee: [bounds and Merris problem section] The claimed solution to Merris’ open problem and the bounds that “implicitly encompass” Chan–Lam results are stated to follow from the same orientation technique. If the diagonal-handling issue above is unresolved, both the solution and the generality of the bounds rest on an incomplete foundation; a concrete counter-example or explicit rule for the diagonal terms is required before these claims can be accepted.

    Authors: With the explicit diagonal rule provided in the revision, the orientation technique applies uniformly, so the coefficient bounds and the solution to Merris’ open problem remain valid for general linear combinations. We will include a concrete verification example for a small non-tree graph and restate the bounds derivation with the diagonal rule made explicit. revision: yes

  3. Referee: [generalized theorems and multiplicity bound] The generalization of the Frobenius–König theorem and Laplace expansion (third part) is used to prove the star-degree multiplicity lower bound. The proof sketch in the abstract does not indicate whether the generalized statements impose extra hypotheses on the immanant character χ or on the support of M that would restrict applicability to the linear-combination matrices under study.

    Authors: The generalized statements are formulated for arbitrary characters χ and any matrix whose support matches that of a linear combination matrix (symmetric, non-negative off-diagonals). No further hypotheses are required. The abstract is only a summary; the full proofs already specify the conditions, which are satisfied here. We will add a short remark after each theorem and a brief sentence in the abstract to make the scope explicit. revision: partial

Circularity Check

0 steps flagged

No circularity: combinatorial interpretations and theorem generalizations stand independently.

full rationale

The paper applies vertex-orientation to interpret coefficients of immanantal polynomials for linear combination matrices M = αD + βA, generalizes the Frobenius-König and Laplace theorems to immanants, derives bounds that extend prior results on trees and bipartite graphs, and solves Merris' open problem. These steps use explicit combinatorial constructions and algebraic extensions whose validity does not reduce to redefinition of the target quantities or to fitted parameters extracted from the same data. No self-citation chains, ansatzes smuggled via prior work, or uniqueness theorems imported from the authors themselves appear as load-bearing premises. The derivation chain remains self-contained against external combinatorial and matrix-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard definition of the immanant via irreducible characters of the symmetric group and on ordinary graph-theoretic notions of degree and adjacency matrices; no new free parameters or postulated entities are introduced.

axioms (2)
  • standard math Immanants are defined as the sum over permutations weighted by the character of an irreducible representation of the symmetric group.
    This is the classical definition invoked throughout the work.
  • domain assumption Graphs under consideration are finite, undirected, and simple unless otherwise stated.
    Standard assumption in the graph-theory literature on adjacency and degree matrices.

pith-pipeline@v0.9.0 · 5502 in / 1415 out tokens · 50479 ms · 2026-05-10T20:23:44.863145+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Agrawal, Determinant versus permanent, European Mathematical Society, 2007

    M. Agrawal, Determinant versus permanent, European Mathematical Society, 2007. 3

    work page 2007

  2. [2]

    Bolognini, P

    D. Bolognini, P. Sentinelli, Immanant varieties,Linear Algebra Appl.682 (2024) 164–190. 2

    work page 2024

  3. [3]

    Botti, R

    P. Botti, R. Merris, Almost all trees share a complete set of immanantal polynomials, J. Graph Theory17 (1993) 467–476. 2

    work page 1993

  4. [4]

    Brouwer, W.H

    A.E. Brouwer, W.H. Haemers, Spectra of graphs,Springer, 2011. 2, 3

    work page 2011

  5. [5]

    B ¨urgisser, The computational complexity of immanants,SIAM J

    P. B ¨urgisser, The computational complexity of immanants,SIAM J. Computing30 (2000) 1023–1040. 2

    work page 2000

  6. [6]

    Cash, Immanants and immanantal polynomials of chemical graphs,J

    G. Cash, Immanants and immanantal polynomials of chemical graphs,J. Chem. In- form. Comput. Sci.43 (2003) 1942–1946. 2

    work page 2003

  7. [7]

    O. Chan, T. Lam, Immanant inequalities for Laplacians of trees,SIAM J. Matrix Anal. Appl.21 (1999) 129–144. 3, 4 26

    work page 1999

  8. [8]

    O. Chan, T. Lam, Hook immanantal inequalities for Laplacians of trees,Linear Alge- bra Appl.261 (1997) 23–47. 3

    work page 1997

  9. [9]

    O. Chan, T. Lam, Vertex orientations and immanants of bipartite graphs,Available on Semantic Scholar, 1997. 4, 8, 11

    work page 1997

  10. [10]

    O. Chan, T. Lam, Immanant of Laplacian matrix of trees, manuscript, 1997. 3, 5, 11

    work page 1997

  11. [11]

    Cvetkovi ´c, P

    D.M. Cvetkovi ´c, P. Rowlinson, S. Simi´c, An introduction to the theory of graph spec- tra,Cambridge: Cambridge university press., 2010. 3

    work page 2010

  12. [12]

    de Guise, D

    H. de Guise, D. Spivak, J. Kulp, and I. Dhand, D-functions and immanants of unitary matrices and submatrices,J. Phys. A: Math. Theor.49 (2016) 09LT01 (12pp). 2

    work page 2016

  13. [13]

    Diaconis and S

    P. Diaconis and S. N. Evans, Immanants and finite point processes,J. Combinat. Theory, Ser. A91 (2000) 305–321. 2

    work page 2000

  14. [14]

    X. Dong, T. Wu, H. Lai, Some immanantal inequalities and equalities for linear com- bination matrices of (di)graphs, subbmitted. 4

    work page

  15. [15]

    Faria, Multiplicity of integer roots of polynomials of graphs,Linear Algebra Appl

    I. Faria, Multiplicity of integer roots of polynomials of graphs,Linear Algebra Appl. 229 (1995) 15–35. 20

    work page 1995

  16. [16]

    Faria, Permanental roots and the star degree of a graph,Linear Algebra Appl.64 (1985) 255–265

    I. Faria, Permanental roots and the star degree of a graph,Linear Algebra Appl.64 (1985) 255–265. 20

    work page 1985

  17. [17]

    Glynn, The permanent of a square matrix,European J

    D.G. Glynn, The permanent of a square matrix,European J. Combin.31 (2010) 1887–

    work page 2010

  18. [18]

    Godsil, Algebraic combinatorics,Chapman and Hall, New York, 1993

    C.D. Godsil, Algebraic combinatorics,Chapman and Hall, New York, 1993. 3

    work page 1993

  19. [19]

    Goulden, D

    I. Goulden, D. Jackson, Immanants of combinatorial matrices,J. Algebra148 (1992) 305–324. 2

    work page 1992

  20. [20]

    Haiman, Hecke algebra characters and immanant conjectures,J

    M. Haiman, Hecke algebra characters and immanant conjectures,J. Amer. Math. Soc. 6 (1993) 569–595. 2

    work page 1993

  21. [21]

    James, A

    C. James, A. Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics, Addison-Wesley, Reading, Mass., 1981. 5

    work page 1981

  22. [22]

    C. Li, A. Zaharia, Induced operators on symmetry classes of tensors,Trans. Am. Math. Soc.354 (2002) 807–836. 2

    work page 2002

  23. [23]

    S. Liu, H. Zhang, On the characterizing properties of the permanental polynomials of graphs,Linear Algebra Appl.438 (2013) 157–172. 23

    work page 2013

  24. [24]

    W. Li, S. Liu, T. Wu, H. Zhang, On the permanental polynomials of graphs, in: Graph Polynomials, Y . Shi, M. Dehmer, X. Li, I. Gutman (Eds.),CRC Press, Boca Raton, 2017, 101–122. 3

    work page 2017

  25. [25]

    Littlewood, The theory of group characters, 2nd ed., Oxford Univ

    D.E. Littlewood, The theory of group characters, 2nd ed., Oxford Univ. Press, Lon- don, 1950. 2

    work page 1950

  26. [26]

    Marcus, H

    M. Marcus, H. Minc, Generalized matrix functions,Trans. Am. Math. Soc.116 (1965) 316–329. 2

    work page 1965

  27. [27]

    Marcus, P.J

    M. Marcus, P.J. Nikolai, Inequalities for some monotone matrix functions,Canad. J. Math.21 (1969) 485-194. 4

    work page 1969

  28. [28]

    Merris, Single-hook characters and Hamiltonian circuits,Linear Multilinear Alge- bra14 (1983) 21–35

    R. Merris, Single-hook characters and Hamiltonian circuits,Linear Multilinear Alge- bra14 (1983) 21–35. 4

    work page 1983

  29. [29]

    Merris, The second immanantal polynomial and the centroid of a graph,SIAM J

    R. Merris, The second immanantal polynomial and the centroid of a graph,SIAM J. Algebraic Discrete Methods7 (1986) 484–503. 2, 3, 10, 21

    work page 1986

  30. [30]

    Merris, Immanantal invariants of graphs,Linear Algebra Appl.401 (2005) 67–75

    R. Merris, Immanantal invariants of graphs,Linear Algebra Appl.401 (2005) 67–75. 15, 16, 20 27

    work page 2005

  31. [31]

    Merris, K.R

    R. Merris, K.R. Rebman, W. Watkins, Permanental polynomials of graphs,Linear Algebra Appl.38 (1981) 273–288. 10

    work page 1981

  32. [32]

    Minc, Permanents, Addision-Wesley, London, 1978

    H. Minc, Permanents, Addision-Wesley, London, 1978. 3

    work page 1978

  33. [33]

    Mowshowitz, The characteristic polynomial of a graph,J

    A. Mowshowitz, The characteristic polynomial of a graph,J. Combinator. Theory, Ser. B12 (1972) 177–193. 3

    work page 1972

  34. [34]

    Rhoades, M

    B. Rhoades, M. Skandera, Kazhdan–Lusztig immanants and products of matrix mi- nors,J. Algebra304 (2006) 793–811. 2

    work page 2006

  35. [35]

    Sagan, The symmetric group: representations, combinatorial algorithms, and sym- metric functions,Wadsworth, 1991

    B. Sagan, The symmetric group: representations, combinatorial algorithms, and sym- metric functions,Wadsworth, 1991. 5

    work page 1991

  36. [36]

    Schur, ¨Uber endliche Gruppen undHermitesche Formen,Math

    I. Schur, ¨Uber endliche Gruppen undHermitesche Formen,Math. Z.1 (1918), 184–

    work page 1918

  37. [37]

    R. P. Stanley, J. R. Stembridge, On immanants of Jacobi–Trudi matrices and permu- tations with restricted position,J. Combinator. Theory, Ser. A62 (1993) 261–279. 2

    work page 1993

  38. [38]

    Stembridge, Some conjectures for immanant,Can

    J. Stembridge, Some conjectures for immanant,Can. J. Math.44 (1992) 1079–1099. 2

    work page 1992

  39. [39]

    Van Mieghem, Graph spectra for complex networks, Cambridge university press,

    P. Van Mieghem, Graph spectra for complex networks, Cambridge university press,

    work page

  40. [40]

    T. Wu, Y . Yu, L. Feng, X. Gao, On the second immanantal polynomials of graphs, Discrete Math.347 (2024) 114105. 3, 20

    work page 2024

  41. [41]

    G. Yu, H. Qu, The coefficients of the immanantal polynomial,Appl. Math. Comput. 339 (2018) 38–44. 2, 4 School ofMathematicalSciences, XiamenUniversity, Xiamen, Fujian361005, China Email address:a3566293588@163.com School ofMathematics andStatistics, QinghaiMinzuUniversity, Xining, Qinghai810007, China Email address:mathtzwu@163.com

    work page 2018