# 电竞训练基地: PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND

PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND ALEXANDER POSTNIKOV Abstract. The volume and the number of lattice points of the permutohedron Pnare given by certain multivariate polynomials that have remarkable com- binatorial properties. We give 3 diff erent formulas for these polynomials. We also study a more general class of polytopes that includes the permutohedron, the associahedron, the cyclohedron, the Stanley-Pitman polytope, and various generalized associahedra related to wonderful compactifi cations of De Concini- Procesi. These polytopes are constructed as Minkowsky sums of simplices. We calculate their volumes and describe their combinatorial structure. The coef- fi cients of monomials in VolPnare certain positive integer numbers, which we call the mixed Eulerian numbers. These numbers are equal to the mixed volumes of hypersimplices. Various specializations of these numbers give the usual Eulerian numbers, the Catalan numbers, the numbers (n+1)n?1of trees (or parking functions), the binomial coeffi cients, etc. We calculate the mixed Eulerian numbers using certain binary trees. Many results are extended to an arbitrary Weyl group. 1. Permutohedron Let x1,.,xn+1be real numbers. The permutohedron Pn(x1,.,xn+1) is the convex polytope in Rn+1 defi ned as the convex hull of all permutations of the vector (x1,.,xn+1): Pn(x1,.,xn+1) := ConvexHull((xw(1),.,xw(n+1)) | w ∈ Sn+1), where Sn+1is the symmetric group. Actually, this is an n-dimensional polytope that belongs to some hyperplane H ? Rn+1. More generally, for a Weyl group W, we can defi ne the weight polytope as a convex hull of a Weyl group orbit: PW(x) := ConvexHull(w(x) | w ∈ W), where x is a point in the weight space on which the Weyl group acts. For example, for n = 2 and distinct x1,x2,x3, the permutohedron P2(x1,x2,x3) (type A2weight polytope) is the hexagon shown below. If some of the numbers x1,x2,x3are equal to each other then the permutohedron degenerates into a trian- gle, or even a single point. Date: November 21, 2004; based on transparencies dated July 26, 2004. Key words and phrases.Permutohedron, associahedron, Minkowsky sum, mixed volume, Weyl’s character formula, Hall’s marriage theorem, wonderful compactifi cation, nested families, generalized Catalan numbers, Stanley-Pitman polytope, parking functions, hypersimplices, mixed Eulerian numbers, binary trees, shifted tableaux, Gelfand-Zetlin patterns. 1 2ALEXANDER POSTNIKOV P2(x1,x2,x3) = (x1,x2,x3) Question: What is the volume of the permutohedron Vn:= VolPn? Since Pndoes not have the full dimension in Rn+1, one needs to be careful with defi nition of the volume. We assume that the volume form Vol is normalized so that the volume of a unit parallelepiped formed by generators of the integer lattice Zn+1∩ H is 1. More generally, we can ask the following question. Question: What is the number of lattice points Nn:= Pn∩ Zn+1? We will see that both Vnand Nnare polynomials of degree n in the variables x1,.,xn+1. The polynomial Vnis the top homogeneous part of Nn. The Ehrhart polynomial of Pnis E(t) = Nn(tx1,.,txn), and Vn is its top degree coeffi cient. We will give 3 totally diff erent formulas for these polynomials. Let us fi rst mention the special case (x1,.,xn+1) = (n+1,.,1). The polytope Pn(n + 1,n,.,1) = ConvexHull((w(1),.,w(n + 1)) | w ∈ Sn+1) is the most symmetric permutohedron.It is invariant under the action of the symmetric group Sn+1. For example, for n = 2, it is the regular hexagon: regular hexagon subdivided into 3 rhombi The polytope Pn(n + 1,.,1) is a zonotope, i.e., Minkowsky sum of line intervals. It is well known that ? Vn(n + 1,.,1) = (n + 1)n?1is the number of trees on n + 1 labelled vertices. Indeed, Pn(n+1,.,1) can be subdivided into parallelepipeds of unit volume associated with trees. This follows from a general result about zonotopes. ? Nn(n + 1,.,1) is the number of forests on n + 1 labelled vertices. In general, for arbitrary x1,.,xn+1, the permutohedron Pn(x1,.,xn+1) is not a zonotope. We cannot easily calculate its volume by subdividing it into par- allelepipeds. PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND3 2. First Formula Theorem 2.1. Fix any distinct numbers λ1,.,λn+1such that λ1+···+λn+1= 0. We have Vn(x1,.,xn+1) = 1 n! X w∈Sn+1 (λw(1)x1+ ··· + λw(n+1)xn+1)n (λw(1)? λw(2))(λw(2)? λw(3))···(λw(n)? λw(n+1)). Notice that all λi’s in the right-hand side are canceled after the symmetrization. More generally, let W be the Weyl group associated with a rank n root system, and let α1,.,αnbe a choice of simple roots. Theorem 2.2. Let λ be any regular weight. The volume of the weight polytope is VolPW(x) = f |W| X w∈W (λ,x)n (λ,w(α1))···(λ,w(αn)) , where the volume is normalized so that the volume of the parallelepiped generated by the simple roots αiis 1, and f is the index of the root lattice in the weight lattice. Idea of Proof. Let us use Khovansky-Pukhlikov’s method [PK]. Instead of counting the number of lattice points in P, calculate the sum Σ[P] of formal exponents eaover lattice points a ∈ P ∩ Zn. We can work with unbounded polytopes. For example, for a simplicial cone C, the sum Σ[C] is given by a simple rational expression. Any polytope P can be explicitly presented as an alternating sum of simplicial cones Σ[P] = Σ[C1] ± Σ[C2] ± ··· over vertices of P. Applying this method to the weight polytope, we obtain the following claim. Theorem 2.3. For a dominant weight μ, the sum of exponents over lattice points of the weight polytope PW(μ) equals Σ[PW(μ)] := X a∈PW(μ)∩(L+μ) ea= X w∈W ew(μ) (1 ? e?w(α1))···(1 ? e?w(αn)), where L be the root lattice. Compare this claim with Weyl’s character formula! If we replace the product over simple roots αiin the right-hand side of Theorem 2.3 by a similar product over all positive roots, we obtain exactly Weyl’s character formula. Theorem 2.2 and its special case Theorem 2.1 and be deduced from Theorem 2.3 in the same way as Weyl’s dimension formula can be deduced from Weyl’s character formula.? Remark 2.4. The sum of exponents Σ[PW(μ)] over lattice points of the weight polytope is obtained from the character ch Vμof the irreducible representation Vμ of the associated Lie group by replacing all nonzero coeffi cients in chVμwith 1. For example, in type A, chVμis the Schur polynomial sμand Σ[Pn(μ)] is obtained from the Schur polynomial sμ by erasing the coeffi cients of all monomials. 4ALEXANDER POSTNIKOV 3. Second Formula Let us use the coordinates y1,.,yn+1related x1,.,xn+1by ? ? ? ? ? ? ? ? ? ? ? y1= ?x1 y2= ?x2+ x1 y3= ?x3+ 2x2? x1 ··· yn+1= ??n 0 ? xn+ ?n 1 ? xn?1? ··· ± ?n n ? x1 Write Vn= Vol Pn(x1,.,xn+1) as a polynomial in the variables y1,.,yn+1. Theorem 3.1. We have Vn= 1 n! X (S1,.,Sn) y|S1|···y|Sn|, where the sum is over ordered collections of subsets S1,.,Sn? [n + 1] such that, for any distinct i1,.,ik, we have |Si1∪ ··· ∪ Sik| ≥ k + 1. This theorem implies that n!Vnis a polynomial in y2,.,yn+1with positive integer coeffi cients. For example, V1= Vol([(x1,x2),(x2,x1)]) = x1? x2= y2and 2V2= 6y2 2+ 6y2y3+ y23. Remark 3.2. The condition on subsets S1,.,Snin Theorem 3.1 is very similar to the condition in Hall’s marriage theorem. One just needs to replace the inequality ≥ k + 1 with ≥ k to obtain Hall’s marriage condition. It is not hard to prove the following analog of Hall’s theorem. Dragon marriage problem: There are n + 1 brides and n grooms living in a medieval village. A dragon comes to the village and takes one of the brides. We are given a collection G of pairs of brides and grooms that can marry each other. Find the condition on G that ensures that, no matter which bride the dragon takes, it will be possible to match the remaining brides and grooms. Proposition 3.3. (Dragon marriage theorem) Let S1,.,Sn? [n + 1]. The fol- lowing three conditions are equivalent: (1) For any distinct i1,.,ik, we have |Si1∪ ··· ∪ Sik| ≥ k + 1. (2) For any j ∈ [n+1], there is a system of distinct representatives in S1,.,Sn that avoids j. (This is a reformulation of the dragon marriage problem.) (3) One can remove some elements from Si’s to get the edge set of a spanning tree in Kn+1. Theorem 3.1 can be extended to a larger class of polytopes discussed below. 4. Generalized permutohedra Let ?[n+1]= ConvexHull(e1,.,en+1) be the standard coordinate simplex in Rn+1. For a subset I ? [n+1], let ?I= ConvexHull(ei| i ∈ I) denotes the face of the coordinate simplex ?[n+1]. Let Y = {YI} be a collection of parameters YI≥ 0 for all nonempty subsets I ? [n + 1]. Let us defi ne the generalized permutohedron Pn(Y ) as the Minkowsky sum of the simplices ?Iscaled by factors YI: Pn(Y) := X I?[n+1] YI· ?I(Minkowsky sum) PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND5 Generalized permutohedra are obtained from usual permutohedra by moving their faces while preserving all angles. So, instead of n degrees of freedom in usual permutohedra, we have 2n+1? 2 degrees of freedom in generalized permutohedra. a generalized permutohedron this is also a generalized permutohedron The combinatorial type of Pn(Y) depends only on the set of B ? 2[n+1]of I’s for which YI6= 0. Here are some interesting examples of generalized permutohedra. ? If YI= y|I|, i.e., the variables YIare equal to each other for all subsets of the same cardinality, then Pn(Y) is the usual permutohedron Pn. ? If B = {{i,i + 1,.,j} | 1 ≤ i ≤ j ≤ n} is the set of consecutive intervals, then Pn (Y) is the associahedron, also known as the Stasheff polytope. The polytope Pn (Y) can be equivalently defi ned as the Newton polytope of Q 1≤i≤j≤n+1(xi+xi+1+···+xj). This is exactly Loday’s realization of the associahedron, see [L]. ? If B is the set of cyclic intervals, then Pn(Y) is a cyclohedron. ? If B is the set of connected subsets of nodes of a Dynkin diagram, then Pn (Y) the polytope related to De Concini-Procesi’s wonderful compactifi - cation, see [DP], [DJS]. ? If B = {[i] | i = 1,.,n + 1} is the complete fl ag of initial intervals, then Pn(Y) is the Stanley-Pitman polytope from [SP]. Theorem 3.1 can be extended to generalized permutohedra, as follows. Theorem 4.1. The volume of the generalized permutohedron Pn(Y) is given by VolPn(Y) = 1 n! X (S1,.,Sn) YS1···YSn, where the sum is over ordered collections of subsets S1,.,Sn? [n + 1] such that, for any distinct i1,.,ik, we have |Si1∪ ··· ∪ Sik| ≥ k + 1. 6ALEXANDER POSTNIKOV Theorem 4.2. The number of lattice points in the generalized permutohedron Pn(Y) is Pn(Y) ∩ Zn+1= 1 n! X (S1,.,Sn) {YS1···YSn}, where the summation is over the same collections (S1,.,Sn) as before, and (Y I Y aI I ) := (Y[n+1]+1){a[n+1]} Y I6=[n+1] Y {aI} I , where Y {a} = Y (Y +1)···(Y +a?1). In other words, the formula for the number of lattice points in Pn(Y) is obtained from the formula for the volume by replacing usual powers in all terms by raising powers. These formulas generalize formulas from [SP] for the volume and the number of lattice points in the Stanley-Pitman polytope. In this case, collections (S1,.,Sn) of initial intervals Si= [si] that satisfy the dragon marriage condition, see Proposi- tion 3.3, are in one-to-one correspondence with parking functions (s1,.,sn). The volume Pn(Y) is given by the sum over parking functions. 5. Nested families and generalized Catalan numbers In this section, we describe the combinatorial structure of the class of generalized permutohedra Pn(Y) such that the set B ? 2[n+1]of subsets I with nonzero YI satisfi es the following connectivity condition: (B1) If I,J ∈ B and I ∩ J 6= ?, then I ∪ J ∈ B. All examples of generalized permutohedra mentioned in the previous section satisfy this additional condition. Without loss of generality we will also assume that (B2) B contains all singletons {i}, for i ∈ [n + 1]. Indeed, the Minkowsky sum of a polytope with ?{i}, which is a single point, is just a parallel translation of the polytope. Sets B ? 2[n+1]that satisfy conditions (B1) and (B2) are called building sets. Note that condition (B1) implies that all maximal by inclusion elements in B are pairwise disjoint. Let us say that a subset N in a building set B is a nested family if it satisfi es the following conditions: (N1) For any I,J ∈ N, we have either I ? J, or J ? I, or I and J are disjoint. (N2) For any collection of k ≥ 2 disjoint subsets I1,.,Ik∈ N, their union I1∪ ··· ∪ Ikis not in B. (N3) N contains all maximal elements of B. Let N(B) be the poset of all nested families in B ordered by reverse inclusion. Theorem 5.1. The poset of faces of the generalized permutohedron Pn(Y) ordered by inclusion is isomorphic to N(B). This claim was independently discovered by E. M. Feichtner and B. Sturm- fels [FS]. For a graph G on the set of vertices [n+1], let BGbe the collection of nonempty subsets I ? [n+1] such that the induced graph G|Iis connected. Then BG satisfi es conditions (B1) and (B2) of a building set. The generalized permutohedron associ- ated with BGis combinatorially equivalent to the graph associahedron constructed PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND7 by Carr and Devadoss [CD] using blow-ups. In this case, it is enough to require condition (N2) only for pairs of subsets, in the defi nition of a nested family. Remark 5.2. Since our generalized permutohedra include the associahedron, one can also call them generalized associahedra. However this name is already reserved for a diff erent generalization of the associahedron studied by Fomin, Chapoton, and Zelevinsky [FCZ]. Let fB(q) be the f-polynomial of the generalized permutohedron: fB(q) = n X i=0 fiqi= X N∈N(B) qn+1?|N|, where fiis the number of i-dimensional faces of Pn(Y). Let us say that a building set B is connected if it has a unique maximal element. Each building set B is a union of pairwise disjoint connected building sets, called the connected components of B. For a subset S ? [n+1], the induced building set is defi ned as B|S= {I ∈ B | I ? S}. In the case of building sets BGassociated with graphs G, notions of connected components and induced building sets correspond to similar notions for graphs. Theorem 5.3. The f-polynomial fB(q) is determined by the following recurrence relations: (1) If B consists of a single singleton, then fB(q) = 1. (2) If B has connected components B1,.,Bk, then fB(q) = fB1(q)···fBk(q). (3) If B ? 2[n+1]is a connected building and n ≥ 1, then fB(q) = X S([n+1] qn?|S|fB|S(q). Defi ne the generalized Catalan number, for a building set B, as the number C(B) = fB(0) of vertices of the corresponding generalized permutohedron Pn(Y). These numbers are given by the recurrence relations similar to the relations in Theorem 5.3. (But in (3) we sum only over subsets S ? [n + 1] of cardinality n). For a graph G, let C(G) = C(BG). Let Tpqrbe the graph that has a central node with 3 attached chains of with p, q and r vertices. For example, T111is the Dynkin diagram of type D4. The above recurrence relations implies the following expression for the generating function for generalized Catalan numbers: X p,q,r≥0 C(Tpqr)xpyqzr= C(x)C(y)C(z) 1 ? xC(x) ? y C(y) ? z C(z) ,