Séminaire Lotharingien de Combinatoire 66 (2012), Article B66c

THE LOCAL h-VECTOR OF THE CLUSTER SUBDIVISION OF A SIMPLEX

CHRISTOS A. ATHANASIADIS AND CHRISTINA SAVVIDOU

Abstract. The cluster complex Δ(Φ) is an abstract simplicial complex, introduced by Fomin and Zelevinsky for a finite root system Φ. The positive part of Δ(Φ) naturally defines a simplicial subdivision of the simplex on the vertex set of simple roots of Φ. The local h-vector of this subdivision, in the sense of Stanley, is computed and the corresponding γ-vector is shown to be nonnegative. Combinatorial interpretations to the entries of the local h-vector and the corresponding γ-vector are provided for the classical root systems, in terms of noncrossing partitions of types A and B. An analogous result is given for the barycentric subdivision of a simplex.

1. Introduction and results

Local h-vectors were introduced by Stanley [27] as a fundamental tool in his theory of face enumeration for subdivisions of simplicial complexes. Given a (finite, topological) simplicial subdivision Γ of the abstract simplex 2^{V} on an n-element vertex set V, the local h-polynomial ℓ_{V} (Γ, x) is defined as an alternating sum of the h-polynomials of the restrictions of Γ to the faces of 2^{V} (see Section 2 for all relevant definitions). The local h-vector of Γ is the sequence of coefficients ℓ_{V} (Γ) = (ℓ_{0}, ℓ_{1}, …, ℓ_{n}), where ℓ_{V} (Γ, x) = ℓ_{0} + ℓ_{1}x + ⋯ + ℓ_{n}x^{n}.

The importance of local h-vectors stems from their appearance in the locality formula [27, Theorem 3.2], which expresses the h-polynomial of a simplicial subdivision of a pure simplicial complex Δ as a sum of local contributions, one for each face of Δ. Several fundamental properties of local h-vectors, including symmetry for all topological subdivisions, nonnegativity for quasi-geometric subdivisions and unimodality for regular (geometric) subdivisions, were proven in [27].

The local h-vector of the barycentric subdivision of a simplex affords an elegant interpretation [27, Proposition 2.4] in terms of the combinatorics of permutations. The focus of this paper is on another example of subdivision of the simplex with remarkable combinatorial properties, termed as the cluster subdivision. This is the simplicial subdivision of the simplex on the vertex set of simple roots of a finite root system Φ which is naturally defined by the positive part of the cluster complex Δ(Φ) [18] (see the discussion below). Our main results compute the local h-vector of the cluster subdivision, providing combinatorial interpretations for the classical root systems in terms of the combinatorics of noncrossing partitions (for the deep connections between cluster combinatorics and noncrossing partitions see, for instance, [3, 9, 24]).

Before proceeding further, we recall the following notation and terminology from [2]. Let Γ be a simplicial subdivision of an (n − 1)-dimensional simplex 2^{V}. Since ℓ_{V} (Γ, x) has symmetric coefficients, there exists [19, Proposition 2.1.1] a unique polynomial ξ_{V} (Γ, x) = ξ_{0} + ξ_{1}x + ⋯ + ξ_{⌊n/2⌋}x^{⌊n/2⌋} such that

Key words and phrases. Local h-vector, barycentric subdivision, cluster complex, cluster subdivision, γ-vector, noncrossing partition.

ℓ_{V} (Γ, x) = ∑_{i=0}^{⌊n/2⌋} ξ_{i}x^{i}(1 + x)^{n−2i}.

Following [2, Section 5], we will refer to ξ_{V} (Γ, x) as the local γ-polynomial of Γ (with respect to V) and to the sequence ξ_{V} (Γ) = (ξ_{0}, ξ_{1}, …, ξ_{⌊n/2⌋}) as the local γ-vector of Γ (with respect to V). As explained in [2], these concepts play a role in the theory of face enumeration for flag homology spheres and their flag simplicial subdivisions.

We will show that ξ_{V} (Γ, x) has nonnegative coefficients for all cluster subdivisions by providing combinatorial interpretations in terms of noncrossing partitions, or by explicit computation. Since cluster subdivisions are geometric and flag, this result provides evidence for a conjecture by the first author [2, Conjecture 5.4], stating that ξ_{V} (Γ, x) has nonnegative coefficients for a family of simplicial subdivisions of the simplex which includes all flag geometric subdivisions. We will also provide combinatorial interpretations to the coefficients of ξ_{V} (Γ, x) for the barycentric subdivision of the simplex.

The remainder of this section states the main results of this paper in more precise form. Their proofs are given in Sections 3 and 4, after some of the relevant background on simplicial complexes, cluster complexes, simplicial subdivisions and noncrossing partitions is recalled in Section 2. Remarks and related open problems are included in Section 5.

1.1. Cluster subdivisions. Let Φ be a finite root system of rank n, equipped with a positive system Φ^{+} and corresponding simple system Π = {α_{i} : i ∈ I}, where I is an n-element index set. The cluster complex Δ(Φ) was introduced by Fomin and Zelevinsky in the context of algebraic Y -systems [18]. It is an abstract simplicial complex on the vertex set Φ^{+} ∪ (−Π), consisting of the positive roots and the negative simple roots, which is homeomorphic to the (n − 1)-dimensional sphere. When Φ is crystallographic, the combinatorics of Δ(Φ) encodes the exchange of clusters in the corresponding cluster algebra of finite type [17]. An overview of cluster complexes and their connection to cluster algebras can be found in [16]. The restriction Δ_{+}(Φ) of Δ(Φ) on the vertex set Φ^{+}, known as the positive part of Δ(Φ), is homeomorphic to the (n−1)-dimensional ball.

The complex Δ_{+}(Φ) has the structure of a (geometric) simplicial subdivision of the simplex 2^{Π} on the vertex set Π (see Section 2.4). The restriction of this subdivision to the face {α_{i} : i ∈ J} of 2^{Π} indexed by J ⊆ I is the complex Δ_{+}(Φ_{J}), where Φ_{J} is the standard parabolic root subsystem of Φ corresponding to J (so that Φ_{I} = Φ). We will refer to this subdivision as the cluster subdivision associated to Φ and will denote it by Γ(Φ). We will write

(1)  ℓ_{I}(Γ(Φ), x) = ∑_{i=0}^{n} ℓ_{i}(Φ)x^{i}

for the local h-polynomial of Γ(Φ) and ℓ_{I}(Φ) = (ℓ_{0}(Φ), ℓ_{1}(Φ), …, ℓ_{n}(Φ)) for the corresponding local h-vector. The relevant definitions lead (see Section 2.4) to the formula

(2)  ℓ_{I}(Γ(Φ), x) = ∑_{J⊆I} (−1)^{|I∖J|} h(Δ_{+}(Φ_{J}), x),

THE LOCAL h-VECTOR OF THE CLUSTER SUBDIVISION 3

where h(Δ_{+}(Φ_{J}), x) is the h-polynomial of Δ_{+}(Φ_{J}). The results of [27], mentioned earlier, imply that ℓ_{I}(Γ(Φ), x) has nonnegative and symmetric coefficients for every root system Φ.

The h-polynomial of Δ_{+}(Φ) admits several combinatorial interpretations [4, Corollary 1.4 and Theorem 1.5] [3, Corollaries 7.4 and 7.5] in terms of order ideals of roots, hyperplane regions, Weyl group orbits on a finite torus, lattice points and noncrossing partitions. It was computed explicitly for all irreducible (crystallographic) root systems in [4, Section 6]. We denote by NC^{A}(n) and NC^{B}(n) the set of noncrossing partitions of the set {1, 2, …, n} and that of B_{n}-noncrossing partitions, respectively, and refer to Section 2.5 for the relevant background and any undefined terminology. Our first result determines the local h-polynomial of Γ(Φ) as follows.

Theorem 1.1. Let ℓ_{I}(Γ(Φ), x) = ∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} be the local h-polynomial of the cluster subdivision Γ(Φ), associated to an irreducible root system Φ of rank n and Cartan-Killing type X. Then ℓ_{i}(Φ) is equal to:

• the number of partitions π ∈ NC^{A}(n) with i blocks, such that every singleton block of π is nested, if X = A_{n},

• the number of partitions π ∈ NC^{B}(n) with no zero block and i pairs {B, −B} of nonzero blocks, such that every positive singleton block of π is nested, if X = B_{n},

