Erdős-Ko-Rado for Perfect Matchings

Abstract

A perfect matching of a complete graph $K_{2n}$ is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if $\mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, then $|\mathcal{F}|\le (2(n-1)-1)!!$ and if equality holds, then $\mathcal{F}={\mathcal{F}}_{ij}$ where ${\mathcal{F}}_{ij}$ is the family of all perfect matchings of $K_{2n}$ that contain some fixed edge $ij$. We give a short algebraic proof of this result, resolving a question of Godsil and Meagher. Along the way, we show that if a family $\mathcal{F}$ is non-Hamiltonian, that is, $m\cup m^{\prime }\ncong C_{2n}$ for any $m,m^{\prime }\in \mathcal{F}$, then $|\mathcal{F}|\le (2(n-1)-1)!!$ and this bound is met with equality if and only if $\mathcal{F}={\mathcal{F}}_{ij}$. Our results make ample use of a somewhat understudied symmetric commutative association scheme arising from the Gelfand pair $(S_{2n},S_2\wr S_n)$. We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.