The (n-2,2)-Spectrum of a Graph

Boris Shapiro

arxiv: 2605.17501 · v1 · pith:VASC5TRInew · submitted 2026-05-17 · 🧮 math.CO · math.GR

The (n-2,2)-Spectrum of a Graph

Boris Shapiro This is my paper

Pith reviewed 2026-05-19 22:36 UTC · model grok-4.3

classification 🧮 math.CO math.GR

keywords symmetric group representationsgraph spectrumtree reconstructiontrace polynomialsupport forestsLaplacian operatorgraph isomorphismmoment invariants

0 comments

The pith

A weighted trace polynomial from the (n-2,2) representation reconstructs every tree from its second moment except for one exceptional n.

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

The paper refines the ordinary Laplacian spectrum of a graph by examining the action of a sum of transpositions over edges inside the irreducible representation (n-2,2) of the symmetric group S_n. It supplies an explicit model of the resulting operator on an edge space, derives coordinate formulas, and expresses the trace moments as linear combinations of support-forest counts when the graph is a tree. The central result states that a weighted version of the trace polynomial already determines any tree uniquely from the second moment for every n except one special value, where the fourth moment is enough. This construction supplies a new family of spectral invariants that connect representation theory directly to combinatorial enumeration of subforests.

Core claim

The author establishes an explicit edge-space realization of the operator coming from the (n-2,2) component, shows that its trace moments equal explicit linear combinations of support-forest counts on trees, and proves that the resulting weighted trace polynomial reconstructs every tree from the second moment alone except for a single exceptional value of n where the fourth moment suffices.

What carries the argument

The operator induced by X_G = sum of transpositions over edges, acting in the (n-2,2) representation, whose trace moments are linear combinations of support-forest counts.

If this is right

The second moment of the (n-2,2) operator already supplies enough data to identify trees for all but one n.
The third moment equals a linear combination of three-edge subgraph counts.
The same moment formulas specialize to any tree and give universal expressions in support-forest enumerations.
The weighted trace polynomial yields a concrete invariant that separates trees in the unweighted graph-isomorphism setting.

Where Pith is reading between the lines

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

The same operator model could be tested on small non-tree graphs to see whether the moments still separate isomorphism classes.
Replacing the weight function by other polynomials might produce higher-order invariants that resolve the remaining exceptional n.
The support-forest profile conjecture stated at the end suggests a direct combinatorial route to tree isomorphism that bypasses full representation matrices.

Load-bearing premise

The trace moments of the induced operator equal precisely the stated linear combinations of support-forest counts with no extra dependencies on basis choice or graph-specific normalizations.

What would settle it

Explicit computation of the second-moment weighted trace polynomial for two non-isomorphic trees on all n except the claimed exceptional value, or of the fourth-moment version on that exceptional n, to check whether the polynomials differ.

read the original abstract

We study a representation-theoretic refinement of the ordinary Laplacian spectrum of a graph. Given a graph $G$ on $n$ vertices, one may associate to it the element \[ X_G=\sum_{ij\in E(G)} (ij)\in \C[S_n]. \] The action of $X_G$ in irreducible representations of $S_n$ produces spectral invariants of graphs. The standard representation $(n-1,1)$ recovers the ordinary graph Laplacian spectrum, up to the elementary affine change $X_G=mI-L_G$, where $m=|E(G)|$. The next component, $(n-2,2)$, gives the first representation-theoretic correction. We give an explicit edge-space model for this component, derive a concrete coordinate formula for the induced operator, give a conceptual formula for all trace moments, specialize it to trees as universal linear combinations of support-forest counts, and then compute the first three moments explicitly. The third moment is expressed in terms of three-edge subgraph counts. We also introduce a weighted trace polynomial and prove that this weighted refinement already reconstructs every tree from the second moment, except for a single exceptional value of $n$ where the fourth moment suffices. Finally we discuss the relation with the invariant-theoretic approach of Thi\'ery \cite{Thiery} and formulate a more explicit support-forest-profile conjecture for the unweighted graph isomorphism problem for trees.

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.

Desk Editor's Note private letter to a colleague

Shapiro gives an explicit edge-space model for the (n-2,2) action and shows the resulting weighted trace polynomial reconstructs trees from the second moment in all but one case.

read the letter

