On the Spectra of Simplicial Rook Graphs

The simplicial rook graph S R ( d , n ) is the graph whose vertices are the lattice points in the n th dilate of the standard simplex in R d , with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of S R ( 3 , n ) have integral spect...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2015-09, Vol.31 (5), p.1589-1611
Main Authors: Martin, Jeremy L., Wagner, Jennifer D.
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Graph representations
Graphs
Mathematics
Mathematics and Statistics
Matrix
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The simplicial rook graph S R ( d , n ) is the graph whose vertices are the lattice points in the n th dilate of the standard simplex in R d , with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of S R ( 3 , n ) have integral spectrum for every  n . The proof proceeds by calculating an explicit eigenbasis. We conjecture that S R ( d , n ) is integral for all  d and  n , and present evidence in support of this conjecture. For n < 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.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-014-1452-y