EUVIMEDEUVIMED entdecken
Crossref

Minimum Maximal Matchings in Permutahedra

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

The Electronic Journal of Combinatorics · 05.06.2026 · 33 (2)

DOI: 10.37236/14145 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 05.06.2026. Verfasst von Sofia Brenner und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

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}
}
Kostenlos starten →