• n − 2 times the number of partitions π ∈ NC^{A}(n − 1) with i blocks, if X = D_{n}.

Moreover, ℓ_{I}(Γ(Φ), x) is equal to

(m − 2)x,  if X = I_{2}(m)
8x + 8x^{2},  if X = H_{3}
42x + 124x^{2} + 42x^{3},  if X = H_{4}
10x + 29x^{2} + 10x^{3},  if X = F_{4}
7x + 63x^{2} + 125x^{3} + 63x^{4} + 7x^{5},  if X = E_{6}
16x + 204x^{2} + 644x^{3} + 644x^{4} + 204x^{5} + 16x^{6},  if X = E_{7}
44x + 748x^{2} + 3380x^{3} + 5472x^{4} + 3380x^{5} + 748x^{6} + 44x^{7}, if X = E_{8}.

We will write ξ_{I}(Φ) = (ξ_{0}(Φ), ξ_{1}(Φ), …, ξ_{⌊n/2⌋}(Φ)) for the local γ-vector of Γ(Φ), so that

(3)  ℓ_{I}(Γ(Φ), x) = ∑_{i=0}^{⌊n/2⌋} ξ_{i}(Φ) x^{i}(1 + x)^{n−2i}.

Our second result computes the numbers ξ_{i}(Φ) (hence, via equation (3), the numbers ℓ_{i}(Φ) as well) explicitly.

Theorem 1.2. Let Φ be an irreducible root system of rank n and Cartan-Killing type X and let ξ_{i}(Φ) be the integers uniquely defined by (3). Then ξ_{0}(Φ) = 0 and

ξ_{i}(Φ) = \begin{cases}\frac{1}{n − i + 1}\binom{n}{i}\binom{n − i − 1}{i − 1}, & if X = A_{n} \\ \binom{n}{i}\binom{n − i − 1}{i − 1}, & if X = B_{n} \\ \frac{n − 2}{i}\binom{2i − 2}{i − 1}\binom{n − 2}{2i − 2}, & if X = D_{n} \end{cases}

for 1 ≤ i ≤ ⌊n/2⌋. Moreover,

∑_{i=0}^{⌊n/2⌋} ξ_{i}(Φ)x^{i} = \begin{cases}(m − 2)x, & if X = I_{2}(m) \\ 8x, & if X = H_{3} \\ 42x + 40x^{2}, & if X = H_{4} \\ 10x + 9x^{2}, & if X = F_{4} \\ 7x + 35x^{2} + 13x^{3}, & if X = E_{6} \\ 16x + 124x^{2} + 112x^{3}, & if X = E_{7} \\ 44x + 484x^{2} + 784x^{3} + 120x^{4}, & if X = E_{8}. \end{cases}

The proof of Theorem 1.2, given in Section 3, shows that when X = A_{n} (respectively, X = B_{n}), the numbers ξ_{i}(Φ) enumerate partitions π ∈ NC^{A}(n) (respectively, partitions π ∈ NC^{B}(n) with no zero block) which have no singleton block, by the number of blocks; see Propositions 3.1 and 3.2.

When Φ is crystallographic, the cluster complex Δ(Φ) can be realized as the boundary complex of a simplicial convex polytope [11]. One may deduce from this statement that Γ(Φ) is a regular (geometric) subdivision of the simplex 2^{Π}. Thus [27, Theorem 5.2] implies that the local h-vector of Γ(Φ) is unimodal, i.e., ℓ_{0}(Φ) ≤ ℓ_{1}(Φ) ≤ ⋯ ≤ ℓ_{⌊n/2⌋}(Φ). The following corollary of Theorem 1.2 provides a stronger statement.

Corollary 1.3. For every root system Φ the local γ-vector of Γ(Φ) is nonnegative, i.e., we have ξ_{i}(Φ) ≥ 0 for every index i.

1.2. Barycentric subdivisions. Let V be an n-element set. We denote by sd(2^{V}) the (first) barycentric subdivision of the simplex 2^{V} and by S_{n} the set of permutations of {1, 2, …, n}. We recall that for w ∈ S_{n}, a descent of w is an index 1 ≤ i ≤ n − 1 such that w(i) > w(i + 1); an excedance of w is an index 1 ≤ i ≤ n such that w(i) > i. The local h-polynomial of sd(2^{V}) was computed in [27, Proposition 2.4] as

(4)  ℓ_{V} (sd(2^{V}), x) = ∑_{w∈D_{n}} x^{ex(w)},

where D_{n} is the set of derangements (permutations with no fixed points) in S_{n} and ex(w) is the number of excedances of w ∈ S_{n}. We will provide similar combinatorial interpretations to the local γ-polynomial of sd(2^{V}) after we introduce some more terminology.

For w ∈ S_{n}, an ascending run (or simply, a run) of w is a maximal string {i, i+1, …, j} of integers, such that w(i) < w(i + 1) < ⋯ < w(j). A double descent of w is an index 2 ≤ i ≤ n − 1 such that w(i − 1) > w(i) > w(i + 1); a double excedance of w is an index 1 ≤ i ≤ n such that w(i) > i > w^{−1}(i). A left to right maximum of w is an index 1 ≤ j ≤ n such that w(i) < w(j) for all 1 ≤ i < j.

Theorem 1.4. Let (ξ_{0}, ξ_{1}, …, ξ_{⌊n/2⌋}) be the local γ-vector of the barycentric subdivision sd(2^{V}) of the (n − 1)-dimensional simplex 2^{V}. Then ξ_{i} is equal to each of the following:

(i) the number of permutations w ∈ S_{n} with i runs and no run of length one, (ii) the number of derangements w ∈ D_{n} with i excedances and no double excedance, (iii) the number of permutations w ∈ S_{n} with i descents and no double descent, such

that every left to right maximum of w is a descent. In particular, we have ξ_{i} ≥ 0 for all 0 ≤ i ≤ ⌊n/2⌋.

For the first few values of n we have:

∑_{i=0}^{⌊n/2⌋} ξ_{i}x^{i} = \begin{cases}x, & if n = 2, 3 \\ x + 5x^{2}, & if n = 4 \\ x + 18x^{2}, & if n = 5 \\ x + 47x^{2} + 61x^{3}, & if n = 6 \\ x + 108x^{2} + 479x^{3}, & if n = 7 \\ x + 233x^{2} + 2414x^{3} + 1385x^{4}, & if n = 8 \\ x + 486x^{2} + 9970x^{3} + 19028x^{4}, & if n = 9. \end{cases}

The right-hand side of (4) is known as the derangement polynomial of order n; see, for instance, [12, Section 1], where some of its basic properties are summarized. Theorem 1.4 gives a combinatorial proof of the unimodality of this polynomial, thus answering a question of Brenti [8]; see the third comment in Section 5. Moreover, it implies that for given n, the sum of the coefficients ξ_{i} is equal to the total number of permutations in S_{n} with no ascending run of length one. Such permutations have been considered (in a more general context) and enumerated by Gessel [20, Chapter 5].

We should point out that the nonnegativity of the numbers ξ_{i} follows from the fact that the derangement polynomials are (symmetric and) real-rooted [31]. Alternatively, this can be deduced from [2, Proposition 6.1], which proves the nonnegativity of the local γ-vector for a family of flag simplicial subdivisions which can be obtained from the trivial subdivision of a simplex by successive stellar subdivisions.

2. Subdivisions, clusters and noncrossing partitions

This section begins by recalling basic definitions on simplicial complexes, simplicial subdivisions and their enumerative invariants. Cluster complexes are then reviewed and cluster subdivisions are formally defined. The section ends with a brief discussion of noncrossing partitions of types A and B. More information on these topics can be found in [5, 16, 25, 29] and references therein. Throughout this paper, |S| denotes the cardinality, and 2^{S} the set of all subsets, of a finite set S.

2.1. Simplicial complexes. Given a finite set Ω, an (abstract) simplicial complex on the ground set Ω is a collection Δ of subsets of Ω such that F ⊆ G ∈ Δ implies F ∈ Δ. The elements of Δ are called faces. The dimension of a face F is defined as one less than the cardinality of F. The dimension of Δ is the maximum dimension of a face and is denoted by dim(Δ). Faces of Δ of dimension zero are called vertices. A face of Δ which is maximal with respect to inclusion is called a facet. The simplicial complex Δ is said to be pure if all its facets have the same dimension. The link of the face F ∈ Δ is the subcomplex of Δ defined as link_{Δ}(F) = {G∖F : G ∈ Δ, F ⊆ G}. The restriction of Δ on the ground set Ω_{0} ⊆ Ω is the subcomplex of Δ consisting of those faces which are contained in Ω_{0}.

