2014/09/06 by Nathan Lindzey, Lindzey, Nathan
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Finite Group Theory Research #Graph Theory and Algorithms #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1409.2057
openalex publication_date 2014/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A perfect matching of a complete graph K2n is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if F is family of intersecting perfect matchings of K2n, then |F| ≤ (2(n-1) - 1)!! and if equality holds, then F = Fij where Fij is the family of all perfect matchings of K2n 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 F is non-Hamiltonian, that is, m ∪ m' \not ≅ C2n for any m,m' ∈ F, then |F| ≤ (2(n-1) - 1)!! and this bound is met with equality if and only if F = Fij. Our results make ample use of a somewhat understudied symmetric commutative association scheme arising from the Gelfand pair (S2n,S2 \wr Sn). We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.