EUVIMEDOpdag EUVIMED
Crossref

Minimum Maximal Matchings in Permutahedra

Sofia Brenner, Jiří Fink, Hung Hoang, Arturo Merino, Vincent Pilaud

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.

AbstractBibliografiske oplysningerCiteRelated studies

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}
}
Start for free →