Faces of Generalized Permutohedra

Alex Postnikov ^{1}, Victor Reiner ^{2}, Lauren Williams ^{3}

Received: May 5, 2007 Revised: June 16, 2008

Communicated by Günter Ziegler

Abstract. The aim of the paper is to calculate face numbers of simple generalized permutohedra, and study their f-, h- and γvectors. These polytopes include permutohedra, associahedra, graphassociahedra, simple graphic zonotopes, nestohedra, and other interesting polytopes.

We give several explicit formulas for h-vectors and γ-vectors involving descent statistics. This includes a combinatorial interpretation for γ-vectors of a large class of generalized permutohedra which are flag simple polytopes, and confirms for them Gal’s conjecture on the nonnegativity of γ-vectors.

We calculate explicit generating functions and formulae for hpolynomials of various families of graph-associahedra, including those corresponding to all Dynkin diagrams of finite and affine types. We also discuss relations with Narayana numbers and with Simon Newcomb’s problem.

We give (and conjecture) upper and lower bounds for f-, h-, and γ-vectors within several classes of generalized permutohedra.

An appendix discusses the equivalence of various notions of deformations of simple polytopes.

2000 Mathematics Subject Classification: Primary 05Axx. Keywords and Phrases: polytopes, face numbers, permutohedra.

1supported in part by NSF CAREER Award DMS-0504629 2supported in part by NSF Grant DMS-0601010 3supported in part by an NSF Postdoctoral Fellowship

Documenta Mathematica 13 (2008) 207–273

208 Alex Postnikov, Victor Reiner, Lauren Williams Contents 1 Introduction 208 2 Face numbers 211 3 Generalized permutohedra and the cone-preposet dictio-

nary 215 4 Simple generalized permutohedra 222 5 The case of zonotopes 224 6 Building sets and nestohedra 226 7 Flag nestohedra 231 8 B-trees and B-permutations 233 9 Chordal building sets and their nestohedra 236 10 Examples of nestohedra 239 11 γ-vectors of nestohedra 242 12 Graph-associahedra for single branched trees 252 13 Graph-associahedra for path-like graphs 260 14 Bounds and monotonicity for face numbers of graph-

associahedra 263 15 Appendix: Deformations of a simple polytope 266 1 Introduction Generalized permutohedra are a very well-behaved class of convex polytopes studied in [Post’05], as generalizations of the classical permutohedra, associahedra, cyclohedra, etc. That work explored their wonderful properties from the point of view of valuations such as volumes, mixed volumes, and number of lattice points. This paper focuses on their further good behavior with respect to face enumeration in the case when they are simple polytopes. Simple generalized permutohedra include as an important subclass (the duals of) the nested set complexes considered by DeConcini and Procesi in their work on wonderful compactifications of hyperplane arrangements; see [DP’95, FS’05]. In particular, when the arrangement comes from a Coxeter system, one obtains interesting flag simple polytopes studied by Davis, Januszkiewicz, and

Documenta Mathematica 13 (2008) 207–273

Scott [DJS’03]. These polytopes can be combinatorially described in terms of the corresponding Coxeter graph. Carr and Devadoss [CD’06] studied these polytopes for arbitrary graphs and called them graph-associahedra. We mention here two other recent papers in which generalized permutohedra have appeared. Morton, Pachter, Shiu, Sturmfels, and Wienand [M–W’06] considered generalized permutohedra from the point of view of rank tests on ordinal data in statistics. The normal fans of generalized permutohedra are what they called submodular rank tests. Agnarsson and Morris [AM’06] investigated closely the 1-skeleton (vertices and edges) in the special case where generalized permutohedra are Minkowski sums of standard simplices.

Let us formulate several results of the present paper. A few definitions are required. A connected building set B on [n] := {1, …, n} is a collection of nonempty subsets in [n] such that

1. if I, J ∈ B and I ∩ J ≠ ∅, then I ∪ J ∈ B,

2. B contains all singletons {i} and the whole set [n];

see Definition 6.1. An interesting subclass of graphical building sets B(G) comes from connected graphs G on [n]. The building set B(G) contains all nonempty subsets of vertices I ⊆ [n] such that the induced graph G|_{I} is connected. The nestohedron P_{B} is defined (see Definition 6.3) as the Minkowski sum

P_{B} = ∑_{I∈B} Δ_{I}

of the coordinate simplices Δ_{I} := ConvexHull(e_{i} | i ∈ I), where the e_{i} are the endpoints of the coordinate vectors in ℝ^{n}. According to [Post’05, Theorem 7.4] and [FS’05, Theorem 3.14] (see Theorem 6.5 below), the nestohedron P_{B} is a simple polytope which is dual to a simplicial nested set complex. For a graphical building set B(G), the nestohedron P_{B(G)} is called the graph-associahedron. In the case when G is the n-path, P_{B(G)} is the usual associahedron; and in the case when G = K_{n} is the complete graph, P_{B(G)} is the usual permutohedron. Recall that the f-vector and the h-vector of a simple d-dimensional polytope P are (f_{0}, f_{1}, …, f_{d}) and (h_{0}, h_{1}, …, h_{d}), where f_{i} is the number of i-dimensional faces of P and ∑ h_{i} (t + 1)^{i} = ∑ f_{i} t^{i}. It is known that the h-vector of a simple polytope is positive and symmetric. Since the h-vector is symmetric, one can define another vector called the γ-vector (γ_{1}, γ_{2}, …, γ_{⌊d/2⌋}) by the relation

∑_{i=0}^{d} h_{i} t^{i} = ∑_{i=0}^{⌊ \frac{d}{2} ⌋} γ_{i} t^{i}(1 + t)^{d−2i}.

A simplicial complex Δ is called a flag complex (or a clique complex) if its simplices are cliques (i.e., subsets of vertices with complete induced subgraphs) of some graph (1-skeleton of Δ). Say that a simple polytope is flag if its dual simplicial complex is flag.

Gal conjectured [Gal’05] that the γ-vector has nonnegative entries for any flag simple polytope. Let us that say a connected building set B is chordal if, for any of the sets I = {i_{1} < ⋯ < i_{r}} in B, all subsets {i_{s}, i_{s+1}, …, i_{r}} also belong to B; see Definition 9.2. By Proposition 9.4, graphical chordal building sets B(G) are exactly building sets coming from chordal graphs. By Proposition 9.7, all nestohedra P_{B} for chordal building sets are flag simple polytopes. So Gal’s conjecture applies to this class of chordal nestohedra, which include graphassociahedra for chordal graphs and, in particular, for trees. For a building set B on [n], define (see Definition 8.7) the set 𝔖_{n}(B) of Bpermutations as the set of permutations w of size n such that, for any i = 1, …, n, there exists I ∈ B such that I ⊆ {w(1), …, w(i)}, and I contains both w(i) and max{w(1), w(2), …, w(i)}. It turns out that B-permutations are in bijection with vertices of the nestohedron P_{B}; see Proposition 8.10. Let des(w) = #{i | w(i) > w(i + 1)} denote the number of descents in a permutation w. Let 𝔖̂_{n} be the subset of permutations w of size n without two consecutive descents and without final descent, i.e., there is no i ∈ [n − 1] such that w(i) > w(i + 1) > w(i + 2), assuming that w(n + 1) = 0.

Theorem 1.1. (Corollary 9.6 and Theorem 11.6) Let B be a connected chordal building set on [n]. Then the h-vector of the nestohedron P_{B} is given by

∑_{i} h_{i} t^{i} = ∑_{w∈𝔖_{n}(B)} t^{des(w)},

and the γ-vector of the nestohedron P_{B} is given by

∑_{i} γ_{i} t^{i} = ∑_{w∈𝔖_{n}(B)∩𝔖̂_{n}} t^{des(w)}.

This result shows that Gal’s conjecture is true for chordal nestohedra.

The paper is structured as follows. Sections 2, 3, and 4 give some background on face numbers and general results about generalized permutohedra. More specifically, Section 2 reviews polytopes, cones, fans, and gives basic terminology of face enumeration for polytopes (f-vectors), simple polytopes (h-vectors), and flag simple polytopes (γ-vectors). Section 3 reviews the definition of generalized permutohedra, and recasts this definition equivalently in terms of their normal fans. It then sets up the dictionary between preposets, and cones and fans coming from the braid arrangement. In particular, one finds that each vertex in a generalized associahedron has associated to it a poset that describes its normal cone. This is used to characterize when the polytope is simple, namely when the associated posets have Hasse diagrams which are trees. In Section 4 this leads to a combinatorial formula for the h-vector in terms of descent statistics on these tree-posets. The remainder of the paper deals with subclasses of simple generalized permutohedra. Section 5 dispenses quickly with the very restrictive class of simple zonotopal generalized permutohedra, namely the simple graphic zonotopes.

Sections 6 through 11 deal with the very interesting class of nestohedra, culminating with a proof of Gal’s conjecture for chordal nestohedra. More specifically, Section 6 discusses nestohedra P_{B} coming from a building set B, where the posets associated to each vertex are rooted trees. These include graphassociahedra. Section 7 characterizes the flag nestohedra. Section 8 discusses B-trees and B-permutations. These trees and permutations are in bijection with each other and with vertices of the nestohedron P_{B}. The h-polynomial of a nestohedron is the descent-generating function for Btrees. Then Section 9 introduces the class of chordal building sets and shows that h-polynomials of their nestohedra are descent-generating functions for Bpermutations. Section 10 illustrates these formulas for h-polynomials by several examples: the classical permutohedron and associahedron, the cyclohedron, the stellohedron (the graph-associahedron for the star graph), and the Stanley-Pitman polytope. Section 11 gives a combinatorial formula for the γ-vector of all chordal nestohedra as a descent-generating function (or peak-generating function) for a subset of B-permutations. This result implies Gal’s nonnegativity conjecture for this class of polytopes. The warm-up example here is the classical permutohedron, and the section concludes with the examples of the associahedron and cyclohedron. Sections 12 through 14 give some graph-associahedra calculations as well as conjectures. Specifically, Section 12 calculates the generating functions for fpolynomials of the graph-associahedra for all trees with one branching point and discusses a relation with Simon Newcomb’s problem. Section 13 deals with graphs that are formed by a path with two small fixed graphs attached to the ends. It turns out that the h-vectors of graph-associahedra for such pathlike graphs can be expressed in terms of h-vectors of classical associahedra. The section includes explicit formulas for graph-associahedra for the Dynkin diagrams of all finite and affine Coxeter groups. Section 14 gives some bounds and monotonicity conjectures for face numbers of generalized permutohedra. The paper ends with an Appendix which clarifies the equivalence between various kinds of deformations of a simple polytope.

Acknowledgments: The authors thank Federico Ardila, Richard Ehrenborg, Ira Gessel, Sangwook Kim, Jason Morton, Margaret Readdy, Anne Shiu, Richard Stanley, John Stembridge, Bernd Sturmfels, Oliver Wienand, and Andrei Zelevinsky for helpful conversations.

2 Face numbers

This section recalls some standard definitions from the theory of convex polytopes and formulates Gal’s extension of the Charney-Davis conjecture.

2.1 Polytopes, cones, and fans

A convex polytope P is the convex hull of a finite collection of points in ℝ^{n}. The dimension of a polytope (or any other subset in ℝ^{n}) is the dimension of its affine span. A polyhedral cone in ℝ^{n} is a subset defined by a conjunction of weak inequalities of the form λ(x) ≥ 0 for linear forms λ ∈ (ℝ^{n})^{∗}. A face of a polyhedral cone is a subset of the cone given by replacing some of the inequalities λ(x) ≥ 0 by the equalities λ(x) = 0. Two polyhedral cones σ_{1}, σ_{2} intersect properly if their intersection is a face of each. A complete fan of cones F in ℝ^{n} is a collection of distinct nonempty polyhedral cones covering ℝ^{n} such that (1) every nonempty face of a cone in F is also a cone in F, and (2) any two cones in F intersect properly. Cones in a fan F are also called faces of F. Note that fans can be alternatively defined only in terms of their top dimensional faces, as collections of distinct pairwise properly intersecting ndimensional cones covering ℝ^{n}. A face F of a convex polytope P is the set of points in P where some linear functional λ ∈ (ℝ^{n})^{∗} achieves its maximum on P, i.e.,

F = {x ∈ P | λ(x) = max{λ(y) | y ∈ P }}.

Faces that consist of a single point are called vertices and 1-dimensional faces are called edges of P. Given any convex polytope P in ℝ^{n} and a face F of P, the normal cone to P at F, denoted N_{F} (P), is the subset of linear functionals λ ∈ (ℝ^{n})^{∗} whose maximum on P is achieved on all of the points in the face F, i.e.,

N_{F} (P) := {λ ∈ (ℝ^{n})^{∗} | λ(x) = max{λ(y) | y ∈ P } for all x ∈ F }.

Then N_{F} (P) is a polyhedral cone in (ℝ^{n})^{∗}, and the collection of all such cones N_{F} (P) as one ranges through all faces F of P gives a complete fan in (ℝ^{n})^{∗} called the normal fan N (P). A fan of the form N (P) for some polytope P is called a polytopal fan. The combinatorial structure of faces of P can be encoded by the lattice of faces of P ordered via inclusion. This structure is also encoded by the normal fan N (P). Indeed, the map F ↦ N_{F} (P) is an inclusion-reversing bijection between the faces of P and the faces of N (P). A cone is called pointed if it contains no lines (1-dimensional linear subspaces), or equivalently, if it can be defined by a conjunction of inequalities λ_{i}(x) ≥ 0 in which the λ_{i} span (ℝ^{n})^{∗}. A fan is called pointed if all its faces are pointed. If the polytope P ⊂ ℝ^{n} is full-dimensional, that is dim P = n, then the normal fan N (P) is pointed. For polytopes P of lower dimension d, define the (n − d)- dimensional subspace P^{⊥} ⊂ (ℝ^{n})^{∗} of linear functionals that are constant on P. Then all cones in the normal fan N (P) contain the subspace P^{⊥}. Thus N (P) can be reduced to a pointed fan in the space (ℝ^{n})^{∗}/P^{⊥}.

A polytope P is called simple if any vertex of P is incident to exactly d = dim P edges. A cone is called simplicial if it can be given by a conjunction of linear inequalities λ_{i}(x) ≥ 0 and linear equations μ_{j}(x) = 0 where the covectors λ_{i} and μ_{j} form a basis in (ℝ^{n})^{∗}. A fan is called simplicial if all its faces are simplicial. Clearly, simplicial cones and fans are pointed. A convex polytope P ⊂ ℝ^{n} is simple if and only if its (reduced) normal fan N (P)/P^{⊥} is simplicial. The dual simplicial complex Δ_{P} of a simple polytope P is the simplicial complex obtained by intersecting the (reduced) normal fan N (P)/P^{⊥} with the unit sphere. Note that i-simplices of Δ_{P} correspond to faces of P of codimension i + 1.

2.2 f-vectors and h-vectors

For a d-dimensional polytope P, the face number f_{i}(P) is the number of idimensional faces of P. The vector (f_{0}(P), …, f_{d}(P)) is called the f-vector, and the polynomial f_{P} (t) = ∑_{i=0}^{d} f_{i}(P) t^{i} is called the f-polynomial of P. Similarly, for a d-dimensional fan F, f_{i}(F) is the number of i-dimensional faces of F, and f_{F}(t) = ∑_{i=0}^{d} f_{i}(F) t^{i}. Note that face numbers of a polytope P and its (reduced) normal cone F = N (P)/P^{⊥} are related as f_{i}(P) = f_{d−i}(F), or equivalently, f_{P} (t) = t^{d} f_{F}(t^{−1}). We will most often deal with the case where P is a simple polytope, or equivalently, when F is a simplicial fan. In these situations, there is a more compact encoding of the face numbers f_{i}(P) or f_{i}(F) by smaller nonnegative integers. One defines the h-vector (h_{0}(P), …, h_{d}(P)) and h-polynomial h_{P} (t) = ∑_{i=0}^{d} h_{i}(P) t^{i} uniquely by the relation

f_{P} (t) = h_{P} (t + 1), or equivalently, f_{j}(P) = ∑_{i} \binom{i}{j}h_{i}(P), j = 0, …, d.

(1)

For a simplicial fan F, the h-vector (h_{0}(F), …, h_{d}(F)) and the h-polynomial h_{F}(t) = ∑_{i=0}^{d} h_{i}(F) t^{i} are defined by the relation t^{d} f_{F}(t^{−1}) = h_{F}(t + 1), or equivalently, f_{j}(F) = ∑_{i} \binom{i}{d−j}h_{i}(F), for j = 0, …, d. Thus the h-vector of a simple polytope coincides with the h-vector of its normal fan. The nonnegativity of h_{i}(P) for a simple polytope P comes from its well-known combinatorial interpretation [Zieg’94, §8.2] in terms of the 1-skeleton of the simple polytope P. Let us extend this interpretation to arbitrary complete simplicial fans. For a simplicial fan F in ℝ^{d}, construct the graph G_{F} with vertices corresponding to d-dimensional cones and edges corresponding to (d−1)-dimensional cones of F, where two vertices of G_{F} are connected by an edge whenever the corresponding cones share a (d − 1)-dimensional face. Pick a vector g ∈ ℝ^{d} that does not belong to any (d − 1)-dimensional face of F and orient edges of G_{F}, as follows. Orient an edge {σ_{1}, σ_{2}} corresponding to two cones σ_{1} and σ_{2} in F as (σ_{1}, σ_{2}) if the vector g points from σ_{1} to σ_{2} (in a small neighborhood of the common face of these cones).

Proposition 2.1. For a simplicial fan F, the ith entry h_{i}(F) of its h-vector equals the number of vertices with outdegree i in the oriented graph G_{F}. These numbers satisfy the Dehn-Sommerville symmetry: h_{i}(F) = h_{d−i}(F).

Corollary 2.2. (cf. [Zieg’94, §8.2]) Let P ∈ ℝ^{n} be a simple polytope. Pick a generic linear form λ ∈ (ℝ^{n})^{∗}. Let G_{P} be the 1-skeleton of P with edges directed so that λ increases on each edge. Then h_{i}(P) is the number of vertices in G_{P} of outdegree i.

Proof of Proposition 2.1. The graph G_{F} has a unique vertex of outdegree 0. Indeed, this is the vertex corresponding to the cone in F containing the vector g. For any face F of F (of an arbitrary dimension), let G_{F}(F) be the induced subgraph on the set of d-dimensional cones of F containing F as a face. Then G_{F}(F) ≃ G_{F′}, where F′ is the link of the face F in the fan F, which is also a simplicial fan of smaller dimension. Thus the subgraph G_{F}(F) also contains a unique vertex of outdegree 0 (in this subgraph). There is a surjective map ϕ : F ↦ σ from all faces of F to vertices of G_{F} (i.e., d-dimensional faces of F) that sends a face F to the vertex σ of outdegree 0 in the subgraph G_{F}(F). Now, for a vertex σ of G_{F} of outdegree i, the preimage ϕ^{−1}(σ) contains exactly \binom{d−i}{d−j} faces of dimension j. Indeed, ϕ^{−1}(σ) is formed by taking all possible intersections of σ with some subset of its (d−1)-dimensional faces {F_{1}, …, F_{d−i}} on which the vector g is directed towards the interior of σ; there are exactly d − i such faces because σ has indegree i in G_{F}. Thus a face of dimension j in ϕ^{−1}(σ) has the form F_{i_{1}} ∩ ⋯ ∩ F_{i_{d−j}} for a (d − j)-element subset {i_{1}, …, i_{d−j}} ⊆ [d − i]. Let h̃_{i} be the number of vertices of G_{F} of outdegree i. Counting j-dimensional faces in preimages ϕ^{−1}(σ) one obtains the relation f_{j}(F) = ∑_{i} \binom{d−i}{d−j} h̃_{i}. Comparing this with the definition of h_{i}(F), one deduces that h_{i}(F) = h̃_{d−i}. Note that the numbers h_{i}(F) do not depend upon the choice of the vector g. It follows that the numbers h̃_{i} of vertices with given outdegrees also do not depend on g. Replacing the vector g with −g reverses the orientation of all edges in the d-regular graph G_{F}, implying the the symmetry h̃_{i} = h̃_{d−i}.

The Dehn-Sommerville symmetry means that h-polynomials are palindromic polynomials: t^{d} h_{F}(\frac{1}{t}) = h_{F}(t). In this sense the h-vector encoding is more compact, since it is determined by roughly half of its entries, namely h_{0}, h_{1}, …, h_{⌊ \frac{d}{2} ⌋}. Whenever possible, we will try to either give further explicit combinatorial interpretations or generating functions for the f- and h-polynomials of simple generalized permutohedra.

2.3 Flag simple polytopes and γ-vectors

A simplicial complex Δ is called a flag simplicial complex or clique complex if it has the following property: a collection C of vertices of Δ forms a simplex in Δ if and only if there is an edge in the 1-skeleton of Δ between any two vertices in C. Thus flag simplicial complexes can be uniquely recovered from their 1-skeleta. We call a simple polytope P is a flag polytope if its dual simplicial complex Δ_{P} is a flag simplicial complex. We next discuss γ-vectors of flag simple polytopes, as introduced by Gal [Gal’05] and independently in a slightly different context by Bränden [Brä’04, Brä’06]; see also the discussion in [Stem’07, §1D]. A conjecture of Charney and Davis [ChD’95] led Gal [Gal’05] to define the following equivalent encoding of the f-vector or h-vector of a simple polytope P, in terms of smaller integers, which are conjecturally nonnegative when P is flag. Every palindromic polynomial h(t) of degree d has a unique expansion in terms of centered binomials t^{i}(1+t)^{d−2i} for 0 ≤ i ≤ d/2, and so one can define the entries γ_{i} = γ_{i}(P) of the γ-vector (γ_{0}, γ_{1}, …, γ_{⌊ \frac{d}{2} ⌋}) and the γ-polynomial γ_{P} (t) := ∑_{i=0}^{⌊ \frac{d}{2} ⌋} γ_{i}t^{i} uniquely by

h_{P} (t) = ∑_{i=0}^{⌊ \frac{d}{2} ⌋} γ_{i} t^{i}(1 + t)^{d−2i} = (1 + t)^{d}γ_{P} (\frac{t}{(1 + t)^{2}} ) .

Conjecture 2.3. [Gal’05] The γ-vector has nonnegative entries for any flag simple polytope. More generally, the nonnegativity of the γ-vector holds for every flag simplicial homology sphere.

Thus we will try to give explicit combinatorial interpretations, where possible, for the γ-vectors of flag simple generalized permutohedra. As will be seen in Section 7.1, any graph-associahedron is a flag simple polytope.

3 Generalized permutohedra and the cone-preposet dictionary

This section reviews the definition of generalized permutohedra from [Post’05]. It then records some observations about the relation between cones and fans coming from the braid arrangement and preposets. (Normal fans of generalized permutohedra are examples of such fans.) This leads to a characterization for when generalized permutohedra are simple, an interpretation for their h-vector in this situation, and a corollary about when the associated toric variety is smooth. The material in this section and in the Appendix (Section 15) has substantial overlap with recent work on rank tests of non-parametric statistics [M–W’06]. We have tried to indicate in places the corresponding terminology used in that paper.

3.1 Generalized permutohedra

Recall that a usual permutohedron in ℝ^{n} is the convex hull of n! points obtained by permuting the coordinates of any vector (a_{1}, …, a_{n}) with strictly increasing coordinates a_{1} < ⋯ < a_{n}. So the vertices of a usual permutohedron can be labelled v_{w} = (a_{w^{−1}(1)}, …, a_{w^{−1}(n)}) by the permutations w in the symmetric group 𝔖_{n}. The edges of this permutohedron are [v_{w}, v_{ws_{i}}], where s_{i} = (i, i + 1) is an adjacent transposition. Then, for any w ∈ 𝔖_{n} and any s_{i}, one has

