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

Abstract

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{}{}{0ex}{}{N}{2}\right)$, 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_α)$. 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)$.

18 pages