Suppose that Ω_{1} and Ω_{2} are two disjoint finite sets. The (simplicial) join Δ_{1} ∗ Δ_{2} of two collections Δ_{1} and Δ_{2} of subsets of Ω_{1} and Ω_{2}, respectively, is the collection whose elements are the sets of the form F_{1} ∪ F_{2}, where F_{1} ∈ Δ_{1} and F_{2} ∈ Δ_{2}. The join of two (or more) simplicial complexes is again a simplicial complex.

Every simplicial complex Δ has a geometric realization ∥Δ∥ [5, Section 9], uniquely defined up to homeomorphism. All topological properties of Δ we mention in the sequel will refer to those of ∥Δ∥. In particular, we say that Δ is a simplicial (topological) ball if ∥Δ∥ is homeomorphic to a ball. The boundary of a simplicial d-dimensional ball Δ is the subcomplex ∂Δ, consisting of all subsets of those (d−1)-dimensional faces of Δ which are contained in a unique facet of Δ. The interior of this ball is the set Δ∖∂Δ; the interior faces are the elements of Δ∖∂Δ. For example, the (abstract) simplex 2^{V}, consisting of all subsets of an n-element set V, is a simplicial (n − 1)-dimensional ball whose only interior face is V. The join of two (or more) simplicial balls is a simplicial ball whose interior is equal to the join of the interiors of these balls.

2.2. Simplicial subdivisions. Given a finite set V, a (finite, topological) simplicial subdivision [27, Section 2] of the abstract simplex 2^{V} is a simplicial complex Γ together with a map σ : Γ → 2^{V}, such that the following hold for every F ⊆ V: (a) the set Γ_{F} := σ^{−1}(2^{F}) is a subcomplex of Γ which is a simplicial ball of dimension dim(F); and (b) the interior of Γ_{F} is equal to σ^{−1}(F). The set σ(E) is called the carrier of the face E ∈ Γ. The complex Γ_{F} is called the restriction of Γ to F ⊆ V. The subdivision Γ is called quasi-geometric [27, Definition 4.1 (a)] if there do not exist E ∈ Γ and face F ∈ 2^{V} of dimension smaller than dim(E), such that the carrier of every vertex of E is contained in F. Moreover, Γ is called geometric [27, Definition 4.1 (b)] if there exists a geometric realization of Γ which geometrically subdivides a geometric realization of 2^{V}.

Suppose that Γ is a simplicial subdivision of the simplex 2^{V} and Γ′ is a simplicial subdivision of the simplex 2^{V′}, where V and V′ are disjoint sets. The join Γ ∗ Γ′ naturally becomes a simplicial subdivision of the simplex 2^{V} ∗ 2^{V′} = 2^{V ∪V′} if one defines the carrier of a face E ∪ E′ ∈ Γ ∗ Γ′ as the union of the carriers of E ∈ Γ and E′ ∈ Γ′. Given faces F ⊆ V and F′ ⊆ V′, the restriction of Γ ∗ Γ′ to the face F ∪ F′ of this simplex is then equal to Γ_{F} ∗ Γ′_{F′}.

2.3. Face enumeration. A fundamental enumerative invariant of a simplicial complex Δ is the h-polynomial, defined by

h(Δ, x) = ∑_{F ∈Δ} x^{|F |}(1 − x)^{d−|F |},

where dim(Δ) = d − 1. For the join of two simplicial complexes Δ_{1} and Δ_{2} we have h(Δ_{1} ∗ Δ_{2}, x) = h(Δ_{1}, x)h(Δ_{2}, x).

The local h-vector of a simplicial subdivision of a simplex was defined in [27, Definition 2.1] as follows.

Definition 2.1. Let V be an n-element set and Γ be a simplicial subdivision of the simplex 2^{V}. The polynomial ℓ_{V} (Γ, x) = ℓ_{0} + ℓ_{1}x + ⋯ + ℓ_{n}x^{n} defined by

(5)  ℓ_{V} (Γ, x) = ∑_{F ⊆V} (−1)^{n−|F |} h(Γ_{F} , x)

is the local h-polynomial of Γ (with respect to V). The sequence ℓ_{V} (Γ) = (ℓ_{0}, ℓ_{1}, …, ℓ_{n}) is the local h-vector of Γ (with respect to V).

The local h-vector ℓ_{V} (Γ) = (ℓ_{0}, ℓ_{1}, …, ℓ_{n}) was shown to be symmetric (meaning that ℓ_{i} = ℓ_{n−i} holds for 0 ≤ i ≤ n) for every simplicial subdivision Γ of 2^{V} [27, Theorem 3.3] and to have nonnegative entries for every quasi-geometric simplicial subdivision Γ of 2^{V} [27, Corollary 4.7]. Moreover (see [27, Example 2.3]), ℓ_{0} = 0 and ℓ_{1} is equal to the number of interior vertices of Γ, for n ≥ 1.

We recall from the introduction that, given a simplicial subdivision Γ of an (n − 1)- dimensional simplex 2^{V}, the local γ-polynomial ξ_{V} (Γ, x) = ξ_{0} + ξ_{1}x + ⋯ + ξ_{⌊n/2⌋}x^{⌊n/2⌋} of Γ (with respect to V) is uniquely defined by

(6)  ℓ_{V} (Γ, x) = (1 + x)^{n} ξ_{V} (Γ, \frac{x}{(1 + x)^{2}} ) = ∑_{i=0}^{⌊n/2⌋} ξ_{i}x^{i}(1 + x)^{n−2i}.

The following lemma will be used in the proof of Corollary 1.3.

Lemma 2.2. Let V and V′ be disjoint finite sets. For all simplicial subdivisions Γ of 2^{V} and Γ′ of 2^{V′} we have ℓ_{V ∪V′} (Γ ∗ Γ′, x) = ℓ_{V} (Γ, x) ℓ_{V′}(Γ′, x) and ξ_{V ∪V′} (Γ ∗ Γ′, x) = ξ_{V} (Γ, x) ξ_{V′}(Γ′, x).

Proof. Let n = |V | and n′ = |V′|. Using the defining equation (5), we find that

ℓ_{V ∪V′} (Γ ∗ Γ′, x) = ∑_{F ⊆V} ∑_{F′⊆V′} (−1)^{|V ∪V′|−|F ∪F′|} h((Γ ∗ Γ′)_{F ∪F′}, x)

= ∑_{F ⊆V} ∑_{F′⊆V′} (−1)^{n+n′−|F |−|F′|} h(Γ_{F} ∗ Γ′_{F′}, x)

= ∑_{F ⊆V} ∑_{F′⊆V′} (−1)^{n−|F |} h(Γ_{F} , x) (−1)^{n′−|F′|} h(Γ′_{F′}, x)

= ℓ_{V} (Γ, x) ℓ_{V′}(Γ′, x).

This result and (6) imply that ξ_{V ∪V′} (Γ ∗ Γ′, x) = ξ_{V} (Γ, x) ξ_{V′}(Γ′, x). □

2.4. Cluster complexes and subdivisions. Let Φ be a finite root system of rank n. As in the introduction, we will fix a positive system Φ^{+} with corresponding simple system Π = {α_{i} : i ∈ I}, where I is an n-element index set, and set Φ_{≥−1} := Φ^{+} ∪ (−Π). For J ⊆ I, the standard parabolic root subsystem Φ_{J} is endowed with the induced positive system Φ_{J}^{+} = Φ^{+} ∩ Φ_{J} and corresponding simple system Π_{J} = {α_{i} : i ∈ J}.

The cluster complex Δ(Φ) is a simplicial complex on the vertex set Φ_{≥−1}. Its faces are the sets consisting of mutually compatible elements of Φ_{≥−1}, where compatibility is a symmetric binary relation on Φ_{≥−1} defined in [18, Section 3]. We refer the reader to [18] [16, Section 4.3] for the precise definition of compatibility and collect the properties of Δ(Φ) and its restriction Δ_{+}(Φ) on the vertex set Φ^{+} which will be important for us, in the following proposition. Part (ii) is implicit in [18, Section 3] (see Lemma 3.12 and the proof of Theorem 1.10 there) and [6, Section 8]. The other parts follow directly from the results of [18, Section 3].

