Germain Poullot: An inductive construction of the submodular cone

Abstract: A deformed permutahedron (a.k.a submodular function, generalized permutahedron, polymatroid) is a polytope whose edges have direction e_i - e_j for some i ≠ j. The collection of all deformed permutahedra in R^n forms a cone, called the submodular cone. We present an inductive construction of the submodular cone, using an operation called the GP-sum: from two deformed permutahedra in R^n, we create (bijectively) one deformed permutahedra in dimension R^{n+1}.

Empowered by this construction, we create new rays of the submodular cone, i.e. new Minkowski indecomposable deformed permutahedra. We improve the bounds on the number of these rays: the n-th submodular cone has at least 2^{2^n} rays. We also state bounds (upper and lower) on f-vector of the submodular cone, on the total number of its faces, and on the number of faces which are simplicial cones.