Minimum Maximal Matchings in Permutahedra

Abstract

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