The Action of the Lie Algebra $\mathfrak{sl}_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=\binom N2$, and defines on it the diagonal action of the Lie algebra $\mathfrak{gl}_n$, and, after restriction, the action of $\mathfrak{sl}_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{sl}_n$ and a derivation of its spectrum by means of the quadratic Casimir operator of $\mathfrak{gl}_n$ and the Schur--Weyl decomposition.

It is proved that the adjacency operator belongs to the center of the algebra $\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 $\Sym^m(\mathbb C^3)$.