Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph

Abstract

We give a new recurrence formula for the eigenvalues of the derangement graph. Consequently, we provide a simpler proof of the Alternating Sign Property of the derangement graph. Moreover, we prove that the absolute value of the eigenvalue decreases whenever the corresponding partition with a fixed first part decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales [C.Y. Ku, D.B. Wales, Eigenvalues of the derangement graph, J. Combin. Theory Ser. A 117 (2010) 289-312] regarding the lower and upper bounds for the absolute values of these eigenvalues. © 2013 Elsevier Ltd.