Proposition 2.3. (i) The cluster complex Δ(Φ) is homeomorphic to an (n − 1)-

dimensional sphere. (ii) The complex Δ_{+}(Φ) is homeomorphic to an (n − 1)-dimensional ball. (iii) For J ⊆ I we have link_{Δ(Φ)}(−Π_{J}) = Δ(Φ_{J}). (iv) For J ⊆ I, the restriction of Δ(Φ) to the vertex set (Φ_{J})_{≥−1} is equal to Δ(Φ_{J})

and that of Δ_{+}(Φ) to the vertex set Φ_{J}^{+} is equal to Δ_{+}(Φ_{J}).

(v) If Φ is a direct product Φ_{1} × Φ_{2}, then Δ(Φ) = Δ(Φ_{1}) ∗ Δ(Φ_{2}) and Δ_{+}(Φ) = Δ_{+}(Φ_{1}) ∗ Δ_{+}(Φ_{2}). □

The following result of [4] will be needed in Section 3 in order to compute the right-hand side of (2).

Lemma 2.4. ([4, Proposition 6.1]) For the h-polynomial of Δ_{+}(Φ) we have

h(Δ_{+}(Φ), x) = \begin{cases}∑_{i=0}^{n} \frac{1}{i + 1}\binom{n}{i}\binom{n − 1}{i}x^{i}, & if X = A_{n} \\ ∑_{i=0}^{n} \binom{n}{i}\binom{n − 1}{i}x^{i}, & if X = B_{n} \\ ∑_{i=0}^{n} (\binom{n}{i}\binom{n − 2}{i} + \binom{n − 2}{i − 2}\binom{n − 1}{i}) x^{i}, & if X = D_{n}, \end{cases}

where X is the Cartan-Killing type of Φ. □

We now formally define the cluster subdivision Γ(Φ). Given a positive root α ∈ Φ^{+}, there is a unique set J ⊆ I such that α is a positive linear combination of the elements of Π_{J}. We call Π_{J} the support of α and for E ∈ Δ_{+}(Φ), we denote by σ(E) the union of the supports of the elements of E. Equivalently, σ(E) is the smallest set Π_{J} ⊆ Π such that α ∈ Φ_{J}^{+} for every α ∈ E.

Proposition 2.5. The map σ : Δ_{+}(Φ) ↦ 2^{Π} defines a simplicial subdivision Γ(Φ) of the simplex 2^{Π}, whose local h-polynomial is given by (2).

Figure 1. The cluster subdivision of type A_{3}.

Proof. It suffices to show that for every J ⊆ I: (a) σ^{−1}(2^{Π_{J}}) is a subcomplex of Δ_{+}(Φ) which is homeomorphic to a ball of dimension |J| − 1; (b) σ^{−1}(Π_{J}) is the interior of this ball; and (c) σ^{−1}(2^{Π_{J}}) = Δ_{+}(Φ_{J}). Indeed, (a) and (b) confirm that σ defines a simplicial subdivision of the simplex 2^{Π} and (c) ensures that the restriction of this subdivision to the face Π_{J} of 2^{Π} is equal to Δ_{+}(Φ_{J}). Equation (2) is a consequence of the last statement and Definition 2.1.

Part (c) follows from the definition of the map σ and Proposition 2.3 (iv) and part (a) follows from (c) and Proposition 2.3 (ii). To verify (b), we may assume that J = I. We need to show that the boundary of Δ_{+}(Φ) is equal to the union of the subcomplexes Δ_{+}(Φ_{J}), where J runs through the proper subsets of I. For that, it suffices to show that an (n − 2)-dimensional face, say E, of Δ_{+}(Φ) is contained in a unique facet of Δ_{+}(Φ) if and only if E ∈ Δ_{+}(Φ_{J}) for some (n − 1)-element set J ⊆ I. This is a consequence of parts (i) and (iii) of Proposition 2.3. Indeed, part (i) implies that E is contained in exactly two facets of Δ(Φ). Part (iii) implies that at most one of these contains a negative simple root and that this is the case if and only if E ∈ Δ_{+}(Φ_{J}) for some (n − 1)-element set J ⊆ I. □

Example 2.6. The complex Δ_{+}(Φ) and cluster subdivision Γ(Φ) are drawn on Figure 1 for the root system Φ of type A_{3}. The simple roots α_{1}, α_{2}, α_{3} have been labeled so that α_{1} is orthogonal to α_{3}.

The subdivision Γ(Φ) triangulates the 2-dimensional simplex 2^{Π} into five 2-dimensional simplices, which are the facets of Δ_{+}(Φ). There is one interior vertex, namely α_{1}+α_{2}+α_{3}. The supports of α_{1} + α_{2} and α_{2} + α_{3} are equal to {α_{1}, α_{2}} and {α_{2}, α_{3}}, respectively. The restriction of Γ(Φ) on the face {α_{1}, α_{2}} of 2^{Π} is a subdivision of a 1-dimensional simplex with one interior vertex, namely α_{1} + α_{2}. □

Remark 2.7. One can define a cluster complex, and hence a corresponding cluster subdivision, for every orientation of the Dynkin diagram of Φ [22]; see also [24, Section 7] (the cluster complex of [18] [16, Section 4.3], treated here, corresponds to the alternating orientation). By [22, Proposition 3.4] (see also [24, Proposition 7.3]) and the results of [22, Section 6], the h-vector of the positive part of the cluster complex and the local h-vector of the corresponding cluster subdivision do not depend on the orientation chosen. □

Figure 2. The noncrossing partition {{1, 5, 6}, {2, 4}, {3}, {7}, {8, 9}}.

We conclude this section with the following lemma, which will be used in the proof of Corollary 1.3.

Lemma 2.8. If Φ is a direct product Φ_{1} × Φ_{2}, then Γ(Φ) = Γ(Φ_{1}) ∗ Γ(Φ_{2}).

Proof. This statement follows from Proposition 2.3 (v) and the definitions of the cluster subdivision and the join of two simplicial subdivisions. □

2.5. Noncrossing partitions. This section summarizes those concepts and results from the theory of noncrossing partitions which are involved in the statements and proofs of Theorems 1.1 and 1.2.

The set of noncrossing partitions of {1, 2, …, n}, which we will denote by NC^{A}(n), was introduced and studied by Kreweras [21]. It consists of all set partitions π of {1, 2, …, n} with the following property: if a < b < c < d are such that a, c are contained in a block B of π and b, d are contained in a block B′ of π, then B = B′. An example of a noncrossing partition for n = 9 is shown on Figure 2. Among several other fundamental results, Kreweras [21, Section 4] showed that the cardinality of NC^{A}(n) is equal to the nth Catalan number \frac{1}{n+1} \binom{2n}{n} and that

(7)  ∑_{π∈NC^{A}(n)} x^{n−|π|} = ∑_{i=0}^{n} \frac{1}{i + 1}\binom{n}{i}\binom{n − 1}{i}x^{i}.

We will say that a singleton block {b} of π ∈ NC^{A}(n) is nested if some block of π contains elements a and c such that a < b < c; otherwise we say that {b} is nonnested. For the example of Figure 2 the singleton block {3} is nested, while {7} is not. Clearly, a partition π ∈ NC^{A}(n) with nonnested singleton block {b} is determined by its restrictions to {1, 2, …, b − 1} and {b + 1, …, n}, which are again noncrossing partitions.

Noncrossing partitions of type B were defined by Reiner [25] as follows. A set partition π of {1, 2, …, n} ∪ {−1, −2, …, −n} is called a B_{n}-partition if the following conditions hold: (a) if B is a block of π, then −B (the set obtained by negating the elements of B) is also a block of π; and (b) there is at most one block of π (called the zero block, if present) which contains both i and −i for some i ∈ {1, 2, …, n}. Such a partition can be represented pictorially [1, Section 2] by placing the integers 1, 2, …, n, −1, −2, …, −n (in this order) along a line and drawing arcs above the line between i and j whenever i and j lie in the same block B of π and no other element between them does. The B_{n}-partition π is called noncrossing if no two arcs in this diagram cross. An example for n = 7 appears in Figure 3. The set of noncrossing B_{n}-partitions will be denoted by NC^{B}(n).

