Minimum maximal matchings in permutahedra

Abstract

We prove that the minimal size $M(\ddot{I}{€}_n)$ of a maximal matching in the permutahedron $\ddot{I}{€}_n$ is asymptotically $n!/3$. On the one hand, we obtain a lower bound $M(\ddot{I}{€}_n)\ge n!(n-1)/(3n-2)$ by considering $4$-cycles in the permutahedron. On the other hand, we obtain an asymptotical upper bound $M(\ddot{I}{€}_n)\le n!(1/3+o(1))$ by multiple applications of Hall's theorem (similar to the approach of Forcade (1973) for the hypercube) and an exact upper bound $M(\ddot{I}{€}_n)\le n!/3$ by an explicit construction. We also derive bounds on minimum maximal matchings in products of permutahedra.

11 pages, 2 figures