Published April 2010 | Version Submitted
Journal Article Open

Eigenvalues of the derangement graph

  • 1. ROR icon National University of Singapore
  • 2. ROR icon California Institute of Technology

Abstract

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.

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.

Attached Files

Submitted - 0803.2901.pdf

Files

0803.2901.pdf

Files (262.5 kB)

Name Size
md5:06449327243e328e22b59ecaec9c7ece
262.5 kB Preview Download

Additional details

Identifiers

Eprint ID
17899
Resolver ID
CaltechAUTHORS:20100408-101413008

Related works

Dates

Created
2010-04-21
Created from EPrint's datestamp field
Updated
2021-11-08
Created from EPrint's last_modified field

Caltech Custom Metadata