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) x 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 Cayleygraph. 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.

Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap / Cesi, Filippo. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - 16:1(2009).

Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap

CESI, Filippo
2009

Abstract

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) x 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 Cayleygraph. 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.
2009
01 Pubblicazione su rivista::01a Articolo in rivista
Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap / Cesi, Filippo. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - 16:1(2009).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/66648
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact