The absolute values of the perfect matching derangement graph's eigenvalues almost follow the lexicographic order of partitions

Abstract

In 2013, Ku and Wong showed that for any partitions $\mu$ and ${\mu }^{\prime }$ of a positive integer $n$ with the same first part $u$ and the lexicographic order $\mu ◃{\mu }^{\prime }$, the eigenvalues ${\xi }_{\mu }$ and ${\xi }_{{\mu }^{\prime }}$ of the derangement graph ${\Gamma }_n$ have the property $|{\xi }_{\mu }|\le |{\xi }_{{\mu }^{\prime }}|$, where the equality holds if and only if $u=3$ and all other parts are less than $3$. In this article, we obtain an analogous conclusion on the eigenvalues of the perfect matching derangement graph ${\mathcal{M}}_{2n}$ of $K_{2n}$ by finding a new recurrence formula for the eigenvalues of ${\mathcal{M}}_{2n}$.

13 pages