Transposition Cayley Spectra and Subgraph Counts

Abstract

Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(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\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{i,j\}\in E(G)}(ij)$ and its regular spectral moments $M_k(G)=\operatorname{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 $\Gamma(G)$, a precise connectedness test, and the identification of the standard irreducible component with the shifted graph Laplacian $mI-L_G$.