We will be interested in the enumeration of noncrossing B_{n}-partitions with no zero block, by the number of blocks. Although we have not been able to locate the following statement explicitly in the literature, its proof follows easily from that of [1, Theorem 2.3].

Figure 3. A B_{7}-noncrossing partition.

Lemma 2.9. The number of partitions π ∈ NC^{B}(n) which have no zero block and a total of k pairs \{B, −B\} of nonzero blocks is equal to \binom{n}{k}\binom{n−1}{k−1}.

Proof. The proof of [1, Theorem 2.3], given in [1, Section 4], shows that the partitions π ∈ NC^{B}(n) which have no zero block and a total of k pairs {B, −B} of nonzero blocks are in one-to-one correspondence with pairs (S, f), where S is a k-element subset of \{1, 2, …, n\} and f : S → \{1, 2, … \} is a map whose values sum to n. Since there are \binom{n}{k} ways to choose S and, for any such choice, there are \binom{n−1}{k−1} ways to choose f, the result follows. □

We will say that a singleton block {b} of π ∈ NC^{B}(n) is nested if some block of π contains an element which precedes b and one which succeeds b in the linear ordering 1, 2, …, n, −1, −2, …, −n; otherwise we say that {b} is nonnested. The example of Figure 3 has the nonnested positive singleton block {3} and the nested positive singleton block {7}. A partition π ∈ NC^{B}(n) with nonnested positive singleton block {b} is determined by its restrictions to {1, 2, …, b − 1} and {b + 1, …, n} ∪ {−b − 1, …, −n}, which are noncrossing partitions of types A and B, respectively.

3. Proofs for cluster subdivisions

This section provides proofs for Theorems 1.1 and 1.2 and Corollary 1.3. As part of the proof for the types A_{n} and B_{n}, combinatorial interpretations similar to those of Theorem 1.1 for the numbers ℓ_{i}(Φ) are provided for the numbers ξ_{i}(Φ).

As in previous sections, Φ = Φ_{I} will be a finite root system of rank n. We will denote by D(Φ) the Dynkin diagram of Φ and identify the vertex set of D(Φ) with the n-element index set I. We will first treat the root systems of types A_{n}, B_{n} and D_{n}.

3.1. The root system A_{n}. The following proposition is the main result of this section. Note that noncrossing partitions with no singleton block and given number of blocks, which appear there, were considered and enumerated by Kreweras [21, Section 5].

Proposition 3.1. For the root system Φ of type A_{n} the following hold:

• ℓ_{i}(Φ) is equal to the number of partitions π ∈ NC^{A}(n) with i blocks, such that every singleton block of π is nested,

• ξ_{i}(Φ) is equal to the number of partitions π ∈ NC^{A}(n) which have no singleton

block and a total of i blocks. Moreover, we have the explicit formula

(8)  ξ_{i}(Φ) = \begin{cases}0, & if i = 0 \\ \frac{1}{n − i + 1}\binom{n}{i}\binom{n − i − 1}{i − 1}, & if 1 ≤ i ≤ ⌊n/2⌋. \end{cases}

For the first few values of n we have

∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} = \begin{cases}0, & if n = 1 \\ x, & if n = 2 \\ x + x^{2}, & if n = 3 \\ x + 4x^{2} + x^{3}, & if n = 4 \\ x + 8x^{2} + 8x^{3} + x^{4}, & if n = 5 \\ x + 13x^{2} + 29x^{3} + 13x^{4} + x^{5}, & if n = 6 \\ x + 19x^{2} + 73x^{3} + 73x^{4} + 19x^{5} + x^{6}, & if n = 7 \\ x + 26x^{2} + 151x^{3} + 266x^{4} + 151x^{5} + 26x^{6} + x^{7}, & if n = 8 \end{cases}

and

∑_{i=0}^{⌊n/2⌋} ξ_{i}(Φ)x^{i} = \begin{cases}0, & if n = 1 \\ x, & if n = 2, 3 \\ x + 2x^{2}, & if n = 4 \\ x + 5x^{2}, & if n = 5 \\ x + 9x^{2} + 5x^{3}, & if n = 6 \\ x + 14x^{2} + 21x^{3}, & if n = 7 \\ x + 20x^{2} + 56x^{3} + 14x^{4}, & if n = 8. \end{cases}

The Dynkin diagram D(Φ) is a path on the vertex set I. For notational convenience we set I = {1, 2, …, n}, where i and i + 1 are adjacent in D(Φ) for 1 ≤ i ≤ n − 1.

Proof of Proposition 3.1. We need to compute the right-hand side of (2), so we focus on h(Δ_{+}(Φ_{J}), x). Lemma 2.4 and Equation (7) show that

(9)  h(Δ_{+}(Φ_{I}), x) = ∑_{π∈NC^{A}(n)} x^{n−|π|}.

For general J ⊆ I we have a direct product decomposition Φ_{J} = Φ_{1} × ⋯ × Φ_{k} into irreducible subsystems Φ_{1}, …, Φ_{k}. The Dynkin diagrams of Φ_{1}, …, Φ_{k} are the connected components of the diagram obtained from D(Φ) by deleting the vertices in I∖J. Since D(Φ) is a path with no multiple edges, each Φ_{i} is again a root system of type A. Denoting by p_{i} the rank of Φ_{i} and using Proposition 2.3 (v) and Equation (9) we find that

h(Δ_{+}(Φ_{J}), x) = h(Δ_{+}(Φ_{1}) ∗ ⋯ ∗ Δ_{+}(Φ_{k}), x) = ∏_{i=1}^{k} h(Δ_{+}(Φ_{i}), x)

= ∏_{i=1}^{k} ∑_{π∈NC^{A}(p_{i})} x^{p_{i}−|π|} = ∑_{π∈NC^{A}(J)} x^{n−|π|},

where NC^{A}(J) denotes the set of partitions π ∈ NC^{A}(n) such that {a} is a nonnested singleton of π for every a ∈ I∖J. The previous computation and (2) imply that

(10)  ∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} = ∑_{J⊆I} (−1)^{|I∖J|} ∑_{π∈NC^{A}(J)} x^{n−|π|}.

A simple application of the principle of inclusion-exclusion shows that the right-hand side of (10) is equal to the sum of x^{n−|π|}, where π runs through those partitions in NC^{A}(n) which have no nonnested singleton block. This result and the fact that ℓ_{i}(Φ) = ℓ_{n−i}(Φ) yield the desired interpretation for ℓ_{i}(Φ).

To prove the interpretation claimed for ξ_{i}(Φ) we need to show that

(11)  ∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} = ∑_{i=0}^{⌊n/2⌋} m_{i} x^{i}(1 + x)^{n−2i},

where m_{i} is the number of partitions π ∈ NC^{A}(n) with a total of i blocks, none of which is a singleton. Let us denote by NC_{0}^{A}(n) the subset of NC^{A}(n) consisting of those noncrossing partitions, every singleton block of which is nested. We define an equivalence relation on NC^{A}(n) by declaring two partitions π_{1} and π_{2} equivalent if there is a one-to-one correspondence, say f, from the set of nonsingleton blocks of π_{1} to the set of nonsingleton blocks of π_{2} such that for every nonsingleton block B of π_{1} the sets B and f(B) have the same minimum and the same maximum element. For example, the partition in Figure 2 is equivalent to a total of four noncrossing partitions, namely itself, {{1, 5, 6}, {2, 3, 4}, {7}, {8, 9}}, {{1, 6}, {2, 3, 4}, {5}, {7}, {8, 9}} and {{1, 6}, {2, 4}, {3}, {5}, {7}, {8, 9}}.

We leave it to the reader to check that this relation restricts to an equivalence relation on NC_{0}^{A}(n) and that each equivalence class within NC_{0}^{A}(n) contains a unique partition π_{0} having no singleton block. Moreover, for the equivalence class O(π_{0}) of such a partition π_{0} ∈ NC_{0}^{A}(n) we have

∑_{π∈O(π_{0})} x^{|π|} = x^{i}(1 + x)^{n−2i},

where i is the number of blocks of π_{0}. Summing the previous equation over all elements π_{0} ∈ NC_{0}^{A}(n) which have no singleton block we get (11).

