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

DOI10.1016/J.EJC.2013.01.008MaRDI QIDQ2444728zbMATH OpenOpenAlexWikidataFDO

Authors Cheng Yeaw Ku, K. B. Wong

Publication date 11 April 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.3878

zbMATH Keywords

alternating sign property of derangement graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

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 decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales (J. of Combin. Theory, Series A 117 (2010) 289--312) regarding the lower and upper bound for the absolute values of these eigenvalues.

Recommendations

• On the spectrum of the derangement graph
• Eigenvalues of the matching derangement graph
• Eigenvalues of the derangement graph
• A note on eigenvalues of the derangement graph.
• Alternating sign property of the perfect matching derangement graph

Cites work

• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Eigenvalues of the derangement graph
• Generating a random permutation with random transpositions
• scientific article; zbMATH DE number 2042680 (Why is no real title available?)
• Intersecting families of permutations
• On the spectrum of the derangement graph
• Shift operators and factorial symmetric functions
• Shifted Jack polynomials, binomial formula, and applications
• Spectra of Cayley graphs
• The factorial Schur function

Cited in

(14)

• On the spectrum of the derangement graph
• Eigenvalues of the matching derangement graph
• The spectrum of eigenvalues for certain subgraphs of the k-point fixing graph
• Alternating sign property of the perfect matching derangement graph
• Eigenvalues of Cayley graphs
• On the spectrum of the perfect matching derangement graph
• Cayley graph on symmetric group generated by elements fixing k points
• On the partition associated to the smallest eigenvalues of the k-point fixing graph
• Erdős-Ko-Rado for perfect matchings
• A note on eigenvalues of the derangement graph.
• The absolute values of the perfect matching derangement graph's eigenvalues almost follow the lexicographic order of partitions
• Largest independent sets of certain regular subgraphs of the derangement graph
• The smallest eigenvalues of the 1-point fixing graph
• Eigenvalues of the derangement graph

This page was built for publication: Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444728)