The Action of the Lie Algebra ${\mathfrak{s}\mathfrak{l}}_n$ on Colored Graphs and Multicolored Johnson Graphs

We consider the space of $(n-1)$-colored graphs on a fixed set of $N$ vertices. Each edge position of the complete graph $K_N$ has $n$ possible states: the absence of an edge and $n-1$ colors. This gives a natural identification of the space of such graphs with the tensor power $({\mathbb{C}}^n{)}^{\otimes m}$, where $m=\left(\genfrac{}{}{0px}{}{N}{2}\right)$, and defines on it the diagonal action of the Lie algebra ${\mathfrak{g}\mathfrak{l}}_n$, and, after restriction, the action of ${\mathfrak{s}\mathfrak{l}}_n$. For a fixed profile $\alpha =({\alpha }_0,\dots ,{\alpha }_{n-1})$, we consider the graph $J(m;\alpha )$ whose vertices are colored graphs of this profile and whose adjacency is defined by a single exchange of states in two edge positions. This graph is the transposition graph on the set of words with fixed profile, also known as the \emph{multislice}. The main result is an expression of the adjacency operator in terms of the root operators of ${\mathfrak{s}\mathfrak{l}}_n$ and a derivation of its spectrum by means of the quadratic Casimir operator of ${\mathfrak{g}\mathfrak{l}}_n$ and the Schur–Weyl decomposition. It is proved that the adjacency operator belongs to the center of the algebra ${\text{End}}_{S_m}({\mathcal{C}}_{\alpha })$. The contribution of each spectral block to the multiplicity of the corresponding eigenvalue is described in terms of a Kostka number and the dimension of a Specht module. For $n=2$, one obtains the classical Johnson graph and its known spectrum. As applications, a formula for the valency is established, connectivity is proved, the Hoffman bound for independent sets is obtained, and the three-state case is considered in detail; in this case the natural symmetrized subspace realizes the module ${\text{Sym}}^m({\mathbb{C}}^3)$.