v_{w} − v_{ws_{i}} = k_{w,i}(e_{w(i)} − e_{w(i+1)})  (2)

where the k_{w,i} are some strictly positive real scalars, and e_{1}, …, e_{n} are the standard basis vectors in ℝ^{n}. Note that a usual permutohedron in ℝ^{n} has dimension d = n − 1, because it is contained in an affine hyperplane where the sum of coordinates x_{1} + ⋯ + x_{n} is constant.

Definition 3.1. [Post’05, Definition 6.1] A generalized permutohedron P is the convex hull of n! points v_{w} in ℝ^{n} labelled by the permutations w in the symmetric group 𝔖_{n}, such that for any w ∈ 𝔖_{n} and any adjacent transposition s_{i}, one still has equation (2), but with k_{w,i} assumed only to be nonnegative, that is, k_{w,i} can vanish.

The Appendix shows that all n! points v_{w} in a generalized permutohedron P are actually vertices of P (possibly with repetitions); see Theorem 15.3. Thus a generalized permutohedron P comes naturally equipped with the surjective map Ψ_{P} : 𝔖_{n} → Vertices(P) given by Ψ_{P} : w ↦ v_{w}, for w ∈ 𝔖_{m}. Definition 3.1 says that a generalized permutohedron is obtained by moving the vertices of the usual permutohedron in such a way that directions of edges are preserved, but some edges (and higher dimensional faces) may degenerate. In the Appendix such deformations of a simple polytope are shown to be equivalent to various other notions of deformation; see Proposition 3.2 below and the more general Theorem 15.3.

3.2 Braid arrangement

Let x_{1}, …, x_{n} be the usual coordinates in ℝ^{n}. Let ℝ^{n}/(1, …, 1)ℝ ≃ ℝ^{n−1} denote the quotient space modulo the 1-dimensional subspace generated by the vector (1, …, 1). The braid arrangement is the arrangement of hyperplanes {x_{i}−x_{j} = 0}_{1≤i<j≤n} in the space ℝ^{n}/(1, …, 1)ℝ. These hyperplanes subdivide the space into the polyhedral cones

C_{w} := {x_{w(1)} ≤ x_{w(2)} ≤ ⋯ ≤ x_{w(n)}}

labelled by permutations w ∈ 𝔖_{n}, called Weyl chambers (of type A). The Weyl chambers and their lower dimensional faces form a complete simplicial fan, sometimes called the braid arrangement fan. Note that a usual permutohedron P has dimension d = n − 1, so one can reduce its normal fan modulo the 1-dimensional subspace P^{⊥} = (1, …, 1)ℝ. The braid arrangement fan is exactly the (reduced) normal fan N (P)/P^{⊥} for a usual permutohedron P ⊂ ℝ^{n}. Indeed, the (reduced) normal cone N_{v_{w}}(P)/P^{⊥} of P at vertex v_{w} is exactly the Weyl chamber C_{w}. (Here one identifies ℝ^{n} with (ℝ^{n})^{∗} via the standard inner product.)

Recall that the Minkowski sum P + Q of two polytopes P, Q ⊂ ℝ^{n} is the polytope P +Q := {x+y | x ∈ P, y ∈ Q}. Say that P is a Minkowski summand of R, if there is a polytope Q such that P + Q = R. Say that a fan F is refined by a fan F′ if any cone in F is a union of cones in F′. The following proposition is a special case of Theorem 15.3.

Proposition 3.2. A polytope P in ℝ^{n} is a generalized permutohedron if and only if its normal fan (reduced by (1, …, 1)ℝ) is refined by the braid arrangement fan. Also, generalized permutohedra are exactly the polytopes arising as Minkowski summands of usual permutohedra.

This proposition shows that generalized permutohedra lead to the study of cones given by some inequalities of the form x_{i} − x_{j} ≥ 0 and fans formed by such cones. Such cones are naturally related to posets and preposets.

3.3 Preposets, equivalence relations, and posets

Recall that a binary relation R on a set X is a subset of R ⊆ X ×X. A preposet is a reflexive and transitive binary relation R, that is (x, x) ∈ R for all x ∈ X, and whenever (x, y), (y, z) ∈ R one has (x, z) ∈ R. In this case we will often use the notation x ⪯_{R} y instead of (x, y) ∈ R. Let us also write x ≺_{R} y whenever x ⪯_{R} y and x ≠ y. An equivalence relation ≡ is the special case of a preposet whose binary relation is also symmetric. Every preposet Q gives rise to an equivalence relation ≡_{Q} defined by x ≡_{Q} y if and only if both x ⪯_{Q} y and y ⪯_{Q} x. A poset is the special case of a preposet Q whose associated equivalence relation ≡_{Q} is the trivial partition, having only singleton equivalence classes. Every preposet Q gives rise to the poset Q/≡_{Q} on the equivalence classes X/≡_{Q}. A preposet Q is uniquely determined by ≡_{Q} and Q/≡_{Q}, that is, a preposet is just an equivalence relation together with a poset structure on the equivalence classes. A preposet Q on X is connected if the undirected graph having vertices X and edges {x, y} for all x ⪯_{Q} y is connected. A covering relation x ⋖_{Q} y in a poset Q is a pair of elements x ≺_{Q} y such that there is no z such that x ≺_{Q} z ≺_{Q} y. The Hasse diagram of a poset Q on X is the directed graph on X with edges (x, y) for covering relations x ⋖_{Q} y. We call a poset Q a tree-poset if its Hasse diagram is a spanning tree on X. Thus tree-posets correspond to directed trees on the vertex set X. A linear extension of a poset Q on X is a linear ordering (y_{1}, …, y_{n}) of all elements in X such that y_{1} ≺_{Q} y_{2} ≺_{Q} ⋯ ≺_{Q} y_{n}. Let L(Q) denote the set of all linear extensions of Q. The union R_{1} ∪ R_{2} of two binary relations R_{1}, R_{2} on X is just their union as two subsets of X × X. Given any reflexive binary relation Q, denote by \overline{Q} the preposet which is its transitive closure. Note that if Q_{1} and Q_{2} are two preposets on the same set X, then the binary relation Q_{1} ∪Q_{2} is not necessarily a preposet. However, we can obtain a preposet by taking its transitive closure \overline{Q_{1} ∪ Q_{2}}. Let R ⊆ Q denote containment of binary relations on the same set, meaning containment as subsets of X × X. Also let R^{op} be the opposite binary relation, that is (x, y) ∈ R^{op} if and only if (y, x) ∈ R. For two preposets P and Q on the same set, let us say that Q is a contraction of P if there is a binary relation R ⊆ P such that Q = \overline{P ∪ R^{op}}. In other words, the equivalence classes of ≡_{Q} are obtained by merging some equivalence classes of ≡_{P} along relations in P and the poset structure on equivalence classes of ≡_{Q} is induced from the poset structure on classes of ≡_{P}. For example, the preposet 1 < {2, 3} < 4 (where {2, 3} is an equivalence class) is a contraction of the poset P = (1 < 3, 2 < 3, 1 < 4, 2 < 4). However, the preposet ({1, 2} < 3, {1, 2} < 4) is not a contraction of P because 1 and 2 are incomparable in P.

Definition 3.3. We say that two preposets Q_{1} and Q_{2} on the same set intersect properly if the preposet \overline{Q_{1} ∪ Q_{2}} is both a contraction of Q_{1} and of Q_{2}. A complete fan of posets^{4} on X is a collection of distinct posets on X which pairwise intersect properly, and whose linear extensions (disjointly) cover all linear orders on X.

Compare Definition 3.3 to the definitions of properly intersecting cones and complete fans of cones in Section 2.1. Proposition 3.5 will elucidate this connection.

Example 3.4. The two posets P_{1} := 1 < 2 and P_{2} := 2 < 1 on the set {1, 2} intersect properly. Here \overline{P_{1} ∪ P_{2}} is equal to \{1 < 2, 2 < 1\}. These P_{1} and P_{2} form a complete fan of posets. However, the two posets Q_{1} := 2 < 3 and Q_{2} := 1 < 2 < 3 on the set {1, 2, 3} do not intersect properly. In this case \overline{Q_{1} ∪ Q_{2}} = Q_{2}, which is not a contraction of Q_{1}.

3.4 The dictionary

Let us say that a braid cone is a polyhedral cone in the space ℝ^{n}/(1, …, 1)ℝ ≃ ℝ^{n−1} given by a conjunction of inequalities of the form x_{i} − x_{j} ≥ 0. In other words, braid cones are polyhedral cones formed by unions of Weyl chambers or their lower dimensional faces. There is an obvious bijection between preposets and braid cones. For a preposet Q on the set [n], let σ_{Q} be the braid cone in the space ℝ^{n}/(1, …, 1)ℝ defined by the conjunction of the inequalities x_{i} ≤ x_{j} for all i ⪯_{Q} j. Conversely, one can always reconstruct the preposet Q from the cone σ_{Q} by saying that i ⪯_{Q} j whenever x_{i} ≤ x_{j} for all points in σ_{Q}.

Proposition 3.5. Let the cones σ, σ′ correspond to the preposets Q, Q′ under the above bijection. Then (1) The preposet \overline{Q ∪ Q′} corresponds to the cone σ ∩ σ′.

4In [M–W’06], this is called a convex rank test.

Documenta Mathematica 13 (2008) 207–273

(2) The preposet Q is a contraction of Q′ if and only if the cone σ is a face σ′.

(3) The preposets Q, Q′ intersect properly if and only if the cones σ, σ′ do.

(4) Q is a poset if and only if σ is a full-dimensional cone, i.e., dim σ = n−1.

(5) The equivalence relation ≡_{Q} corresponds to the linear span Span(σ) of σ.

(6) The poset Q/≡_{Q} corresponds to a full-dimensional cone inside Span(σ_{Q}).

(7) The preposet Q is connected if and only if the cone σ is pointed.

(8) If Q is a poset, then the minimal set of inequalities describing the cone σ is {x_{i} ≤ x_{j} | i ⋖_{Q} j}. (These inequalities associated with covering relations in Q are exactly the facet inequalities for σ.)

(9) Q is a tree-poset if and only if σ is a full-dimensional simplicial cone.

(10) For w ∈ 𝔖_{n}, the cone σ contains the Weyl chamber C_{w} if and only if Q is a poset and w is its linear extension, that is w(1) ≺_{Q} w(2) ≺_{Q} ⋯ ≺_{Q} w(n).

Proof. (1) The cone σ ∩ σ′ is given by conjunction of all inequalities for σ and σ′. The corresponding preposet is obtained by adding all inequalities that follow from these, i.e., by taking the transitive closure of Q ∪ Q′.

(2) Faces of σ′ are obtained by replacing some inequalities x_{i} ≤ x_{j} defining σ′ with equalities x_{i} = x_{j}, or equivalently, by adding the opposite inequalities x_{i} ≥ x_{j}.

(3) follows from (1) and (2).

(4) σ is full-dimensional if its defining relations do not include any equalities x_{i} = x_{j}, that is ≡_{Q} has only singleton equivalence classes.

(5) The cone associated with the equivalence relation ≡_{Q} is given by the equations x_{i} = x_{j} for i ≡_{Q} j, which is exactly Span(σ).

(6) Follows from (4) and (5).

(7) The maximal subspace contained in the half-space {x_{i} ≤ x_{j}} is given by x_{i} = x_{j}. Thus the maximal subspace contained in the cone σ is given by the conjunction of equations x_{i} = x_{j} for i ≤_{Q} j. If Q is disconnected then this subspace has a positive dimension. If Q is connected then this subspace is given by x_{1} = ⋯ = x_{n}, which is just the origin in the space ℝ^{n}/(1, …, 1)ℝ.

(8) The inequalities for the covering relations i⋖_{Q} j imply all other inequalities for σ and they cannot be reduced to a smaller set of inequalities.

(9) By (4) and (7) full-dimensional pointed cones correspond to connected posets. These cones will be simplicial if they are given by exactly n − 1 inequalities. By (8) this means that the corresponding poset should have exactly n − 1 covering relations, i.e., it is a tree-poset.

(10) Follows from (4) and definitions.

According to Proposition 3.5, a full-dimensional braid cone σ associated with a poset Q can be described in three different ways (via all relations in Q, via covering relations in Q, and via linear extensions L(Q) of Q) as

σ = {x_{i} ≤ x_{j} | i ⪯_{Q} j} = {x_{i} ≤ x_{j} | i ⋖_{Q} j} = ⋃_{w∈L(Q)} C_{w}.

Let F be a family of d-cones in ℝ^{d} which intersect properly. Since they have disjoint interiors, they will correspond to a complete fan if and only if their closures cover ℝ^{d}, or equivalently, their spherical volumes sum to the volume of the full (d − 1)-sphere. A braid cone corresponding to a poset Q is the union of the Weyl chambers C_{w} for all linear extensions w ∈ L(Q), and every Weyl chamber has the same spherical volume (\frac{1}{n!} of the sphere) due to the transitive Weyl group action. Therefore, a collection of properly intersecting posets {Q_{1}, …, Q_{t}} on [n] correspond to a complete fan on braid cones if and only if

⋃_{i=1}^{t} L(Q_{i}) = 𝔖_{n}(disjoint union), or equivalently, if and only if ∑_{i=1}^{t} |L(Q_{i})| = n!,

cf. Definition 3.3.

Corollary 3.6. A complete fan of braid cones (resp., pointed braid cones, simplicial braid cones) in ℝ^{n}/(1, …, 1)ℝ corresponds to a complete fan of posets (resp., connected posets, tree-posets) on [n].

Using Proposition 3.2, we can relate Proposition 3.5 and Corollary 3.6 to generalized permutohedra. Indeed, normal cones of a generalized permutohedron (reduced modulo (1, …, 1)ℝ) are braid cones. For a generalized permutohedron P, define the vertex poset Q_{v} at a vertex v ∈ Vertices(P) as the poset on [n] associated with the normal cone N_{v}(P)/(1, …, 1)ℝ at the vertex v, as above.

Corollary 3.7. For a generalized permutohedron (resp., simple generalized permutohedron) P, the collection of vertex posets {Q_{v} | v ∈ Vertices(P)} is a complete fan of posets (resp., tree-posets).

Thus normal fans of generalized permutohedra correspond to certain complete fans of posets, which we call polytopal. In [M–W’06], the authors call such fans submodular rank tests, since they are in bijection with the faces of the cone of submodular functions. That cone is precisely the deformation cone we discuss in the Appendix.

Example 3.8. In [M–W’06], the authors modify an example of Studený [Stud’05] to exhibit a non-polytopal complete fan of posets. They also kindly provided us with the following further nonpolytopal example, having 16 posets Q_{v}, all of them tree-posets: (1, 2 < 3 < 4) (which means that 1 < 3 and 2 < 3), (1, 2 < 4 < 3), (3, 4 < 1 < 2), (3, 4 < 2 < 1), (1 < 4 < 2, 3), (4 < 1 < 2, 3), (2 < 3 < 1, 4), (3 < 2 < 1, 4), (1 < 3 < 2 < 4), (1 < 3 < 4 < 2), (3 < 1 < 2 < 4), (3 < 1 < 4 < 2), (2 < 4 < 1 < 3), (2 < 4 < 3 < 1), (4 < 2 < 1 < 3), (4 < 2 < 3 < 1). This gives a complete fan of simplicial cones, but does not correspond to a (simple) generalized permutohedron.

Recall that Ψ_{P} : 𝔖_{n} → Vertices(P) is the surjective map Ψ_{P} : w ↦ v_{w}; see Definition 3.1. The previous discussion immediately implies the following corollary.

Corollary 3.9. Let P be a generalized permutohedron in ℝ^{n}, and v ∈ Vertices(P) be a vertex. For w ∈ 𝔖_{n}, one has Ψ_{P} (w) = v whenever the normal cone N_{v}(P) contains the Weyl chamber C_{w}. The preimage Ψ_{P}^{−1}(v) ⊆ 𝔖_{n} of a vertex v ∈ Vertices(P) is the set L(Q_{v}) of all linear extensions of the vertex poset Q_{v}.

We remark on the significance of this cone-preposet dictionary for toric varieties associated to generalized permutohedra or their normal fans; see Fulton [Ful’93] for further background. A complete fan F of polyhedral cones in ℝ^{d} whose cones are rational with respect to ℤ^{d} gives rise to a toric variety X_{F}, which is normal, complete and of complex dimension d. This toric variety is projective if and only if F is the normal fan N (P) for some polytope P, in which case one also denotes X_{F} by X_{P}. The toric variety X_{F} is quasi-smooth or orbifold if and only if F is a complete fan of simplicial cones; in the projective case, where F = N (P), this corresponds to P being a simple polytope. In this situation, the h-numbers of F (or of P) have the auxiliary geometric meaning as the (singular cohomology) Betti numbers h_{i} = dim H^{i}(X_{F}, ℂ). The symmetry h_{i} = h_{d−i} reflects Poincaré duality for this quasi-smooth variety. The toric variety X_{F} is smooth exactly when every top-dimensional cone of F is not only simplicial but unimodular, that is, the primitive vectors on its extreme rays form a ℤ-basis for ℤ^{d}. Equivalently, the facet inequalities ℓ_{1}, …, ℓ_{d} can be chosen to form a ℤ-basis for (ℤ^{d})^{∗} = Hom(ℤ^{d}, ℤ) inside (ℝ^{d})^{∗}. One has X_{F} both smooth and projective if and only if F = N (P) for a Delzant polytope P, that is, one which is simple and has every vertex normal cone unimodular.

Corollary 3.10. (cf. [Zel’06, §5]) A complete fan F of posets gives rise to a complete toric variety X_{F}, which will be projective if and only if F is associated with the normal fan N (P) for a generalized permutohedron. A complete fan F of tree-posets gives rise to a (smooth, not just orbifold) toric variety X_{F}, which will be projective if and only F is associated with the normal fan N (P) of a simple generalized permutohedron. In other words, simple generalized permutohedra are always Delzant.

Proof. All the assertions should be clear from the above discussion, except for the last one about simple generalized permutohedra being Delzant. However, a tree-poset Q corresponds to a set of functionals x_{i} − x_{j} for the edges {i, j} of a tree, which are well-known to give a ℤ-basis for (ℤ^{d})^{∗}, cf. [Post’05, Proposition 7.10].

4 Simple generalized permutohedra

The goal of this section is to combinatorially interpret the h-vector of any simple generalized permutohedron.

4.1 Descents of tree-posets and h-vectors

Definition 4.1. Given a poset Q on [n], define the descent set Des(Q) to be the set of ordered pairs (i, j) for which i ⋖_{Q} j is a covering relation in Q with i >_{ℤ} j, and define the statistic number of descents des(Q) := |Des(Q)|.

Theorem 4.2. Let P be a simple generalized permutohedron, with vertex posets {Q_{v}}_{v∈Vertices(P)}. Then one has the following expression for its h-polynomial:

h_{P} (t) = ∑_{v∈Vertices(P)} t^{des(Q_{v})}.  (3)

More generally, for a complete fan F = {Q_{v}} of tree-posets (see Definition 3.3), one also has h_{F}(t) = ∑_{v} t^{des(Q_{v})}.

Proof. (cf. proof of Proposition 7.10 in [Post’05]) Let us prove the more general claim about fans of tree-posets, that is, simplicial fans coarsening the braid arrangement fan. Pick a generic vector g = (g_{1}, …, g_{n}) ∈ ℝ^{n} such that g_{1} < ⋯ < g_{n} and construct the directed graph G_{F}, as in Proposition 2.1. Let σ = {x_{i} ≤ x_{j} | i⋖_{Q_{v}} j} be the cone of F associated with poset Q_{v}; see Proposition 3.5(8). Let σ′ be an adjacent cone separated from σ by the facet x_{i} = x_{j}, i ⋖_{Q_{v}} j. The vector g points from σ to σ′ if and only if g_{i} >_{ℝ} g_{j}, or equivalently, i >_{ℤ} j. Thus the outdegree of σ in the graph G_{F} is exactly the descent number des(Q). The claim now follows from Proposition 2.1.

For a usual permutohedron P in ℝ^{n}, the vertex posets Q_{v} are just all linear orders on [n]. So h_{P} (t) is the classical Eulerian polynomial^{5}

A_{n}(t) := ∑_{w∈𝔖_{n}} t^{des(w)},  (4)

where des(w) := #{i | w(i) > w(i+1)} is the descent number of a permutation w. Any element w in the Weyl group 𝔖_{n} sends a complete fan F = {Q_{i}} of treeposets to another such complete fan wF = {wQ_{i}}, by relabelling all of the posets. Since wF is an isomorphic simplicial complex, with the same h-vector, this leads to a curious corollary.

5Note that a more standard convention is to call tA_{n}(t) the Eulerian polynomial.

Documenta Mathematica 13 (2008) 207–273

Definition 4.3. Given a tree-poset Q on [n], define its generalized Eulerian polynomial

A_{Q}(t) := ∑_{w∈𝔖_{n}} t^{des(wQ)}.

Note that A_{Q} depends upon Q only as an unlabelled poset.

When Q is a linear order, A_{Q}(t) is the usual Eulerian polynomial A_{n}(t).

Corollary 4.4. The h-polynomial h_{P} (t) of a simple generalized permutohedron P is the “average” of the generalized Eulerian polynomials of its vertex tree-posets Q_{v}:

h_{P} (t) = \frac{1}{n!} ∑_{v∈Vertices(P)} A_{Q_{v}}(t).

See Example 5.5 below for an illustration of Theorem 4.2 and Corollary 4.4.

4.2 Bounds on the h-vector and monotonicity

It is natural to ask for upper and lower bounds on the h-vectors of simple generalized permutohedra. Some of these follow immediately from an h-vector monotonicity result of Stanley [Stan’92] that applies to complete simplicial fans.

Definition 4.5. A simplicial complex Δ′ is a geometric subdivision of a simplicial complex Δ if they have geometric realizations that are topological spaces on the same underlying set, and every face of Δ′ is contained in a single face of Δ.

Theorem 4.6. (see [Stan’92, Theorem 4.1]) If Δ′ is a geometric subdivision of a Cohen-Macaulay simplicial complex Δ, then the h-vector of Δ′ is componentwise weakly larger than that of Δ. In particular this holds when Δ, Δ′ come from two complete simplicial fans and Δ′ refines Δ, e.g., the normal fans of two simple polytopes P, P′ in which P is a Minkowski summand of P.

Corollary 4.7. A simple generalized permutohedron P in ℝ^{n} has hpolynomial coefficientwise smaller than that of the permutohedron, namely the Eulerian polynomial A_{n}(t).

Proof. Proposition 3.2 tells us that the normal fan of P is refined by that of the permutohedron, so the above theorem applies.

Question 4.8. Does the permutohedron also provide an upper bound for the f-vectors, flag f- and flag h-vectors, generalized h-vectors, and cd-indices of generalized permutohedra also in the non-simple case? Is there also a monotonicity result for these other forms of face and flag number data when one has two generalized permutohedra P, P′ in which P is a Minkowski summand of P′?

The answer is “Yes” for f-vectors and flag f-vectors, which clearly increase under subdivision. The answer is also “Yes” for generalized h-vectors, which Stanley also showed [Stan’92, Corollary 7.11] can only increase under geometric subdivisions of rational convex polytopes. But for flag h-vectors and cd-indices, this is not so clear.

Later on (Example 6.11, Section 7.2, and Section 14) we will say more about lower bounds for h-vectors of simple generalized permutohedra within various classes.

