Transposition Cayley Spectra and Subgraph Counts
Abstract
Let G be a finite simple graph on the vertex set [n], and let Γ(G) be the Cayley graph of the symmetric group Sn generated by the transpositions corresponding to the edges of G. We study the inverse spectral problem for the assignment G↦ Γ(G) through the group-algebra operator AG=∑{i,j}∈ E(G)(ij) and its regular spectral moments Mk(G)=tr(AGk). The moments admit two all-order forms: a universal support expansion in non-induced subgraph counts of G, and a representation-theoretic expansion over the irreducible representations of Sn. We compute the first nontrivial moments through order six. In particular, the fourth moment already contains the Coxeter triangle relation and determines the signed local invariant 6NK3(G)−NP3(G), rather than NP3(G) alone. Consequently, for triangle-free graphs the spectrum determines the second moment of the degree sequence. We also give a simplified sixth-moment formula for triangle-free graphs, showing that in this class the spectrum determines 5NK1,3(G)+2NP4(G)+12NC4(G). Further structural consequences include bipartiteness and spectral symmetry of Γ(G), a precise connectedness test, and the identification of the standard irreducible component with the shifted graph Laplacian mI−LG.
Related
- Orthogonality graphs of real Cayley-Dickson algebras. Part II: The subgraph on pairs of basis elements
- Normal approximation for subgraph counts in random intersection graphs: the case of cliques
- Tests of graph homogeneity, subgraph counts, and quasirandomness
- Exact Realization of Edge and Induced Three-Vertex Subgraph Counts
- Fluctuations of subgraph counts in exponential random graphs
BibTeX
@misc{shapiro2026transposition,
title = {{Transposition Cayley Spectra and Subgraph Counts}},
author = {Boris Shapiro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14373},
eprint = {2610.14373},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14373},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Transposition Cayley Spectra and Subgraph Counts
AU - Boris Shapiro
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14373
UR - https://arxiv.org/abs/2610.14373
AB - Let G be a finite simple graph on the vertex set [n], and let Γ(G) be the Cayley graph of the symmetric group S_n generated by the transpositions corresponding to the edges of G. We study the inverse spectral problem for the assignment G↦ Γ(G) through the group-algebra operator A_G=∑_{i,j}∈ E(G)(ij) and its regular spectral moments M_k(G)=tr(A_G^k). The moments admit two all-order forms: a universal support expansion in non-induced subgraph counts of G, and a representation-theoretic expansion over the irreducible representations of S_n. We compute the first nontrivial moments through order six. In particular, the fourth moment already contains the Coxeter triangle relation and determines the signed local invariant 6N_K_3(G)−N_P_3(G), rather than N_P_3(G) alone. Consequently, for triangle-free graphs the spectrum determines the second moment of the degree sequence. We also give a simplified sixth-moment formula for triangle-free graphs, showing that in this class the spectrum determines 5N_K_1,3(G)+2N_P_4(G)+12N_C_4(G). Further structural consequences include bipartiteness and spectral symmetry of Γ(G), a precise connectedness test, and the identification of the standard irreducible component with the shifted graph Laplacian mI−L_G.
ER -