Séminaire Lotharingien de Combinatoire, 93B.155 (2025), 12 pp.
Arnau Padrol and Germain Poullot
New Criteria for Polytope Indecomposability and New Rays of the Submodular Cone
Abstract.
A polytope is indecomposable if it cannot be expressed (non-trivially) as a Minkowski sum of other polytopes. Certifying indecomposability is difficult, and several criteria have been developed since Gale introduced the concept in 1954. Our first contribution is a new indecomposability criterion that encompasses most of the previous techniques. The major new ingredient is the introduction of the (extended) graph of edge-length dependencies, which has diverse applications in the study of deformation cones of polytopes.
Our main motivation is to provide new indecomposable deformed permutahedra that are not matroid polytopes. In 1970, Edmonds proposed the problem of characterizing the extreme rays of the submodular cone, that is, indecomposable deformed permutahedra. Matroid polytopes from connected matroids give one such family of polytopes. We present a new infinite disjoint family via truncations of certain graphical zonotopes.
This way, we obtain 2⌊(n-1)/2⌋ new indecomposable deformations of the n-permutahedron Πn ⊆ Rn.
Received: November 15, 2024.
Accepted: February 15, 2025.
Final version: April 1, 2025.