A Caltech Library Service

Eigenvalues of the derangement graph

Ku, Cheng Yeaw and Wales, David B. (2010) Eigenvalues of the derangement graph. Journal of Combinatorial Theory. Series A, 117 (3). pp. 289-312. ISSN 0097-3165.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the Cayley graph on the symmetric group S_n generated by derangements. It is well known that the eigenvalues of this graph are indexed by partitions of n. We investigate how these eigenvalues are determined by the shape of their corresponding partitions. In particular, we show that the sign of an eigenvalue is the parity of the number of cells below the first row of the corresponding Ferrers diagram. We also provide some lower and upper bounds for the absolute values of these eigenvalues.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2009 Elsevier Inc. Received 20 March 2008. Available online 12 October 2009. We would like to thank the anonymous referees for the comments that helped us make several improvements to this paper.
Subject Keywords:Derangement; Cayley graph; Eigenvalue; Symmetric group
Issue or Number:3
Record Number:CaltechAUTHORS:20100408-101413008
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:17899
Deposited By: Tony Diaz
Deposited On:21 Apr 2010 18:57
Last Modified:03 Oct 2019 01:35

Repository Staff Only: item control page