5 The case of zonotopes

This section illustrates some of the foregoing results in the case where the simple generalized permutohedron is a zonotope; see also [Post’05, §8.6]. Zonotopal generalized permutohedra are exactly the graphic zonotopes, and those that are simple correspond to a very restrictive class of graphs that are easily dealt with. A zonotope is a convex polytope Z which is the Minkowski sum of onedimensional polytopes (line segments), or equivalently, a polytope whose normal fan N (Z) coincides with chambers and cones of a hyperplane arrangement. Under this equivalence, the line segments which are the Minkowski summands of Z lie in the directions of the normal vectors to the hyperplanes in the arrangement. Given a graph G = (V, E) without loops or multiple edges, on node set V = [n] and with edge set E, define the associated graphic zonotope Z_{G} to be the Minkowski sum of line segments in the directions {e_{i} − e_{j}}_{ij∈E}. Proposition 3.2 then immediately implies the following.

Proposition 5.1. The zonotopal generalized permutohedra are exactly the graphic zonotopes Z_{G}.

Simple zonotopes are very special among all zonotopes, and simple graphic zonotopes have been observed [Kim’06] to correspond to a very restrictive class of graphic zonotopes, namely those whose biconnected components are all complete graphs. Recall that for a graph G = (V, E), there is an equivalence relation on E defined by saying e ∼ e′ if there is some circuit (i.e., cycle which is minimal with respect to inclusion of edges) of G containing both e, e′. The ∼-equivalence classes are then called biconnected components of G.

Proposition 5.2. [Kim’06, Remark 5.2] The graphic zonotope Z_{G} corresponding to a graph G = (V, E) is a simple polytope if and only if every biconnected component of G is the set of edges of a complete subgraph some subset of the vertices V. In this case, if V_{1}, …, V_{r} ⊆ V are the node sets for these complete subgraphs, then Z_{G} is isomorphic to the Cartesian product of usual permutohedra of dimensions |V_{j}| − 1 for j = 1, 2, …, r.

Let us give another description for this class of graphs. For a graph F with n edges e_{1}, …, e_{n}, the line graph Line(F) of F is the graph on the vertex set [n] where {i, j} is an edge in Line(F) if and only if the edges e_{i} and e_{j} of F have a common vertex. The following claim is left as an exercise for the reader.

Remark 5.3. For a graph G, all biconnected components of G are edge sets of complete graphs if and only if G is isomorphic to the line graph Line(F) of some forest F. Biconnected components of Line(F) correspond to non-leaf vertices of F.

For the sake of completeness, we include a proof of Proposition 5.2.

Proof of Proposition 5.2. If the biconnected components of G induce subgraphs isomorphic to graphs G_{1}, …, G_{r} then one can easily check that Z_{G} is the Cartesian product of the zonotopes Z_{G_{i}}. Since a Cartesian product of polytopes is simple if and only if each factor is simple, this reduces to the case where r = 1. Also note that when r = 1 and G is a complete graph, then Z_{G} is the permutohedron, which is well-known to be simple. For the reverse implication, assume G is biconnected but not a complete graph, and it will suffice, by Proposition 3.5(9), to construct a vertex v of Z_{G} whose poset Q_{v} is not a tree-poset. One uses the fact [GZ’83] that a vertex v in the graphic zonotope Z_{G} corresponds to an acyclic orientation of G, and the associated poset Q_{v} on V is simply the transitive closure of this orientation. Thus it suffices to produce an acyclic orientation of G whose transitive closure has Hasse diagram which is not a tree. Since G is biconnected but not complete, there must be two vertices {x, y} that do not span an edge in E, but which lie in some circuit C. Traverse this circuit C in some cyclic order, starting at the node x, passing through some nonempty set of vertices V_{1} before passing through y, and then through a nonempty set of vertices V_{2} before returning to x. One can then choose arbitrarily a total order on the node set V so that these sets appear as segments in this order:

V_{1}, x, y, V_{2}, V − (V_{1} ∪ V_{2} ∪ {x, y}).

It is then easily checked that if one orients the edges of G consistently with this total order, then the associated poset has a non-tree Hasse diagram: for any v_{1} ∈ V_{1} and v_{2} ∈ V_{2}, one has v_{1} < x, y < v_{2} with x, y incomparable.

Corollary 5.4. Let Z_{G} be a simple graphic zonotope, with notation as in Proposition 5.2. Then Z_{G} is flag, and its f-polynomial, h-polynomial, and γ-polynomial are all equal to products for j = 1, 2, …, r of the f-, h-, or γpolynomials of (|V_{j}| − 1)-dimensional permutohedra.

Proof. Use Proposition 5.2 along with the fact that a Cartesian product of simple polytopes is flag if and only if each factor is flag, and has f-, h- and γ-polynomial equal to the product of the same polynomials for each factor.

Example 5.5. Consider the graph G = (V, E) with V = [4] := {1, 2, 3, 4} and E = {12, 13, 23, 14}, whose biconnected components are the triangle 123 and the edge 14, which are both complete subgraphs on node sets V_{1} = {1, 2, 3} and V_{2} = {1, 4}. Hence the graphic zonotope Z_{G} is simple and flag, equal to the Cartesian product of a hexagon with a line segment, that is, Z_{G} is a hexagonal prism. Its f-, h- and γ-polynomials are

\begin{aligned}f_{Z_{G}}(t) & = (2 + t)(6 + 6t + t^{2}) & = 12 + 18t + 8t^{2} + t^{3} \\ h_{Z_{G}}(t) & = A_{2}(t)A_{3}(t) = (1 + t)(1 + 4t + t^{2}) & = 1 + 5t + 5t^{2} + t^{3} \\ γ_{Z_{G}}(t) & = (1)(1 + 2t) & = 1 + 2t. \end{aligned}

One can arrive at the same h-polynomial using Theorem 4.2. One lists the tree-posets Q_{v} for each of the 12 vertices v of the hexagonal prism Z_{G}, coming in 5 isomorphism types, along with the number of descents for each:

type poset Q_{v}  des
chain: 2 < 3 < 1 < 4  1
3 < 2 < 1 < 4  2
4 < 1 < 2 < 3  1
4 < 1 < 3 < 2  2
vee: 1 < 2 < 3 and 1 < 4 0
1 < 3 < 2 and 1 < 4 1

type  poset Q_{v}  des
wedge: 2 < 3 < 1 and 4 < 1 2
3 < 2 < 1 and 4 < 1 3
wye: 2 < 1 < 3 and 1 < 4 1
3 < 1 < 2 and 1 < 4 1
lambda: 3 < 1 < 2 and 4 < 1 2
2 < 1 < 3 and 4 < 1 2

and finds that ∑_{v} t^{des(Q_{v})} = 1 + 5t + 5t^{2} + t^{3}. Lastly one can get this h-polynomial from Corollary 4.4, by calculating directly that

A_{chain}(t) = 1 + 11t + 11t^{2} + t^{3} = A_{4}(t)
A_{vee}(t) = 3 + 10t + 8t^{2} + 3t^{3}
A_{wedge}(t) = 3 + 8t + 10t^{2} + 3t^{3}
A_{wye}(t) = A_{lambda}(t) = 2 + 10t + 10t^{2} + 2t^{3}

and then the h-polynomial is

\frac{1}{4!} [4A_{chain}(t) + 2A_{vee}(t) + 2A_{wedge}(t) + 2A_{wye}(t) + 2A_{lambda}(t)]
== 1 + 5t + 5t^{2} + t^{3}.

6 Building sets and nestohedra

This section reviews some results from [FS’05], [Post’05], and [Zel’06] regarding the important special case of generalized permutohedra that arise from building sets. These generalized permutohedra, which we call nestohedra, turn out to always be simple, and they include the graph-associahedra, which in turn generalize the associahedron, cyclohedron, and permutohedron; this will be fleshed out in Section 10. Their dual simplicial complexes, the nested set complexes, are defined, and several tools are given for calculating their f- and h-vectors. The notion of nested sets goes back to work of Fulton and MacPherson [FM’94], and DeConcini and Procesi [DP’95] defined building sets and nested set complexes. However, our exposition mostly follows [Post’05] and [Zel’06].

6.1 Building sets, nestohedra, and nested set complexes

Definition 6.1. [Post’05, Definition 7.1] A collection B of nonempty subsets of a finite set S is a building set if it satisfies the conditions:

(B1) If I, J ∈ B and I ∩ J ≠ ∅, then I ∪ J ∈ B.

(B2) B contains all singletons {i}, for i ∈ S.

For a building set B on S and a subset I ⊆ S, define the restriction of B to I as B|_{I} := {J ∈ B | J ⊆ I}. Let B_{max} ⊂ B denote the inclusion-maximal subsets of a building B. Then elements of B_{max} are pairwise disjoint subsets that partition the set S. Call the restrictions B|_{I}, for I ∈ B_{max}, the connected components of B. Say that a building set is connected if B_{max} has only one element: B_{max} = {S}.

Example 6.2. Let G be a graph (with no loops nor multiple edges) on the node set S. The graphical building B(G) is the set of nonempty subsets J ⊆ S such that the induced graph G|_{J} on node set J is connected. Then B(G) is a building set. The graphical building set B(G) is connected if and only if the graph G is connected. The connected components of the graphical B(G) building set correspond to connected components of the graph G. Also each restriction B(G)|_{I} is the graphical building set B(G|_{I}) for the induced subgraph G|_{I}.

Definition 6.3. Let B be a building set on [n] := {1, …, n}. Faces of the standard coordinate simplex in ℝ^{n} are the simplices Δ_{I} := ConvexHull(e_{i} | i ∈ I), for I ⊆ [n], where the e_{i} are the endpoints of the coordinate vectors in ℝ^{n}. Define the nestohedron^{6} P_{B} as the Minkowski sum of these simplices

P_{B} := ∑_{I∈B} y_{I}Δ_{I},  (5)

where y_{I} are strictly positive real parameters; see [Post’05, Section 6].

Note that since each of the normal fans N (Δ_{I}) is refined by the braid arrangement fan, the same holds for their Minkowski sum [Zieg’94, Prop. 7.12], and hence the nestohedra P_{B} are generalized permutohedra by Proposition 3.2.

6Called the nested set polytope in [Zel’06].

Documenta Mathematica 13 (2008) 207–273

It turns out that P_{B} is always a simple polytope, whose poset of faces does not depend upon the choice of the positive parameters y_{I}. To describe this combinatorial structure it is convenient to describe the dual simplicial complex of P_{B}.

Definition 6.4. [Post’05, Definition 7.3] For a building set B, let us say that a subset N ⊆ B \ B_{max} is a nested set if it satisfies the conditions:

(N1) For any I, J ∈ N one has either I ⊆ J, J ⊆ I, or I and J are disjoint.

(N2) For any collection of k ≥ 2 disjoint subsets J_{1}, …, J_{k} ∈ N, their union J_{1} ∪ ⋯ ∪ J_{k} is not in B.

Define the nested set complex Δ_{B} as the collection of all nested sets for B.

It is immediate from the definition that the nested set complex Δ_{B} is an abstract simplicial complex on node set B. Note that this slightly modifies the definition of a nested set from [Post’05], following [Zel’06], in that one does not include elements of B_{max} in nested sets.

Theorem 6.5. [Post’05, Theorem 7.4], [FS’05, Theorem 3.14] Let B be a building set on [n]. The nestohedron P_{B} is a simple polytope of dimension n − |B_{max}|. Its dual simplicial complex is isomorphic to the nested set complex Δ_{B}.

An explicit correspondence between faces of P_{B} and nested sets in Δ_{B} is described in [Post’05, Proposition 7.5]. The dimension of the face of P_{B} associated with a nested set N ∈ Δ_{B} equals n − |N| − |B_{max}|. Thus vertices of P_{B} correspond to inclusion-maximal nested sets in Δ_{B}, and all maximal nested sets contain exactly n − |B_{max}| elements.

Remark 6.6. For a building set B on [n], it is known [FY’04, Theorem 4] that one can obtain the nested set complex Δ_{B} (resp., the nestohedron P_{B}) via the following stellar subdivision (resp., shaving) construction, a common generalization of

• the barycentric subdivision of a simplex as the dual of the permutohedron,

• Lee’s construction of the associahedron [Lee’89, §3].

Start with an (n − 1)-simplex whose vertices (resp., facets) have been labelled by the singletons i for i ∈ [n], which are all in B. Then proceed through each of the non-singleton sets I in B, in any order that reverses inclusion (i.e., where larger sets come before smaller sets), performing a stellar subdivision on the face with vertices (resp., shave off the face which is the intersection of facets) indexed by the singletons in I.

Remark 6.7. Note that if B_{1}, …, B_{k} are the connected components of a building set B, then P_{B} is isomorphic to the direct product of polytopes P_{B_{1}} × ⋯ × P_{B_{k}}. Thus it is enough to investigate generalized permutohedra P_{B} and nested set complexes Δ_{B} only for connected buildings.

Remark 6.8. The definition (5) of the nestohedron P_{B} as a Minkowski sum should make it clear that whenever one has two building sets B ⊆ B′, then P_{B} is a Minkowski summand of P_{B′}. Hence Theorem 4.6 implies the h-vector of P_{B′} is componentwise weakly larger than that of P_{B}.

Remark 6.9. Nestohedra P_{B(G)} associated with graphical building sets B(G) are called graph-associahedra, and have been studied in [CD’06, Post’05, Tol’05, Zel’06]. In [CD’06], the sets in B(G) are called tubes, and the nested sets are called tubings. In particular, the h-vector monotonicity discussed in Remark 6.8 applies to graph-associahedra P_{B(G)}, P_{B(G′)} associated to graphs G, G′ where G is an edgesubgraph of G′.

Example 6.10. (Upper bound for nestohedra: the permutohedron) see [Post’05, Sect. 8.1] For the complete graph K_{n}, the building set B(K_{n}) = 2^{[n]} \ {∅} consists of all nonempty subsets in [n]. Let us call it the complete building set. The corresponding nestohedron (the graph-associahedron of the complete graph) is the usual (n − 1)-dimensional permutohedron in ℝ^{n}. The k-th component h_{k} of its h-vector is the Eulerian number, that is the number of permutations in 𝔖_{n} with k descents; and its h-polynomial is the Eulerian polynomial A_{n}(t); see (4). This h-vector gives the componentwise upper bound on h-vectors for all (d−1)- dimensional nestohedra. This also implies that the f-vector of the permutohedron gives the componentwise upper bound on f-vectors of nestohedra.

Example 6.11. (Lower bound for nestohedra: the simplex) The smallest possible connected building set B = {{1}, {2}, …, {n}, [n]} gives rise to the nestohedron P_{B} which is the (n − 1)-simplex in ℝ^{n}. In this case

f(t) = ∑_{i=1}^{n} \binom{n}{i}t^{i−1} = \frac{(1 + t)^{n} − 1}{t} and h(t) = 1 + t + t^{2} + ⋯ + t^{n−1}

give trivial componentwise lower bounds on the f-, h-vectors of nestohedra.

6.2 Two recurrences for f-polynomials of nestohedra

There are two useful recurrences for f-polynomials of nestohedra and nested set complexes. Let f_{B}(t) be the f-polynomial of the nestohedron P_{B}:

f_{B}(t) := ∑ f_{i} t^{i} = ∑_{N∈Δ_{B}} t^{|S|−|B_{max}|−|N|},

where f_{i} = f_{i}(P_{B}) is the number of i-dimensional faces of P_{B}. As usual, it is related to the h-polynomial as f_{B}(t) = h_{B}(t + 1).

Theorem 6.12. [Post’05, Theorem 7.11] The f-polynomial f_{B}(t) is determined by the following recurrence relations:

1. If B consists of a single singleton, then f_{B}(t) = 1.

2. If B has connected components B_{1}, …, B_{k}, then

f_{B}(t) = f_{B_{1}}(t) ⋯ f_{B_{k}}(t).

3. If B is a connected building set on S, then

f_{B}(t) = ∑_{I⊊S} t^{|S|−|I|−1}f_{B|_{I}} (t).

Another recurrence relation for f-polynomials was derived in [Zel’06], and will be used in Section 12.4 below. It will be more convenient to work with the f-polynomial of nested set complexes

f̃_{B}(t) := ∑_{N∈Δ_{B}} t^{|N|} = t^{|S|−|B_{max}|}f_{B}(t^{−1}),

where B is a building set on S. For a building set B on S and a subset I ⊂ S, recall that the restriction of B to I is defined as B|_{I} = {J ∈ B | J ⊆ I}. Also define the contraction of I from B as the building set on S \ I given by

B/I := {J ∈ S \ I | J ∈ B or J ∪ I ∈ B},

see [Zel’06, Definition 3.1]. A link decomposition of nested set complexes was constructed in [Zel’06]. It implies the following recurrence relation for the f-vector.

Theorem 6.13. [Zel’06, Proposition 4.7] For a building set B on a nonempty set S, one has

\frac{d}{dt} f̃_{B}(t) = ∑_{I∈B\B_{max}} f̃_{B|_{I}} (t) · f̃_{B/I}(t) and f̃_{B}(0) = 1.

Let G be a simple graph on S and let I ∈ B(G), i.e., I is a connected subset of nodes of G. It has already been mentioned that B(G)|_{I} = B(G|_{I}); see Example 6.2. Let G/I be the graph on the node set S \ I such that two nodes i, j ∈ S \ I are connected by an edge in G/I if and only if

1. i and j are connected by an edge in G, or

2. there are two edges (i, k) and (j, l) in G with k, l ∈ I.

Then the contraction of I from the graphical building set B(G) is the graphical building set associated with the graph G/I, that is B(G)/I = B(G/I).

7 Flag nestohedra

This section characterizes the flag nested set complexes and nestohedra, and then identifies those which are “smallest”.

7.1 When is the nested set complex flag?

For a graphical building set B(G) it has been observed ([Post’05, §8,4], [Zel’06, Corollary 7.4]) that one can replace condition (N2) in Definition 6.4 with a weaker condition:

(N2’) For a disjoint pair of subsets I, J ∈ N, one has I ∪ J ∉ B.

This implies that nested set complexes associated to graphical buildings are flag complexes. More generally, one has the following characterization of the nested set complexes which are flag.

Proposition 7.1. For a building set B, the following are equivalent.

(i) The nested set complex Δ_{B} (or equivalently, the nestohedron P_{B}) is flag.

(ii) The nested sets for B are the subsets N ⊆ B\B_{max} which satisfy conditions (N1) and (N2’).

(iii) If J_{1}, …, J_{ℓ} ∈ B with ℓ ≥ 2 are pairwise disjoint and their union J_{1} ∪ ⋯∪J_{ℓ} is in B, then one can reindex so that for some k with 1 ≤ k ≤ ℓ−1 one has both J_{1} ∪ ⋯ ∪ J_{k} and J_{k+1} ∪ ⋯ ∪ J_{ℓ} in B.

Proof. The equivalence of (i) and (ii) essentially follows from the definitions. We will show here the equivalence of (i) and (iii). Assume that (iii) fails, and let J_{1}, …, J_{ℓ} provide such a failure with ℓ minimal. Note that this means ℓ ≥ 3, and minimality of ℓ forces J_{r} ∪ J_{s} ∉ B for each r ≠ s; otherwise one could replace the two sets J_{r}, J_{s} on the list with the set J_{r} ∪ J_{s} to obtain a counterexample of size ℓ − 1. Therefore all of the pairs {J_{r}, J_{s}} index edges of Δ_{B}, although {J_{1}, …, J_{ℓ}} does not. Hence Δ_{B} is not flag, i.e., (i) fails. Now assume (i) fails, i.e., Δ_{B} is not flag. Let J_{1}, …, J_{ℓ} be subsets in B, for which each pair {J_{r}, J_{s}} with r ≠ s is a nested set, but the whole collection M := {J_{1}, …, J_{ℓ}} is not, and assume that this violation has ℓ minimal. Because {J_{r}, J_{s}} are nested for r ≠ s, it must be that M does satisfy condition (N1), and so M must fail condition (N2). By minimality of ℓ, it must be that the J_{1}, …, J_{ℓ} are pairwise disjoint and their union J_{1} ∪ ⋯ ∪ J_{ℓ} is in B. Bearing in mind that J_{r} ∪ J_{s} ∉ B for r ≠ s, it must be that ℓ ≥ 3. But then M must give a violation of property (iii), else one could use property (iii) to produce a violation of (i) either of size k or of size ℓ − k, which are both smaller than ℓ.

Corollary 7.2. For graphical buildings B(G), the graph-associahedron P_{B(G)} and nested set complex Δ_{B(G)} are flag.

7.2 Stanley-Pitman polytopes and their relatives

One can now use Proposition 7.1 to characterize the inclusion-minimal connected building sets B for which Δ_{B} and P_{B} are flag. For any building set B on [n] with Δ_{B} flag, one can apply Proposition 7.1(iii) with {J_{1}, …, J_{ℓ}} equal to the collection of singletons {{1}, …, {n}}, since they are disjoint and their union [n] is also in B. Thus after reindexing, some initial segment [k] and some final segment [n] \ [k] must also be in B. Iterating this, one can assume after reindexing that there is a plane binary tree τ with these properties

• the singletons {{1}, …, {n}} label the leaves of τ,

• each internal node of τ is labelled by the set I which is the union of the singletons labelling the leaves of the subtree below it (so [n] labels the root node), and

• the building set B contains of all of the sets labelling nodes in this tree.

It is not hard to see that these sets labelling the nodes of τ already comprise a building set B_{τ} which satisfies Proposition 7.1(iii), and therefore give rise to a nested set complex Δ_{B_{τ}} and nestohedron P_{B_{τ}} which are flag. See Figure 1.

Figure 1: A binary tree τ and building set B_{τ}, along with its complex of nested sets Δ_{B_{τ}}, drawn first as in the construction of Remark 6.6, and then redrawn as the boundary of an octahedron.

The previous discussion shows the following.

Proposition 7.3. The building sets B_{τ} parametrized by plane binary trees τ are exactly the inclusion-minimal building sets among those which are connected and have the nested set complex and nestohedron flag.

As a special case, when τ is the plane binary tree having leaves labelled by the singletons and internal nodes labelled by all initial segments [k], one obtains the building set B_{τ} whose nestohedron P_{B_{τ}} is the Stanley-Pitman polytope from [StPi’02]; see [Post’05, §8.5]. The Stanley-Pitman polytope is shown there to be combinatorially (but not affinely) isomorphic to an (n − 1)-cube; the argument given there generalizes to prove the following.

Proposition 7.4. For any plane binary tree τ with n leaves, the nested set complex Δ_{B_{τ}} is isomorphic to the boundary of a (n − 1)-dimensional crosspolytope (hyperoctahedron), and P_{B_{τ}} is combinatorially isomorphic to an (n − 1)-cube.

Proof. Note that the sets labelling the non-root nodes of τ can be grouped into n − 1 pairs {I_{1}, J_{1}}, …, {I_{n−1}, J_{n−1}} of siblings, meaning that I_{k}, J_{k} are nodes with a common parent in τ. One then checks that the nested sets for B_{τ} are exactly the collections N containing at most one set from each pair {I_{k}, J_{k}}. As a simplicial complex, this is the boundary complex of an (n − 1)- dimensional cross-polytope in which each pair {I_{k}, J_{k}} indexes an antipodal pair of vertices.

Note that in this case,

f_{B_{τ}} (t) = (2 + t)^{n−1}, h_{B_{τ}} (t) = (1 + t)^{n−1}, γ_{B_{τ}} (t) = 1 = 1 + 0 · t + 0 · t^{2} + · · · .

