On Ray of the Deformation Cone of Permutahedra

Abstract

Deformed permutahedra were originally introduced by Edmonds in 1970, under the name of polymatroids, and rediscovered in 2009 under the name of generalized permutahedra by Postnikov. This family of polytopes appeares naturally in many areas of mathematics, such as algebraic combinatorics, optimization, game theory, statistics, mathematical economics, etc. While it is known that the set of deformed permutahedra can be parameterized by the cone of sub- modular functions, the structure of the submodular cone is far from being well understood. In particular determining the rays of Defess(Pn+1) remains an open problem since the 1970s. We present our recent findings ( [1]) regarding this problem, namely we identify that the median hypersimplex as the generator of a Sn+1-invariant ray in Defess(Pn+1)