Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl arXiv EuDML
In a recent paper Gunnells, Scott and Walden have determined the complete spectrum of the Schreier graph on the symmetric group corresponding to the Young subgroup $S_{n-2}\times S_2$ and generated by initial reversals. In particular they find that the first nonzero eigenvalue, or spectral gap, of the Laplacian is always 1, and report that "empirical evidence" suggests that this also holds for the corresponding Cayley graph. We provide a simple proof of this last assertion, based on the decomposition of the Laplacian of Cayley graphs, into a direct sum of irreducible representation matrices of the symmetric group.
Filippo Cesi. Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/267
@article{10_37236_267,
author = {Filippo Cesi},
title = {Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/267},
zbl = {1185.05079},
url = {http://geodesic.mathdoc.fr/articles/10.37236/267/}
}
Cité par Sources :