which gives a lower bound for the f- and h-vectors of flag nestohedra by Remark 6.8. If one assumes Conjecture 2.3, then it would also give a lower bound for γ-vectors of flag nestohedra (and for flag simplicial polytopes in general). Note that the permutohedron is a graph-associahedron (and hence a flag nestohedra). Therefore, Corollary 4.7 implies that the permutohedron provides the upper bound on the f- and h-vectors among the flag nestohedra.

8 B-trees and B-permutations

This section discusses B-trees and B-permutations, which are two types of combinatorial objects associated with vertices of the nestohedron P_{B}. The h-polynomial of P_{B} equals the descent-generating function for B-trees.

8.1 B-trees and h-polynomials

This section gives a combinatorial interpretation of the h-polynomials of nestohedra. Since nestohedra P_{B} are always simple, one should expect some description of their vertex tree-posets Q_{v} (see Corollaries 3.7 and 3.9) in terms of the building set B. Recall that a rooted tree is a tree with a distinguished node, called its root. One can view a rooted tree T as a partial order on its nodes in which i <_{T} j if j lies on the unique path from i to the root. One can also view it as a directed graph in which all edges are directed towards the root; we will use both viewpoints here. For a node i in a rooted tree T, let T_{≤i} denote the set of all descendants of i, that is j ∈ T_{≤i} if there is a directed path from the node j to the node i. Note that i ∈ T_{≤i}. Nodes i and j in a rooted tree are called incomparable if neither i is a descendant of j, nor j is a descendant of i.

Definition 8.1. [Post’05, Definition 7.7], cf. [FS’05] For a connected building set B on [n], let us define a B-tree as a rooted tree T on the node set [n] such that

(T1) For any i ∈ [n], one has T_{≤i} ∈ B.

(T2) For k ≥ 2 incomparable nodes i_{1}, …, i_{k} ∈ [n], one has ⋃_{j=1}^{k} T_{≤i_{j}} ∉ B.

Note that, when the nested set complex Δ_{B} is flag, that is when B satisfies any of the conditions of Proposition 7.1, one can define a B-tree by requiring condition (T2) only for k = 2.

Proposition 8.2. [Post’05, Proposition 7.8], [FS’05, Proposition 3.17] For a connected building set B, the map sending a rooted tree T to the collection of sets {T_{≤i} |i is a nonroot vertex} ⊂ B gives a bijection between B-trees and maximal nested sets. (Recall that maximal nested sets correspond to the facets of the nested set complex Δ_{B} and to the vertices of the nestohedron P_{B}.) Furthermore, if the B-tree T corresponds to the vertex v of P_{B} then T = Q_{v}, that is, T is the vertex tree-poset for v in the notation of Corollary 3.7.

Question 8.3. Does a simple (indecomposable) generalized permutohedron P come from a (connected) building set if and only if every poset Q_{v} is a rooted tree, i.e. has a unique maximal element?

Proposition 8.2 and Theorem 4.2 yield the following corollary.

Corollary 8.4. For a connected building set B on [n], the h-polynomial of the generalized permutohedron P_{B} is given by

h_{B}(t) = ∑_{T} t^{des(T)},

where the sum is over B-trees T.

The following description of B-trees is straightforward from the definition.

Proposition 8.5. [Post’05, Section 7] Let B be a connected building set on S and let i ∈ S. Let B_{1}, …, B_{r} be the connected components of the restriction B|_{S\{i}}. Then all B-trees with root at i are obtained by picking a B_{j}-tree T_{j}, for each component B_{j}, j = 1, …, r, and connecting the roots of T_{1}, …, T_{r} with the node i by edges.

In other words, each B-tree is obtained by picking a root i ∈ S, splitting the restriction B|_{S\{i}} into connected components, then picking nodes in all connected components, splitting corresponding restrictions into components, etc. Recall Definition 3.1 of the surjection Ψ_{B} := Ψ_{P_{B}}

Ψ_{B} : 𝔖_{n} ⟶ Vertices(P_{B}) = {B-trees},

Here and below one identifies vertices of the nestohedron P_{B} with B-trees via Proposition 8.2. By Corollary 3.9, for a B-tree T, one has Ψ_{B}(w) = T if and only if w is a linear extension of T. Proposition 8.5 leads to an explicit recursive description of the surjection Ψ_{B}.

Proposition 8.6. Let B be a connected building set on [n]. Given a permutation w = (w(1), …, w(n)) ∈ 𝔖_{n}, one recursively constructs a B-tree T = T (w), as follows. The root of T is the node w(n). Let B_{1}, …, B_{r} be the connected components of the restriction B|_{{w(1),...,w(n−1)}}. Restricting w to each of the sets B_{i} gives a subword of w, to which one can recursively apply the construction and obtain a B_{i}-tree T_{i}. Then attach these T_{1}, …, T_{r} as subtrees of the root node w(n) in T. This association w ↦ T (w) is the map Ψ_{B}.

8.2 B-permutations

It is natural to ask for a nice section of the surjection Ψ_{B}; these are the Bpermutations defined next.

Definition 8.7. Let B be a building set on [n]. Define the set 𝔖_{n}(B) ⊂ 𝔖_{n} of B-permutations as the set of permutations w ∈ 𝔖_{n} such that for any i ∈ [n], the elements w(i) and max{w(1), w(2), …, w(i)} lie in the same connected component of the restricted building set B|_{{w(1),...,w(i)}}.

The following construction of B-permutations is immediate from the definition.

Lemma 8.8. A permutation w ∈ 𝔖_{n} is a B-permutation if and only if it can be constructed via the following procedure. Pick w(n) from the connected component of B that contains n; then pick w(n − 1) from the connected component of B|_{[n]\{w(n)}} that contains the maximal element of [n]\{w(n)}; then pick w(n−2) from the connected component of B|_{[n]\{w(n),w(n−1)}} that contains the maximal element of [n] \ {w(n), w(n − 1)}, etc. Continue in this manner until w(1) has been chosen.

Let T be a rooted tree on [n] viewed as a tree-poset where the root is the unique maximal element. The lexicographically minimal linear extension of T is the permutation w ∈ 𝔖_{n} such that w(1) is the minimal leaf of T (in the usual order on ℤ), w(2) is the minimal leaf of T − {w(1)} (the tree T with the vertex w(1) removed), w(3) is the minimal leaf of T − {w(1), w(2)}, etc. There is the following alternative “backward” construction for the lexicographically minimal linear extension of T.

Lemma 8.9. Let w be the lexicographically minimal linear extension of a rooted tree T on [n]. Then the permutation w can be constructed from T, as follows: w(n) is the root of T; w(n − 1) is the root of the connected component of T − {w(n)} that contains the maximal vertex of this forest (in the usual order on ℤ); w(n − 2) is the root of the connected component of T − {w(n), w(n − 1)} that contains the maximal vertex of this forest, etc. In general, w(i) is the root of the connected component of the forest

T − {w(n), …, w(i + 1)}

that contains the vertex max(w(1), …, w(i)).

Proof. The proof is by induction on the number of vertices in T. Let T′ be the rooted tree obtained from T by removing the minimal leaf l. Then the lexicographically minimal linear extension w of T is w = (l, w′), where w′ is the lexicographically minimal linear extension of T′, and both w and w′ are written in list notation. By induction, w′ can be constructed from T′ backwards. When one performs the backward construction for T, the vertex l can never be the root of the connected component of T − {w(n), …, w(i + 1)} containing the maximal vertex, for i > 1. So the backward procedure for T produces the same permutation w = (l, w′).

The next claim gives a correspondence between B-trees and B-permutations.

Proposition 8.10. Let B be a connected building set on [n]. The set 𝔖_{n}(B) of B-permutations is exactly the set of lexicographically minimal linear extensions of the B-trees. (Equivalently, 𝔖_{n}(B) is the set of lexicographically minimal representatives of fibers of the map Ψ_{B}.) In particular, the map Ψ_{B} induces a bijection between B-permutations and Btrees, and 𝔖_{n}(B) is a section of the map Ψ_{B}.

Proof. Let w ∈ 𝔖_{n} be a permutation and let T = T (w) be the corresponding Btree constructed as in Proposition 8.6. Note that, for i = n−1, n−2, …, 1, the connected components of the forest T |_{{w(1),...,w(i)}} = T − {w(n), …, w(i + 1)} correspond to the connected components of the building set B|_{{w(1),...,w(i)}}, and corresponding components have the same vertex sets. According to Lemma 8.9, the permutation w is the lexicographically minimal linear extension of T if and only if w is a B-permutation as described in Lemma 8.8.

9 Chordal building sets and their nestohedra

This section describes an important class of building sets B, for which the descent numbers of B-trees are equal to the descent numbers of B-permutations. In this case, the h-polynomial of the nestohedron P_{B} equals the descentgenerating function of the corresponding B-permutations.

9.1 Descents in posets vs. descents in permutations

A descent of a permutation w ∈ 𝔖_{n} is a pair^{7} (w(i), w(i + 1)) such that w(i) > w(i+1). Let Des(w) be the set of all descents in w. Also recall that the descent set Des(Q) of a poset Q is the set of pairs (a, b) such that a ⋖_{Q} b and a >_{ℤ} b; see Definition 4.1.

Lemma 9.1. Let Q be any poset on [n], and let w = w(Q) be the lexicographically minimal linear extension of Q. Then one has Des(w) ⊆ Des(Q).

Proof. One must show that any descent (a, b) (with a >_{ℤ} b) in w must come from a covering relation a ⋖_{Q} b in the poset Q. Indeed, if a and b are incomparable in Q, then the permutation obtained from w by transposing a and b would be a linear extension of P which is lexicographically smaller than w. On the other hand, if a and b are comparable but not adjacent elements in Q, then they can never be adjacent elements in a linear extension of Q.

In particular, this lemma implies that, for a B-tree T and the corresponding B-permutation w (i.e., w is the lexicographically minimal linear extension of T), one has Des(w) ⊆ Des(T). The rest of this section discusses a special class of building sets for which one always has Des(w) = Des(T).

9.2 Chordal building sets

Definition 9.2. A building set B on [n] is chordal if it satisfies the following condition: for any I = {i_{1} < ⋯ < i_{r}} ∈ B and s = 1, …, r, the subset {i_{s}, i_{s+1}, …, i_{r}} also belongs to B.

Recall that a graph is called chordal if it has no induced k-cycles for k ≥ 4. It is well known [FG’65] that chordal graphs are exactly the graphs that admit a perfect elimination ordering, which is an ordering of vertices such that, for each vertex v, the neighbors of v that occur later than v in the order form a clique. Equivalently, a graph G is chordal if its vertices can be labelled by numbers in [n] so that G has no induced subgraph G|_{{i<j<k}} with the edges (i, j), (i, k) but without the edge (j, k). Let us call such graphs on [n] perfectly labelled chordal graphs.^{8}

Example 9.3. A tree on [n] is called decreasing if the labels decrease in the shortest path from the vertex n (the root) to another vertex. It is easy to see that decreasing trees are exactly the trees which are perfectly labelled chordal graphs. Clearly, any unlabelled tree has such a decreasing labelling of vertices.

The following claim justifies the name “chordal building set.”

7A more standard convention is say that a descent is an index i such that w(i) > w(i+1).

8We can also call them 312-avoiding graphs because they are exactly the graphs that have no induced 3-path a—b—c with the relative order of the vertices a, b, c as in the permutation 312. Note that, unlike the pattern avoidance in permutations, a 312-avoiding graph is the same thing as a 213-avoiding graph.

Documenta Mathematica 13 (2008) 207–273

Proposition 9.4. A graphical building set B(G) is chordal if and only if G is a perfectly labelled chordal graph.

Proof. Suppose that G contains an induced subgraph G|_{{i<j<k}} with exactly two edges (i, j), (i, k). Then {i, j, k} ∈ B(G) but {j, k} ∉ B(G). Thus B(G) is not a chordal building set. On the other hand, suppose that B(G) is not chordal. Then one can find an s and a connected subset I = {i_{1} < ⋯ < i_{r}} of vertices in G such that {i_{s}, i_{s+1}, …, i_{r}} ∉ B(G). In other words, the induced graph G′ = G|_{{i_{s},...,i_{k}}} is disconnected. Let us pick a shortest path P in G|_{{i_{1},...,i_{r}}} that connects two different components of G′. Let i be the minimal vertex in P and let j and k be the two vertices adjacent of i in the path P. Clearly, j > i and k > i. It is also clear that (i, j) is not an edge of G. Otherwise there is a shorter path obtained from P by replacing the edges (i, j) and (i, k) with the edge (j, k). So one has found a forbidden induced subgraph G|_{{i,j,k}}. Thus G is not a perfectly labelled chordal graph.

Proposition 9.5. Let B be a connected chordal building set. Then, for any B-tree T and the corresponding B-permutation w, one has Des(w) = Des(T).

Proof. Let T be a B-tree and let w be the corresponding B-permutation, which can be constructed backward from T as described in Lemma 8.9. Let us fix i ∈ {n−1, n−2, …, 1}. Let T_{1}, …, T_{r}, T′_{1}, …, T′_{s} be the connected components of the forest T −{w(n), w(n−1), …, w(i+1)}, where T_{1}, …, T_{r} are the subtrees whose roots are the children of the vertex w(i + 1), and T′_{1}, …, T′_{s} are the remaining subtrees. Let I = T_{≤w(i+1)} ⊂ [n] be the set of all descendants of w(i + 1) in T. By Definition 8.1(T1), one has I ∈ B. Suppose that the vertex m = max(w(1), …, w(i)) appears in one of the subtrees T_{1}, …, T_{r}, say, in the tree T_{1}. Then, by Lemma 8.9, w(i) should be the root of T_{1}. We claim that all vertices in T_{2}, …, T_{r} are less than w(i + 1). Indeed, this is clear if w(i + 1) is the maximal element in I. Otherwise, the set I′ = I ∩ {w(i + 1) + 1, …, n − 1, n} is nonempty, I′ ∈ B because B is chordal, and I′ contains the maximal vertex m. Since the vertex set J of T_{1} should be an element of B, it follows that I′ ⊆ J. So all vertices of T_{2}, …, T_{r} are less than w(i + 1). Thus none of the edges of T joining the vertex w(i + 1) with the roots of T_{2}, T_{3}, …, T_{r} can be a descent edge. The only potential descent edge is the edge (w(i), w(i+1)) that attaches the subtree T_{1} to w(i+1). This edge will be a descent edge in T if and only if w(i) > w(i+1), i.e., exactly when (w(i), w(i+1)) is a descent in the permutation w. Now suppose that the maximal vertex m = max(w(1), …, w(i)) appears in one of the remaining subtrees T′_{1}, …, T′_{s}, which are not attached to the vertex w(i+1), say, in T′_{1}. In this case w(i+1) should be greater than all w(1), …, w(i). (Otherwise, if w(i + 1) < m, then at the previous step of the backward construction for w, T′_{1} is the connected component of T −{w(n), …, w(i+1)} that contains the vertex max(w(1), …, w(i+1)) = m. So w(i+1) should have been the root of T′_{1}.) In this case, none of the edges joining the vertex w(i + 1) with the components T_{1}, …, T_{r} can be a descent edge and (w(i), w(i + 1)) cannot be a descent in w. This proves that descent edges of T are in bijection with descents in w.

Corollary 8.4 and Proposition 9.5 imply the following formula.

Corollary 9.6. For a connected chordal building set B, the h-polynomial of the nestohedron P_{B} equals

h_{B}(t) = ∑_{w∈𝔖_{n}(B)} t^{des(w)},

where des(w) is the usual descent number of a permutation w ∈ 𝔖_{n}(B).

Let us give an additional nice property of nestohedra for chordal building sets.

Proposition 9.7. For a chordal building set B, the nestohedron P_{B} is a flag simple polytope.

Proof. Let us check that a chordal building set B satisfies the condition in Proposition 7.1(iii). Using the notation of that proposition, let J_{1} ∪ ⋯ ∪ J_{ℓ} = {i_{1} < ⋯ < i_{r}}. Let U_{s} be the union of those subsets J_{1}, ..., J_{ℓ} that have a nonempty intersection with {i_{s}, i_{s+1}, …, i_{r}}. Since {i_{s}, i_{s+1}, …, i_{n}} is in B (because B is chordal), the subset U_{s} should also be in B (by Definition 6.1(B1)). Clearly, U_{1} is the union of all J_{i}’s and U_{r} consists of a single J_{i}. It is also clear that U_{j+1} either equals U_{j} or is obtained from U_{j} by removing a single subset J_{i}. It follows that there exists an index s such that U_{s} = (J_{1} ∪ ⋯ ∪ J_{ℓ}) \ J_{i}. This gives an index i such that (J_{1} ∪ ⋯ ∪ J_{ℓ}) \ J_{i} and J_{i} are both in B, as needed.

10 Examples of nestohedra

Let us give several examples that illustrate Corollary 8.4 and Corollary 9.6. The f- and h-numbers for the permutohedron and associahedron are well-known.

10.1 The permutohedron

For the complete building set B = B(K_{n}) the nestohedron P_{B} is the usual permutohedron; see Example 6.10 and [Post’05, Sect. 8.1]. In this case B-trees are linear orders on [n] and B-permutations are all permutations 𝔖_{n}(B) = 𝔖_{n}. Thus, as noted before in Example 6.10, the h-polynomial is the usual Eulerian polynomial A_{n}(t), and the h-numbers are the Eulerian numbers h_{k}(P_{B}) = A(n, k) := #{w ∈ 𝔖_{n} | des(w) = k}.

10.2 The associahedron

Let G = Path_{n} denote the graph which is a path having n nodes labelled consecutively 1, …, n. The graphical building set B = B(Path_{n}) consists of all intervals [i, j], for 1 ≤ i ≤ j ≤ n. The corresponding nestohedron P_{B(Path_{n})} is the usual Stasheff associahedron; see [CD’06, Post’05]. In this case, the B-trees correspond to unlabelled plane binary trees on n nodes, as follows; see [Post’05, Sect. 8.2] for more details. A plane binary tree is a rooted tree with two types of edges (left and right) such that every node has at most one left and at most one right edge descending from it. From Proposition 8.5, one can see that a B-tree is a binary tree with n nodes labelled 1, 2, …, n so that, for any node, all nodes in its left (resp., right) branch have smaller (resp., bigger) labels. Conversely, given an unlabelled plane binary tree, there is a unique way to label its nodes 1, 2, …, n to create a B-tree, namely in the order of traversal of a depth-first search. Furthermore, note that descent edges correspond to right edges. It is well-known that the number of unlabelled binary trees on n nodes is equal to the Catalan number C_{n} = \frac{1}{n+1} \binom{2n}{n}, and the number of binary trees on n nodes with k − 1 right edges is the Narayana number N(n, k) = \frac{1}{n} \binom{n}{k}\binom{n}{k−1}; see [Stan’99, Exer. 6.19c and Exer. 6.36]. Therefore, the h-numbers of the associahedron P_{B(Path_{n})} are the Narayana numbers: h_{k}(P_{B(Path_{n}})) = N(n, k + 1), for k = 0, …, n − 1. It is also well-known that the f-numbers of the associahedron are f_{k}(P_{B(Path_{n}})) = \frac{1}{n+1} \binom{n−1}{k}\binom{2n−k}{n}. This follows from a classical Kirkman-Cayley formula [Cay’1890] for the number of ways to draw k noncrossing diagonals in an n-gon. In this case, the B-permutations are exactly 312-avoiding permutations w ∈ 𝔖_{n}. Recall that a permutation w is 312-avoiding if there is no triple of indices i < j < k such that w(j) < w(k) < w(i). Thus Corollary 9.6 says that the h-polynomial of the associahedron P_{B(Path_{n})} is ∑_{w} t^{des(w)} where the sum runs over all 312-avoiding permutations in 𝔖_{n}. This is consistent with the known fact that the Narayana numbers count 312-avoiding permutations according to their number of descents; see Simion [Sim’94, Theorem 5.4] for a stronger statement.

10.3 The cyclohedron

If G = Cycle_{n} is the n-cycle, then the nestohedron P_{B(Cycle_{n})} is the cyclohedron or Bott-Taubes polytope; see [CD’06, Post’05]. The h-polynomial of the cyclohedron was computed by Simion [Sim’03, Corollary 1]:

h_{B(Cycle_{n})}(t) = ∑_{k=0}^{n} \binom{n}{k}^{2}t^{k}.  (6)

Note that the n-cycle (for n > 3) is not a chordal graph, so Corollary 9.6 does not apply to this case.

10.4 The stellohedron

Let m = n − 1. Let G = K_{1,m} be the m-star graph with the central node m + 1 connected to the nodes 1, …, m. Let us call the associated polytope P_{B(K_{1,m})} the stellohedron. From Proposition 8.5 one sees that B(K_{1,m})-trees are in bijection with partial permutations of [m], which are ordered sequences u = (u_{1}, …, u_{r}) of distinct numbers in [m], where r = 0, …, m. The tree T associated to a partial permutation u = (u_{1}, …, u_{r}) has the edges

(u_{r}, u_{r−1}), …, (u_{2}, u_{1}), (u_{1}, m + 1), (m + 1, i_{1}), …, (m + 1, i_{m−r})

where i_{1}, …, i_{m−r} are the elements of [m] \ {u_{1}, …, u_{r}}. The root of T is u_{r} if r ≥ 1, or m + 1 if r = 0. For r ≥ 1, one has des(T) = des(u) + 1, where the descent number of a partial permutation is

des(u) := #{i = 1, …, r − 1 | u_{i} > u_{i+1}}.

Also for the tree T associated with the empty partial permutation (for r = 0) one has des(T) = 0. Corollary 8.4 then says that

h_{B(K_{1,m})}(t) = 1 + ∑_{u} t^{des(u)+1} = 1 + ∑_{r=1}^{m} \binom{m}{r} ∑_{k=1}^{r} A(r, k) t^{k},  (7)

where the first sum is over nonempty partial permutations w of [m]. In particular, the total number of vertices of the stellohedron P_{B(K_{1,m})} equals

f_{0}(P_{B(K_{1,m})}) = ∑_{r=0}^{m} \binom{m}{r} · r! = ∑_{r=0}^{m} \frac{m!}{r!}.

This sequence appears in [Sloa] as A000522. In this case, B(K_{1,m})-permutations are permutations w ∈ 𝔖_{m+1} such that m + 1 appears before the first descent. Such permutations w are in bijection with partial permutations u of [m]. Indeed, u is the part of w after the entry m + 1. Since our labelling of K_{1,m} (with the central node labelled m + 1) is decreasing (see Example 9.3), Corollary 9.6 implies that the h-polynomial of the stellohedron P_{B(K_{1,m})} is h(t) = ∑_{w} t^{des(w)}, where the sum runs over all such permutations w ∈ 𝔖_{m+1}. This agrees with the above expression in terms of partial permutations.

10.5 The Stanley-Pitman polytope

Let B_{PS} = {[i, n], {i} | i = 1, …, n}, the collection of all intervals [i, n] and singletons {i}. This (non-graphical) building set is chordal. According to [Post’05, §8.5], the corresponding nestohedron P_{B_{PS}} is the Stanley-Pitman polytope from [StPi’02].

By Proposition 8.5, B_{PS}-trees have the following form T (I). For an increasing sequence I of positive integers i_{1} < i_{2} < ⋯ < i_{k} = n, construct the tree T (I) on [n] with the root at i_{1} and the chain of edges (i_{1}, i_{2}), (i_{2}, i_{3}), …, (i_{k−1}, i_{k}); also, for each j ∈ [n]\I, one has the edge (i_{l}, j) where i_{l} is the minimal element of I such that i_{l} > j. In this case, B_{PS}-permutations are permutations w ∈ 𝔖_{n} such that w(1) < w(2) < ⋯ < w(k) > w(k + 1) > ⋯ > w(n), for some k = 1, …, n. Using B_{PS}-trees or B_{PS}-permutations one can easily deduce that the hpolynomial of the Stanley-Pitman polytope is h_{B_{PS}}(t) = (1 + t)^{n−1}. This is not surprising since P_{B_{PS}} is combinatorially isomorphic to the (n − 1)-dimensional cube.

