Faces of generalized permutohedra

Take a convex shape — any convex shape — and ask how many faces it has. Not just the obvious ones, the flat sides and the corners, but all of them, counted by dimension, arranged into a single polynomial that encodes the whole geometry. For an enormous and surprising family of polytopes — shapes that emerge in optimization theory, phylogenetics, and algebraic combinatorics — Postnikov, Reiner, and Williams found a way to read that polynomial directly from the combinatorics of trees and permutations. No geometry required. That's what this paper delivers. Start with the concrete picture. A permutohedron in n-dimensional space is the convex hull of the n-factorial points you get by permuting the coordinates of a vector with strictly increasing entries. That polytope lives in an n-minus-one-dimensional hyperplane, and the braid arrangement — the family of hyperplanes where coordinate i equals coordinate j — cuts that space into exactly n-factorial chambers, one for each permutation. The permutohedron is the prototype of what comes next. A generalized permutohedron is what you get when you deform that prototype while preserving the directions of its edge vectors, allowing some edges to collapse but keeping the overall combinatorial shadow of the braid arrangement. The reduced normal fan of the polytope must be refined by the braid arrangement fan — that's the geometric condition. Equivalently, a generalized permutohedron is a Minkowski summand of some dilated permutohedron, which is the algebraic condition. These two characterizations say the same thing from different angles, and both are useful. The family is wide. Permutohedra themselves sit at one end. Zonotopes — Minkowski sums of line segments in the directions of e-i minus e-j — are another subfamily; the graphic zonotopes associated with graphs G are generalized permutohedra, and they're simple exactly when every biconnected component of G is a complete graph. Then there are nestohedra: Minkowski sums of coordinate simplices indexed by a combinatorial structure called a building set. A building set B is a collection of subsets of the ground set satisfying a connectivity condition, and the nestohedron P-B is the Minkowski sum over sets I in B of the simplex spanned by the standard basis vectors indexed by I. Every nestohedron is a generalized permutohedron, it's always simple, and its dual simplicial complex is the nested-set complex of B. Graph-associahedra are the nestohedra where the building set comes from connected subgraphs of a graph G: the path graph gives the classical associahedron, the complete graph recovers the permutohedron, and the star graph gives the stellohedron. Each of these lives inside the same framework. Now, how do you count the faces? The paper organizes that counting into three nested encodings. The f-vector is the raw tally: f-i of P counts the number of i-dimensional faces. The h-vector is a linear change of basis — you take the f-polynomial, substitute one-over-t for t, multiply by t to the d-th power, and that equals the h-polynomial evaluated at t-plus-one. That sounds like bookkeeping, but it has concrete meaning: each entry h-i counts the number of vertices of the simple polytope whose outdegree in a natural orientation of the edge graph equals i. Because of that interpretation, the h-vector entries are nonnegative, and they satisfy Dehn-Sommerville symmetry: h-i equals h-(d-minus-i). The h-polynomial is palindromic. When you have a palindromic polynomial, you can compress it further. Every palindromic polynomial of degree d has a unique expansion in terms of t to the i times one plus t to the (d-minus-2i), where i runs from zero to the floor of d over two. The coefficients in that expansion form the gamma-vector. Gal conjectured that for any flag simple polytope — one where no missing face has size smaller than two, which you can picture as a complex where every minimal missing piece is an edge — the gamma-vector entries are all nonnegative. That conjecture is the animating problem the paper sets out to resolve for a large class of polytopes. The main theorem connecting geometry to combinatorics is Theorem 4.2, and it is elegant. To each vertex v of a simple generalized permutohedron, attach a tree poset Q-v — a partial order on the integer labels one through n, shaped like a tree. A descent of Q-v is a covering relation where the top element has a smaller integer label than the bottom: a place where the labeling goes downward in value. The theorem says the h-polynomial of the polytope equals the sum, over all vertices v, of t raised to the number of descents of Q-v. The full face-count data, encoded in the h-polynomial, is the descent-generating function of these tree posets. Discrete combinatorics recovers polyhedral geometry. For the usual permutohedron, this reduces to something classical. The vertex posets are just total orders — ordinary permutations — and descents of a permutation are positions i where w of i is greater than w of (i-plus-one). So Theorem 4.2 recovers the Eulerian polynomial exactly: h of the permutohedron equals the sum over permutations w of t to the descent number of w. The generalized construction replaces permutations with orderings constrained by a tree, and the Eulerian polynomial becomes a generalized Eulerian polynomial for that tree. The hexagonal prism, analyzed in the paper as a graphic zonotope with twelve vertices, illustrates this: the descent-generating sum over its vertex posets evaluates to one plus five t plus five t squared plus t cubed. And a monotonicity bound follows from Stanley's subdivision theorem: since the braid fan refines the normal fan of any generalized permutohedron, the h-polynomial of any simple generalized permutohedron is bounded coefficientwise from above by the Eulerian polynomial of the full permutohedron. The graph-associahedra come with their own algebraic machinery. The paper derives explicit generating functions and recurrences for h-polynomials across entire families of graphs, including all Dynkin diagrams of finite and affine types. Narayana numbers — which count lattice paths by the number of peaks, and which appear in Simon Newcomb's problem about sorting shuffled sequences — emerge as the coefficients for the path graph associahedra. The connection to Newcomb's problem is not decorative: it reflects the fact that the same descent statistics on permutations that count faces of the associahedron also govern the probability structure of certain card-shuffling sequences. Now for Gal's conjecture. The paper proves it for all chordal nestohedra: those where the building set is chordal, meaning every cycle of length four or more in the associated graph has a chord. Theorem 11.6 and Corollary 11.13 together establish that for any connected chordal building set B, the gamma-polynomial of the nestohedron P-B is a genuine peak-generating function over a natural set of B-permutations. The key objects are B-permutations, which are in bijection with vertices of P-B, and their peak statistics. A peak of a permutation w is a position i where w of (i-minus-one) is less than w of i, which is greater than w of (i-plus-one) — a local maximum. The formula: the gamma-polynomial equals the sum over a specific class of B-permutations — those with no double or final descent — of t raised to the number of peaks minus one. Each gamma-r counts B-permutations with exactly r-plus-one peaks and no double or final descent. The mechanism is B-hop equivalence. The Shapiro-Wan-Getu method, developed here into B-hop operations on B-permutations, partitions all B-permutations into equivalence classes. If a permutation has p peaks and n-minus-2p-plus-one intermediary entries — positions that are neither peaks nor the fixed boundary values — then its hop class has size two to the power of (n-minus-2p-plus-one), and the descent-generating function of that class equals t to the p times one plus t to the (n-minus-2p-plus-one). Each class has a unique representative with no double or final descent. Summing across classes gives the gamma formula, and since the class sizes are genuine counting numbers, the gamma entries are nonnegative. Gal's conjecture holds for all chordal nestohedra. Step back and look at the appendix. Three apparently different ways to deform a simple polytope — moving vertex positions while preserving edge directions, scaling edge lengths, and translating facet hyperplanes — turn out to be equivalent descriptions of the same phenomenon. Theorem 15.3 characterizes all of them as the polytopes whose normal fan is refined by the original fan, which is exactly the Minkowski-summand condition. Theorem 15.5 establishes linear isomorphisms between the three deformation cones, with dimensions equal to the number of facets minus the polytope dimension. This ties directly to toric geometry and to the braid-arrangement characterization of generalized permutohedra. What the paper ultimately shows is that face-counting — which sounds like bookkeeping — is a window into deep structural symmetry. A shape's combinatorial invariants, from the raw f-vector down to the compressed gamma-vector, are encoded in descent statistics and peak statistics of discrete objects attached to its vertices. The geometry and the combinatorics are not just analogous. They are, in a precise technical sense, the same thing. This lecture was created by ennepō. Go to https://ennepo.ai to Discover, Create and Follow the latest research in your field. Read when you can. Listen when you want to.