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.
Fields of Study & Subjects
graph theory and CDMA systems
Bayesian Methods and Mixture Models
Wireless Communication Networks Research
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 2
- Publication date
- 5 June 2026
- Language
- EN