11 γ-vectors of nestohedra

Recall that the γ-vector (γ_{0}, γ_{1}, …, γ_{⌊d/2⌋}) of a d-dimensional simple polytope is defined via its h-polynomial as h(t) = ∑ γ_{i} t^{i}(1+t)^{d−2i}; and the γ-polynomial is γ(t) = ∑ γ_{i} t^{i}; see Section 2.3. The main result of this section is a formula for the γ-polynomial of a chordal nestohedron as a descent-generating function (or peak-generating function) for some set of permutations. This implies that Gal’s conjecture (Conjecture 2.3) holds for this class of flag simple polytopes. To prove this, we will employ a certain combinatorial approach that goes back to work of Shapiro, Woan, and Getu [SWG’83], also used by Foata and Strehl, and more recently by Bränden; see [Brä’06] for a thorough discussion. Suppose P is a simple polytope and one has a combinatorial formula for the h-polynomial h_{P} (t) = ∑_{a∈A} t^{f(a)}, where f(a) is some statistic on the set A. Suppose further that one has a partition of A into f-symmetric Boolean classes, i.e. such that the f-generating function for each class is t^{r}(1 + t)^{2n−r} for some r. Let Â ⊂ A be the set of representatives of the classes where f(a) takes its minimal value. Then the γ-polynomial equals γ_{P} (t) = ∑_{a∈Â} t^{f(a)}. Call f(a) a “generalized descent-statistic.” Additionally, define

peak(a) = min{f(b) | a and b in the same class} + 1

and call it a “generalized peak statistic.”

11.1 A warm up: γ-vector for the permutohedron

We review here the beautiful construction of Shapiro, Woan, and Getu [SWG’83] that leads to a nonnegative formula for the γ-vector of the usual permutohedron. This subsection also serves as a warm-up for a more general construction in the following subsection. Some notation is necessary. Recall that a descent in a permutation w ∈ 𝔖_{n} is a pair (w(i), w(i + 1)) such that w(i) > w(i + 1), where i ∈ [n − 1]. A final descent is when w(n − 1) > w(n), and a double descent is a pair of consecutive descents, i.e. a triple w(i) > w(i + 1) > w(i + 2).

Additionally, define a peak of w to be an entry w(i) for 1 ≤ i ≤ n such that w(i − 1) < w(i) > w(i + 1). Here (and below) set w(0) = w(n + 1) = 0 and so a peak can occur in positions 1 or n. On the other hand, a valley of w is an entry w(i) for 1 < i < n such that w(i − 1) > w(i) < w(i + 1). The peak-valley sequence of w is the subsequence in w formed by all peaks and valleys. Let 𝔖̂_{n} denote the set of permutations in 𝔖_{n} which do not contain any final descents or double descents. Let peak(w) denote the number of peaks in a permutation w. It is clear that peak(w)−1 = des(w), for permutations w ∈ 𝔖̂_{n} (and only for these permutations).

Theorem 11.1. (cf. [SWG’83, Proposition 4]) The γ-polynomial of the usual permutohedron P_{B(K_{n})} is

∑_{w∈𝔖̂_{n}} t^{peak(w)−1} = ∑_{w∈𝔖̂_{n}} t^{des(w)}.

Example 11.2. Let us calculate the γ-polynomial of the two dimensional permutohedron P_{B(K_{3})}. One has 𝔖̂_{3} = {(1, 2, 3), (2, 1, 3), (3, 1, 2)}. Of these, (1, 2, 3) has one peak (and no descents), and (2, 1, 3) and (3, 1, 2) have two peaks (and one descent). Therefore, the γ-polynomial is 1 + 2t.

Say that an entry w(i) of w is an intermediary entry if w(i) is not a peak or a valley. Say that w(i) is an ascent-intermediary entry if w(i − 1) < w(i) < w(i+1) and that it is a descent-intermediary entry if w(i−1) > w(i) > w(i+1). (Here again one should assume that w(0) = w(n+1) = 0.) Note that the set 𝔖̂_{n} is exactly the set of permutations in 𝔖_{n} without descent-intermediary entries. It is convenient to graphically represent a permutation w ∈ 𝔖_{n} by a piecewise linear “mountain range” M_{w} obtained by connecting the points (x_{0}, 0), (x_{1}, w(1)), (x_{2}, w(2)), …, (x_{n}, w(n)), (x_{n+1}, 0) on ℝ^{2} by straight line intervals, for some x_{0} < x_{1} < ⋯ < x_{n+1}; see Figure 2. Then peaks in w correspond to local maxima of M_{w}, valleys correspond to local minima of M_{w}, ascent-intermediary entries correspond to nodes on ascending slopes of M_{w}, and descent-intermediary entries correspond to nodes on descending slopes of M_{w}. For example, the permutation w = (6, 5, 4, 10, 8, 2, 1, 7, 9, 3) shown in Figure 2 has three peaks 6, 10, 9, two valleys 4, 1, one ascent-intermediary entry 7, and four descent-intermediary entries 5, 8, 2, 3. Its peak-valley sequence is (6, 4, 10, 1, 9). As noted in Section 4.1, the h-polynomial of the permutohedron is the descentgenerating function for permutations in 𝔖_{n} (the Eulerian polynomial). In order to prove Theorem 11.1, one constructs an appropriate partitioning of 𝔖_{n} into equivalence classes, where each class has exactly one element from 𝔖̂_{n}. To describe the equivalence classes of permutations, one must introduce some operations on permutations.

Definition 11.3. Let us define the leap operations L_{a} and L_{a}^{−1} that act on permutations. Informally, the permutation L_{a}(w) is obtained from w by moving

Figure 2: Mountain range M_{w} for w = (6, 5, 4, 10, 8, 2, 1, 7, 9, 3)

an intermediary node a on the mountain range M_{w} directly to the right until it hits the next slope of M_{w}. The permutation L_{a}^{−1}(w) is obtained from w by moving a directly to the left until it hits the next slope of M_{w}. More formally, for an intermediary entry a = w(i) in w, the permutation L_{a}(w) is obtained from w by removing a from the i-th position and inserting a in the position between w(j) and w(j + 1), where j is the minimal index such that j > i and a is between w(j) and w(j + 1), i.e., w(j) < a < w(j + 1) or w(j) > a > w(j + 1). The leap operation L_{a} is not defined if all entries following a in w are less than a. Similarly, the inverse operation L_{a}^{−1}(w) is given by removing a from the ith position in w and inserting a between w(k) and w(k + 1), where k is the maximum index such that k < i and a is between w(k) and w(k + 1). The operation L_{a}^{−1} is is not defined if all entries preceding a in w are less than a.

For example, for the permutation w shown on Figure 2, one has L_{2}(w) = (6, 5, 4, 10, 8, 1, 2, 7, 9, 3) and L_{2}^{−1}(w) = (2, 6, 5, 4, 10, 8, 1, 7, 9, 3). Clearly, if a is an ascent-intermediary entry in w then a is a descentintermediary entry in L_{a}^{±1}(w), and vice versa. Note that if a is an ascentintermediary entry in w, then L_{a}(w) is always defined, and if a is a decentintermediary entry, then L_{a}^{−1}(w) is always defined.

Definition 11.4. Let us also define the hop operations H_{a} on permutations. For an ascent-intermediary entry a in w, define H_{a}(w) = L_{a}(w); and, for a descent-intermediary entry a in w, define H_{a}(w) = L_{a}^{−1}(w).

For example, for the permutation w shown on Figure 2, the permutation H_{2}(w) = (2, 6, 5, 4, 10, 8, 1, 7, 9, 3) is obtained by moving the descentintermediary entry 2 to the left to the first ascending slope, and H_{7}(w) = (6, 5, 4, 10, 8, 2, 1, 9, 7, 3) is obtained by moving the ascent-intermediary entry 7 to the right to the last descending slope. Note that leaps and hops never change the shape of the mountain range M_{w}, that is, they never change the peak-valley sequence of w. They just move intermediary nodes from one slope of M_{w} to another. It is quite clear from the definition that all leap and hop operations pairwise commute with each other. It is also clear that two hops H_{a} get us back to the original permutation.

Lemma 11.5. For intermediary entries a and b in w, one has (H_{a})^{2}(w) = w and H_{a}(H_{b}(w)) = H_{b}(H_{a}(w)).

Thus the hop operations H_{a} generate the action of the group (ℤ/2ℤ)^{m} on the set of permutations with a given peak-valley sequence, where m is the number of intermediary entries in such permutations. We say that two permutations are hop-equivalent if they can be obtained from each other by the hop operations H_{a} for various a’s. The partitioning of 𝔖_{n} into hop-equivalence classes allows us to prove Theorem 11.1.

Proof of Theorem 11.1. The number des(w) of descents in w equals the number of peaks in w plus the number of descent-intermediary entries in w minus 1 (because the last entry is either a peak or a descent-intermediary entry, but it does not contribute a descent). Notice that if a is an ascent-intermediary (resp., descent-intermediary) entry in w then the number of descent-intermediary entries in H_{a}(w) increases (resp., decreases) by 1 and the number of peaks does not change. If w ∈ 𝔖_{n} has p = peak(w) peaks then it has p − 1 valleys and n − 2p + 1 intermediary entries. Lemma 11.5 implies that the hop-equivalence class C of w involves 2^{n−2p+1} permutations. Moreover, the descent-generating function for these permutations is ∑_{u∈C} t^{des(u)} = t^{p}(t+1)^{n−2p+1}. Each hop-equivalence class has exactly one representative u without descent-intermediary entries, that is u ∈ 𝔖̂_{n}. Thus, summing the contributions of hop-equivalence classes, one can write the h-polynomial of the permutohedron as

h(t) = ∑_{w∈𝔖_{n}} t^{des(w)} = ∑_{w∈𝔖̂_{n}} t^{peak(w)−1}(t + 1)^{n+1−2 peak(w)}.

Comparing this to the definition of the γ-polynomial, one derives the theorem.

11.2 γ-vectors of chordal nestohedra

According to Proposition 9.7, nestohedra for chordal building sets are flag simple polytopes. Thus Gal’s conjecture (Conjecture 2.3) applies. This section proves this conjecture and presents a nonnegative combinatorial formula for γpolynomials of such nestohedra as peak-generating functions for some subsets of permutations. Let B be a connected chordal building set on [n]. Recall that 𝔖_{n}(B) is the set of B-permutations; see Definition 8.7. Let 𝔖̂_{n}(B) := 𝔖_{n}(B) ∩ 𝔖̂_{n} be the subset of B-permutations which have no final descent or double descent. The following theorem is the main result of this section.

Theorem 11.6. For a connected chordal building B on [n], the γ-polynomial of the nestohedron P_{B} is the peak-generating function for the permutations in 𝔖̂_{n}(B):

γ_{B}(t) = ∑_{w∈𝔖̂_{n}(B)} t^{peak(w)−1} = ∑_{w∈𝔖̂_{n}(B)} t^{des(w)}.

As noted earlier, peak(w) − 1 = des(w) for w ∈ 𝔖̂_{n}. The proof of Theorem 11.6 will be an extension of the proof given for the γ-vector of the permutohedron in Section 11.1. Recall that Corollary 9.6 interprets the h-polynomial of P_{B} as the descent-generating function for Bpermutations w ∈ 𝔖_{n}(B). Theorem 11.6 will be proven by constructing an appropriate partitioning of the set 𝔖_{n}(B) into equivalence classes, where each equivalence class has exactly one representative from 𝔖̂_{n}(B). As before, one uses (suitably generalized) hop operations to describe equivalence classes of elements of 𝔖_{n}(B). One needs powers of the leap operations L_{a}^{r} := (L_{a})^{r}, for r ≥ 0, and L_{a}^{r} := (L_{a}^{−1})^{−r}, for r ≤ 0; see Definition 11.3. In other words, for r > 0, L_{a}^{r}(w) is obtained from w by moving the intermediary entry a to the right until it hits the r-th slope from its original location; and, for r < 0, by moving a to the left until it hits (−r)-th slope from its original location. Clearly, L_{a}^{r}(w) is defined whenever r is in a certain integer interval r ∈ [r_{min}, r_{max}]. It is also clear that, if a is an ascent-intermediary entry in w, then a is ascent-intermediary in L_{a}^{r}(w) for even r and a is descent-intermediary in L_{a}^{r}(w) for odd r, and vice versa if a is descent-intermediary in w. Note that for a B-permutation w ∈ 𝔖_{n}(B), the permutations L_{a}^{r}(w) may no longer be B-permutations. The next lemma ensures that at least some of them will be B-permutations.

Lemma 11.7. Let B be a chordal building on [n]. Suppose that w ∈ 𝔖_{n}(B) is a B-permutation.

(1) If a is an ascent-intermediary letter in w, then there exists an odd positive integer r > 0 such that L_{a}^{r}(w) ∈ 𝔖_{n}(B) and L_{a}^{s}(w) ∉ 𝔖_{n}(B), for all 0 < s < r.

(2) If a is a descent-intermediary letter in w, then there exists an odd negative integer r < 0 such that L_{a}^{r}(w) ∈ 𝔖_{n}(B) and L_{a}^{s}(w) ∉ 𝔖_{n}(B), for all 0 > s > r.

The proof of Lemma 11.7 will require some preparatory notation and observations. For a permutation w ∈ 𝔖_{n} and a ∈ [n] such that w(i) = a, let

{w ↖a} := {w(j) | j ≤ i, w(j) ≥ a}

be the set of all entries in w which are located to the left of a and are greater than or equal to a (including the entry a itself). The arrow in this notation refers to our graphical representation of a permutation as a mountain range M_{w}: the set {w ↖a} is the set of entries in w located to the North-West of the entry a.

According to Definition 8.7, the set 𝔖_{n}(B) is the set of permutations w such that, for i = 1, …, n, there exists I ∈ B such that both w(i) and max(w(1), …, w(i)) are in I and I ⊂ {w(1), …, w(i)}. If B is chordal, then I′ := I ∩ [w(i), ∞] also belongs to B (see Definition 9.2) and satisfies the same properties. Clearly max(w(1), …, w(i)) = max{w ↖w(i)}. Thus, for a chordal building set, one can reformulate Definition 8.7 of B-permutations as follows.

Lemma 11.8. Let B be a chordal building set. Then 𝔖_{n}(B) is the set of permutations w ∈ 𝔖_{n} such that for any a ∈ [n], the elements a and max{w ↖a} are in the same connected component of B|_{{w ↖a}}. Equivalently, there exists I ∈ B such that a ∈ I, max{w ↖a} ∈ I, and I ⊂ {w ↖a}.

Let us now return to the setup of Lemma 11.7. There are 2 possible reasons why the permutation u = L_{a}^{r}(w) may no longer be a B-permutation, that is, fail to satisfy the conditions in Lemma 11.8:

(A) It is possible that the entry a and the entry max{u ↖a} are in different connected components of B|_{{u ↖a}}.

(B) It is also possible that another entry b ≠ a in u and max{u ↖b} are in different connected components of B|_{{u ↖b}}.

Let us call these two types of failure A-failure and B-failure. The following auxiliary result is needed.

Lemma 11.9. Let us use the notation of Lemma 11.7.

(1) For left leaps u = L_{a}^{r}(w), r < 0, one can never have a B-failure.

(2) For the maximal left leap u = L_{a}^{r_{min}}(w), where the entry a goes all the way to the left, one cannot have an A-failure.

(3) For the maximal right leap u = L_{a}^{r_{max}}(w), where the entry a goes all the way to the right, one cannot have an A-failure.

(4) Let u = L_{a}^{r}(w) and u′ = L_{a}^{r+1}(w), for r ∈ ℤ, be two adjacent leaps such that a is descent-intermediary in u (and, thus, a is ascent-intermediary in u′). Then there is an A-failure in u if and and only if there is an A-failure in u′.

Proof. (1) Since w ∈ 𝔖_{n}(B), there is a subset I ∈ B that contains both b and max{w ↖b} and such that I ⊂ {w ↖b}. The same subset I works for u because {u ↖b} = {w ↖b} or {u ↖b} = {w ↖b} ∪ {a}.

(2) In this case, a is greater than all preceding entries in u, so a = max{u ↖a}.

(3) In this case, a is greater than all following entries in u. The interval I = [a, n] contains both a and max{u ↖a}, I ⊂ {u ↖a}, and I ∈ B because B is chordal.

(4) In this case, all entries between the position of a in u and the position of a in u′ are less than a. Thus {u ↖a} = {u′ ↖a}. So u has an A-failure if and only if u′ has an A-failure.

Proof of Lemma 11.7. It is easier to prove the second part of the lemma.

(2) By parts (1) and (2) of Lemma 11.9, there exists a negative r such that L_{a}^{r}(w) ∈ 𝔖_{n}(B). Let us pick such an r with minimal possible absolute value. Then r should be odd, by part (4) of Lemma 11.9, which proves (2).

(1) Suppose that there is an entry b ≠ a in the permutation w such that b and m = max{w ↖b} are in different connected components of B|_{{w ↖b}\{a}}. In this case, a ∈ {w ↖b}, that is b < a and b is located to the right of a in w. (Otherwise, b and m are in different connected components of B|_{{w ↖b}}, which is impossible because w is a B-permutation.) Let us pick the leftmost entry b in w that satisfies this condition. Then the permutation u = L_{a}^{r}(w) has a B-failure if the letter a moves to the right of this entry b; and u has no B-failure if a stays to the left of b. By our assumptions, a stays to the left of b in L_{a}^{1}(w), so such a u exists. Let u = L_{a}^{r}(w) be the maximal right leap (i.e., with maximal r > 0) such that the entry a stays to the left of b. Then all entries in u between the positions of a and b should be less than a. Thus m = max{u ↖a} = max{w ↖b}. Since w ∈ 𝔖_{n}(B), there is an I ∈ B such that b, m ∈ I and I ⊂ {w ↖b}. This subset I should also contain the entry a. (Otherwise, b and m would be in the same connected component B|_{{w ↖b}\{a}}, contrary to our choice of b.) Thus I′ := I ∩ [a, +∞] ∈ B contains both a and m and I′ ⊂ {u ↖a}. This means that there is no A-failure in u. Thus u ∈ 𝔖_{n}(B). If there is no entry b in w as above, then none of the permutations L_{a}^{r}(w) has a B-failure. In this case L_{a}^{r_{max}}(w) ∈ 𝔖_{n}(B) by part (3) of Lemma 11.9. In all cases, there exists a positive r such that L_{a}^{r}(w) ∈ 𝔖_{n}(B) and only Afailures are possible in L_{a}^{s}(w), for 0 < s < r. Let us pick the minimal such r. Then r should be odd by part (4) of Lemma 11.9, as needed.

Definition 11.10. Let us define the B-hop operations BH_{a}. For a Bpermutation w with an ascent-intermediary (resp., descent-intermediary) entry a, the permutation BH_{a}(w) is the right leap u = L_{a}^{r}(w), r > 0 (resp., the left leap u = L_{a}^{r}(w), r < 0) with minimal possible |r| such that u is a B-permutation. Informally, BH_{a}(w) is obtained from w by moving the node a on its mountain range M_{w} directly to the right if a is ascent-intermediary in w, or directly left if a is descent-intermediary in w (possibly passing through several slopes) until one hits a slope and obtain a B-permutation.

Lemma 11.7 says that the B-hop BH_{a}(w) is well-defined for any intermediary entry a in w. It also says that if a is ascent-intermediary in w then a is descentintermediary in BH_{a}(w), and vice versa. Moreover, according to that lemma, (BH_{a})^{2}(w) = w.

Example 11.11. Let G be the decreasing tree shown on Figure 3. Then the graphical building B = B(G) is chordal; see Example 9.3. Figure 3 shows several B-hops of the B-permutation w = (1, 10, 8, 3, 6, 9, 7, 4, 12, 11, 5, 2):

BH_{1}(w) = L_{1}(w) = (10, 8, 3, 6, 9, 7, 4, 12, 11, 5, 2, 1),
BH_{5}(w) = (L_{5})^{−5}(w) = (1, 5, 10, 8, 3, 6, 9, 7, 4, 12, 11, 2),
BH_{6}(w) = L_{6}(w) = (1, 10, 8, 3, 9, 7, 6, 4, 12, 11, 5, 2).

Figure 3: A B(G)-permutation w and some B-hops

Let us now show that the B-hop operations pairwise commute with each other.

Lemma 11.12. Let a and b be two intermediary entries in a B-permutation w. Then BH_{a}(BH_{b}(w)) = BH_{b}(BH_{a}(w)).

Proof. Let us first assume that both a and b are descent-intermediary entries in w. Without loss of generality assume that a > b. In this case BH_{a}(w) = L_{a}^{r}(w) and BH_{b}(w) = L_{b}^{s}(w) for some negative odd r and s, that is the entries a and b of w are moved to the left. According to Lemma 11.9(1), in this case one does not need to worry about B-failures. In other words, BH_{a}(w) is the first left leap L_{a}^{r}(w) (i.e., with minimal −r > 0) that has no A-failure. Similarly, BH_{b}(w) is the first left leap L_{b}^{s}(w) without A-failures (where A-failures concern the entry b). Since A-failures for permutations u = L_{a}^{t}(w), t < 0, are described in terms of the set {u ↖a} ⊂ [a, ∞], moving the entry b < a in w will have no effect on these A-failures. Thus, for the permutation w′ = BH_{b}(w), one has BH_{a}(w′) = L_{a}^{r}(w′) with exactly the same r as in BH_{a}(w) = L_{a}^{r}(w). However, for permutations u = L_{b}^{t}(w), t < 0, the sets {u ↖b} might change if one first performs the operation BH_{a} to w. Namely, let w̃ = BH_{a}(w) and ũ = L_{b}^{t}(w̃) = L_{b}^{t}(L_{a}^{r}(w)). Then {ũ ↖b} = {u ↖b} ∪ {a} if a is located to the left of b in ũ and a is located to the right of b in u (and {ũ ↖b} = {u ↖b} otherwise). Notice that one always has m = max{u ↖b} = max{ũ ↖b}, since this maximum is the maximal peak preceding b in u (or in ũ), and leaps and hops have no affect on the peaks. If b and m are in the same connected component of B|_{{u ↖b}} then they are also in the same connected component of B|_{{ũ ↖b}}, that is if there is no A-failure for u then there is no A-failure for ũ. Suppose that there is no A-failure for ũ but there is an A-failure for u. Then the sets {u ↖b} and {ũ ↖b} have to be different. That means that a is located to the left of b in ũ and a is located to the right of b in u. Let I be the element I ∈ B such that b, m ∈ I and I ⊂ {ũ ↖b}. Then I should contain the entry a. (Otherwise, I ⊂ {u ↖b} and there would be no A-failure for u.) Let ŵ = Lt̂ ; a(w) be the left leap with maximal possible −t̂ ≥ 0 such that the position of a in ŵ is located to the right of the position of b in ũ. Since ũ = L_{b}^{t}(L_{a}^{r}(w)), it follows that |t̂| < |r|. In other words, if one starts moving to the right from the node b along the mountain range Mũ, the (ascending) slope that first crosses the level a is the place where the entry a is located in ŵ. Note that t̂ is odd because a should be an ascent-intermediary entry in ŵ; in particular t̂< 0. Since all entries in ŵ located between the position of b in ũ and the position of a in ŵ are less than a, one deduces that {ũ ↖b} ∩ [a, ∞] = {ŵ ↖a}. Thus the subset Î = I ∩ [a, ∞] has three important properties: it lies in B (because B is chordal); it contains both a and m = max{ŵ ↖a}; and it is a subset of {ŵ ↖a}. It follows that there is no A-failure in ŵ. This contradicts the fact that L_{a}^{r}(w) ≠ Lt̂ ; a(w) is the first left leap that has no A-failure. Thus u has an A-failure if and only if ũ has an A-failure. It follows that BH_{b}(w̃) = L_{b}^{s}(w̃) with exactly the same s as in BH_{b}(w) = L_{b}^{s}(w). This proves that BH_{a}(BH_{b}(w)) = L_{a}^{r}(L_{b}^{s}(w)) = L_{b}^{s}(L_{a}^{r}(w)) = BH_{b}(BH_{a}(w)), in the case when both a and b are descent-intermediary in w. Let us now show that the general case easily follows. Suppose that, say, a is ascent-intermediary and b is descent-intermediary in w. Then, for w′′ = BH_{a}(w) both a and b are descent-intermediary. One has BH_{a}(BH_{b}(w′′)) = BH_{b}(BH_{a}(w′′)). Thus BH_{a}(BH_{b}(BH_{a}(w))) = BH_{b}(BH_{a}(BH_{a}(w))) = BH_{b}(w). Applying BH_{a} to both sides, one deduces BH_{b}(BH_{a}(w)) = BH_{a}(BH_{b}(w)). The other cases are similar.

