We prove that the minimal size M(Π<inf>n</inf> ) of a maximal matching in the permutahedron Π<inf>n</inf> is asymptotically n!/3. On the one hand, we obtain a lower bound M(Π<inf>n</inf> ) ≥ n!(n − 1)/(3n − 2) by considering 4-cycles in the permutahedron. On the other hand, we obtain an asymptotical upper bound M(Π<inf>n</inf> ) ≥ 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(Π<inf>n</inf> ) ≥ n!/3 by an explicit construction. We also derive bounds on minimum maximal matchings in products of permutahedra.
