Erdős-Ko-Rado for Perfect Matchings
Lindzey, Nathan
Original · EN
A perfect matching of a complete graph K₂ₙ 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 K₂ₙ, then |F| ≤ (2(n-1) - 1)!! and if equality holds, then F = Fij where Fij is the family of all perfect matchings of K₂ₙ 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' C₂ₙ 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 (S₂ₙ,S₂ Sₙ). We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.