Thus the B-hop operations BH_{a} generate the action of the group (ℤ/2ℤ)^{m} on the set of B-permutations with a given peak-valley sequence, where m is the number of intermediary entries in such permutations. We say that two B-permutation are B-hop-equivalent if they can be obtained from each other by the B-hop operations BH_{a} for various a’s. This gives the partitioning of the set of B-permutations into B-hop-equivalence classes. One can now prove Theorem 11.6 by literally repeating the argument in the proof of Theorem 11.1.

Proof of Theorem 11.6. For a B-permutation w ∈ 𝔖_{n}(B) with p = peak(w), the descent-generating function of the B-hop-equivalence class C of w is ∑_{u∈C} t^{des(u)} = t^{p}(t + 1)^{n−2p+1}. Each B-hop-equivalence class has exactly one representative without descent-intermediary entries, that is, in the set 𝔖̂_{n}(B). Thus the h-polynomial of the nestohedron P_{B} (see Corollary 9.6) is

h_{P_{B}}(t) = ∑_{w∈𝔖_{n}(B)} t^{des(w)} = ∑_{w∈𝔖̂_{n}(B)} t^{peak(w)−1}(t + 1)^{n+1−2 peak(w)}.

Comparing this to the definition of the γ-polynomial, one derives the theorem.

Corollary 11.13. Gal’s conjecture holds for all graph-associahedra corresponding to chordal graphs.

11.3 γ-vectors for the associahedron and cyclohedron

In Propositions 11.14 and 11.15 we give two explicit formulas which can be derived from the expressions for the corresponding h-polynomials (see Sections 10.2 and 10.3) using standard quadratic transformations of hypergeometric series; e.g., see [RSW’03, Lemma 4.1].

Proposition 11.14. The γ-polynomial of the associahedron P_{B(Path_{n})} is

γ(t) = ∑_{r=0}^{⌊ \frac{n−1}{2} ⌋} C_{r}\binom{n − 1}{2r} t^{r},

where C_{r} = \frac{1}{r+1} \binom{2r}{r} is the r-th Catalan number.

Proposition 11.15. The γ-polynomial of the cyclohedron P_{B(Cycle_{n})} is

γ(t) = ∑_{r=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{r, r, n − 2r} t^{r},

We now give three combinatorial proofs of Proposition 11.14 as an alternative to using hypergeometric series.

First proof of Proposition 11.14. It is known that the Narayana polynomial which is the h-polynomial of P_{B(Path_{n})} is also the rank generating function for the well-studied lattice of noncrossing partitions NC(n). An explicit symmetric chain decomposition for NC(n) was given by Simion and Ullman [SU’91], who actually produced a much stronger decomposition of NC(n) into disjoint Boolean intervals placed symmetrically about the middle rank(s) of NC(n). Their decomposition contains exactly C_{r} \binom{n−1}{2r} such Boolean intervals of rank n − (2r + 1) for each r = 0, 1, …, \frac{n−1}{2}, which immediately implies the formula for the γ-polynomial; see [SU’91, Corollary 3.2].

Second proof of Proposition 11.14. By Section 10.2, the h-polynomial of P_{B(Path_{n})} counts plane binary trees on n nodes according to their number of right edges. There is a natural map from binary trees to full binary trees, i.e., those in which each node has zero or two children: if a node has a unique child, contract this edge from the node to its child. If the original binary tree T has n nodes, then the resulting full binary tree T′ will have 2r + 1 nodes, 2r edges and r right edges for some r = 0, 1, …, ⌊(n − 1)/2⌋. There are C_{r} such full binary trees for each r. Given such a full binary tree T′, one can produce all of the binary trees in its preimage by inserting n − (2r + 1) more nodes and deciding if they create left or right edges. One chooses the locations of these nodes from 2r + 1 choices, either an edge of the full binary tree they will subdivide or located above the root, giving \binom{n−(2r+1)+(2r+1)−1}{n−(2r+1)} = \binom{n−1}{2r} possible locations. Thus the generating function with respect to the number of right edges for the preimage of T′ is \binom{n−1}{2r} t^{r}(t + 1)^{n−(2r+1)}, where the term t^{r}(t + 1)^{n−(2r+1)} comes from choosing whether each of the new nodes creates a left or a right edge. It follows that the generating function for all binary trees on n nodes is h_{Path_{n}}(t) = ∑_{r} C_{r} \binom{n−1}{2r} t^{r}(t + 1)^{n−(2r+1)}, where C_{r} counts full binary trees. This implies the needed expression for the γ-vector of the associahedron P_{B(Path_{n})}. Equivalently, one can describe the subdivision of all binary trees into classes where two binary trees are in the same class if they can be obtained from each other by switches of left and right edges coming from single child nodes. Then one gets exactly C_{r}\binom{n−1}{2r} classes having t^{r}(t+1)^{n−(2r+1)} as its generating function counting number of right edges, for each r = 0, 1, …, ⌊(n − 1)/2⌋.

Third proof of Proposition 11.14. This proof is based on our general approach to γ-vectors of chordal nestohedra. According to Section 10.2, B-permutations for the associahedron are 312-avoiding permutations and h-polynomial is equal to the sum h_{P_{B(Pathn)}}(t) = ∑_{w} q^{peak(w)−1} over all 312-avoiding permutations w ∈ 𝔖_{n}. By Theorem 11.6, γ_{r}(P_{B(Path_{n})}) equals the number of 312-avoiding permutations with no descent-intermediary elements and r + 1 peaks. The (flattenings of) peak-valley sequences of such permutations are exactly 312avoiding alternating permutations in 𝔖_{2r+1}, that is 312-avoiding permutations w′ such that w′_{1} > w′_{2} < w′_{3} > ⋯ < w′_{2r+1}. It is known that the number of such permutations equals the Catalan number C_{r}; see [Man’02, Theorem 2.2]. Then there are \binom{n−1}{2r} ways to insert the remaining n − (2r + 1) descent-intermediary elements.

12 Graph-associahedra for single branched trees

Our goal in this section is to compute a generating function that computes the h-polynomials of all graph-associahedra in which the graph is a tree having at most one branched vertex (i.e., a vertex of valence 3 or more).

12.1 Associahedra and Narayana polynomials

First recall (see Section 10.2) that the h-numbers of the associahedron P_{B(Path_{n})} are the Narayana numbers h_{k}(P_{B(Path_{n})}) = N(n, k) := \frac{1}{n} \binom{n}{k}\binom{n}{k−1}, and the hpolynomial of the associahedron is the Narayana polynomial:

h_{B(Path_{n})}(t) = C_{n}(t) := ∑_{k=1}^{n} N(n, k) t^{k−1}.  (8)

Recall the well-known recurrence and generating function for the Narayana polynomials C_{n}(t). The recurrence in Theorem 6.12 for the f-polynomials f_{B(Path_{n})}(t) = h_{B(Path_{n})}(t + 1) = C_{n}(t + 1) can be written as follows. When one removes k vertices from the n-path, it splits into k + 1 (possibly empty) paths. So one obtains

C_{n}(t) = ∑_{k≥1}(t − 1)^{k−1} ∑_{m_{1}+···+m_{k+1}=n−k} C_{m_{1}}(t) ⋯ C_{m_{k+1}}(t), for n ≥ 1, (9)

where the sum is over m_{1}, …, m_{k+1} ≥ 0 such that ∑ m_{i} = n − k. Here one assumes that C_{0}(t) = 1. Let C(t, x) be the generating function for the Narayana polynomials:

C(t, x) := ∑_{n≥1} C_{n}(t) x^{n} = x + (1 + t)x^{2} + (1 + 3t + t^{2})x^{3} + ⋯  (10)

= \frac{1 − x − tx − \sqrt{(1 − x − tx)^{2} − 4tx^{2}}}{2tx} .

The recurrence relation (9) is equivalent to the following well-known functional equation:

C = tx C^{2} + (1 + t) x C + x,  (11)

see [Stan’99, Exer. 6.36b].

12.2 Generating function for single branched trees

Trees with at most one branched vertex have the following form. For a_{1}, …, a_{k} ≥ 0, let T_{a_{1},...,a_{k}} be the graph obtained by attaching k chains of lengths a_{1}, …, a_{k} to one central node. For example, T_{0,...,0} is the graph with a single node and T_{1,...,1} is the k-star graph K_{1,k}.

Theorem 12.1. One has the following generating function for the hpolynomials of graph-associahedra P_{B(T_{a_{1},...,a_{k}})} for the graphs T_{a_{1},...,a_{k}}:

\begin{aligned}T (t, x_{1}, …, x_{k}) & := ∑_{a_{1},...,a_{k}≥0} h_{T_{a_{1},...,a_{k}}} (t) x_{1}^{a_{1}+1} ⋯ x_{k}^{a_{k}+1} \\ & = \frac{(t − 1) ϕ_{1} ⋯ ϕ_{k}}{t − ∏_{i=1}^{k}(1 + (t − 1) ϕ_{i})} \end{aligned}

where ϕ_{i} = x_{i}(1 + t C(t, x_{i})), and C(t, x) is the generating function for the Narayana polynomials from (10).

This theorem immediately implies the following formula from [Post’05].

Corollary 12.2. [Post’05, Proposition 8.7] The generating function for the number of vertices in the graph-associahedron P_{B(T_{a_{1},...,a_{k}})} is

∑_{a_{1},...,a_{k}} f_{0}(P_{B(T_{a_{1},...,a_{k}})}) x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}} = \frac{C̄(x_{1}) ⋯ C̄(x_{k})}{1 − x_{1} C̄(x_{1}) − ⋯ − x_{k} C̄(x_{k})},

where C̄(x) = ∑_{n≥0} C_{n} x^{n} = \frac{1−\sqrt{1−4x}}{2x} is the generating function for the Catalan numbers.

Documenta Mathematica 13 (2008) 207–273

Proof. The claim is obtained from Theorem 12.1 in the limit t → 1. Note however that one needs to use l’Hôpital’s rule before plugging in t = 1.

The first proof of Theorem 12.1 is fairly direct, using Corollary 8.4 and the solution to Simon Newcomb’s problem. The second uses Theorem 6.13 to set up and then solve a system of PDE’s; it has the advantage of producing a generating function for the h-polynomials of one further family of graphassociahedra.

12.3 Theorem 12.1 via Simon Newcomb’s problem

Let us first review Simon Newcomb’s problem and its solution. Let w = (w(1), …, w_{m}) be a permutation of the multiset {1^{c_{1}}, …, k^{c_{k}}}, that is, each i appears in w exactly c_{i} times, for i = 1, …, k. A descent in w is an index i such that w(i) > w(i + 1). Let des(w) denote the number of descents in w. Simon Newcomb’s Problem is the problem of counting permutations of a multiset with a given number of descents, see [Mac’17, Sec. IV, Ch. IV] and [GJ’83, Sec. 4.2.13]. Let us define the multiset Eulerian polynomial as

A_{c_{1},...,c_{k}}(t) := ∑_{w} t^{des(w)},

where the sum is over all permutations w of the multiset {1^{c_{1}}, …, k^{c_{k}}}. By convention, set A_{0,...,0}(t) = 1. In particular, the polynomial A_{1,...,1}(t) is the usual Eulerian polynomial. It is clear that A_{c_{1},...,c_{k}}(1) = \binom{m}{c_{1},...,c_{k}}, the total number of multiset permutations. A solution to Simon Newcomb’s problem can be expressed by the following generating function for the A_{c_{1},...,c_{k}}(t).

Proposition 12.3. [GJ’83, Sec. 4.2.13] One has

∑_{c_{1},...,c_{k}≥0} A_{c_{1},...,c_{k}}(t) y_{1}^{c_{1}} ⋯ y_{k}^{c_{k}} = \frac{t − 1}{t − ∏_{i=1}^{k}(1 + (t − 1) y_{i})}.

Theorem 12.1 then immediately follows from Proposition 12.3 and the following proposition.

Proposition 12.4. The generating function for the h-polynomials of the polytopes P_{B(T_{a_{1},...,a_{k}})} equals

T (t, x_{1}, …, x_{k}) = ∑_{c_{1},...,c_{k}≥0} A_{c_{1},...,c_{k}}(t) ϕ_{1}^{c_{1}+1} ⋯ ϕ_{k}^{c_{k}+1}.

Proof. Let us label nodes of the graph T_{a_{1},...,a_{k}} by integers in [n], where n = a_{1} + ⋯ + a_{k} + 1, so that the first chain is labelled by 1, …, a_{1}, the second chain is labelled by a_{1} + 1, …, a_{1} + a_{2}, etc., with all labels increasing towards the central node, and finally the central node has the maximal label n.

Let T be a T_{a_{1},...,a_{k}}-tree. Suppose that the root r of T belongs to the w(1)-st chain of the graph T_{a_{1},...,a_{k}}. If one removes the node r from the graph T_{a_{1},...,a_{k}}, then the graph decomposes into 2 connected components, one of which is a chain Path_{b_{1}} and the other is T_{a_{1},...,a′_{w(1)},...,a_{k}}, where a′_{w(1)} = a_{w(1)} − b_{1} − 1 and all other indices are the same as before. (The first component is empty if b_{1} = 0.) According to Proposition 8.5, the tree T is obtained by attaching a Path_{b_{1}}-tree T_{1} and a T_{a_{1},...,a′_{w(1)},...,a_{k}}-tree T′ to the root r. (Here one assumes that there is one empty Path_{0}-tree T_{1}, for b_{1} = 0.) Let us repeat the same procedure with the tree T′. Assume that its root belongs to the w(2)-nd chain and split it into a Path_{b_{2}}-tree T_{2} and a tree T′′. Then repeat this procedure with T′′, etc. Keep on doing this until one gets a tree T^{′···′} with the root at the central node n. Finally, if one removes the central node n from T^{′···′}, then it splits into k trees T̃_{1}, …, T̃_{k} such that T̃_{j} is a Path_{d_{j}}-tree, for j = 1, …, k. So each T_{a_{1},...,a_{k}}-tree T gives us the following data:

1. a sequence (w(1), …, w_{m}) ∈ [k]^{m};

2. a Path_{b_{i}}-tree T_{i}, for i = 1, …, m;

3. a Path_{d_{j}}-tree T̃_{j}, for j = 1, …, k.

This data satisfies the following conditions:

1. m, b_{1}, …, b_{m}, d_{1}, …, d_{k} ≥ 0, and

2. (b_{1} + 1)e_{w(1)} + ⋯ + (b_{m} + 1)e_{w_{m}} + (d_{1}, …, d_{k}) = (a_{1}, …, a_{k}),

where e_{1}, …, e_{k} are the standard basis vectors in ℝ^{k}. Conversely, data of this form gives us a unique T_{a_{1},...,a_{k}}-tree T. The number of descents in the tree T is

des(T) = ∑_{i=1}^{m} des(T_{i}) + ∑_{j=1}^{k} des(T̃_{j}) + l + des(w),

where l is the number of nonempty trees among T_{1}, …, T_{m}, T̃_{1}, …, T̃_{k}. Indeed, all descents in trees T_{i} and T̃_{j} correspond to descents in T, each nonempty tree T_{i} or T̃_{j} gives an additional descent for the edge that attaches this tree, and descents in w correspond to descent edges that attach trees T′, T′′, . . .. Let us fix a sequence w = w(1), …, w(m). For i ∈ [k], let c_{i} be the number of times the integer i appears in w. In other words, w is a permutation of the multiset {1^{c_{1}}, …, k^{c_{k}}}. Then the total contribution to the generating function T (t, x_{1}, …, x_{k}) of trees T whose data involve w is equal to t^{des(w)} ϕ_{1}^{c_{1}+1} ⋯ ϕ_{k}^{c_{k}+1}. Indeed, the term 1 in ϕ_{i} = x_{i}(1 + t · C(t, x_{i})) corresponds to an empty tree, and the term t · C(t, x_{i}) corresponds to nonempty trees, which contribute one additional descent. The term ϕ_{i}^{c_{i}} comes from the c_{i} trees T_{j_{1}}, …, T_{j_{c_{i}}}, where w_{j_{1}}, …, w_{j_{c_{i}}} are all occurrences of i in w. Finally, additional 1’s in the exponents of ϕ_{i}’s come from the trees T̃_{1}, …, T̃_{k}. Summing this expression over all permutations w of the multiset {1^{c_{1}}, …, k^{c_{k}}} and then over all c_{1}, …, c_{k} ≥ 0, one obtains the needed expression for the generating function T (t, x_{1}, …, x_{k}).

Remark 12.5. One can dualize all definitions, statements, and arguments in this section, as follows. An equivalent dual formulation to Theorem 12.1 says

T (t, x_{1}, …, x_{k}) = \frac{(1 − t) ψ_{1} ⋯ ψ_{k}}{1 − t ∏_{i=1}^{k}(1 + (1 − t) ψ_{i})}

where ψ_{i} = x_{i}(1 + C(t, x_{i})). The equivalence to Theorem 12.1 follows from the relation ϕ_{i} · ψ_{i} = (t − 1)(ϕ_{i} − ψ_{i}), which is a reformulation of the functional equation (11). The dual multiset Eulerian polynomial is Ā_{c_{1},...,c_{k}}(t) := ∑_{w} t^{wdes(w)+1}, where the sum is over permutations w of the multiset M = {1^{c_{1}}, …, k^{c_{k}}}, m = c_{1} + ⋯ + c_{k}, and wdes(w) is the number of weak descents in the multiset permutation w, that is, the number of indices i for which w(i) ≥ w(i + 1). The bijection which reverses the word w shows that Ā_{c_{1},...,c_{k}}(t) = t^{m} A_{c_{1},...,c_{k}}(t^{−1}) and consequently one has an equivalent formulation of the solution to Simon Newcomb’s problem:

∑_{c_{1},...,c_{k}≥0} Ā_{c_{1},...,c_{k}}(t) y_{1}^{c_{1}} ⋯ y_{k}^{c_{k}} = \frac{1 − t}{1 − t ∏_{i=1}^{k}(1 + (1 − t) y_{i})}.

Then one can modify the proof of Proposition 12.4, by switching the labels i with n + 1 − i in the graph T_{a_{1},...,a_{k}}, and applying a similar argument to show

T (t, x_{1}, …, x_{k}) = ∑_{c_{1},...,c_{k}≥0} Ā_{c_{1},...,c_{k}}(t) ψ_{1}^{c_{1}+1} ⋯ ψ_{k}^{c_{k}+1}.

12.4 Proof of Theorem 12.1 via PDE

This section rederives Theorem 12.1 using Theorem 6.13. It also calculates the generating function for f-polynomials of graph-associahedra corresponding to another class of graphs, the hedgehog graphs defined below. Recall that Path_{n} is the path with n nodes, and T_{a_{1},...,a_{k}} is the graph obtained by attaching the paths Path_{a_{1}}, …, Path_{a_{k}} to a central node. Let us also define the hedgehog graph H_{a_{1},...,a_{k}} as the graph obtained from the disjoint union of the chains Path_{a_{1}}, …, Path_{a_{k}} by adding edges of the complete graph between the first vertices of all chains. For example, H_{0,...,0} is the empty graph, H_{1,...,1} = K_{k}, and H_{2,...,2} is a graph with 2k vertices obtained from the complete graph K_{k} by adding a “leaf” edge hanging from each of the k original nodes. By convention, for the empty graph, one has f̃_{H_{0,...,0}}(t) = 0. Theorem 6.13 gives the following recurrence relation for f-polynomials of path graphs:

\frac{d}{dt}f̃_{Path_{n}}(t) = ∑_{r=1}^{n−1}(n − r + 1) · f̃_{Path_{r}}(t) · f̃_{Path_{n−r}}(t).

Indeed, there are n − r + 1 connected r-element subsets I of nodes of Path_{n}, the deletion Path_{n}|_{I} is isomorphic to Path_{r}, and the contraction Path_{n}/I is isomorphic to Path_{n−r}.

For graphs T_{a_{1},...,a_{k}}, Theorem 6.13 gives the following recurrence relation:

\begin{matrix}\frac{d}{dt}f̃_{T_{a_{1},...,a_{k}}} (t) = ∑_{i=1}^{k} ∑_{r=1}^{a_{i}} f̃_{Path_{r}}(t) · f̃_{T_{a_{1},...,a_{i}−r,...,a_{k}}} (t) · (a_{i} − r + 1) \\ + ∑ f̃_{T_{b_{1},...,b_{k}}} (t) · f̃_{H_{a_{1}−b_{1},...,a_{k}−b_{k}}} (t), \end{matrix}

where the second sum is over b_{1}, …, b_{k} such that 0 ≤ b_{i} ≤ a_{i}, for i = 1, …, k. Indeed, a connected subset I of vertices of G = T_{a_{1},...,a_{k}} either belongs to one of the chains Path_{a_{i}}, or contains the central node. In the first case, the restriction is G|_{I} = Path_{r} and the contraction is G/I = T_{a_{1},...,a_{i}−r,...,a_{k}}, where r = |I|. In the second case, the restriction G|_{I} has the form T_{b_{1},...,b_{k}} and the contraction is G/I = H_{a_{1}−b_{1},...,a_{k}−b_{k}}. Similarly, for hedgehog graphs H_{a_{1},...,a_{k}}, one obtains the recurrence relation

\begin{matrix}\frac{d}{dt}f̃_{H_{a_{1},...,a_{k}}} (t) = ∑_{i=1}^{k} ∑_{r=1}^{a_{i}} f̃_{Path_{r}}(t) · f̃_{H_{a_{1},...,a_{i}−r,...,a_{k}}} (t) · (a_{i} − r) \\ + ∑ f̃_{H_{b_{1},...,b_{k}}} (t) · f̃_{H_{a_{1}−b_{1},...,a_{k}−b_{k}}} (t), \end{matrix}

where the second sum is over b_{1}, …, b_{k} such that 0 ≤ b_{i} ≤ a_{i}, for i = 1, …, k. In all cases one has the initial conditions f̃_{Path_{n}}(0) = f̃_{T_{a_{1},...,a_{k}}} (0) = f̃_{H_{a_{1},...,a_{k}}} (0) = 1, except f̃_{Path_{0}}(t) = f̃_{H_{0,...,0}}(t) = 0.

