View publication
| Title | Minimum Maximal Matchings in Permutahedra |
| Authors | Sofia Brenner, Jiří Fink, Hung P. Hoang, Arturo Merino, Vincent Pilaud |
| Publication date | June 2026 |
| Abstract |
We prove that the minimal size M(Pi) of a maximal matching in the permutahedron Pi is asymptotically n!/3. On the one hand, we obtain a lower bound 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 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 M(Pi n) \le n!/3 by an explicit construction. We also derive bounds on minimum maximal matchings in products of permutahedra. |
| Pages | P2.50 |
| Volume | 33 |
| Journal name | Electronic Journal of Combinatorics |