Finally, (8) is a consequence of the equality ξ_{i}(Φ) = m_{i} and the results of [21, p. 344], which enumerate noncrossing partitions with no singleton block and given number of blocks. □

3.2. The root system B_{n}. This section proves the following statement on the case X = B_{n}.

Proposition 3.2. For the root system Φ of type B_{n} the following hold:

• ℓ_{i}(Φ) is equal to the number of partitions π ∈ NC^{B}(n) with no zero block and i pairs {B, −B} of nonzero blocks, such that every positive singleton block of π is nested,

• ξ_{i}(Φ) is equal to the number of partitions π ∈ NC^{B}(n) which have no zero block, no singleton block and a total of i pairs {B, −B} of nonzero blocks.

Moreover, we have the explicit formula

(12)  ξ_{i}(Φ) = \begin{cases}0, & if i = 0 \\ \binom{n}{i}\binom{n − i − 1}{i − 1}, & if 1 ≤ i ≤ ⌊n/2⌋. \end{cases}

For the first few values of n we have

∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} = \begin{cases}2x, & if n = 2 \\ 3x + 3x^{2}, & if n = 3 \\ 4x + 14x^{2} + 4x^{3}, & if n = 4 \\ 5x + 35x^{2} + 35x^{3} + 5x^{4}, & if n = 5 \\ 6x + 69x^{2} + 146x^{3} + 69x^{4} + 6x^{5}, & if n = 6 \\ 7x + 119x^{2} + 427x^{3} + 427x^{4} + 119x^{5} + 7x^{6}, & if n = 7 \end{cases}

and

∑_{i=0}^{⌊n/2⌋} ξ_{i}(Φ)x^{i} = \begin{cases}2x, & if n = 2 \\ 3x, & if n = 3 \\ 4x + 6x^{2}, & if n = 4 \\ 5x + 20x^{2}, & if n = 5 \\ 6x + 45x^{2} + 20x^{3}, & if n = 6 \\ 7x + 84x^{2} + 105x^{3}, & if n = 7 \\ 8x + 140x^{2} + 336x^{3} + 70x^{4}, & if n = 8. \end{cases}

The Dynkin diagram D(Φ) is a path on the vertex set I = {1, 2, …, n} with one double edge. We will assume that i and i + 1 are adjacent in D(Φ) for 1 ≤ i ≤ n − 1 and that the double edge connects vertices n − 1 and n.

Proof of Proposition 3.2. A proof which parallels that of Proposition 3.1 can be given as follows. We denote by NC_{+}^{B}(n) the set of partitions π ∈ NC^{B}(n) which do not have a zero block. To compute the right-hand side of (2), we consider h(Δ_{+}(Φ_{J}), x) for J ⊆ I. Lemmas 2.4 and 2.9, together with some straightforward computations, show that

(13)  h(Δ_{+}(Φ_{I}), x) = ∑_{π∈NC_{+}^{B}(n)} x^{n−∥π∥},

where ∥π∥ stands for the number of pairs {B, −B} of (nonzero) blocks of π. For general J ⊆ I we claim that

(14)  h(Δ_{+}(Φ_{J}), x) = ∑_{π∈NC_{+}^{B}(J)} x^{n−∥π∥},

where NC_{+}^{B}(J) denotes the set of partitions π ∈ NC_{+}^{B}(n) such that {a} is a nonnested (positive) singleton block of π for every a ∈ I∖J. Given (14), the first statement follows by an application of inclusion-exclusion, as in the type A_{n} case.

The proof of (14) proceeds without essential change if n − 1 or n does not belong to J. Otherwise we have {n−1, n} ⊆ J and the argument in the proof of Proposition 3.1 should be modified as follows. Let b denote the maximum element of I∖J. Then {b+1, …, n} is the vertex set of the Dynkin diagram of one of the irreducible components, say Φ_{k}, of Φ_{J}. This component is of type B, while each of Φ_{1}, …, Φ_{k−1} is of type A. Moreover, given π ∈ NC_{+}^{B}(J), the restriction of π on {b+1, …, n}∪{−b−1, …, −n} is a noncrossing partition of type B, while that on the vertex set of the Dynkin diagram of each of Φ_{1}, …, Φ_{k−1} is a noncrossing partition of type A. Thus (14) follows by the computation in proof of Proposition 3.1 and the use of (9) and (13).

For the second statement, we need to replace the equivalence relation on NC^{A}(n) by one on NC_{+}^{B}(n), defined as follows. Suppose that π ∈ NC_{+}^{B}(n) has a nested positive singleton block {b}. Then there is a unique block B ∈ π such that replacing the blocks B, −B, {b} and {−b} of π by the unions B ∪{b} and (−B)∪{−b} results in a noncrossing partition π′ ∈ NC_{+}^{B}(n). The required equivalence relation on NC_{+}^{B}(n) is defined as the finest equivalence relation under which π and π′ are equivalent for all such pairs (π, b). For example, the partition in Figure 3 is equivalent to exactly one other noncrossing partition, of which {5, 6, 7, −4} is a block. The proof then proceeds as in the type A_{n} case with only trivial adjustments; the details are left to the reader.

Finally, to deduce the explicit formula (12) we argue as in the proof of Lemma 2.9. The proof of [1, Theorem 2.3] shows that the partitions π ∈ NC^{B}(n) which have no zero block, no singleton block and a total of i pairs {B, −B} of nonzero blocks are in one-to-one correspondence with pairs (S, f), where S is an i-element subset of {1, 2, …, n} and f : S → {2, 3, … } is a function whose values sum to n. Clearly, the number of such pairs is given by the right-hand side of (12) and the proof follows. □

3.3. The root system D_{n}. This section proves the following part of Theorems 1.1 and 1.2.

Proposition 3.3. For the root system Φ of type D_{n} we have:

ℓ_{i}(Φ) = (n − 2) · # {π ∈ NC^{A}(n − 1) : |π| = i}

= \begin{cases}0, & if i = 0 \\ \frac{n − 2}{i}\binom{n − 1}{i − 1}\binom{n − 2}{i − 1}, & if 1 ≤ i ≤ n, \end{cases}

and

ξ_{i}(Φ) = \begin{cases}0, & if i = 0 \\ \frac{n − 2}{i}\binom{2i − 2}{i − 1}\binom{n − 2}{2i − 2}, & if 1 ≤ i ≤ ⌊n/2⌋. \end{cases}

For the first few values of n we have

∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} = \begin{cases}2x + 6x^{2} + 2x^{3}, & if n = 4 \\ 3x + 18x^{2} + 18x^{3} + 3x^{4}, & if n = 5 \\ 4x + 40x^{2} + 80x^{3} + 40x^{4} + 4x^{5}, & if n = 6 \\ 5x + 75x^{2} + 250x^{3} + 250x^{4} + 75x^{5} + 5x^{6}, & if n = 7 \end{cases}

and

∑_{i=0}^{⌊n/2⌋} ξ_{i}(Φ)x^{i} = \begin{cases}2x + 2x^{2}, & if n = 4 \\ 3x + 9x^{2}, & if n = 5 \\ 4x + 24x^{2} + 8x^{3}, & if n = 6 \\ 5x + 50x^{2} + 50x^{3}, & if n = 7 \\ 6x + 90x^{2} + 180x^{3} + 30x^{4}, & if n = 8. \end{cases}

One can easily deduce from Proposition 3.3 a combinatorial interpretation to the numbers ξ_{i}(Φ); see also [23, Section 11.3]. We are not aware, however, of one which is analogous to those in Propositions 3.1 and 3.2 for types A_{n} and B_{n}.

The following notation and enumerative result will be used in the proof of Proposition 3.3. We will write

C_{n}(x) := ∑_{π∈NC^{A}(n)} x^{|π|−1} = ∑_{π∈NC^{A}(n)} x^{n−|π|} = ∑_{i=0}^{n} \frac{1}{i + 1}\binom{n}{i}\binom{n − 1}{i}x^{i}

and

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

Then (see, for instance, [23, Equation (11)] and [28, Exercise 6.36]) we have

(16)  F (x, t) = xt F^{2}(x, t) + (1 + x)t F (x, t) + t.

We will label the vertices of the Dynkin diagram D(Φ) so that i and i + 1 are adjacent in D(Φ) for 1 ≤ i ≤ n − 3, while n − 2 is adjacent to both n − 1 and n.