The above recurrence relations can be written in a more compact form using these generating functions:

F_{A}(t, x) := ∑_{n≥1} f̃_{Path_{n}}(t) x^{n+1} = x^{2} + (1 + 2t) x^{3} + (1 + 5t + 5t^{2}) x^{4} + ⋯,

F_{T} (t, x_{1}, …, x_{k}) := ∑_{a_{1},...,a_{k}≥0} f̃_{T_{a_{1},...,a_{k}}} (t) x_{1}^{a_{1}+1} ⋯ x_{k}^{a_{k}+1},

F_{H}(t, x_{1}, …, x_{k}) := ∑_{a_{1},...,a_{k}≥0} f̃_{H_{a_{1},...,a_{k}}} (t) x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}}.

Note that F_{A} and F_{T} are related to generating functions from Section 12: F_{A}(t, x) = t^{−1}x C(t^{−1} + 1, tx), and F_{T} (t, x_{1}, …, x_{k}) = t^{−k} T (t^{−1} + 1, tx_{1}, …, tx_{k}).

The above recurrence relations can be expressed as the following partial differential equations with initial conditions at t = 0:

\frac{∂F_{A}}{∂t} = F_{A} · \frac{∂F_{A}}{∂x} , F_{A}|_{t=0} = \frac{x^{2}}{1 − x},  (12)

\frac{∂F_{T}}{∂t} = ∑_{i=1}^{k} F_{A}(t, x_{i}) \frac{∂F_{T}}{∂x_{i}} + F_{T} · F_{H}, F_{T} |_{t=0} = \frac{x_{1} ⋯ x_{k}}{∏_{i=1}^{k}(1 − x_{i})}, (13)

\frac{∂F_{H}}{∂t} = ∑_{i=1}^{k} F_{A}(t, x_{i}) \frac{∂F_{H}}{∂x_{i}} + (F_{H})^{2}, F_{H}|_{t=0} = \frac{1 − ∏_{i=1}^{k}(1 − x_{i})}{∏_{i=1}^{k}(1 − x_{i})}.(14)

One can actually solve these partial differential equations for arbitrary initial conditions, as follows.

Proposition 12.6. The solutions F (t, x), G(t, x_{1}, …, x_{k}), H(t, x_{1}, …, x_{k}), and R(t, x_{1}, …, x_{k}) to the following system of partial differential equations with initial conditions

\frac{∂F}{∂t} = F · \frac{∂F}{∂x} , F |_{t=0} = f_{0}(x),  (15)
\frac{∂G}{∂t} = ∑_{i=1}^{k} F (t, x_{i}) \frac{∂G}{∂x_{i}} , G|_{t=0} = g_{0}(x_{1}, …, x_{k}),  (16)

\frac{∂H}{∂t} = ∑_{i=1}^{k} F (t, x_{i}) \frac{∂H}{∂x_{i}} + H^{2}, H|_{t=0} = h_{0}(x_{1}, …, x_{k}),  (17)

\frac{∂R}{∂t} = ∑_{i=1}^{k} F (t, x_{i}) \frac{∂R}{∂x_{i}} + R · H, R|_{t=0} = r_{0}(x_{1}, …, x_{k})  (18)

are given by

f_{0}(x + t · F) = F (implicit form)
G = g_{0}(ξ_{1}, …, ξ_{k})
H = −(t + (h_{0}(ξ_{1}, …, ξ_{k}))^{−1})^{−1}
R = −r_{0}(ξ_{1}, …, ξ_{k}) · (1 + t · h_{0}(ξ_{1}, ⋯, ξ_{k}))^{−1}

where ξ_{i} = x_{i} + t · F (t, x_{i}), for i = 1, …, k.

Proof. Let us first solve (15). For a constant C, consider the function x(t) given implicitly as F (t, x) = C, i.e., the graph of x(t) is a level curve for F (t, x). The tangent vector to the graph of x(t) at some point (t_{0}, x_{0}) such that F (t_{0}, x_{0}) = C is (1, \frac{dx(t_{0})}{dt}). The derivative of the function F (t, x) at the point (t_{0}, x_{0}) in the direction of this vector should be 0, i.e., 1 · \frac{∂F (t_{0},x_{0})}{∂t} + \frac{dx(t_{0})}{dt} · \frac{∂F (t_{0},x_{0})}{∂x} = 0. This equation, together with the differential equation (15) for F, implies that \frac{d}{dt} x(t) = −C. Solving this trivial differential equation for x(t) one deduces that x(t) = −C · t + B(C), where B is a function that depends only on the constant C. Since C can be an arbitrary constant, one deduces that

x = −F (t, x) · t + B(F (t, x)), or, equivalently, B^{⟨−1⟩}(x + t · F (t, x)) = F (t, x).

Plugging the initial condition F |_{t=0} = f_{0}(x) in the last expression, one gets

B^{⟨−1⟩}(x) = f_{0}(x).

Thus the solution F (t, x) is given by f_{0}(x + t · F) = F, as needed. Direct verification shows that the function G = R(F (t, x_{1}), …, F (t, x_{k})) satisfies the differential equation (16), for an arbitrary R(y_{1}, …, y_{k}). The initial condition for t = 0 gives R(f_{0}(x_{1}), …, f_{0}(x_{k})) = g_{0}(x_{1}, …, x_{k}). Thus R(y_{1}, …, y_{k}) = g_{0}(B(y_{1}), …, B(y_{k})), where B = f_{0}^{⟨−1⟩}, as above. Since B(F (t, x)) = x + t · F (t, x), one deduces that G = g_{0}(B(F (t, x_{1})), …, B(F (t, x_{k}))) = g_{0}(ξ_{1}, …, ξ_{k}), as needed. Making the substitution H = −(t + G(t, x_{1}, …, x_{k}))^{−1} in differential equation (17) for H, one obtains equation (17) for G with g_{0} = −(h_{0})^{−1}. By the previous calculation, one has G = −(h_{0}(ξ_{1}, …, ξ_{k}))^{−1}. Thus the solution for (17) is H = −(t + (h_{0}(ξ_{1}, …, ξ_{k}))^{−1})^{−1}. Making the substitution R = H · G in equation (17) for R, where H is the solution to (17), one obtains equation (16) for G with g_{0} = r_{0}/h_{0}. By the above calculation, one has G = r_{0}(ξ_{1}, …, x_{k})/h_{0}(ξ_{1}, …, ξ_{k}). Thus,

R = −\frac{1}{t + (h_{0}(ξ_{1}, …, ξ_{k}))^{−1}} · \frac{r_{0}(ξ_{1}, …, x_{k})}{h_{0}(ξ_{1}, …, ξ_{k})} = −\frac{r_{0}(ξ_{1}, …, x_{k})}{1 + t · h_{0}(ξ_{1}, ⋯, ξ_{k})},

as needed.

Applying Proposition 12.6 to differential equation (12) for F_{A}(t, x), one obtains the implicit solution:

\frac{(x + t · F_{A})^{2}}{1 − x − t · F_{A}} = F_{A}.

This is equivalent to the quadratic equation (11) for C(t, x). Explicitly, one gets

F_{A}(t, x) = \frac{(1 − x − 2tx) − \sqrt{(1 − x − 2tx)^{2} − 4t(t + 1)x^{2}}}{2t(t + 1)} .  (19)

Applying Proposition 12.6 to differential equations (13) and (14) for the generating functions F_{T} and F_{H}, one obtains the following result.

Theorem 12.7. The generating functions F_{T} (t, x_{1}, …, x_{k}) and F_{H}(t, x_{1}, …, x_{k}) are given by the following expressions

F_{T} (t, x_{1}, …, x_{k}) = \frac{ξ_{1} ⋯ ξ_{n}}{(t + 1)(1 − ξ_{1}) ⋯ (1 − ξ_{n}) − t},

F_{H}(t, x_{1}, …, x_{k}) = \frac{1 − (1 − ξ_{1}) ⋯ (1 − ξ_{k})}{(t + 1)(1 − ξ_{1}) ⋯ (1 − ξ_{n}) − t},

where ξ_{i} = x_{i} + t · F_{A}(t, x_{i}) and F_{A} is given by (19).

Documenta Mathematica 13 (2008) 207–273

Note that the above expression for F_{T} is equivalent to Theorem 12.1, using (1).

13 Graph-associahedra for path-like graphs

The goal of this section is to use Theorem 6.12 to compute the h-polynomials of the graph-associahedra of a fairly general infinite family of graphs, including all Dynkin diagrams of finite and affine Coxeter groups. Let A and B be two connected graphs with a marked vertex in each, and let n_{0} be the total number of unmarked vertices in A and B. For n > n_{0}, let G_{n} = G_{n}(A, B) be the graph obtained by connecting the marked vertices in A and B by the path Path_{n−n_{0}} so that the total number of vertices in G_{n} is n. Call graphs of the form G_{n} path-like graphs because, for large n, they look like paths with some “small” graphs attached to their ends. The following claim shows that the h-polynomials of the graph-associahedra P_{B(G_{n})} can be expressed as linear combinations (with polynomial coefficients) of the h-polynomials C_{n}(t) of usual associahedra; see (8).

Theorem 13.1. There exist unique polynomials g_{0}(t), g_{1}(t), …, g_{n_{0}}(t) ∈ ℤ[t] of degrees deg g_{i}(t) ≤ i such that, for any n > n_{0} one has

h_{G_{n}}(t) = g_{0}(t) C_{n}(t) + g_{1}(t) C_{n−1}(t) + ⋯ + g_{n_{0}}(t) C_{n−n_{0}}(t).

The polynomial g_{i}(t) is a palindromic polynomial, that is g_{i}(t) = t^{i} g_{i}(t^{−1}), for i = 0, …, n_{0}.

Similarly, one can express the f-polynomials of P_{B(G_{n})} as a linear combination of the f-polynomials of usual associahedra, because f_{G}(t) = h_{G}(t + 1). One can rewrite this theorem in terms the generating function C(t, x) for the Narayana numbers; see (10).

Corollary 13.2. There exists a unique polynomial g(t, x) ∈ ℤ[t, x] such that for any n > n_{0}, h_{G_{n}}(t) is the coefficient of x^{n} in g(t, x) C(t, x). The polynomial g(t, x) has degree at most n_{0} with respect to x, and satisfies g(t, x) = g(t^{−1}, tx).

Proof. This follows from Theorem 13.1, by setting g(t, x) = g_{0}(t) + g_{1}(t) x + ⋯ + g_{n_{0}}(t) x^{n_{0}}.

Proof of Theorem 13.1. Let us first prove the existence of the linear expansion. The recurrence from Theorem 6.12 will be used to prove this claim by induction on the total number of vertices in A and B. Suppose that A or B is disconnected, say, A is a disjoint union of graphs A_{1} and A_{2} where A_{1} contains the marked vertex. Let G̃_{n} := G_{n}(A_{1}, B) and let r be the number of vertices in A_{2}. Then h_{G_{n}}(t) = hG̃_{n−r}(t) h_{A_{2}}(t), where deg h_{A_{2}}(t) ≤ r − 1. By induction, hG̃_{n−r}(t) can be expressed as a linear combination of C_{n−r}(t), C_{n−r−1}(t), …, C_{n−n_{0}}(t), which produces the needed expression for h_{G_{n}}(t).

Now assume that both A and B are connected graphs. Theorem 6.12(3) gives the expression for the h-polynomial as the sum h_{G_{n}}(t) = ∑_{L}(t − 1)^{|L|−1}h_{G_{n}\L}(t) over nonempty subsets L of vertices of G_{n}, where G_{n} \ L denotes the graph G_{n} with removed vertices in L. (Here one has shifted t by −1 to transform f-polynomials into h-polynomials.) Let us write L as a disjoint union L = I ∪ J ∪ K, where I is a subset of unmarked vertices of A, J is a subset of unmarked vertices of B, and K is a subset of vertices in the path connecting the marked vertices. The contribution of the terms with K = ∅ to the above sum is ∑_{I,J}(t−1)^{|I|+|J|−1}h_{G_{n}\(I∪J)}(t). Note that G_{n} \(I ∪J) = G_{n−r}(A\I, B \J), where r = |I| + |J|. By induction, one can express each term h_{G_{n}\(I∪J)}(t) as a combination of C_{n−r}(t), …, C_{n−n_{0}}(t). The remaining terms involve a nonempty subset K of vertices in the path Path_{n−n_{0}}. When one removes these k = |K| vertices from the path, it splits into k + 1 smaller paths Path_{m_{1}}, …, Path_{m_{k+1}} with m_{i} ≥ 0; cf. paragraph before (9). Thus the remaining contribution to h_{G_{n}}(t) can be written as

∑_{I,J} ∑_{m_{1},...,m_{k+1}≥0}(t − 1)^{|I|+|J|+k−1} h_{G_{p}(A\I,∘)}(t) C_{m_{2}}(t) ⋯ C_{m_{k}}(t) h_{G_{q}(∘,B\J)}(t),

where ∘ is the graph with a single vertex,

\begin{aligned}p & = m_{1} + |A \ I| − 1, \\ q & = m_{k+1} + |B \ J| − 1, and \\ k + ∑ m_{i} & = n − n_{0}. \end{aligned}

By induction, one can express h_{G_{p}(A\I,∘)}(t) and h_{G_{q}(∘,B\J)}(t) as linear combinations of the C_{m′}(t). So the remaining contribution to h_{G_{n}}(t) can be written as a sum of several expressions of the form

s(t) ∑_{k≥1} ∑_{m′_{1},m_{2},...,m_{k},m′_{k+1}}(t − 1)^{k−1}C_{m′_{1}}(t) C_{m_{2}}(t) ⋯ C_{m_{k}}(t) C_{m′_{k+1}}(t),

where the sum is over m′_{1}, m_{2}, …, m_{k}, m′_{k+1} such that m′_{1} ≥ a, m_{2}, …, m_{k} ≥ 0, m′_{k+1} ≥ b, m′_{1} + m_{2} + ⋯ + m_{k} + m′_{k+1} + k = n − c. This expression depends on nonnegative integers a, b, c such that a + b + c = n_{0} and a polynomial s(t) of degree deg s(t) ≤ c. If one extends the summation to all m′_{1}, m′_{k+1} ≥ 0, one obtains the expansion (9) for C_{n−c}(t) times s(t). Applying the inclusionexclusion principle and equation (9), one deduces that the previous sum equals

s(t) (C_{n−c}(t) − ∑_{m′_{1}=0}^{a−1} t C_{m′_{1}}(t) C_{n−c−m′_{1}−1}(t) − ⋯) ,

which is a combination of C_{n}(t), …, C_{n−n_{0}}(t) as needed. It remains to show the uniqueness of the linear expansion and show that the g_{i}(t) are palindromic polynomials. (Here one assumes that the graphs A and B are connected.) According to Corollary 13.2, the polynomial H(t, x) := ∑_{n>n_{0}} h_{G_{n}}(t) x^{n} can be written as H(t, x) = g(t, x) C(t, x) + r(t, x), where g(t, x), r(t, x) ∈ ℤ[t, x]. If H(t, x) = g̃(t, x) C(t, x)+r̃(t, x) with g̃(t, x) ≠ g(t, x), then this would imply that C(t, x) is a rational function, which contradicts the formula (10) involving a square root. This proves the uniqueness claim. One has H(t, x) = H(t^{−1}, tx)/t and C(t, x) = C(t^{−1}, tx)/t because hpolynomials are palindromic. Thus

H(t, x) = g(t, x) C(t, x) + r(t, x) = g(t^{−1}, tx) C(t, x) + \frac{1}{t}r(t^{−1}, tx).

This implies that g(t, x) = g(t^{−1}, tx). Otherwise, C(t, x) would be a rational function. The equation g(t, x) = g(t^{−1}, tx) says that the coefficients g_{i}(t) of g(t, x) = ∑_{i} g_{i}(t) x^{i} are palindromic.

Let us illustrate Theorem 13.1 by several examples. For a series of path-like graphs G_{n}, let g{G_{n}} denote the polynomial g(t, x) that appears in the generating functions ∑_{n≥n_{0}} h_{G_{n}}(t) x^{n} = g(t, x) C(t, x) + r(t, x). For instance, the expression g{D_{n}} = 2 − (t + 1)x − tx^{2} (see the example below) is equivalent to the expression h_{D_{n}}(t) = 2C_{n}(t) − (t + 1) C_{n−1}(t) − t C_{n−2}(t), for n > 2.

Examples 13.3. Define daisy graphs as Daisy_{n,k} := T_{n−k−1,1^{k}}; see Section 12. (Here 1^{k} means a sequence of k ones.) They include type D Dynkin diagrams D_{n} := Daisy_{n,2}. For fixed k, the Daisy_{n,k} form the series of path-like graphs for A = K_{1,k} (the k-star with marked central vertex) and B = ∘ (the graph with a single vertex). Also define kite graphs as Kite_{n,k} := H_{n−k+1,1^{k−1}}; see Section 12.4. They are path-like graphs for A = K_{k} and B = ∘. The affine Dynkin diagram of type D̃_{n−1} is the nth path-like graph in the case when both A and B are 3-paths with marked central vertices. Here are the polynomials g{G_{n}} for several series of such graphs:

g{D_{n}} = 2 − (t + 1) x − t x^{2},
g{D̃_{n−1}} = 4 − 4(t + 1) x + (t − 1)^{2} x^{2} + 2 t(t + 1) x^{3} + t^{2} x^{4},
g{Kite_{n,3}} = 2 − (t + 1) x,
g{Daisy_{n,3}} = 6 − 6(t + 1) x + (1 − 5 t + t^{2}) x^{2} − t(t + 1) x^{3},
g{Daisy_{n,4}} = 24 − 36(t + 1) x + (14 − 16 t + 14 t^{2}) x^{2} +
+ (−1 + 3 t + 3 t^{2} − t^{3}) x^{3} − (t + t^{2} + t^{3}) x^{4}.

The formulas for D_{n}, Kite_{n,k}, and Daisy_{n,k} were derived from Theorems 12.1 and 12.7. The formula for the affine Dynkin diagram D̃_{n−1} was obtained using the inductive procedure given in the proof of Theorem 13.1.

Remark 13.4. The induction from the proof of Theorem 13.1 is quite involved. It is very difficult to calculate by hand other examples for bigger graphs A and B. It would be interesting to find a simpler procedure for finding the polynomials g{G_{n}}. Also it would be interesting to find explicit formulas for the polynomials g{G_{n}} for all daisy graphs, kite graphs, and other “natural” series of path-like graphs.

14 Bounds and monotonicity for face numbers of graphassociahedra

Section 7.2 showed that the f- and h-vectors of flag nestohedra coming from connected building sets are bounded below by those of hypercubes and bounded above by those of permutohedra. It is natural to ask for the bounds within the subclass of graph-associahedra corresponding to connected graphs. Permutohedra are graph-associahedra corresponding to complete graphs, and so they still provide the upper bound for the f- and h-vectors. For lower bounds on f- and h-vectors, the monotonicity discussed in Remark 6.9 implies that the f- and h-vector of any graph-associahedron P_{B(G)} for a connected graph G is bounded below by the graph-associahedron for any spanning tree inside G. Thus it is of interest to look at bounds for f-, h- and γ-vectors of graph-associahedra for trees. A glance at Figure 4 suggests that, roughly speaking, trees which are more branched and forked (that is, farther from being a path) tend to have higher entries componentwise in their γ-vectors, and hence also in their f- and hvectors. In fact, in that figure, which shows all trees on 7 vertices grouped by their degree sequences, one sees several (perhaps misleading) features:

(i) The degree sequences are ordered linearly under the majorization (or dominance) partial ordering on partitions of 2(n − 1) (= 2 · (7 − 1) = 12 here).

(ii) The γ-vectors of these trees are linearly ordered under the componentwise partial order.

(iii) Trees whose degree sequence are lower in the majorization order have componentwise smaller γ-vectors.

(iv) The trees are distinguished up to isomorphism by their γ-vectors.

Additionally, it seems that the Wiener index [Wie’47] for graphs has some correlation with the γ-vector. The Wiener index W (G) of a graph G is defined as the sum of distances d(i, j) over unordered pairs i, j of vertices in G, where d(i, j) is the number of edges in the shortest path from i to j. The Wiener index W (T) of a tree is equal to the number of forbidden 312 patterns (see the remarks following Definition 9.2) provided by the tree T (plus the constant \binom{n}{2}). Thus, for two trees on n vertices, if one has W (T) < W (T′), then roughly speaking one might expect that the generalized permutohedron P_{B(T)} has a larger gamma vector than P_{B(T′)}. This is exactly the case for trees on 7 vertices, as shown in Figure 4. It shows that as the γ-vectors decrease, the Wiener indices (weakly) increase. Note that Figure 4: The γ-vectors (γ_{0}, γ_{1}, γ_{2}, γ_{3}) for graph-associahedra of all trees on 7 vertices, grouped by degree sequence.

in this case, the Wiener index together with the degree sequence completely distinguish all equivalence classes of trees. For trees on n vertices, the maximum and minimum values of the Wiener index are, respectively, ∑_{i=1}^{n−1} i(n−i) = n(n^{2}−1)/6 for Path_{n}, and (n−1)^{2} for K_{1,n−1}. None of the properties (i)-(iv) persist for all trees. For example, when looking at trees on n = 8 nodes, one finds that

(i) the degree sequences are only partially ordered by the majorization order on partitions of 2(n − 1) = 14:

22222211 < 32222111
< 33221111 < 33311111, 42221111
< 43211111 < 44111111, 52211111
< 53111111 < 62111111 < 71111111

(ii) there are trees, such as the two shown in Figure 5(a) and (b), whose γ-vectors are incomparable componentwise,

(iii) there are trees, such as the two shown in Figure 5(d) and (c), where the degree sequence of one strictly majorizes that of the other, but its γ-vector is strictly smaller, and

(iv) there are nonisomorphic trees, such as the two shown in Figure 5(d) and (e), having the same γ-vector.

Figure 5: The γ-vectors of the graph-associahedra of some trees on 8 nodes.

Nevertheless, we do make some monotonicity conjectures about the face numbers for graph-associahedra.

Conjecture 14.1. There exists a partial order ≺ on the set of (unlabelled, isomorphism classes of) trees with n nodes, having these properties:

• Path_{n} is the unique ≺-minimum element,

• K_{1,n−1} is the unique ≺-maximum element, and

• T ≺ T′ implies γ_{P_{B(T)}} ≤ γ_{P_{B(T′)}} componentwise.

We suspect that such a partial order ≺ can be defined so that T, T′ will, in particular, be comparable whenever T, T′ are related by one of the flossing moves considered in [BR’04, §4.2]. Assuming Conjecture 14.1, the γ-vectors (and hence also the f-, h-vectors) of graph-associahedra for trees on n nodes would have the associahedron P_{B(Path_{n})} and the stellohedron P_{B(K_{1,n−1})} giving their lower and upper bounds. This would also imply that the f-, h-vectors of graph-associahedra for connected graphs on n nodes would have associahedra and permutohedra giving their lower and upper bounds. To make a similar assertion for γ-vectors it would be nice to have the following analogue of Stanley’s monotonicity result (Theorem 4.6).

Conjecture 14.2. When Δ, Δ′ are two flag simplicial complexes and Δ′ is a geometric subdivision of Δ, the γ-vector of Δ′ is componentwise weakly larger than that of Δ. In particular, when B, B′ are building sets giving rise to flag nestohedra and B ⊂ B′, (such as graphical buildings B(G) ⊂ B(G′) for an edgesubgraph G ⊂ G′) then the γ-vector of P_{B′} is componentwise weakly larger than that of P_{B}.