The main takeaway is that this paper works out a concrete coordinate formula for the operator coming from the (n-2,2) component of X_G in the group algebra, then turns the trace moments into explicit counts of support forests on trees and proves a weighted polynomial version reconstructs the tree from the second moment except for one exceptional n. That reconstruction claim and the support-forest expression for the moments are the genuinely new pieces relative to the Thiéry reference cited in the abstract. The third-moment formula in terms of three-edge subgraphs is also worked out explicitly. The setup is clean: start from the standard representation that recovers the Laplacian, move to the next irrep, and keep everything combinatorial. The derivations look internally consistent at the level of the abstract, and the moments are tied directly to external counts rather than fitted parameters. The potential soft spot is exactly the one the stress-test flags. The linear combinations of forest counts only stay universal if the coordinate formula for the operator produces basis-independent traces. If the edge-space model introduces a hidden normalization that changes with the choice of basis, the reconstruction would not hold for arbitrary trees once the basis is varied. The abstract presents the model as canonical, but the load-bearing step is the verification that traces remain invariant. Since the full derivations are not in the abstract, that check still needs to be done. This paper is for people working on representation-theoretic graph invariants or on tree isomorphism via moments. A reader who already knows the symmetric-group approach to graphs will get the most out of the explicit formulas and the reconstruction theorem. It is worth sending to peer review because the claims are specific, the combinatorial content is new, and the potential flaw is checkable rather than fatal.

Referee Report

1 major / 1 minor

Summary. The paper studies a representation-theoretic refinement of the ordinary Laplacian spectrum of a graph G on n vertices via the element X_G = sum_{ij in E(G)} (ij) in C[S_n]. The action in the irreducible representation (n-2,2) is modeled explicitly in edge space, yielding a concrete coordinate formula for the induced operator. Conceptual formulas for all trace moments are derived and specialized to trees as universal linear combinations of support-forest counts; the first three moments are computed explicitly, with the third in terms of three-edge subgraph counts. A weighted trace polynomial is introduced and shown to reconstruct every tree from the second moment except for one exceptional n (where the fourth suffices). The work relates this to Thiéry's invariant-theoretic approach and formulates a support-forest-profile conjecture for the unweighted graph isomorphism problem on trees.

Significance. If the derivations hold, the paper supplies new, explicitly computable spectral invariants for graphs with direct combinatorial interpretations in terms of support forests and subgraph counts. The reconstruction theorem for trees via the weighted trace polynomial from low-order moments represents a concrete advance toward distinguishing non-isomorphic trees by spectral data. Credit is due for the explicit edge-space model, the parameter-free combinatorial expressions for moments, and the falsifiable reconstruction claim rather than an existence result.

major comments (1)

[§3] §3 (Explicit edge-space model for the (n-2,2) component): The coordinate formula for the operator is presented as inducing trace moments that are exactly the stated linear combinations of support-forest counts. However, the derivation of basis independence under changes to the edge-space basis (or representation-space coordinates) is not explicitly verified in a way that rules out spurious normalizations. This step is load-bearing for the central reconstruction claim, because any residual basis dependence would make the moments non-universal and invalidate the theorem that the weighted trace polynomial reconstructs all trees from the second moment.

minor comments (1)

[Final section] The discussion of the relation to Thiéry's work in the final section would benefit from a short table or explicit comparison of the two sets of invariants on a small example tree.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on the manuscript. Their positive assessment of the explicit edge-space model and the reconstruction theorem is appreciated. We address the single major comment below and will revise the manuscript to strengthen the presentation of basis independence.

read point-by-point responses

Referee: [§3] §3 (Explicit edge-space model for the (n-2,2) component): The coordinate formula for the operator is presented as inducing trace moments that are exactly the stated linear combinations of support-forest counts. However, the derivation of basis independence under changes to the edge-space basis (or representation-space coordinates) is not explicitly verified in a way that rules out spurious normalizations. This step is load-bearing for the central reconstruction claim, because any residual basis dependence would make the moments non-universal and invalidate the theorem that the weighted trace polynomial reconstructs all trees from the second moment.

Authors: We agree that an explicit verification of basis independence strengthens the exposition, particularly since the reconstruction theorem relies on the universality of the moments. The edge-space model is obtained by realizing the action of X_G in the (n-2,2) representation via the standard Young orthogonal basis (or an equivalent coordinate system for the Specht module). The trace moments are then the traces of powers of this operator. While this construction is representation-theoretically basis-independent by definition, we acknowledge that the original text does not include a direct check ruling out coordinate artifacts. In the revised manuscript we will insert a short paragraph in §3 showing that the moments equal the inner product of the character of (n-2,2) with the class function induced by X_G^k; this quantity is manifestly independent of any choice of basis or normalization in the edge space. The combinatorial expansion into support-forest counts then inherits the same invariance. This clarification will be added without altering any statements or proofs. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit model yields external combinatorial counts; reconstruction is a proved theorem

