Eigenvalues of the perfect matching derangement graph

• Main Author: Koh, Samuel Zhi Kang
• Other Authors: Bernhard Schmidt
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Science::Mathematics::Discrete mathematics::Graph theory
• Online Access: https://hdl.handle.net/10356/168329
• Institution: Nanyang Technological University

The perfect matching derangement graph M2n is the graph whose vertex set consists of the perfect matchings of the complete graph K2n such that two vertices (perfect matchings) are adjacent if and only if they have no edges in common, i.e. they are "derangement" with respect to each other. The perfect matching derangement graph is a graph in the association scheme associated with the Gelfand pair (S2n;Hn) where Hn is the hyperoctrahedral group of degree n. It is well-known that each eigenvalue of M2n is associated with a partition. Godsil, Meagher, and Lindzey conjectured that the sign of the eigenvalue of the perfect matching derangement graph M2n is alternating with respect to the number of boxes in the first row of the Young diagram representation of a partition. This is known as the alternating sign property for M2n. In this thesis, we settle the conjecture in the affirmative. Our approach is based on a combinatorial formula for some shifted symmetric functions which allows us to obtain a recurrence formula for the eigenvalues of M2n. Another graph related to M2n is the permutation derangement graph. Our method also provides a new recurrence relation concerning the eigenvalues of this graph.