Proof of Proposition 3.3. Let us write ℓ_{n}(x) := ℓ_{I}(Γ(Φ), x) = ∑_{i=0}^{n} ℓ_{i}(Φ)x^{i} for n ≥ 4. The proposed formula for ℓ_{i}(Φ) is equivalent to the equation

(17)  ℓ_{n}(x) = (n − 2) · x C_{n−1}(x).

The formula for ξ_{i}(Φ) follows from that and the known explicit formula (see [23, Proposition 11.14]) for the γ-polynomial associated to C_{n}(x). Thus, it suffices to prove (17).

We begin by rewriting the right-hand side of (2) in the following way. For 1 ≤ r ≤ n, we will denote by J_{r} the collection of all subsets J ⊆ I which contain {1, 2, …, r − 1} but do not contain r. Using Proposition 2.3 (v) and the type A_{n} case of Lemma 2.4, we find that

∑_{J∈J_{r}} (−1)^{|I∖J|} h(Δ_{+}(Φ_{J}), x) = \begin{cases}− ℓ_{n−1}(x), & if r = 1 \\ − C_{r−1}(x) ℓ_{n−r}(x), & if 2 ≤ r ≤ n − 3 \\ 0, & if r = n − 2, \\ C_{n−2}(x) − C_{n−1}(x), & if r = n − 1, \\ − C_{n−1}(x), & if r = n. \end{cases}

As a result, (2) can be rewritten as

ℓ_{n}(x) = h(Δ_{+}(Φ_{I}), x) − ℓ_{n−1}(x) − ∑_{r=2}^{n−3} C_{r−1}(x) ℓ_{n−r}(x) + C_{n−2}(x) − 2C_{n−1}(x).

Thus, using induction on n, it suffices to prove that

h(Δ_{+}(Φ_{I}), x) = (n − 2)xC_{n−1}(x) + (n − 3)xC_{n−2}(x)

+ ∑_{r=2}^{n−3} (n − r − 2)xC_{r−1}(x)C_{n−r−1}(x) − C_{n−2}(x) + 2C_{n−1}(x) (18)

for n ≥ 4. Let R_{n}(x) denote the right-hand side of (18) and S_{n}(x) denote the sum which appears there. It follows directly from (15) that

∑_{n≥4} S_{n}(x)t^{n} = xt^{3}F (x, t) \frac{∂F}{∂t} (x, t) − xt^{2}F^{2}(x, t).

Using (16), as well as the equation which results from that by differentiation with respect to t, we can rewrite the previous equation as

∑_{n≥4} 2S_{n}(x)t^{n} = 2(1 + x)t^{2}F (x, t) + 2t^{2} − 3tF (x, t) + (t^{2} − t^{3} − xt^{3}) \frac{∂F}{∂t} (x, t).

Equating the coefficients of t^{n} in the two sides above, we conclude that

2S_{n}(x) = (n − 4)C_{n−1}(x) − (n − 4)(1 + x)C_{n−2}(x)

and hence that

R_{n}(x) = (n − 2)xC_{n−1}(x) + \frac{n}{2}C_{n−1}(x) + (\frac{n}{2} − 1)(x − 1)C_{n−2}(x).

Equation (18) follows from the formula for h(Δ_{+}(Φ_{I}), x), given by the type D_{n} case of Lemma 2.4, and the previous expression for R_{n}(x) by straightforward computation. This completes the proof of the proposition. □

Proof of Theorems 1.1 and 1.2. The cases X ∈ {A_{n}, B_{n}, D_{n}} are covered by Propositions 3.1, 3.2 and 3.3. For X ∈ {F_{4}, E_{6}, E_{7}, E_{8}} the proposed formulas follow from (2) by explicit computation, based on the formulas for h(Δ_{+}(Φ), x) given in [4, Section 6]. It remains to comment on the cases of types I_{2}(m), H_{3} and H_{4}.

For types I_{2}(m) and H_{3}, it follows from the theory of local h-vectors (see parts (c) and (d) of [27, Example 2.3]) that ξ_{I}(Γ(Φ), x) = tx, where t is the number of interior vertices of Γ(Φ). We have t = m − 2 for X = I_{2}(m) and t = 8 for X = H_{3} (see [6, Figure 1] or Remark 1 in Section 5) and the proposed formulas follow. Finally, let X = H_{4}. From (2),

(3) and the fact that ξ_{0}(Φ) = ℓ_{0}(Φ) = 0 we get

ξ_{1}(Φ)x(1 + x)^{2} + ξ_{2}(Φ)x^{2} = ∑_{J⊆I} (−1)^{|I∖J|} h(Δ_{+}(Φ_{J}), x).

Setting x = 1 in the previous equality we get

(19)  4ξ_{1}(Φ) + ξ_{2}(Φ) = ∑_{J⊆I} (−1)^{|I∖J|} N^{+}(Φ_{J}),

where N^{+}(Ψ) denotes the number of facets of Δ_{+}(Ψ) (i.e., the number of positive clusters for the root system Ψ). The right-hand side of (19) can be easily computed by hand (it equals 208), using [18, Proposition 3.9] and Proposition 2.3 (v). Since ξ_{1}(Φ) = ℓ_{1}(Φ) is equal to the number of interior vertices of Γ(Φ), we have ξ_{1}(Φ) = 42 (see Remark 1 in Section 5). It follows from (19) that ξ_{2}(Φ) = 40. □

Proof of Corollary 1.3. Theorem 1.2 shows that the statement holds when Φ is irreducible. The general case then follows from Lemmas 2.2 and 2.8. □

4. Proof of Theorem 1.4

We first review two of the tools from the combinatorics of permutations which will be used in the proof of Theorem 1.4. Throughout this section, we will denote by E_{n} the set of permutations in S_{n} for which every left to right maximum is a descent.

Descents and excedances. Given a permutation w ∈ S_{n}, we may write w in cycle form so that each cycle begins with its largest element and the cycles of w are arranged in the increasing order of their largest elements (this is the standard representation of w, discussed on [26, p. 17]). We denote by ϕ(w) the sequence (or word) which is obtained after removing the parentheses from the cycles of w, considered as a permutation in S_{n}. For instance, if n = 9 and w = (5 2 4)(6 1)(8)(9 7 3) in standard cycle form, then ϕ(w) = (5, 2, 4, 6, 1, 8, 9, 7, 3) is the permutation in S_{9} which maps 1 to 5, 2 to itself, 3 to 4 etc. The following properties hold (recall that D_{n} denotes the set of derangements in S_{n}):

(a) the map ϕ : S_{n} → S_{n} is bijective,

(b) ϕ(D_{n}) = E_{n},

(c) for w ∈ S_{n} and 1 ≤ i ≤ n we have w(i) < i if and only if i is a descent of ϕ(w). We will denote by ϕ̂: D_{n} → E_{n} the bijective map induced by ϕ on the set D_{n}.

The Foata-Schützenberger-Strehl action. We will need the following variant of the Foata-Schützenberger-Strehl action on permutations; see, for instance, [14, Section V.1] [13, 15]. Up to date expositions and several applications of this construction can be found in [7, 23].

We let w = (w_{1}, w_{2}, …, w_{n}) be a permutation in E_{n}, where w_{i} = w(i) for 1 ≤ i ≤ n, and set w_{0} = 0 and w_{n+1} = n + 1. A double ascent of w is an index 1 ≤ i ≤ n such that w_{i−1} < w_{i} < w_{i+1}. Given a double ascent or a double descent i of w, we define the permutation ψ_{i}(w) ∈ S_{n} as follows: If i is a double ascent of w, then ψ_{i}(w) is the permutation obtained from w by moving w_{i} between w_{j} and w_{j+1}, where j is the largest index satisfying 1 ≤ j < i and w_{j} > w_{i} > w_{j+1} (note that such an index exists, since

Figure 4. The permutation w = (7, 3, 1, 5, 6, 9, 8, 2, 4) ∈ E_{9}.

w ∈ E_{n} and hence i is not a left to right maximum of w). Similarly, if i is a double descent of w, then ψ_{i}(w) is the permutation obtained from w by moving w_{i} between w_{j} and w_{j+1}, where j is the smallest index satisfying i < j ≤ n and w_{j} < w_{i} < w_{j+1} (note that such an index exists, since w_{n+1} = n + 1). For instance, for the example of Figure 4 we have ψ_{4}(w) = (7, 5, 3, 1, 6, 9, 8, 2, 4) and ψ_{7}(w) = (7, 3, 1, 5, 6, 9, 2, 4, 8). Since the values at left to right maxima are unchanged when passing from w to ψ_{i}(w), we have ψ_{i}(w) ∈ E_{n} in both cases.

