Geodesics in a Graph of Perfect Matchings

Roy H. Jennings

Séminaire lotharingien de combinatoire, Tome 74 (2015-2018)

Résumé

Let P_m be the graph on the set of perfect matchings in the complete graph K_2m, where two perfect matchings are connected by an edge if their symmetric difference is a cycle of length four. This paper studies geodesics in P_m. The diameter of P_m, as well as the eccentricity of each vertex, are shown to be m-1. Two proofs are given to show that the number of geodesics between any two antipodes is m^m-2. The first is a direct proof via a recursive formula, and the second is via reduction to the number of minimal factorizations of a given $m$-cycle in the symmetric group S_m. An explicit formula for the number of geodesics between any two matchings in P_m is also given. Let M_m be the graph on the set of non-crossing perfect matchings of 2m labeled points on a circle with the same adjacency condition as in P_m. M_m is an induced subgraph of P_m, and it is shown that M_m has exactly one pair of antipodes having the maximal number m^m-2 of geodesics between them.