Eigenvalues of the perfect matching derangement graph
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 othe...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis-Doctor of Philosophy |
| Language: | English |
| Published: |
Nanyang Technological University
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/168329 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|