We close with a question suggested by the sets of permutations 𝔖_{n}(B) and 𝔖̂_{n}(B) for a chordal building set B which appeared in Corollary 9.6 and Theorem 11.6.

Question 14.3. Given a (non-chordal) building set B, is there a way to define two sets of permutations 𝔖′_{n}(B) and 𝔖̂′_{n}(B) such that:

• the h-polynomial for the nestohedron P_{B} is given by the descent generating function for 𝔖′_{n}(B), and

• the γ-polynomial is given by the peak generating function for 𝔖̂′_{n}(B)?

15 Appendix: Deformations of a simple polytope

The goal of this section is to clarify the equivalence between various definitions of the deformations of a simple polytope, either by

• deforming vertex positions, keeping edges in the same parallelism class, or

• deforming edge lengths, keeping them nonnegative, or

• altering level sets of facet inequalities, but not allowing facets to move past any vertices.

There will be defined below three cones of such deformations which are all linearly isomorphic. This discussion is essentially implicit in [Post’05, Definition 6.1 and §19], but we hope the explication here clarifies this relationship. Let P be a simple d-dimensional polytope in ℝ^{d}. Let V be its set of vertices. Let E ⊆ \binom{V}{2} be its set of edge pairs. Let F be an indexing set for its facets, so that P is defined by facet inequalities h_{f}(x) ≤ α_{f} for f ∈ F, in which each h_{f} is a linear functional in (ℝ^{d})^{∗}, and (α_{f})_{f∈F} ∈ ℝ^{F}.

Definition 15.1. (1) The vertex deformation cone D_{P}^{V} of P is the set of points (x_{v})_{v∈V} ∈ (ℝ^{d})^{V} such that

x_{u} − x_{v} ∈ ℝ_{≥0}(u − v), for every edge uv ∈ E.  (20)

(2) The edge length deformation cone D_{P}^{E} of P is the set of points (y_{e})_{e∈E} ∈ ℝ^{E} such that all y_{e} ≥ 0, and, for any 2-dimensional face of P with edges e_{1} = v_{1}v_{2}, e_{2} = v_{2}v_{3}, …, e_{k−1} = v_{k−1}v_{k}, e_{k} = v_{k}v_{1}, one has

y_{e_{1}}(v_{1} − v_{2}) + y_{e_{2}}(v_{2} − v_{3}) + ⋯ + y_{e_{k}}(v_{k} − v_{1}) = 0.

(3) For β = (β_{f})_{f∈F} ∈ ℝ^{F}, let P_{β} := {x ∈ ℝ^{d} | h_{f}(x) ≤ β_{f}, for f ∈ F } be the polytope obtained from P by parallel translations of the facets. In particular, P_{α} = P. The open facet deformation cone^{9} D_{P}^{F,open} for P is the set of β ∈ ℝ^{F} for which the polytopes P_{β} and P have the same normal fan N (P_{β}) = N (P). (Equivalently, P_{β} and P have the same combinatorial structure.) The (closed) facet deformation cone is the closure D_{P}^{F} of D_{P}^{F,open} inside ℝ^{F}.

It is clear that the definitions of D_{P}^{V} and D_{P}^{E} translate into linear equations and weak linear inequalities. Thus D_{P}^{V} and D_{P}^{E} are (closed) polyhedral cones in the spaces (ℝ^{d})^{V} and ℝ^{E}, correspondingly. The following lemma shows that D_{P}^{F} is also a polyhedral cone.

9This is linearly isomorphic to the type-cone of P described by McMullen [McM’73, §2, p. 88].

Documenta Mathematica 13 (2008) 207–273

Lemma 15.2. For a simple polytope P, the facet deformation cone D_{P}^{F,open} is a full |F |-dimensional open polyhedral cone inside ℝ^{F}, that is a nonempty subset in ℝ^{F} given by strict linear inequalities. Thus D_{P}^{F} is the closed polyhedral cone in ℝ^{F} given by replacing the strict inequalities with the corresponding weak inequalities.

Proof. Since every polytope P_{β} has facet normals in directions which are a subset of those for P, the rays (=1-dimensional normal cones) in N (P_{β}) are a subset of those in N (P). Therefore, one will have N (P_{β}) = N (P) if and only if P_{β}, P have the same face lattices, or equivalently, the same collection of vertexfacet incidences (v, f). This means that one can define the set D_{P}^{F,open} inside ℝ^{F} by a collection of strict linear inequalities on the coordinates β = (β_{f})_{f∈F}. It is next explained how to produce one such inequality for each pair (v_{0}, f_{0}) of a vertex v_{0} and facet f_{0} of P such that v_{0} ∉ f_{0}. If v_{0} lies on the d facets f_{1}, …, f_{d} in P, then v_{0} is the unique solution to the linear system h_{f_{j}}(x) = α_{f_{j}} for j = 1, ..., d. Its corresponding vertex x_{0} in P_{β} is then the unique solution to h_{f_{j}}(x) = β_{f_{j}} for j = 1, ..., d. Note that this implies x_{0} has coordinates given by linear expressions in the coefficients β. Then the inequality corresponding to the vertex-facet pair (v_{0}, f_{0}) asserts that h_{f_{0}}(x_{0}) < β_{f_{0}}. Lastly, note that this system of strict linear inequalities has at least one solution, namely the α for which P_{α} = P. Hence this open polyhedral cone is nonempty.

Theorem 15.3 gives several ways to describe deformations of a simple polytope.

Theorem 15.3. Let P be a d-dimensional simple polytope in ℝ^{d}, with notation as above. Then the following are equivalent for a polytope P′ in ℝ^{d}:

(i) The normal fan N (P) refines the normal fan N (P′).

(ii) The vertices of P′ can be (possibly redundantly) labelled x_{v}, v ∈ V, so that (x_{v})_{v∈V} is a point in the vertex deformation cone D_{P}^{V}, i.e., the x_{v} satisfy conditions (20).

(iii) The polytope P′ is the convex hull of points x_{v}, v ∈ V, such that (x_{v})_{v∈V} is in the vertex deformation cone D_{P}^{V}.

(iv) P′ = P_{β} for some β in the closed facet deformation cone D_{P}^{F}.

(v) P′ is a Minkowski summand of a dilated polytope rP, that is there exist a polytope Q ⊂ ℝ^{d} and a real number r > 0 such that P′ + Q = rP.

Proof. One proceeds by proving the following implications (i) ⇒ (ii) ⇒ (iii) ⇒ (i) ⇒ (iv) ⇒ (iii), (iv) ⇒ (v) ⇒ (i).

(i) implies (ii). The refinement of normal fans gives rise to the redundant labelling of vertices (x_{v})_{v∈P} as follows: given a vertex x of P′, label it by x_{v} for every vertex v in P having its normal cone N_{v}(P) contained in the normal cone N_{x}(P′). There are then two possibilities for an edge uv ∈ E of P: either x_{u} = x_{v}, in which case (20) is trivially satisfied, or else x_{u} ≠ x_{v} so that N_{u}(P), N_{v}(P) lie in different normal cones N_{x_{u}}(P′) ≠ N_{x_{v}}(P′). But then since N (P) refines N (P′), these latter two cones must share a codimension one subcone lying in the same hyperplane that separates N_{u}(P) and N_{v}(P). As this hyperplane has normal vector u − v, this forces x_{u} − x_{v} to be a positive multiple of this vector, as desired. (ii) implies (iii). Trivial. (iii) implies (i). Let P′ be the convex hull of the points x_{v}. Fix a vertex u ∈ V. Let λ ∈ (ℝ^{d})^{∗} be a generic linear functional that belongs to the normal cone N_{u}(P) of P at the vertex u. Then the maximum of λ on P is achieved at the point u and nowhere else. Let us orient the 1-skeleton of P so that λ increases on each directed edge. This connected graph has a unique vertex of outdegree 0, namely the vertex u. Thus, for any other vertex v ∈ V, there is a directed path (v_{1}, …, v_{l}) from v_{1} = v to v_{l} = u in this directed graph. According to the conditions of the lemma, one has have λ(x_{v_{1}}) ≤ λ(x_{v_{2}}) ≤ ⋯ ≤ λ(x_{v_{l}}), so λ(x_{v}) ≤ λ(x_{u}). Thus the maximum of λ on the polytope P′ is achieved at the point x_{u}. This implies that x_{u} is a vertex of P′ and the normal cone N_{x_{u}}(P′) of P′ at this point contains the normal cone N_{u}(P) of P at u. Since the same statement is true for any vertex of P, one deduces that N (P) refines N (P′).

(i) implies (iv). First, note that if N (P′) = N (P) then P′ = P_{β} for some β in the open facet deformation cone D_{P}^{F,open}. Indeed, the facets of P′ are orthogonal to the 1-dimensional cones in N (P′), thus they should be parallel to the corresponding facets of P. Now assume that N (P) refines N (P′). Recall the standard fact [Zieg’94, Prop. 7.12] that the normal fan N (Q_{1} + Q_{2}) of a Minkowski sum Q_{1} + Q_{2} is the common refinement of the normal fans N (Q_{1}) and N (Q_{2}). Thus, for any ϵ > 0, the normal fan of the Minkowski sum P′ + ϵP coincides with N (P). By the previous observation, one should have P′ +ϵP = P_{β(ϵ)} for some β(ϵ) ∈ D_{P}^{F,open}. Since all coordinates of β(ϵ) linearly depend on ϵ, one obtain P′ = P_{β} for β = lim_{ϵ→0} β(ϵ) ∈ D_{P}^{F}. (iv) implies (iii). Given β ∈ D_{P}^{F}, it is the limit point for some family {β(ϵ)} ⊂ D_{P}^{F,open}. One may assume that β(ϵ) linearly depends on ϵ > 0 and lim_{ϵ→0} β(ϵ) = β. Hence P′ = P_{β} is the limit of the polytopes P_{β(ϵ)}, which each have N (P_{β(ϵ)}) = N (P). In particular, the vertices of P_{β(ϵ)} can be labelled by x_{v}(ϵ), v ∈ V. These vertices linearly depend on ϵ and satisfy x_{u}(ϵ) − x_{v}(ϵ) = ℝ_{≥0}(u − v) for any edge uv ∈ E. Taking the limit ϵ → 0, one obtains that P′ is the convex hull of points x_{v} = lim_{ϵ→0} x_{v}(ϵ) satisfying (20). (iv) implies (v). Note that P_{γ} + P_{δ} = P_{γ+δ}, for γ, δ ∈ D_{P}^{F}. Let P′ = P_{β} for β ∈ D_{P}^{F}. The point α (such that P = P_{α}) belongs to the open cone D_{P}^{F,open}. Thus, for sufficiently large r, the point γ = rα − β also belongs to the open cone D_{P}^{F,open}. Let Q = P_{γ}. Then one has P′ + Q = P_{β} + P_{rα−β} = P_{rα} = rP, as needed.

(v) implies (i). This follows from the standard fact [Zieg’94, Prop. 7.12] on normal fans of Minkowski sums mentioned above.

Remark 15.4. We are being somewhat careful here, since Theorem 15.3 can fail when one allows a broader interpretation for a simple polytope P to deform into a polytope P′ by parallel translations of its facets, e.g. if one allows facets to translate past vertices. For example, letting P′ be a regular tetrahedron in ℝ^{3}, and P the result of “shaving off an edge” from P′ with a generically tilted plane in ℝ^{3}, one finds that N (P) does not refine N (P′).

Let us now describe the relationship between the three deformation cones D_{P}^{V}, D_{P}^{E}, and D_{P}^{F}. Let H be the linear subspace in (ℝ^{d})^{V} given by

H := {(x_{v})_{v∈V} ∈ (ℝ^{d})^{V} | x_{u} − x_{v} ∈ ℝ(u − v) for any edge uv ∈ E}.

Clearly, the cone D_{P}^{V} belongs to the subspace H. Let us define two linear maps

ϕ : H → ℝ^{E} and ψ : ℝ^{F} → H.

The map ϕ sends (x_{v})_{v∈V} ∈ H to (y_{e})_{e∈E} ∈ ℝ^{E}, where x_{u} −x_{v} = y_{e}(u−v), for any edge e = uv ∈ E. The map ψ sends β = (β_{f})_{f∈F} to (x_{v})_{v∈V}, where, for each vertex v of P given as the intersection of the facets of P indexed f_{1}, …, f_{d}, the point x_{v} ∈ ℝ^{d} is the unique solution of the linear system {h_{f_{j}}(x) = β_{f_{j}} | j = 1, …, d}. For β ∈ D_{P}^{F,open}, ψ(β) = (x_{v})_{v∈V}, where the x_{v} are the vertices of the polytope P_{β}. One can easily check that ψ(β) ∈ H. Indeed, this is clear for β ∈ D_{P}^{F,open} and thus this extends to all β ∈ ℝ^{F} by linearity. Note that the kernel of the map ϕ is the subspace Δ(ℝ^{d}) ≃ ℝ^{d} embedded diagonally into (ℝ^{d})^{V}. This comes from the fact that the 1-skeleton of P is connected. The vertex deformation cone D_{P}^{V} can be reduced modulo the subspace Δ(ℝ^{d}) of parallel translations of polytopes. Similarly, the facet deformation cone can be reduced modulo the subspace Δ′(ℝ^{d}) = ψ^{−1}(Δ(ℝ^{d})) ≃ ℝ^{d}, where Δ′(x) := (h_{f}(x))_{f∈F} for x ∈ ℝ^{d}.

Theorem 15.5. The map ψ gives a linear isomorphism between the cones D_{P}^{F} and D_{P}^{V}. The map ϕ induces a linear isomorphism between the cones D_{P}^{V} /Δ(ℝ^{d}) and D_{P}^{E}. Thus one has

D_{P}^{E} ≃ D_{P}^{V} /Δ(ℝ^{d}) ≃ D_{P}^{F} /Δ′(ℝ^{d}).

In particular, dim D_{P}^{E} = dim D_{P}^{V} − d = dim D_{P}^{F} − d = |F | − d.

Proof. The claim about the map ψ follows immediately from Theorem 15.3. Let us prove the claim about ϕ. Note that, for (x_{v})_{v∈V} ∈ D_{P}^{V}, the point (y_{e})_{e∈E} = ϕ((x_{v})_{v∈V}) satisfies the condition of Definition 15.1(2) because

y_{e_{1}}(v_{1} − v_{2}) + y_{e_{2}}(v_{2} − v_{3}) + ⋯ + y_{e_{k}}(v_{k} − v_{1}) = (x_{v_{1}} − x_{v_{2}}) + (x_{v_{2}} − x_{v_{3}}) + ⋯ + (x_{v_{k}} − x_{v_{1}}) = 0.

It remains to show that for any (y_{e})_{e∈E} ∈ D_{P}^{E} there exists a unique (modulo diagonal translations) element (x_{v})_{v∈V} ∈ H such that x_{u} − x_{v} = y_{e}(u − v) for any edge e = uv ∈ E. Let us construct the points x_{v} ∈ ℝ^{d}, as follows. Pick a vertex v_{0} ∈ V and pick any point x_{v_{0}} ∈ ℝ^{d}. For any other v ∈ V, find a path (v_{0}, v_{1}, …, v_{l}) from v_{0} to v_{l} = v in the 1-skeleton of P and define x_{v} = x_{v_{0}} − y_{v_{0}v_{1}}(v_{0} − v_{1}) − y_{v_{1}v_{2}}(v_{1} − v_{2}) − ⋯ − y_{v_{l−1}v_{l}}(v_{l−1} − v_{l}). This point x_{v} does not depend on a choice of path from v_{0} to v, because any other path in the 1-skeleton can be obtained by switches along 2-dimensional faces of P. These (x_{v})_{v∈V} satisfy the needed conditions. Finally, note that dim D_{P}^{F} = |F | because D_{P}^{F} is a full-dimensional cone.

References

[AK’06] F. Ardila, C. Klivans: The Bergman complex of a matroid and phylogenetic trees, J. Comb. Th. B 96 (2006), 38–49.

[AKW’06] F. Ardila, C. Klivans, L. Williams: The positive Bergman complex of an oriented matroid, European Journal of Combinatorics 27 (2006), no. 4, 577–591.

[AM’06] G. Agnarsson, W. Morris: On Minkowski Sums of Simplices,

          arXiv: math.CO/ 0605564.

[ARW’05] F. Ardila, V. Reiner, L. Williams: Bergman complexes, Coxeter arrangements, and graph associahedra, Sém. Lothar. Combin. 54a (2006), B54Aj (electronic).

[BR’04] E. Babson, V. Reiner: Coxeter-like complexes, Discrete Math. Theor. Comput. Sci. 6 (2004), no. 2, 223–251 (electronic).

[Brä’04] P. Brändén: Sign-graded posets, unimodality of W -polynomials and the Charney-Davis conjecture, Electron. J. Combin. 11 (2004/06), Research Paper 9, 15 pp.

[Brä’06] P. Brändén: Actions on permutations and unimodality of descent polynomials, European J. Combin. 29 (2008), 2, 514–531.

[Cay’1890] A. Cayley: On the partitions of a polygon, Proc. Lond. Math. Soc. 22 (1890), 237–262.

[CD’06] M. Carr, S. Devadoss: Coxeter complexes and graph associahedra, Topology and its Applications (2006), 2155–2168.

[ChD’95] R. Charney, M. Davis: Euler characteristic of a nonpositively curved, piecewise Euclidean manifold, Pac. J. Math. 171 (1995), 117–137.

[DJS’98] M. Davis, T. Januszkiewicz, R. Scott: Nonpositive curvature of blow-ups, Selecta Math. (N.S.) 4 (1998), no. 4, 491–547.

[DJS’03] M. Davis, T. Januszkiewicz, R. Scott: Fundamental groups of minimal blow-ups, Adv. Math. 177 (2003), 115–179.

[DP’95] C. De Concini, C. Procesi: Wonderful models for subspace arrangements, Selecta Math. (N.S.) 1 (1995), 459–494.

[ER’94] P. H. Edelman, V. Reiner: h-shellings and h-complexes, Adv. Math. 106 (1994), no. 1, 36–64.

[FS’05] E.-M. Feichtner, B. Sturmfels: Matroid polytopes, nested sets and Bergman fans, Portugaliae Mathematica 62 (2005), 437– 468.

[FY’04] E.-M. Feichtner, S. Yuzvinsky: Chow rings of toric varieties defined by atomic lattices, Invent. Math. 155 (2004), 515–536.

[FG’65] D. R. Fulkerson, O. A. Gross: Incidence matrices and interval graphs, Pacific J. Math 15 (1965), 835–855.

[Ful’93] W. Fulton: Introduction to toric varieties, Annals of Mathematics Studies131, Princeton University Press, Princeton, NJ, 1993.

[FM’94] W. Fulton, R. MacPherson: A compactification of configuration spaces, Ann. Math. 139 (1994), 183–225.

[Gal’05] S. R. Gal: Real root conjecture fails for five- and higherdimensional spheres. Discrete Comput. Geom. 34 (2005), no. 2, 269–284.

[GJ’83] I. P. Goulden, D. M. Jackson: Combinatorial Enumeration, John Wiley & Sons, 1983.

[GZ’83] C. Greene, T. Zaslavsky: On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Amer. Math. Soc. 280 (1983), no. 1, 97–126.

[Kim’06] S. W. Kim:, Shellable complexes and diagonal arrangements, Extended abstract, FPSAC 2006 (18th International Conference Formal Power Series and Algebraic Combinatorics).

[Lee’89] C. W. Lee: The associahedron and triangulations of the n-gon, European J. Combin. 10 (1989), no. 6, 551–560.

[Lod’04] J.-L. Loday: Realization of the Stasheff polytope, Archiv der Mathematik (Basel) 83 (2004), no. 3, 267–278; arXiv:

math.AT/0212126.

[Mac’17] P. A. MacMahon: Combinatory Analysis, Vol. I, Cambridge, 1917; reprinted by the American Mathematical Society, 2001.

[Man’02] T. Mansour: Restricted 132-alternating permutations and Chebyshev polynomials, Ann. Comb. 7 (2003), 2, 201–227.

[McM’73] P. McMullen: Representations of polytopes and polyhedral sets, Geometriae Dedicata 2 (1973), 83–99.

[M–W’06] J. Morton, L. Pachter, A. Shiu, B. Sturmfels, O. Wienand:, Geometry of rank tests, Proceedings of the conference Probabilistic Graphical Models, Prague, Czech Republic, 2006; arXiv:

math.ST/0605173

[Post’05] A. Postnikov: Permutohedra, associahedra, and beyond, arXiv:

math.CO/0507163.

[RSW’03] V. Reiner, D. Stanton, V. Welker: The Charney-Davis quantity for certain graded posets, Sém. Lothar. Combin. 50 (2003/04), Art. B50c, 13 pp.

[SWG’83] L. Shapiro, W.J. Woan, S. Getu: Runs, slides and moments. SIAM J. Algebraic Discrete Methods 4 (1983), 459–466.

[Sim’94] R. Simion: Combinatorial statistics on noncrossing partitions, J. Combin. Theory Ser. A 66 (1994), 270–301.

[Sim’03] R. Simion: A type-B associahedron, Adv. in Appl. Math. 30 (2003), 2–25.

[Sloa]  N. Sloane:  The On-Line Encyclopedia of In-
teger  Sequences,  published  electronically  at

www.research.att.com/ njas/sequences/, 2007.

[SU’91] R. Simion, D. Ullman: On the structure of the lattice of noncrossing partitions. Discrete Math. 98 (1991), 193–206.

[Stan’92] R. P. Stanley: Subdivisions and local h-vectors, J. Amer. Math. Soc. 5 (1992), 805–851:

[Stan’96] R. P. Stanley: Combinatorics and commutative algebra, 2nd edition, Progress in Mathematics 41, Birkhäuser Boston, Inc., Boston, MA, 1996.

[Stan’97] R. P. Stanley: Enumerative combinatorics, Volume 1, Cambridge University Press, New York, 1997.

[Stan’99] R. P. Stanley: Enumerative Combinatorics, Volume 2, Cambridge University Press, 1999.

[StPi’02] R. P. Stanley, J. Pitman: A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete & Computational Geometry 27 (2002), no. 4, 603–634; arXiv: math.CO/9908029.

[Stash’63] J. D. Stasheff: Homotopy associativity of H-spaces, I, II, Trans. Amer. Math. Soc. 108 (1963), 275–292; ibid. 293–312.

[Stem’07] J. Stembridge: Coxeter cones and their h-vectors, Adv. Math. 217 (2008), 1935–1961.

[Stud’05] M. Studený: Probabilisic conditional independence structures, Springer Series in Information Science and Statistics. Springer-Verlag, London 2005.

[Tol’05] V. Toledano-Laredo: Quasi-Coxeter algebras, Dynkin diagram cohomology and quantum Weyl groups, arXiv: math.QA/0506529.

[Wie’47] H. Wiener: Stuctural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17-20.

[Zel’06] A. Zelevinsky: Nested complexes and their polyhedral realizations, Pure and Applied Mathematics Quarterly 2 (2006), 655–671.

[Zieg’94] G. M. Ziegler: Lectures on polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, 1994.

Alex Postnikov Department of Mathematics Massachusetts Institute

of Technology 77 Massachusetts Avenue Cambridge, MA 02139, USA apost@math.mit.edu Victor Reiner Department of Mathematics University of Minnesota 206 Church Street S.E. Minneapolis, MN, 55455, USA reiner@math.umn.edu

Lauren Williams

Department of Mathematics Harvard University 1 Oxford Street Cambridge, MA 02138, USA lauren@math.harvard.edu 274

Documenta Mathematica 13 (2008)