On the spectra of simplicial rook graphs

Abstract

The \emph{simplicial rook graph} $\SR(d,n)$ is the graph whose vertices are the lattice points in the $n$th dilate of the standard simplex in $\mathbb{R}^d$, with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of $\SR(3,n)$ have integral spectrum for every~$n$. The proof proceeds by calculating an explicit eigenbasis. We conjecture that $\SR(d,n)$ is integral for all~$d$ and~$n$, and present evidence in support of this conjecture. For $n<\binom{d}{2}$, the evidence indicates that the smallest eigenvalue of the adjacency matrix is $-n$, and that the corresponding eigenspace has dimension given by the Mahonian numbers, which enumerate permutations by number of inversions.