We call two permutations in E_{n} equivalent (under the Foata-Schützenberger-Strehl action on E_{n}) if one can be obtained by applying a sequence of maps of the form ψ_{i} to the other. We leave it to the reader to check that this defines an equivalence relation on E_{n} and that each equivalence class contains a unique element having no double descent. Moreover, if w ∈ E_{n} has no double descent and k double ascents, then the equivalence class O(w) of w has 2^{k} elements and exactly \binom{k}{j} of them have j descents more than w, so that

(20)  ∑_{u∈O(w)} x^{des(u)} = x^{des(w)}(1 + x)^{k} = x^{des(w)}(1 + x)^{n−2des(w)}.

Proof of Theorem 1.4. Starting from (4) we find that

ℓ_{V} (Γ, x) = ∑_{u∈D_{n}} x^{ex(u)} = ∑_{u∈D_{n}} x^{ex(u^{−1})} = ∑_{u∈D_{n}} x^{n−ex(u)} = ∑_{u∈E_{n}} x^{des(u)},

where the last equality uses property (c) for the map ϕ̂ : D_{n} → E_{n}. Summing (20) over all equivalence classes of the Foata-Schützenberger-Strehl action on E_{n} we get

∑_{u∈E_{n}} x^{des(u)} = ∑_{w∈Ê_{n}} x^{des(w)}(1 + x)^{n−2des(w)},

where Ê_{n} denotes the set of permutations w ∈ E_{n} with no double descent. From the previous equalities and (6) we conclude that ξ_{i} is equal to the number of permutations w ∈ Ê_{n} with des(w) = i, so we have derived interpretation (iii) in the theorem. The latter and property (c), applied to the map ϕ̂ : D_{n} → E_{n}, imply that ξ_{i} is also equal to the number of derangements w ∈ D_{n} with n − i excedances and no index j satisfying w(j) < j < w^{−1}(j). Passing to the inverse permutation w^{−1} leads to interpretation (ii) of the theorem.

Finally, to check the equality between (i) and (ii), we work with descending (instead of ascending) runs. We observe that the map ϕ̂ : D_{n} → E_{n} induces a bijection from the set of derangements w ∈ D_{n} with no double excedance onto the set of permutations in S_{n} with no descending run of length one. Moreover, the number of excedances of such w is equal to the number of descending runs of ϕ̂(w) and the proof follows. □

5. Remarks

1. It follows from the results of [27, Section 2] (see also our discussion in Section 2.3) that ℓ_{1}(Φ) = ξ_{1}(Φ) is equal to the number of interior vertices of Γ(Φ). These vertices are exactly the positive roots of Φ with support equal to Π (i.e., the positive roots which do not belong to any proper parabolic root subsystem Φ_{J}). The number of these roots was computed by Chapoton [10] and admits an elegant, uniform formula; see [10, Proposition 1.1]. It would be interesting to find uniform interpretations or formulas for ℓ_{i}(Φ) or ξ_{i}(Φ) for other values of i. We are not aware of a simple closed form expression for ℓ_{i}(Φ) in the type A_{n} and B_{n} cases.

2. It is natural to inquire for a more conceptual proof of Proposition 3.3, in the spirit of those of Propositions 3.1 and 3.2.

3. The unimodality of the derangement polynomials was first proved by Brenti [8, Corollary 1], who also asked for a combinatorial proof [8, p. 1140]. Such a proof was given by Stembridge [30, Corollary 2.2]. Theorem 1.4 provides another combinatorial proof (for a stronger statement). Since the barycentric subdivision sd(2^{V}) is a regular subdivision of 2^{V}, the unimodality of the derangement polynomials also follows from (4) and [27, Theorem 5.2].

Acknowledgments

The authors wish to thank the anonymous referees for their helpful comments. The second author was co-financed by the European Union (European Social Fund - ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: Heracleitus II. Investing in knowledge society through the European Social Fund.

References

[1] C.A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Combin. 5 (1998), Research Paper 42, 16pp (electronic).

[2] C.A. Athanasiadis, Flag subdivisions and γ-vectors, preprint, 2011, arχiv:1106.4520.

[3] C.A. Athanasiadis, T. Brady, J. McCammond and C. Watt, h-Vectors of generalized associahedra and noncrossing partitions, Int. Math. Res. Not. vol. 2006, Article 69705, 28pp.

[4] C.A. Athanasiadis and E. Tzanaki, On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements, J. Algebraic Combin. 23 (2006), 355–375.

[5] A. Björner, Topological methods, in Handbook of Combinatorics (R.L. Graham, M. Grötschel and L. Lovász, eds.), North Holland, Amsterdam, 1995, pp. 1819–1872.

[6] T. Brady and C. Watt, Lattices in finite real reflection groups, Trans. Amer. Math. Soc. 360 (2008), 1983–2005.

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

[8] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc. 108 (1990), 1133–1141.

[9] F. Chapoton, Enumerative properties of generalized associahedra, Sém. Lothar. Combin. 51 (2004), Article B51b, 16pp (electronic).

[10] F. Chapoton, Sur le nombre de rèflections pleines dans les groupes de Coxeter finis, Bull. Belgian Math. Soc. 13 (2006), 585–596.

[11] F. Chapoton, S. Fomin and A.V. Zelevinsky, Polytopal realizations of generalized associahedra, Canad. Math. Bull. 45 (2002), 537–566.

[12] W.Y.C. Chen, R.L. Tang and A.F.Y. Zhao, Derangement polynomials and excedances of type B, Electron. J. Combin. 16 (2) (2009), Research Paper 15, 16pp (electronic).

[13] D. Foata, Groupes de réarrangements et nombres d’Euler, C.R. Acad. Sci. Paris Sr. A–B 275 (1972), 1147–1150.

[14] D. Foata and M.-P. Schützenberger, Théorie Géometrique des Polynômes Eulériens, Lecture Notes in Mathematics 138, Springer-Verlag, 1970.

[15] D. Foata and V. Strehl, Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers, Math. Z. 137 (1974), 257–264.

[16] S. Fomin and N. Reading, Root systems and generalized associahedra, in Geometric Combinatorics (E. Miller, V. Reiner and B. Sturmfels, eds.), IAS/Park City Mathematics Series 13, pp. 389–496, Amer. Math. Society, Providence, RI, 2007.

[17] S. Fomin and A.V. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc. 15 (2002), 497–529.

[18] S. Fomin and A.V. Zelevinsky, Y -systems and generalized associahedra, Ann. of Math. 158 (2003), 977–1018.

[19] S.R. Gal, Real root conjecture fails for five- and higher-dimensional spheres, Discrete Comput. Geom. 34 (2005), 269–284.

[20] I.M. Gessel, Generating functions and enumeration of sequences, Ph.D. Thesis, MIT, 1977.

[21] G. Kreweras, Sur les partitions non-croisées d’un cycle, Discrete Math. 1 (1972), 333–350.

[22] R. Marsh, M. Reineke and A.V. Zelevinsky, Generalized associahedra via quiver representations, Trans. Amer. Math. Soc. 355 (2003), 4171–4186.

[23] A. Postnikov, V. Reiner and L. Williams, Faces of generalized permutohedra, Doc. Math. 13 (2008), 207–273.

[24] N. Reading, Clusters, Coxeter sortable elements and noncrossing partitions, Trans. Amer. Math. Soc. 359 (2007), 5931–5958.

[25] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195– 222.

[26] R.P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 1997.

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

[28] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, Cambridge, 1999.

[29] R.P. Stanley, Combinatorics and Commutative Algebra, second edition, Birkhäuser, Basel, 1996.

[30] J.R. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math. 99 (1992), 307–320.

[31] X. Zhang, On q-derangement polynomials, in Combinatorics and Graph Theory ’95, Vol. 1 (Hefei), pp. 462–465, World Sci. Publishing, River Edge, NJ, 1995.

Department of Mathematics (Division of Algebra-Geometry), University of Athens, Panepistimioupolis, 15784 Athens, Greece

E-mail address: caath@math.uoa.gr, savvtina@math.uoa.gr