Faces of Generalized Permutohedra

Generalized permutahedra are a family of polytopes with a rich combinatorial structure and strong connections to optimization. We prove that they are the universal family of polyhedra with a certain Hopf algebraic structure. Their antipode is remarkably simple: the antipode of a polytope is the alternating sum of its faces. Our construction provides a unifying framework to organize numerous combinatorial structures, including graphs, matroids, posets, set partitions, linear g...

Every regular polytope has the remarkable property that it inherits all symmetries of each of its facets. This property distinguishes a natural class of polytopes which are called hereditary. Regular polytopes are by definition hereditary, but the other polytopes in this class are interesting, have possible applications in modeling of structures, and have not been previously investigated. This paper establishes the basic theory of hereditary polytopes, focussing on the analys...

The goal of this paper is to show that valuation theory and Hopf theory are compatible on the class of generalized permutahedra. We prove that the Hopf structure $\mathbf{GP}^+$ on these polyhedra descends, modulo the inclusion-exclusion relations, to an indicator Hopf monoid $\mathbb{I}(\mathbf{GP}^+)$ of generalized permutahedra that is isomorphic to the Hopf monoid of weighted ordered set partitions. This quotient Hopf monoid $\mathbb{I}(\mathbf{GP}^+)$ is cofree. It is th...

The harmonic polytope and the bipermutahedron are two related polytopes which arose in Ardila, Denham, and Huh's work on the Lagrangian geometry of matroids. We study the bipermutahedron. We show that its faces are in bijection with the vertex-labeled and edge-labeled multigraphs with no isolated vertices; the generating function for its f-vector is a simple evaluation of the three variable Rogers--Ramanujan function. We show that the h-polynomial of the bipermutahedral fan...

Neighborly cubical polytopes are known as the cubical analogues of the cyclic polytopes. Using the short cubical $h$-vectors of cubical polytopes (introduced by Adin), we derive an explicit formula for the face numbers of the neighborly cubical polytopes. These face numbers form a unimodal sequence.

In this short note we consider generalized associahedra of type D_n. We prove that these simple flag polytopes are not nestohedra for n > 3, but the statement of Gal's conjecture holds for them.

This paper focuses on determining the volumes of permutation polytopes associated to cyclic groups, dihedral groups, groups of automorphisms of tree graphs, and Frobenius groups. We do this through the use of triangulations and the calculation of Ehrhart polynomials. We also present results on the theta body hierarchy of various permutation polytopes.

Foata and Sch\"{u}tzenberger gave an expansion for the Eulerian polynomial $A_n(t)$ in terms of the basis $\{t^j(1+t)^{n-1-2j}\}$ for the space of polynomials $f(t)$ satisfying $f(t)=t^{n-1}f(1/t)$. We generalize this result in two ways. First, we provide an analogue for the graded representation of the symmetric group $\mathfrak{S}_n$ on the cohomology of the permutohedral variety. Then we give expansions $h$-polynomials of polytopes obtained by cutting permutohedra with hyp...

It is well-known that the Eulerian polynomials, which count permutations in $S_n$ by their number of descents, give the $h$-polynomial/$h$-vector of the simple polytopes known as permutohedra, the convex hull of the $S_n$-orbit for a generic weight in the weight lattice of $S_n$. Therefore the Eulerian polynomials give the Betti numbers for certain smooth toric varieties associated with the permutohedra. In this paper we derive recurrences for the $h$-vectors of a family of...

The polytope subalgebra of deformations of a zonotope can be endowed with the structure of a module over the Tits algebra of the corresponding hyperplane arrangement. We explore this construction and find relations between statistics on (signed) permutations and the module structure in the case of (type B) generalized permutahedra. In type B, the module structure surprisingly reveals that any family of generators (via signed Minkowski sums) for generalized permutahedra of typ...