Discrete Mathematics & Theoretical Computer Science |

- 1 Department of Mathematics [Kansas]
- 2 Department of Mathematics and Statistics [Washburn]

The $\textit{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 spectra for every $n$. We conjecture that $SR(d,n)$ is integral for all $d$ and $n$, and give a geometric construction of almost all eigenvectors in terms of characteristic vectors of lattice permutohedra. For $n \leq \binom{d}{2}$, we give an explicit construction of smallest-weight eigenvectors in terms of rook placements on Ferrers diagrams. The number of these eigenvectors appears to satisfy a Mahonian distribution.

Source: HAL:hal-01229747v1

Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Section: Proceedings

Published on: January 1, 2013

Imported on: November 21, 2016

Keywords: simplicial rook graph,adjacency matrix,Laplacian matrix,spectral graph theory,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 52 times.

This article's PDF has been downloaded 47 times.