Minimum Maximal Matchings in Permutahedra
The Electronic Journal of Combinatorics · 2026-06-05 · 33 (2)
DOI: 10.37236/14145 ↗At a glance
Journal article in The Electronic Journal of Combinatorics, published online on 2026-06-05. Written by Sofia Brenner and 4 co-authors.
Abstract (original language)
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.
Cite
APA
Brenner, S., Fink, J., Hoang, H., Merino, A., & Pilaud, V. (2026). Minimum Maximal Matchings in Permutahedra. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14145
Vancouver
Brenner S, Fink J, Hoang H, Merino A, Pilaud V. Minimum Maximal Matchings in Permutahedra. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14145
BibTeX
@article{Brenner2026,
author = {Brenner, Sofia and Fink, Jiří and Hoang, Hung and Merino, Arturo and Pilaud, Vincent},
title = {Minimum Maximal Matchings in Permutahedra},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/14145}
}
EUVIMED