full rationale

The derivation begins with the explicit edge-space model for the (n-2,2) representation, produces a concrete coordinate formula for the induced operator, and then extracts trace moments as universal linear combinations of support-forest counts (external graph invariants). These counts are not defined in terms of the moments or the polynomial; the weighted trace polynomial reconstruction for trees is stated and proved as a theorem rather than obtained by fitting or renaming. No load-bearing step reduces to a self-citation, ansatz smuggled via citation, or parameter fitted to the target quantity. The paper remains self-contained against the combinatorial benchmarks it invokes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard decomposition of the group algebra of S_n into irreducibles labeled by partitions and on the combinatorial definition of support forests; no free parameters, ad-hoc axioms, or new postulated entities are introduced.

axioms (1)

standard math The irreducible representations of S_n are labeled by partitions of n, with (n-1,1) the standard representation and (n-2,2) the next one in dominance order.
This is the background representation theory invoked to define the spectral invariants X_G acting in each irrep.

pith-pipeline@v0.9.0 · 5773 in / 1358 out tokens · 62688 ms · 2026-05-19T22:36:23.171624+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We give an explicit edge-space model for this component, derive a concrete coordinate formula for the induced operator, give a conceptual formula for all trace moments, specialize it to trees as universal linear combinations of support-forest counts
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the weighted refinement already reconstructs every tree from the second moment, except for a single exceptional value of n where the fourth moment suffices

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

10 extracted references · 10 canonical work pages

[1]

Diaconis,Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes– Monograph Series, vol

P. Diaconis,Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes– Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988

work page 1988
[2]

Godsil and G

C. Godsil and G. Royle,Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer, New York, 2001

work page 2001
[3]

C. D. Godsil and B. D. McKay,Constructing cospectral graphs, Aequationes Math.25(1982), 257–268

work page 1982
[4]

W. H. Haemers and E. Spence,Enumeration of cospectral graphs, European J. Combin.25(2004), no. 2, 199–211

work page 2004
[5]

B. D. McKay and A. Piperno,Practical graph isomorphism, II, J. Symbolic Comput.60(2014), 94–112

work page 2014
[6]

B. E. Sagan,The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer, New York, 2001

work page 2001
[7]

A. J. Schwenk,Almost all trees are cospectral, in: F. Harary (ed.),New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 275–307

work page 1973
[8]

N. M. Thi´ ery,Algebraic invariants of graphs; a study based on computer exploration, ACM SIGSAM Bull.34(2000), no. 3, 9–20

work page 2000
[9]

E. R. van Dam and W. H. Haemers,Which graphs are determined by their spectrum?, Linear Algebra Appl.373(2003), 241–272

work page 2003
[10]

Whitney,Congruent graphs and the connectivity of graphs, Amer

H. Whitney,Congruent graphs and the connectivity of graphs, Amer. J. Math.54(1932), no. 1, 150–168. Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden Email address:shapiro@math.su.se 12

work page 1932

[1] [1]

Diaconis,Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes– Monograph Series, vol

P. Diaconis,Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes– Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988

work page 1988

[2] [2]

Godsil and G

C. Godsil and G. Royle,Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer, New York, 2001

work page 2001

[3] [3]

C. D. Godsil and B. D. McKay,Constructing cospectral graphs, Aequationes Math.25(1982), 257–268

work page 1982

[4] [4]

W. H. Haemers and E. Spence,Enumeration of cospectral graphs, European J. Combin.25(2004), no. 2, 199–211

work page 2004

[5] [5]

B. D. McKay and A. Piperno,Practical graph isomorphism, II, J. Symbolic Comput.60(2014), 94–112

work page 2014

[6] [6]

B. E. Sagan,The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer, New York, 2001

work page 2001

[7] [7]

A. J. Schwenk,Almost all trees are cospectral, in: F. Harary (ed.),New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 275–307

work page 1973

[8] [8]

N. M. Thi´ ery,Algebraic invariants of graphs; a study based on computer exploration, ACM SIGSAM Bull.34(2000), no. 3, 9–20

work page 2000

[9] [9]

E. R. van Dam and W. H. Haemers,Which graphs are determined by their spectrum?, Linear Algebra Appl.373(2003), 241–272

work page 2003

[10] [10]

Whitney,Congruent graphs and the connectivity of graphs, Amer

H. Whitney,Congruent graphs and the connectivity of graphs, Amer. J. Math.54(1932), no. 1, 150–168. Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden Email address:shapiro@math.su.se 12

work page 1932