Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2502.09968 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909493170798592 |
|---|---|
| author | Brenner, Sofia Fink, Jiří Hoang, Hung. P. Merino, Arturo Pilaud, Vincent |
| author_facet | Brenner, Sofia Fink, Jiří Hoang, Hung. P. Merino, Arturo Pilaud, Vincent |
| contents | We prove that the minimal size $M(π_n)$ of a maximal matching in the permutahedron $π_n$ is asymptotically $n!/3$. On the one hand, we obtain a lower bound $M(π_n) \ge n! (n-1) / (3n-2)$ by considering $4$-cycles in the permutahedron. On the other hand, we obtain an asymptotical upper bound $M(π_n) \le n!(1/3+o(1))$ by multiple applications of Hall's theorem (similar to the approach of Forcade (1973) for the hypercube) and an exact upper bound $M(π_n) \le n!/3$ by an explicit construction. We also derive bounds on minimum maximal matchings in products of permutahedra. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09968 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum maximal matchings in permutahedra Brenner, Sofia Fink, Jiří Hoang, Hung. P. Merino, Arturo Pilaud, Vincent Combinatorics 05C70, 05C76, 52B11, 52B12 We prove that the minimal size $M(π_n)$ of a maximal matching in the permutahedron $π_n$ is asymptotically $n!/3$. On the one hand, we obtain a lower bound $M(π_n) \ge n! (n-1) / (3n-2)$ by considering $4$-cycles in the permutahedron. On the other hand, we obtain an asymptotical upper bound $M(π_n) \le n!(1/3+o(1))$ by multiple applications of Hall's theorem (similar to the approach of Forcade (1973) for the hypercube) and an exact upper bound $M(π_n) \le n!/3$ by an explicit construction. We also derive bounds on minimum maximal matchings in products of permutahedra. |
| title | Minimum maximal matchings in permutahedra |
| topic | Combinatorics 05C70, 05C76, 52B11, 52B12 |
| url | https://arxiv.org/abs/2502.09968 |