Séminaire Lotharingien de Combinatoire 77 (2018), Article B77i

GAMMA-POSITIVITY IN COMBINATORICS AND GEOMETRY

CHRISTOS A. ATHANASIADIS

Abstract. Gamma-positivity is an elementary property that polynomials with symmetric coefficients may have, which directly implies their unimodality. The idea behind it stems from work of Foata, Schützenberger and Strehl on the Eulerian polynomials; it was revived independently by Brändén and Gal in the course of their study of poset Eulerian polynomials and face enumeration of flag simplicial spheres, respectively, and has found numerous applications since then. This paper surveys some of the main results and open problems on gamma-positivity, appearing in various combinatorial or geometric contexts, as well as some of the diverse methods that have been used to prove it.

Contents

1. Introduction  2
2. Gamma-positivity in combinatorics  3
2.1. Variations of Eulerian polynomials  3
2.2. Coxeter–Narayana polynomials  24
2.3. Polynomials arising from enriched poset partitions  27
2.4. Polynomials arising from poset homology  28
2.5. Polynomials arising from symmetric functions  30
2.6. Polynomials arising from trees  33
3. Gamma-positivity in geometry  34
3.1. Flag triangulations of spheres  35
3.2. Flag triangulations of simplices  39
3.3. Examples  42
4. Methods  46
4.1. Valley hopping  47
4.2. Methods of geometric combinatorics  49
4.3. Symmetric/quasisymmetric function methods  52
5. Generalizations  54
5.1. Nonsymmetric γ-positivity  54
5.2. Equivariant γ-positivity  55
5.3. q-γ-positivity  58
References  59

2010 Mathematics Subject Classification. Primary 05A15, 05E45; Secondary 05A05, 05E05, 06A11, 20F55.

Key words and phrases. Gamma-positivity, unimodality, Eulerian polynomial, flag triangulation, hpolynomial, local h-polynomial, quasisymmetric function.

1. Introduction

The unimodality of polynomials is a major theme which has occupied mathematicians for the past few decades. At least three surveys [27, 32, 122] about unimodal, log-concave and real-rooted polynomials, showing the enormous variety of methods which are available to prove these properties, have been written. This survey article focuses on a related elementary property, that of γ-positivity, which directly implies symmetry and unimodality and has provided a new exciting approach to this topic. Gamma-positivity appears surprisingly often in combinatorial and geometric contexts; this article aims to discuss some of the main examples, results, methods and open problems around it.

This introductory section provides basic definitions and related comments, as well as an outline of the remainder of the article. We recall that a polynomial f(x) = ∑_{i} a_{i}x^{i} ∈ ℝ[x] is called

• symmetric, with center of symmetry n/2, if a_{i} = a_{n−i} for all i ∈ ℤ (where a_{i} = 0 for negative values of i),

• unimodal, if 0 ≤ a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{k} ≥ a_{k+1} ≥ ⋯ for some k ∈ ℕ,

• γ-positive, if

(1)  f(x) = ∑_{i=0}^{⌊n/2⌋} γ_{i}x^{i}(1 + x)^{n−2i}

for some n ∈ ℕ and nonnegative reals γ_{0}, γ_{1}, …, γ_{⌊n/2⌋}, and

• real-rooted, if every root of f(x) is real, or else f(x) = 0. The notion of γ-positivity appeared first in the work of D. Foata and M. Schützenberger

[56] and subsequently of D. Foata and V. Strehl [57, 58] on the classical Eulerian polynomials, discussed in detail in Sections 2.1.1 and 4.1. After having implicitly reappeared in the theory of enriched poset partitions of J. Stembridge [133] (see also Section 2.3), it was brought again to light independently by P. Brändén [24, 26] and Ś. Gal [61] in the course of their study of poset Eulerian polynomials and face enumeration of flag triangulations of spheres, respectively (see Sections 2.1.2 and 3.1). These works made it clear that γpositivity is a concept of independent interest which provides a powerful approach to the problem of unimodality for symmetric polynomials. Symmetry and real-rootedness of a polynomial f(x) ∈ ℝ_{≥0}[x] implies its γ-positivity [24, Lemma 4.1] [61, Remark 3.1.1]. On the other hand, every γ-positive polynomial (whether real-rooted or not) is symmetric and unimodal, as a sum of symmetric and unimodal polynomials with a common center of symmetry (a fact already implicit in [62, p. 136]). Thus, γ-positivity can be applied to general situations and may lead to a more elementary proof of the unimodality of f(x), even when the latter is real-rooted. Moreover, an explicit expression of the form (1) gives additional information about f(x) (for instance, it implies a formula for f(−1) and predicts its sign) and the problem to interpret algebraically or combinatorially the coefficients γ_{i} is often of independent interest.

The present article is an expanded version of the author’s lectures at the 77th Séminaire Lotharingien de Combinatoire (September 2016, Strobl, Austria). Section 2 discusses the variety of examples of γ-positive polynomials in combinatorics, beginning with the prototypical example of Eulerian polynomials, together with some general results. Many of these examples come up again in the geometric contexts of Section 3. That section centers around Gal’s conjecture, claiming that h-polynomials of flag simplicial homology spheres are γ-positive. This conjecture and its relatives provide a general framework under which a lot of the seemingly unrelated γ-positivity phenomena of Section 2 can be considered, partially explains their abundance and allows for tools from geometric combinatorics to be applied to their study. Section 4 discusses the plethora of methods used in the literature to prove γ-positivity. Section 5 is devoted to generalizations and variations of the concept of γ-positivity, giving an emphasis to equivariant and symmetric function generalizations. The choice of topics is strongly affected by the author’s knowledge and personal taste; in particular, possible probabilistic aspects of γ-positivity are not treated. Some previously unpublished statements and open problems are included. Other expositions on γ-positivity can be found in [27, Section 3] [97, Chapter 4].

Notation. For integers a ≤ b we set [a, b] := {a, a + 1, …, b} and use the abbreviation [n] := [1, n] for n ∈ ℕ. We will denote by |Ω| the cardinality, and by 2^{Ω} the set of all subsets, of a finite set Ω. For Ω ⊆ ℤ, we will also denote by Stab(Ω) the set of all subsets of Ω which do not contain two consecutive integers.

2. Gamma-positivity in combinatorics

This section describes instances of γ-positivity in combinatorics. Much of the motivation comes from the study of Eulerian polynomials which, along with generalizations and variations, are discussed in detail. For any undefined notation or terminology, we refer to Stanley’s textbooks [125, 127].

2.1. Variations of Eulerian polynomials.

2.1.1. Eulerian polynomials. One of the most important polynomials in combinatorics is the Eulerian polynomial, defined by any of the equivalent formulas

(2)  A_{n}(x) := ∑_{w∈𝔖_{n}} x^{asc(w)} = ∑_{w∈𝔖_{n}} x^{des(w)} = ∑_{w∈𝔖_{n}} x^{exc(w)} = ∑_{w∈𝔖_{n}} x^{wexc(w)−1}

for every positive integer n. Here asc(w), des(w), exc(w) and wexc(w) denotes the cardinality of the set Asc(w) of ascents, Des(w) of descents, Exc(w) of excedances and Wexc(w) of weak excedances, respectively, of the permutation w ∈ 𝔖_{n}, defined by

• Asc(w) := {i ∈ [n − 1] : w(i) < w(i + 1)},
• Des(w) := {i ∈ [n − 1] : w(i) > w(i + 1)},
• Exc(w) := {i ∈ [n − 1] : w(i) > i},
• Wexc(w) := {i ∈ [n] : w(i) ≥ i}.

For the first few values of n, we have

A_{n}(x) = \begin{cases}1, & if n = 1, \\ 1 + x, & if n = 2, \\ 1 + 4x + x^{2}, & if n = 3, \\ 1 + 11x + 11x^{2} + x^{3}, & if n = 4, \\ 1 + 26x + 66x^{2} + 26x^{3} + x^{4}, & if n = 5, \\ 1 + 57x + 302x^{2} + 302x^{3} + 57x^{4} + x^{5}, & if n = 6, \\ 1 + 120x + 1191x^{2} + 2416x^{3} + 1191x^{4} + 120x^{5} + x^{6}, & if n = 7. \end{cases}

The Eulerian polynomial A_{n}(x), which is clearly symmetric, provides the prototypical example of a γ-positive polynomial in combinatorics. The corresponding γ-coefficients for the first few values of n are determined from the expressions

A_{n}(x) = \begin{cases}1 + x, & if n = 2, \\ (1 + x)^{2} + 2x, & if n = 3, \\ (1 + x)^{3} + 8x(1 + x), & if n = 4, \\ (1 + x)^{4} + 22x(1 + x)^{2} + 16x^{2}, & if n = 5, \\ (1 + x)^{5} + 52x(1 + x)^{3} + 136x^{2}(1 + x), & if n = 6, \\ (1 + x)^{6} + 114x(1 + x)^{4} + 720x^{2}(1 + x)^{2} + 272x^{3}, & if n = 7. \end{cases}

The γ-positivity of A_{n}(x) (which, of course, follows from the well known fact that A_{n}(x) is real-rooted for all n) was first shown combinatorially by Foata and Schützenberger [56, Theorem 5.6]. An explicit combinatorial interpretation of the corresponding γ-coefficients follows from the results of [58]. Recall that a double excedance of w ∈ 𝔖_{n} is any index 1 ≤ i ≤ n such that w(i) > i > w^{−1}(i) and that w ∈ 𝔖_{n} is called an up-down permutation, if Asc(w) = {1, 3, 5, … }∩[n−1]. The first four, as well as the last two, interpretations of γ_{n,i} in the following fundamental result are easily shown to be equivalent to one another; the fifth one follows from the fourth and the bijection (one of the fundamental transformations of Foata and Schützenberger [56]) of [127, Proposition 1.3.1]. An additional interpretation, in terms of increasing binary trees, is discussed in [62, p. 136].

Theorem 2.1 (cf. Foata–Strehl [58]). For all n ≥ 1,

(3)  A_{n}(x) = ∑_{i=0}^{⌊(n−1)/2⌋} γ_{n,i}x^{i}(1 + x)^{n−1−2i},

where γ_{n,i} is equal to each of the following:

• the number of w ∈ 𝔖_{n} for which Asc(w) ∈ Stab([n − 2]) has i elements,

• the number of w ∈ 𝔖_{n} for which Asc(w) ∈ Stab([2, n − 1]) has i elements,

• the number of w ∈ 𝔖_{n} for which Des(w) ∈ Stab([n − 2]) has i elements,

• the number of w ∈ 𝔖_{n} for which Des(w) ∈ Stab([2, n − 1]) has i elements,

• the number of w ∈ 𝔖_{n} with i excedances and no double excedance, for which the smallest of the maximum elements of the cycles of w is a fixed point, • the number of w ∈ 𝔖_{n} with i excedances and no double excedance, for which the

largest of the minimum elements of the cycles of w is a fixed point. In particular, A_{n}(x) is γ-positive and

(4)  A_{n}(−1) = \{ \begin{matrix}0, & if n is even, \\ (−1)^{(n−1)/2} γ_{n,(n−1)/2}, & if n is odd, \end{matrix}

for all n, where γ_{n,(n−1)/2} is the number of up-down permutations in 𝔖_{n}.

We will now describe some refinements and variations of this theorem (more related results appear in the sequel). The following two theorems refine the third interpretation of the γ-positivity of A_{n}(x), given in Theorem 2.1. For w ∈ 𝔖_{n}, we denote by inv(w) the number of inversions (pairs (i, j) ∈ [n] × [n] such that i < j and w(i) > w(j)) of w, and let

• (2-13)w be the number of pairs (i, j) ∈ [n − 1] × [n − 1] such that i < j and w(j) < w(i) < w(j + 1),

• (31-2)w be the number of pairs (i, j) ∈ [n] × [n] such that i + 1 < j and w(i + 1) < w(j) < w(i),

• cros(w) be the number of pairs (i, j) ∈ [n] × [n] such that i < j ≤ w(i) < w(j), or w(i) < w(j) < i < j,

• nest(w) be the number of pairs (i, j) ∈ [n] × [n] such that i < j ≤ w(j) < w(i), or

w(j) < w(i) < i < j. Equations (5) and (6) appear as the specialization u = v = w = 1 of [115, Theorem 2] and as [115, Corollary 6]; the expansion (6) for the left-hand side of (5) was originally shown by Brändén [26, Section 5]. Equation (7) is the main statement of [116, Theorem 1]; the positivity of the coefficient of x^{i}(1 + x)^{n−1−2i}, as a polynomial in q, was conjectured in a preprint version of [22]. A related result appears in [22, Remark 3.4].

Theorem 2.2 (Brändén [26], Shin–Zeng [115, 116]). For all n ≥ 1,

(5)  ∑_{w∈𝔖_{n}} p^{(2−13)w}q^{(31−2)w}x^{des(w)} = ∑_{w∈𝔖_{n}} p^{nest(w)}q^{cros(w)}x^{wexc(w)−1}

= ∑_{i=0}^{⌊(n−1)/2⌋} a_{n,i}(p, q) x^{i}(1 + x)^{n−1−2i} (6)

and

(7)  ∑_{w∈𝔖_{n}} q^{inv(w)−exc(w)}x^{exc(w)} = ∑_{i=0}^{⌊(n−1)/2⌋} a_{n,i}(q^{2}, q) x^{i}(1 + x)^{n−1−2i},

where

(8)  a_{n,i}(p, q) = ∑_{w} p^{(2−13)w}q^{(31−2)w},

and the sum runs through all permutations w ∈ 𝔖_{n} for which Des(w) ∈ Stab([n − 2]) has i elements.

The following theorem of J. Shareshian and M. Wachs, the proof of which is sketched in Section 4.3, follows from the methods used to prove the specialization p = 1 in [114, Theorem 4.4]. This special case was stated in [111, Remark 5.5] without giving an explicit interpretation for the coefficients γ_{i}(1, q); it is also implicit in [84] (see Equations (1.4) and (6.1) there) and is reproven by different methods in [83]. For w ∈ 𝔖_{n}, we set

des^{∗}(w) := \begin{cases}des(w), & if w(1) = 1, \\ des(w) − 1, & if w(1) > 1, \end{cases}

and denote by maj(w) the major index (sum of the elements of Des(w)) of w.

Theorem 2.3 (cf. [114, Section 4]). For all n ≥ 1,

(9)  ∑_{w∈𝔖_{n}} p^{des^{∗}(w)}q^{maj(w)−exc(w)}x^{exc(w)} = ∑_{i=0}^{⌊(n−1)/2⌋} γ_{n,i}(p, q) x^{i}(1 + x)^{n−1−2i},

where

(10)  γ_{n,i}(p, q) = ∑_{w} p^{des(w^{−1})}q^{maj(w^{−1})},

and the sum runs through all permutations w ∈ 𝔖_{n} for which Des(w) ∈ Stab([n − 2]) has i elements.

For further generalizations of the γ-positivity of A_{n}(x), see, for instance, [26, Section 4] and [92, Section 4].

We close this section by discussing an interesting variant of A_{n}(x), defined as

(11)  Ã_{n}(x) := 1 + x ∑_{k=1}^{n} \binom{n}{k}A_{k}(x)

and called a binomial Eulerian polynomial. For the first few values of n, we have

Ã_{n}(x) = \begin{cases}1 + x, & if n = 1, \\ 1 + 3x + x^{2}, & if n = 2, \\ 1 + 7x + 7x^{2} + x^{3}, & if n = 3, \\ 1 + 15x + 33x^{2} + 15x^{3} + x^{4}, & if n = 4, \\ 1 + 31x + 131x^{2} + 131x^{3} + 31x^{4} + x^{5}, & if n = 5, \\ 1 + 63x + 473x^{2} + 883x^{3} + 473x^{4} + 63x^{5} + x^{6}, & if n = 6. \end{cases}

This polynomial first appeared in an enumerative-geometric context in [102, Section 10.4], where it was shown to equal the h-polynomial of the n-dimensional stellohedron (see Section 3 for an explanation of these terms); its symmetry follows from this interpretation and was rediscovered in [42].

The γ-positivity of Ã_{n}(x) follows from a more general theorem of A. Postnikov, V. Reiner and L. Williams [102, Theorem 11.6] (see also Theorem 3.11 in the sequel); for the first few values of n, we have

Ã_{n}(x) = \begin{cases}1 + x, & if n = 1, \\ (1 + x)^{2} + x, & if n = 2, \\ (1 + x)^{3} + 4x(1 + x), & if n = 3, \\ (1 + x)^{4} + 11x(1 + x)^{2} + 5x^{2}, & if n = 4, \\ (1 + x)^{5} + 26x(1 + x)^{3} + 43x^{2}(1 + x), & if n = 5, \\ (1 + x)^{6} + 57x(1 + x)^{4} + 230x^{2}(1 + x)^{2} + 61x^{3}, & if n = 6. \end{cases}

We prefer to state a version due to Shareshian and Wachs, which is similar to Theorem 2.1 and affords a q-analog, similar to that of Theorem 2.3 for A_{n}(x).

Theorem 2.4 (Shareshian–Wachs [114, Theorem 4.5] ). For all n ≥ 1,

(12)  1 + x ∑_{k=1}^{n} \binom{n}{k}_{q} ∑_{w∈𝔖_{k}} q^{maj(w)−exc(w)}x^{exc(w)} = ∑_{i=0}^{⌊n/2⌋} γ̃_{n,i}(q) x^{i}(1 + x)^{n−2i},

where \binom{n}{k}_{q} is a q-binomial coefficient,

(13)  γ̃_{n,i}(q) = ∑_{w} q^{maj(w^{−1})} = ∑_{w} q^{inv(w)},

and the sums run through all permutations w ∈ 𝔖_{n} for which Des(w) ∈ Stab([n − 1]) has i elements. In particular,

(14)  Ã_{n}(x) = ∑_{i=0}^{⌊n/2⌋} γ̃_{n,i}x^{i}(1 + x)^{n−2i},

where γ̃_{n,i} is equal to each of the following:

• the number of w ∈ 𝔖_{n} for which Asc(w) ∈ Stab([n − 1]) has i elements,

• the number of w ∈ 𝔖_{n} for which Des(w) ∈ Stab([n − 1]) has i elements,

• the number of w ∈ 𝔖_{n} with i excedances and no double excedance.

Moreover,

(15)  Ã_{n}(−1) = \{ \begin{matrix}0, & if n is odd, \\ (−1)^{n/2} γ̃_{n,n/2}, & if n is even, \end{matrix}

where γ̃_{n,n/2} is the number of up-down permutations in 𝔖_{n}.

For an alternative approach to the γ-positivity of Ã_{n}(x), see Remark 2.18.

Problem 2.5. Find a p-analog of Theorem 2.4, similar to Theorem 2.3.

3 1 2 4

Figure 1. A labeled poset with four elements

2.1.2. Poset Eulerian polynomials. Given a partially ordered set (poset, for short) P with n elements, any bijective map ω : P → [n] is called a labeling. Let us write permutations w ∈ 𝔖_{n} in one-line notation (w(1), w(2), …, w(n)).

Definition 2.6 (Stanley [118] [127, Section 3.15.2]). Let ω : P → [n] be a labeling of a poset P. The (P, ω)-Eulerian polynomial is defined as

A_{P,ω}(x) = ∑_{w∈L(P,ω)} x^{des(w)},

where L(P, ω) is the set which consists of all permutations (a_{1}, a_{2}, …, a_{n}) ∈ 𝔖_{n} such that ω^{−1}(a_{i}) <_{P} ω^{−1}(a_{j}) implies i < j.

The polynomial A_{P,ω}(x) plays a major role in Stanley’s theory of (P, ω)-partitions [118] [127, Section 3.15]; it reduces to the Eulerian polynomial A_{n}(x) when P is an antichain on n elements. For the labeled poset of Figure 2.1.2 we have L(P, ω) = {(1, 4, 2, 3), (1, 4, 3, 2), (4, 1, 2, 3), (4, 1, 3, 2), (1, 3, 4, 2)} and A_{P,ω}(x) = 3x + 2x^{2}. Examples where A_{P,ω}(x) is not real-rooted were given by P. Brändén [25] and J. Stembridge [134] (see also [27, Section 6]), thus disproving long-standing conjectures of J. Neggers [89] [122, Conjecture 1] and R. Stanley [29, Conjecture 1] [32, Conjecture 3.9].

The polynomial A_{P,ω}(x) does not depend on ω, when the latter is assumed to be order preserving (such labelings are called natural), and is thus denoted simply by A_{P}(x). For example, the labeling obtained from the one of Figure 1 by swapping 2 and 4 is natural and shows that for this poset A_{P}(x) = 1 + 3x + x^{2}. Moreover, as a consequence of the reciprocity theorem [127, Theorem 3.15.10] for (P, ω)-partitions, A_{P}(x) is symmetric if P is graded; its unimodality in this case was first shown by V. Reiner and V. Welker [104], whose proof relied on a deep result from algebraic geometry. Brändén [24] [26, Section 6] gave two beautiful combinatorial proofs of the γ-positivity of A_{P}(x) for the more general class of sign-graded posets.

Theorem 2.7 (Brändén [24]). The polynomial A_{P}(x) is γ-positive for every finite graded poset P.

A generalization to finite crystallographic root systems was given by Stembridge [135]. For a different γ-positivity result for posets, due to Stembridge [133], which generalizes

the γ-positivity of A_{n}(x), see Section 2.3.

2.1.3. Coxeter Eulerian polynomials. Let (W, S) be a Coxeter system, with Coxeter length function ℓ_{S} : W → ℕ (see [20, Chapter 1] for definitions). Assuming that W is finite, the W -Eulerian polynomial is defined as

(16)  W (x) := ∑_{w∈W} x^{des(w)},

where des(w) is the number of right descents (elements s ∈ S such that ℓ_{S}(ws) < ℓ_{S}(w)) of w ∈ W. The polynomial W (x) was first studied systematically by F. Brenti [31]. It has similar properties as A_{n}(x), to which it reduces when W is the symmetric group 𝔖_{n}; in particular, W (x) is easily verified to be symmetric for all finite Coxeter groups W. The following statement combines Theorem 2.1 with results of C. Chow [39] and J. Stembridge [135] (the proof that the W -Eulerian polynomials are real-rooted was completed more recently; see [107] and references therein).

Theorem 2.8 ([39] [135, Theorem 1.2]). The W -Eulerian polynomial is γ-positive for every finite Coxeter group W.

Problem 2.9. Find a proof which does not use the classification of finite Coxeter groups.

A common generalization of Theorems 2.7 and 2.8 is provided by [135, Corollary 7.10], mentioned earlier.

Just as is the case for the symmetric groups and the classical Eulerian polynomial, the corresponding γ-coefficients admit interesting combinatorial interpretations for the other infinite families of finite Coxeter groups as well. We now describe such interpretations for the hyperoctahedral groups B_{n}. Recall that B_{n} consists of all permutations w of the set Ω_{n} := {1, −1, 2, −2, …, n, −n} satisfying w(−a) = −w(a) for each a ∈ Ω_{n}. These can be viewed as signed permutations of length n (see Section 2.1.7 for the more general notion of r-colored permutation). The total order

(17)  − 1 <_{r} −2 <_{r} −3 <_{r} ⋯ <_{r} 0 <_{r} 1 <_{r} 2 <_{r} 3 <_{r} ⋯

of ℤ is convenient to use when B_{n} is thought of as a colored permutation (rather than as a Coxeter) group. The B_{n}-Eulerian polynomial is given by

(18)  B_{n}(x) = ∑_{w∈B_{n}} x^{des^{B}(w)} = ∑_{w∈B_{n}} x^{des_{B}(w)},

where

• des^{B}(w) is the number of indices i ∈ {0, 1, …, n − 1} such that w(i) > w(i + 1),

• des_{B}(w) is the number of indices i ∈ {0, 1, …, n − 1} such that w(i) >_{r} w(i + 1) for w ∈ B_{n}, with w(0) := 0. For the first few values of n, we have

B_{n}(x) = \begin{cases}1 + x, & if n = 1, \\ 1 + 6x + x^{2}, & if n = 2, \\ 1 + 23x + 23x^{2} + x^{3}, & if n = 3, \\ 1 + 76x + 230x^{2} + 76x^{3} + x^{4}, & if n = 4, \\ 1 + 237x + 1682x^{2} + 1682x^{3} + 237x^{4} + x^{5}, & if n = 5, \\ 1 + 722x + 10543x^{2} + 23548x^{3} + 10543x^{4} + 722x^{5} + x^{6}, & if n = 6. \end{cases}

A descending run of a permutation w ∈ 𝔖_{n} is any maximal string {a, a + 1, …, b} of integers such that w(a) > w(a + 1) > ⋯ > w(b). A left peak of w is any index i ∈ [n − 1] such that w(i−1) < w(i) > w(i+1), where w(0) := 0 (note that 1 can be a left peak, but n cannot). The following result combines [39, Theorem 4.7] with [94, Proposition 4.15] and provides a B_{n}-analog to Theorem 2.1. The permutation obtained from w ∈ B_{n} by forgetting all signs is denoted by |w|.

Theorem 2.10 ([39, 94]). For all n ≥ 1,

(19)  B_{n}(x) = ∑_{i=0}^{⌊n/2⌋} γ_{n,i}^{B} x^{i}(1 + x)^{n−2i},

where γ_{n,i}^{B} is equal to each of the following:

• the number of permutations w ∈ 𝔖_{n} with i left peaks, multiplied by 4^{i},

• the number of signed permutations w ∈ B_{n} with des^{B}(w) = i, such that |w| ∈ 𝔖_{n}

has i descending runs of size at least two. In particular,

(20)  B_{n}(−1) = \{ \begin{matrix}0, & if n is odd, \\ (−1)^{n/2} γ_{n,n/2}^{B}, & if n is even, \end{matrix}

for all n, where γ_{n,n/2}^{B} is the number of up-down permutations in 𝔖_{n}, multiplied by 4^{n/2}.

For the first few values of n, the numbers γ_{n,i}^{B} are determined from the expressions

B_{n}(x) = \begin{cases}1 + x, & if n = 1, \\ (1 + x)^{2} + 4x, & if n = 2, \\ (1 + x)^{3} + 20x(1 + x), & if n = 3, \\ (1 + x)^{4} + 72x(1 + x)^{2} + 80x^{2}, & if n = 4, \\ (1 + x)^{5} + 232x(1 + x)^{3} + 976x^{2}(1 + x), & if n = 5, \\ (1 + x)^{6} + 716x(1 + x)^{4} + 7664x^{2}(1 + x)^{2} + 3904x^{3}, & if n = 6. \end{cases}

An interesting extension of Theorem 2.8 to affine Weyl groups was found by K. Dilks, T.K. Petersen and J. Stembridge [48]. Let (W, S) be a Coxeter system with Coxeter length function ℓ_{S} : W → ℕ, as before, and assume W is finite, crystallographic and irreducible.

Then, W has a longest element s_{0} and the set of affine right descents of w ∈ W is defined as

aDes(w) := \begin{cases}Des(w), & if ℓ_{S}(ws_{0}) < ℓ_{S}(w), \\ Des(w) ∪ \{s_{0}\}, & if ℓ_{S}(ws_{0}) > ℓ_{S}(w). \end{cases}

The affine Eulerian polynomial associated to W is defined as

(21)  W_{a}(x) := ∑_{w∈W} x^{ades(w)},

where ades(w) is the number of affine right descents of w ∈ W.

Theorem 2.11 (Dilks–Petersen–Stembridge [48, Theorem 4.2]). The affine Eulerian polynomial W_{a}(x) is γ-positive for every finite irreducible crystallographic Coxeter group W.

We close this section with an intriguing related problem, posed by I. Gessel in 2005 (see [26, Conjecture 10.2] [96, Conjecture 1] [97, Problem 4.12]). The two-sided Eulerian polynomial associated to a finite Coxeter group W is defined as

(22)  W (x, y) = ∑_{w∈W} x^{des(w)}y^{des(w^{−1})}.

The specialization W (x, x) appeared also in work of A. Hultman [71, Example 5.9]. The following result was conjectured by Gessel (unpublished) for the symmetric groups and, more generally, by Petersen [98, Conjecture 1] for finite Coxeter groups.

Theorem 2.12 (Lin [80]). Let W be a symmetric or hyperoctahedral group. Then, there exist nonnegative integers γ_{i,j} = γ_{i,j}(W) such that

(23)  W (x, y) = ∑_{2i+j≤n} γ_{i,j}(xy)^{i}(x + y)^{j}(1 + xy)^{n−2i−j},

where n is the rank of W.

It remains an interesting open problem to find a combinatorial interpretation for the numbers γ_{i,j}(W), even in the symmetric group case.

2.1.4. Derangements. Counting derangements (permutations without fixed points) in 𝔖_{n} by the number of excedances leads to a well-behaved analog of the Eulerian polynomial A_{n}(x), defined by

(24)  d_{n}(x) := ∑_{w∈D_{n}} x^{exc(w)},

where D_{n} denotes the set of all derangements in 𝔖_{n}. For the first few values of n, we have

d_{n}(x) = \begin{cases}0, & if n = 1, \\ x, & if n = 2, \\ x + x^{2}, & if n = 3, \\ x + 7x^{2} + x^{3}, & if n = 4, \\ x + 21x^{2} + 21x^{3} + x^{4}, & if n = 5, \\ x + 51x^{2} + 161x^{3} + 51x^{4} + x^{5}, & if n = 6, \\ x + 113x^{2} + 813x^{3} + 813x^{4} + 113x^{5} + x^{6}, & if n = 7. \end{cases}

The polynomial d_{n}(x) (often called the nth derangement polynomial) was first considered in a purely combinatorial context in [122, p. 530] by Stanley who, however, seems to have been motivated by a geometric interpretation [123, Proposition 2.4] of d_{n}(x); see Section 3.3 for more explanation. While the symmetry of d_{n}(x) is nearly obvious, its unimodality was derived by Brenti [30, Corollary 1] from a more general result in the theory of symmetric functions, although it also follows from deep results of Stanley [123] on local h-polynomials, discussed in Section 3.2. A more elementary combinatorial proof was later given by Stembridge [131, Section 2]. More recently, using methods discussed in Section 4.2, M. Juhnke-Kubitzke, S. Murai and R. Sieg [73, Corollary 4.2] found the recurrence

(25)  d_{n}(x) = ∑_{k=0}^{n−2} \binom{n}{k}d_{k}(x)(x + x^{2} + ⋯ + x^{n−1−k}),

which directly implies the unimodality of d_{n}(x) by induction on n.

The question of γ-positivity of d_{n}(x) arises naturally. Just as is the case with A_{n}(x), the polynomial d_{n}(x) turns out to be real-rooted for all n [142], so the interesting part of the question is to find a proof of γ-positivity which provides a combinatorial interpretation for the γ-coefficients. For the first few values of n, we have

d_{n}(x) = \begin{cases}x, & if n = 2, \\ x(1 + x), & if n = 3, \\ x(1 + x)^{2} + 5x^{2}, & if n = 4, \\ x(1 + x)^{3} + 18x^{2}(1 + x), & if n = 5, \\ x(1 + x)^{4} + 47x^{2}(1 + x)^{2} + 61x^{3}, & if n = 6, \\ x(1 + x)^{5} + 108x^{2}(1 + x)^{3} + 479x^{3}(1 + x), & if n = 7. \end{cases}

For a permutation w ∈ 𝔖_{n}, a double descent is any index 2 ≤ i ≤ n − 1 such that w(i − 1) > w(i) > w(i + 1); a left to right maximum is any index 1 ≤ j ≤ n such that w(i) < w(j) for all 1 ≤ i < j.

Theorem 2.13 (cf. [10, Theorem 1.4]). We have d_{n}(x) = ∑_{i=0}^{⌊n/2⌋} ξ_{n,i}x^{i}(1 + x)^{n−2i}, where ξ_{n,i} is equal to each of the following:

• the number of derangements w ∈ D_{n} with i excedances and no double excedance, • the number of w ∈ 𝔖_{n} for which Asc(w) ∈ Stab([2, n − 2]) has i − 1 elements,

• the number of w ∈ 𝔖_{n} for which Des(w) ∈ Stab([2, n − 2]) has i − 1 elements,

• the number of permutations w ∈ 𝔖_{n} with i descents and no double descent, such

that every left to right maximum of w is a descent. In particular, d_{n}(x) is γ-positive and

(26)  d_{n}(−1) = \{ \begin{matrix}0, & if n is odd, \\ (−1)^{n/2} ξ_{n,n/2}, & if n is even, \end{matrix}

for all n, where ξ_{n,n/2} is the number of up-down permutations in 𝔖_{n}.

The first three interpretations appeared (implicitly or explicitly) in various contexts in independent works by several authors, roughly at the same time, who employed different methods; see [10, Equations (1.3) and (3.2)] [84, Section 4] [111, Section 5] [114, Section 6]

[115] [137]. These references provide various interesting refinements, some of which are described in the sequel. A symmetric function generalization is discussed in Section 2.5.

Three refinements of the first interpretation given in Theorem 2.13 were found by H. Shin and J. Zeng [115, 116]. We denote by c(w) the number of cycles of w ∈ 𝔖_{n} and note that the meanings of inv(w) and nest(w) have been explained earlier, before the statement of Theorem 2.2. The result in the following theorem about nest(w) is the specialization q = 1 of [115, Corollary 9], the one about c(w) (which also follows from the proof of Theorem 2.13 given in [10, Section 4]) is a restatement of [115, Theorem 11] and the one about inv(w) appears as [116, Theorem 2]. Theorem 2.14 (Shin–Zeng [115, 116]). For all positive integers n and for each of the statistics stat(w) ∈ {c(w), inv(w), nest(w)},

(27)  ∑_{w∈D_{n}} q^{stat(w)}x^{exc(w)} = ∑_{i=0}^{⌊n/2⌋} b_{n,i}(q) x^{i}(1 + x)^{n−2i},

where

(28)  b_{n,i}(q) = ∑_{w∈D_{n}(i)} q^{stat(w)}

and D_{n}(i) consists of all elements of D_{n} with exactly i excedances and no double excedance.

The following theorem refines the third interpretation of the γ-positivity of d_{n}(x), given in Theorem 2.13. This result was stated in [111, Remark 5.5] without giving an explicit interpretation for the coefficients ξ_{i}(p, q). The combinatorial interpretation which appears here follows from the methods used to prove the specialization p = 1 in [114, Theorem 6.1]; the proof will be sketched in Section 4.3. The special case p = 1 is also implicit in [84] (see Equation (1.3) and Corollary 3.7 there) and is proven by different methods in [83]. Theorem 2.15 (Shareshian–Wachs [111, Remark 5.5] [114, Section 6]). For all n ≥ 1,

(29)  ∑_{w∈D_{n}} p^{des(w)}q^{maj(w)−exc(w)}x^{exc(w)} = ∑_{i=0}^{⌊n/2⌋} ξ_{n,i}(p, q) x^{i}(1 + x)^{n−2i},

where

(30)  ξ_{n,i}(p, q) = p · ∑_{w} p^{des(w^{−1})}q^{maj(w^{−1})},

and the sum runs through all permutations w ∈ 𝔖_{n} for which Des(w) ∈ Stab([2, n − 2]) has i − 1 elements.

The following result, which is derived using the same methods in Section 4.3, generalizes the specialization p = 1 of Theorem 2.15. We denote by fix(w) the number of fixed points of w ∈ 𝔖_{n}.

Theorem 2.16 (Shareshian–Wachs [111, Corollary 4.6] [114, Theorem 6.1]). For all n ≥ 1 and 0 ≤ k ≤ n,

(31)  ∑_{w∈𝔖_{n}: fix(w)=k} q^{maj(w)−exc(w)}x^{exc(w)} = \binom{n}{k}_{q} ∑_{i=0}^{⌊(n−k)/2⌋} ξ_{n−k,i}(q) x^{i}(1 + x)^{n−k−2i},

where \binom{n}{k}_{q} is a q-binomial coefficient, ξ_{n,i}(q) := ξ_{n,i}(1, q) and ξ_{n,i}(p, q) is as in the statement of Theorem 2.15.

Problem 2.17. Find a p-analog of Theorem 2.16 which reduces to Theorem 2.15 for k = 0.

For a generalization of Theorem 2.13 to r-colored permutations and some related results, see Section 2.1.7. We now briefly describe an application to the γ-positivity of binomial Eulerian polynomials.

Remark 2.18. By the symmetry Ã_{n}(x) = x^{n}Ã_{n}(1/x) of the binomial Eulerian polynomial Ã_{n}(x), its defining equation (11) can be rewritten as

Ã_{n}(x) = ∑_{m=0}^{n} \binom{n}{m}x^{n−m}A_{m}(x).

Replacing A_{m}(x) by the expression ∑_{k=0}^{m} \binom{m}{k}d_{k}(x) and changing the order of summation, we obtain the formula

(32)  Ã_{n}(x) = ∑_{k=0}^{n} \binom{n}{k}d_{k}(x) (1 + x)^{n−k}.

Using the γ-expansion of Theorem 2.13 for the derangement polynomials, we conclude that (14) holds with

(33)  γ̃_{n,i} = ∑_{k=2i}^{n} \binom{n}{k}ξ_{k,i}.

Because of the third interpretation for the coefficients ξ_{n,i} given in Theorem 2.13, this formula is equivalent to the combinatorial interpretation for γ̃_{n,i} predicted in [102]. This approach can be generalized in the context of r-colored permutations; details will appear elsewhere. □

2.1.5. Involutions. Let I_{n} := {w ∈ 𝔖_{n} : w^{−1} = w} be the set of involutions in 𝔖_{n} and

(34)  I_{n}(x) = ∑_{w∈I_{n}} x^{des(w)}

be the polynomial defining the Eulerian distribution on I_{n}. For the first few values of n, we have

I_{n}(x) = \begin{cases}1, & if n = 1, \\ 1 + x, & if n = 2, \\ 1 + 2x + x^{2}, & if n = 3, \\ 1 + 4x + 4x^{2} + x^{3}, & if n = 4, \\ 1 + 6x + 12x^{2} + 6x^{3} + x^{4}, & if n = 5, \\ 1 + 9x + 28x^{2} + 28x^{3} + 9x^{4} + x^{5}, & if n = 6, \\ 1 + 12x + 57x^{2} + 92x^{3} + 57x^{4} + 12x^{5} + x^{6}, & if n = 7. \end{cases}

The polynomial I_{n}(x) seems to have first appeared in [136], where V. Strehl proved its symmetry (conjectured by D. Dumont). Strehl’s argument uses basic properties of the Robinson–Schensted correspondence to derive the alternative formula

(35)  I_{n}(x) = ∑_{Q∈SYT(n)} x^{des(Q)},

where SYT(n) stands for the set of all standard Young tableaux with n squares and des(Q) is the numbers of entries (called descents) i ∈ [n − 1] such that i + 1 appears in Q in a lower row than i, for Q ∈ SYT(n). This formula makes the symmetry of I_{n}(x) apparent, since transposing a standard Young tableau interchanges descents with ascents (nondescents).

Two basic results about I_{n}(x) are as follows. The proof of the second part, given in [68], uses the first part to find recursions for the coefficients of I_{n}(x) and proceeds by induction on n.

Theorem 2.19. (a) (Désarménien–Foata [46]) We have

(36)  ∑_{n≥0} \frac{I_{n}(x)}{(1 − x)^{n+1}} z^{n} = ∑_{m≥0} \frac{x^{m}}{(1 − z)^{m+1}(1 − z^{2})^{m(m+1)/2}} ,

where I_{0}(x) := 1.

(b) (Guo–Zeng [68]) The polynomial I_{n}(x) is (symmetric and) unimodal for every positive integer n.

The polynomials I_{n}(x) are not real-rooted (in fact, not even log-concave [13]) for n large enough, but the following data suggests they may be γ-positive:

I_{n}(x) = \begin{cases}1, & if n = 1, \\ 1 + x, & if n = 2, \\ (1 + x)^{2}, & if n = 3, \\ (1 + x)^{3} + x(1 + x), & if n = 4, \\ (1 + x)^{4} + 2x(1 + x)^{2} + 2x^{2}, & if n = 5, \\ (1 + x)^{5} + 4x(1 + x)^{3} + 6x^{2}(1 + x), & if n = 6, \\ (1 + x)^{6} + 6x(1 + x)^{4} + 18x^{2}(1 + x)^{2}, & if n = 7. \end{cases}

Somewhat surprisingly, the following intriguing conjecture is still open (an analogous statement for fixed-point free involutions is conjectured [68, Conjecture 4.3] for large n).

Conjecture 2.20 (Guo–Zeng [68, Conjecture 4.1]). The polynomial I_{n}(x) is γ-positive for every positive integer n.

The previous conjecture suggests that it may be interesting to study the distribution of the descent set Des(w) for w ∈ I_{n}. For instance, for S ⊆ [n − 1] let β_{n}(S) denote the number of permutations w ∈ 𝔖_{n} such that Des(w) = S. It is well known (see [127, Section 1.6.3]) that β_{n}(S) = β_{n}([n − 1]∖S) for every S ⊆ [n − 1] and that for each n ≥ 1, when S ranges over all subsets of [n − 1], the quantity β_{n}(S) attains its maximum for S = {1, 3, 5, … } ∩ [n − 1].

Similarly, for S ⊆ [n − 1] let δ_{n}(S) denote the number of involutions w ∈ I_{n} such that Des(w) = S. Strehl’s proof of the symmetry of I_{n}(x) shows that δ_{n}(S) = δ_{n}([n − 1]∖S) for every S ⊆ [n − 1].

Question 2.21. Is it true that for each n ≥ 1, when S ranges over all subsets of [n − 1], the quantity δ_{n}(S) attains its maximum for S = {1, 3, 5, … } ∩ [n − 1]?

It is natural to consider the B_{n}-analog

(37)  I_{n}^{B}(x) = ∑_{w∈I_{n}^{B}} x^{des_{B}(w)}

of I_{n}(x), where I_{n}^{B} := {w ∈ B_{n} : w^{−1} = w} is the set of involutions in the hyperoctahedral group B_{n}. Presumably (but not obviously), the right-hand side of the defining equation (37) is unaffected when des_{B} is replaced with the Coxeter group descent statistic des^{B} for B_{n}. For the first few values of n, we have

I_{n}^{B}(x) = \begin{cases}1 + x, & if n = 1, \\ 1 + 4x + x^{2}, & if n = 2, \\ 1 + 9x + 9^{2} + x^{3}, & if n = 3, \\ 1 + 17x + 40x^{2} + 17x^{3} + x^{4}, & if n = 4, \\ 1 + 28x + 127x^{2} + 127x^{3} + 28x^{4} + x^{5}, & if n = 5, \\ 1 + 43x + 331x^{2} + 634x^{3} + 331x^{4} + 43x^{5} + x^{6}, & if n = 6. \end{cases}

The symmetry of I_{n}^{B}(x) can be demonstrated by an analog of Strehl’s argument, using basic properties (see [1, Proposition 5.1]) of the Robinson–Schensted correspondence of type B and replacing SYT(n) with the set of all standard Young bitableaux with a total of n squares; see [87, Section 3.2] for the details.

The analog

(38)  ∑_{n≥0} \frac{I_{n}^{B}(x)}{(1 − x)^{n+1}} z^{n} = ∑_{m≥0} \frac{x^{m}}{(1 − z)^{2m+1}(1 − z^{2})^{m^{2}}} ,

of Equation (36) for I_{n}^{B}(x), where I_{0}^{B}(x) := 1, was found by V. Moustakas [87], who also showed that I_{n}^{B}(x) is unimodal for every positive integer n. As expected, the following data suggests that I_{n}^{B}(x) may be γ-positive for every n:

I_{n}^{B}(x) = \begin{cases}1 + x, & if n = 1, \\ (1 + x)^{2} + 2x, & if n = 2, \\ (1 + x)^{3} + 6x(1 + x), & if n = 3, \\ (1 + x)^{4} + 13x(1 + x)^{2} + 8x^{2}, & if n = 4, \\ (1 + x)^{5} + 23x(1 + x)^{3} + 48x^{2}(1 + x), & if n = 5, \\ (1 + x)^{6} + 37x(1 + x)^{4} + 168x^{2}(1 + x)^{2} + 56x^{3}, & if n = 6. \end{cases}

The formulas in the following proposition, which seem not to have appeared in the literature explicitly before, express I_{n}(x) and I_{n}^{B}(x) in terms of Eulerian polynomials of types A and B, respectively. We sketch their proofs, which we find interesting. We recall (see, for instance, [1, Section 2.3]) that the cycle form of elements of B_{n} involves positive (paired) cycles and negative (balanced) cycles.

Proposition 2.22. For n ≥ 1,

(39)  I_{n}(x) = \frac{1}{n!} ∑_{w∈𝔖_{n}}(1 − x)^{n−c(w^{2})}A_{c(w^{2})}(x),

(40)  I_{n}^{B}(x) = \frac{1}{2^{n}n!} ∑_{w∈B_{n}}(1 − x)^{n−c_{+}(w^{2})}B_{c_{+}(w^{2})}(x),

where c(u) stands for the number of cycles of u ∈ 𝔖_{n} and c_{+}(v) stands for the number of positive cycles of v ∈ B_{n}.

Proof. Recall from [125, Section 7.19] that the fundamental quasisymmetric function associated to S ⊆ [n − 1] is defined as

(41)  F_{n,S}(x) = ∑_{\begin{matrix}1≤i_{1}≤i_{2}≤···≤i_{n} \\ j∈S ⇒ i_{j}<i_{j+1} \end{matrix}} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}},

where x = (x_{1}, x_{2}, …) is a sequence of commuting independent indeterminates, and that

(42)  ∑_{m≥1} F_{n,S}(1^{m})x^{m−1} = \frac{x^{|S|}}{(1 − x)^{n+1}} .

Applying this equality for S = Des(w), summing over all involutions w ∈ I_{n}, changing the order of summation on the left-hand side and using the correspondence between involutions and standard Young tableaux, we get

\frac{I_{n}(x)}{(1 − x)^{n+1}} = ∑_{m≥1} ∑_{w∈I_{n}} F_{n,Des(w)}(1^{m})x^{m−1} = ∑_{m≥1} ∑_{Q∈SYT(n)} F_{n,Des(Q)}(1^{m})x^{m−1}

= ∑_{m≥1} ∑_{λ⊢n} ∑_{Q∈SYT(λ)} F_{n,Des(Q)}(1^{m})x^{m−1}.

By using the well known expansion [125, Theorem 7.19.7]

(43)  s_{λ}(x) = ∑_{Q∈SYT(λ)} F_{n,Des(Q)}(x)

of the Schur function s_{λ}(x) associated to λ ⊢ n, our formula for I_{n}(x) may be rewritten as

\frac{I_{n}(x)}{(1 − x)^{n+1}} = ∑_{m≥1} ∑_{λ⊢n} s_{λ}(1^{m})x^{m−1}.

Expanding now s_{λ}(x) in the power-sum basis (see [125, Theorem 7.18.5]) and changing the order of summation, we obtain

\frac{I_{n}(x)}{(1 − x)^{n+1}} = \frac{1}{n!} ∑_{m≥1} ∑_{λ⊢n} ∑_{u∈𝔖_{n}} χ^{λ}(u)m^{c(u)}x^{m−1} = \frac{1}{n!} ∑_{u∈𝔖_{n}} ∑_{m≥1} m^{c(u)}x^{m−1} ∑_{λ⊢n} χ^{λ}(u),

where χ^{λ} is the irreducible character of 𝔖_{n} corresponding to λ ⊢ n. The desired expression (39) for I_{n}(x) follows by applying Worpitzky’s identity ∑_{m≥1} m^{k}x^{m−1} = A_{k}(x)/(1−x)^{k+1} and the fact (see [72, p. 58]) that ∑_{λ⊢n} χ^{λ}(u) is equal to the number of w ∈ 𝔖_{n} satisfying w^{2} = u, for every u ∈ 𝔖_{n}.

The proof of the expression (40) for I_{n}^{B}(x) is similar, provided one uses Poirier’s signed quasisymmetric functions [99] to replace the functions F_{n,S}(x). In the sequel, we assume some familiarity with [1, Section 2], especially with the notion of signed descent set for signed permutations and standard Young bitableaux.

Let x = (x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, …) be sequences of commuting independent indeterminates. Given w ∈ B_{n}, let ε = (ε_{1}, ε_{2}, …, ε_{n}) ∈ {−, +}^{n} be the vector with ith coordinate equal to the sign of w(i), and let Des(w) be the set consisting of those indices i ∈ [n − 1] for which either ε_{i} = + and ε_{i+1} = −, or ε_{i} = ε_{i+1} and |w(i)| > |w(i + 1)|. The signed quasisymmetric function associated (in a more general setting) to w by Poirier [99] may be defined as

(44)  F_{w}(x, y) = ∑_{\begin{matrix}1≤i_{1}≤i_{2}≤···≤i_{n} \\ j∈Des(w) ⇒ i_{j}<i_{j+1} \end{matrix}} z_{i_{1}}z_{i_{2}} ⋯ z_{i_{n}},

where z_{i_{j}} = x_{i_{j}} if ε_{j} = +, and z_{i_{j}} = y_{i_{j}} if ε_{j} = −; see [1, Sections 2.2 and 2.4]. There is a similar definition of F_{Q}(x, y) for every standard Young bitableau Q; see [1, Section 2] for a uniform treatment of these functions. One can check that

(45)  ∑_{m≥1} F_{w}(1^{m}, 01^{m−1})x^{m−1} = \frac{x^{des_{B}(w)}}{(1 − x)^{n+1}} ,

where F_{w}(1^{m}, 01^{m−1}) stands for the specialization x_{1} = ⋯ = x_{m} = y_{2} = ⋯ = y_{m} = 1, y_{1} = 0 and x_{i} = y_{i} = 0 for i > m of the function F_{w}(x, y). Let SYB(λ, μ) denote the set of standard Young bitableaux of shape (λ, μ). Following the proof for I_{n}(x) described earlier and using the one-to-one correspondence between involutions in B_{n} and standard Young bitableaux with a total of n squares, as well as the expansion

(46)  s_{λ}(x)s_{μ}(y) = ∑_{Q∈SYB(λ,μ)} F_{Q}(x, y)

of [1, Proposition 4.2] instead of (43), we arrive at the equation

\frac{I_{n}^{B}(x)}{(1 − x)^{n+1}} = ∑_{m≥1} ∑_{(λ,μ)⊢n} s_{λ}(1^{m})s_{μ}(1^{m−1})x^{m−1}.

Finally, denote by χ^{λ,μ} the irreducible B_{n}-character associated to the bipartition (λ, μ) of n. One uses the characteristic map [1, Equation (2.5)] for B_{n} to expand s_{λ}(x)s_{μ}(y) = ch(χ^{λ,μ}) in the power sum basis, the type B Worpitzky identity ∑_{m≥1}(2m − 1)^{k}x^{m−1} = B_{k}(x)/(1 − x)^{k+1} and the fact (see again [72, p. 58]) that ∑_{(λ,μ)⊢n} χ^{λ,μ}(v) is equal to the number of square roots of v in B_{n}, for every v ∈ B_{n}, to reach the desired conclusion. □

Remark 2.23. Another proof of the symmetry of I_{n}(x) and I_{n}^{B}(x) can be inferred from Proposition 2.22 as follows. Replacing x by 1/x in the right-hand sides of Equations (39) and (40) and using the symmetry of the Eulerian polynomials A_{k}(x) and B_{k}(x), as well as the fact that n − c(u^{2}) and n − c_{+}(v^{2}) are even for all u ∈ 𝔖_{n} and v ∈ B_{n}, we see that x^{n−1}I_{n}(1/x) = I_{n}(x) and x^{n}I_{n}^{B}(1/x) = I^{B}(x), as desired. □

The polynomial I_{n}(x) affords a natural Coxeter group generalization. Given a finite Coxeter group W (together with a set of simple generators), let I_{W} := {w ∈ W : w^{−1} = w} be the set of involutions in W and define

(47)  I_{W} (x) := ∑_{w∈I_{W}} x^{des(w)},

where, as in Equation (16), des(w) is the number of right descents of w (the notions of left and right descents coincide for involutions). The polynomial I_{W} (x) is equal to I_{n}(x), when W is the symmetric group 𝔖_{n}, and presumably to I_{n}^{B}(x), when W is the hyperoctahedral group B_{n}.

The symmetry of I_{W} (x) follows from the work of Hultman [71, Section 5], who showed (in a more general context) that I_{W} (x) is equal to the h-polynomial of a Boolean cell complex which is homeomorphic to a sphere. Thus, it seems natural to ask the following question.

Question 2.24. For which finite Coxeter groups W is I_{W} (x) unimodal, or even γpositive?

Another possible generalization of I_{n}(x) is provided by the polynomial

(48)  I_{n,k}(x) := ∑_{w∈𝔖_{n}:w^{k}=e} x^{des(w)},

defined for positive integers k, where e ∈ 𝔖_{n} stands for the identity permutation. This polynomial is no longer symmetric for k ≥ 3, but it may still be worthwhile to investigate its unimodality. Following the proof of the first part of Proposition 2.22 and using the main result of [106], in the equivalent form stated in [1, Theorem 7.7], to evaluate the quasisymmetric generating function of the descent set over all k-roots of e ∈ 𝔖_{n}, we obtain in the generalization

(49)  I_{n,k}(x) = \frac{1}{n!} ∑_{w∈𝔖_{n}}(1 − x)^{n−c(w^{k})}A_{c(w^{k})}(x)

of Equation (39).

2.1.6. Multiset permutations. Let λ = (λ_{1}, λ_{2}, …, λ_{k}) ⊢ n be an integer partition of n. We denote by M_{λ} the multiset consisting of λ_{i} copies of i for each i ∈ [k] and by 𝔖(M_{λ}) the set of all permutations of M_{λ}, written in one-line notation. The sets of ascents, descents and excedances of w = (a_{1}, a_{2}, …, a_{n}) ∈ 𝔖(M_{λ}) are defined as

• Asc(w) := {i ∈ [n − 1] : a_{i} ≤ a_{i+1}},

• Des(w) := {i ∈ [n − 1] : a_{i} > a_{i+1}},
• Exc(w) := {i ∈ [n − 1] : a_{i} > j_{i}},

where (j_{1}, j_{2}, …, j_{n}) is the unique permutation of M_{λ} with no descents; the cardinalities of these sets are denoted by asc(w), des(w) and exc(w), respectively. We say that w is a Smirnov permutation of type λ if it has no two equal successive entries, and a derangement of type λ if a_{i} ≠ j_{i} for all indices i ∈ [n]. We denote by S_{λ} and D_{λ} the set of all Smirnov permutations and derangements of type λ, respectively.

The following result, which is a consequence of [84, Theorem 5.1] and its proof, generalizes Theorems 2.1 and 2.13 in the context of permutations of multisets.

Theorem 2.25 (Linusson–Shareshian–Wachs [84, Section 5]). For all partitions λ ⊢ n,

(50)  ∑_{w∈S_{λ}} x^{des(w)} = ∑_{i=0}^{⌊(n−1)/2⌋} γ_{λ,i}x^{i}(1 + x)^{n−1−2i}

and

(51)  ∑_{w∈D_{λ}} x^{exc(w)} = ∑_{i=0}^{⌊n/2⌋} ξ_{λ,i}x^{i}(1 + x)^{n−2i},

where • γ_{λ,i} is the number of permutations w ∈ 𝔖(M_{λ}) for which Asc(w) ∈ Stab([n − 2])

has i elements, and

• ξ_{λ,i} is the number of permutations w ∈ 𝔖(M_{λ}) for which Asc(w) ∈ Stab([2, n − 2]) has i − 1 elements.

2.1.7. Colored permutations. Theorem 2.13 has been generalized to the wreath product group ℤ_{r} ≀𝔖_{n}. Recall that the elements of ℤ_{r} ≀𝔖_{n} can be viewed as r-colored permutations of the form σ × z, where σ = (σ(1), σ(2), …, σ(n)) ∈ 𝔖_{n} and z = (z_{1}, z_{2}, …, z_{n}) ∈ {0, 1, …, r − 1}^{n} (the number z_{i} is thought of as the color assigned to σ(i)). To define the notions of descent and excedance for colored permutations, we follow [129, Section 2] [130, Section 3.1]. A descent of σ × z ∈ ℤ_{r} ≀ 𝔖_{n} is any index i ∈ [n] such that either z_{i} > z_{i+1}, or z_{i} = z_{i+1} and σ(i) > σ(i + 1), where σ(n + 1) := n + 1 and z_{n+1} := 0 (in particular, n is a descent if and only if σ(n) has nonzero color). An excedance of σ × z is any index i ∈ [n] such that either σ(i) > i, or σ(i) = i and z_{i} > 0. Let des(w) and exc(w) be the number of descents and excedances, respectively, of w ∈ ℤ_{r} ≀ 𝔖_{n}. The Eulerian polynomial

(52)  A_{n,r}(x) := ∑_{w∈ℤ_{r}≀𝔖_{n}} x^{des(w)} = ∑_{w∈ℤ_{r}≀𝔖_{n}} x^{exc(w)}

for ℤ_{r}≀𝔖_{n} (the second equality being the content of [129, Theorem 3.15] [130, Theorem 15]) was defined and studied by E. Steingrímsson [129, 130], who showed it to be real-rooted for all n, r; it reduces to the Eulerian polynomials A_{n}(x) and B_{n}(x) when r = 1 and r = 2, respectively. The derangement polynomial for ℤ_{r} ≀ 𝔖_{n} is defined as

(53)  d_{n,r}(x) := ∑_{w∈D_{n,r}} x^{exc(w)},

where D_{n,r} denotes the set of all derangements (colored permutations without fixed points of zero color) in ℤ_{r} ≀ 𝔖_{n}. This polynomial was introduced and studied by C. Chow and T. Mansour [41], who showed that it is real-rooted for all positive integers n, r; it reduces to d_{n}(x) for r = 1. For r = 2 it was first studied by W. Chen, R. Tang and A. Zhao [38] and, independently, by C. Chow [40]. For the first few values of n, we have

d_{n,2}(x) = \begin{cases}x, & if n = 1, \\ 4x + x^{2}, & if n = 2, \\ 8x + 20x^{2} + x^{3}, & if n = 3, \\ 16x + 144x^{2} + 72x^{3} + x^{4}, & if n = 4, \\ 32x + 752x^{2} + 1312x^{3} + 232x^{4} + x^{5}, & if n = 5, \\ 64x + 3456x^{2} + 14576x^{3} + 9136x^{4} + 716x^{5} + x^{6}, & if n = 6. \end{cases}

Even though d_{n,r}(x) and A_{n,r}(x) are no longer symmetric for r ≥ 2 and r ≥ 3, respectively, the theory of γ-positivity is still relevant to their study. Indeed, the following theorem shows that d_{n,r}(x) is equal to the sum of two γ-positive, hence symmetric and unimodal, polynomials whose centers of symmetry differ by 1/2 and thus implies its unimodality. We denote by Des(w) the set of descents of w ∈ ℤ_{r}≀𝔖_{n} and set Asc(w) := [n]∖Des(w).

For r = 1, these notions differ from the ones already defined for permutations w ∈ 𝔖_{n} only in the fact that Asc(w) is now forced to contain n. We call w ∈ ℤ_{r} ≀ 𝔖_{n} down-up, if Des(w) = {1, 3, 5, … } ∩ [n].

Theorem 2.26 (Athanasiadis [6, Theorem 1.3 and Corollary 6.1]). For all positive integers n, r,

(54)  d_{n,r}(x) = ∑_{i=0}^{⌊n/2⌋} ξ_{n,r,i}^{+} x^{i}(1 + x)^{n−2i} + ∑_{i=0}^{⌊(n+1)/2⌋} ξ_{n,r,i}^{−} x^{i}(1 + x)^{n+1−2i},

where ξ_{n,r,i}^{+} is the number of permutations w ∈ ℤ_{r} ≀ 𝔖_{n} for which Asc(w) ∈ Stab([2, n]) has i elements and contains n, and ξ_{n,r,i}^{−} is the number of permutations w ∈ ℤ_{r} ≀ 𝔖_{n} for which Asc(w) ∈ Stab([2, n − 1]) has i − 1 elements.

In particular, d_{n,r}(x) is unimodal with a peak at ⌊(n + 1)/2⌋. Moreover, if r ≥ 2, then (−1)^{⌊ \frac{n+1}{2} ⌋} d_{n}^{r}(−1) is equal to the number of down-up colored permutations in ℤ_{r} ≀ 𝔖_{n}.

The following question seems natural to ask.

Question 2.27. Is there a positive expansion for A_{n,r}(x) of the type provided by Equation (54) for d_{n,r}(x)? Is there a (p, q)-analog which reduces to Theorem 2.3 for r = 1?

Problem 2.28. Find a (p, q)-analog of Theorem 2.26 which reduces to Theorem 2.15 for r = 1.

The proof of Theorem 2.26 uses a general result of Linusson, Shareshian and Wachs [84, Corollary 3.8] on the Möbius function of the Rees product for posets, which we discuss in Section 2.4.

Problem 2.29. Find a direct combinatorial proof of Theorem 2.26.

In the case r = 2, further discussed in the sequel, a different combinatorial interpretation for the numbers ξ_{n,2,i}^{+} and ξ_{n,2,i}^{−}, in terms of permutations with no double excedance, was found by Shin and Zeng [116, Section 2]. This suggests the problem to find a combinatorial interpretation for the numbers ξ_{n,r,i}^{+} and ξ_{n,r,i}^{−} which generalizes the first interpretation of the numbers ξ_{n,i}, stated in Theorem 2.13, and prove directly its equivalence to the interpretation of Theorem 2.26.

Let us denote by d_{n,r}^{+}(x) and d_{n,r}^{−}(x) the first and second summand, respectively, in the right-hand side of (54). A geometric interpretation of the former will be discussed in Section 3.3. The following statement appeared as [108, Conjecture 3.7.10] in the special case r = 2; see also [7, Question 4.11].

Conjecture 2.30. The polynomials d_{n,r}^{+}(x) and d_{n,r}^{−}(x) are real-rooted for all positive integers n, r.

We close our discussion with generalizations of A_{n}(x) and d_{n}(x) to r-colored permutations which are different from, but related to (especially for r = 2), A_{n,r}(x) and d_{n,r}(x).

The flag excedance of a colored permutation w = σ ×z ∈ ℤ_{r} ≀𝔖_{n} was defined by E. Bagno and D. Garber [12] as

(55)  fexc(w) = r · exc(σ) + ∑_{i=1}^{n} z_{i},

where the sum of the colors z_{i} takes place in ℤ. The generating polynomial of fexc over all r-colored permutations factors nicely [11, 54] (see also [6, Proposition 2.2]) as

(56)  A_{n,r}^{fexc}(x) := ∑_{w∈ℤ_{r}≀𝔖_{n}} x^{fexc(w)} = (1 + x + x^{2} + ⋯ + x^{r−1})^{n} A_{n}(x).

The polynomial

(57)  f_{n,r}(x) := ∑_{w∈D_{n,r}} x^{fexc(w)}

was studied by P. Mongelli [86, Section 3] in the case r = 2 and by Z. Lin [79, Section 2.4.1] and by H. Shin and J. Zeng [116] for any r ≥ 1; it reduces to d_{n}(x) for r = 1. For r = 2 and for the first few values of n, we have

f_{n,2}(x) = \begin{cases}x, & if n = 1, \\ x + 3x^{2} + x^{3}, & if n = 2, \\ x + 7x^{2} + 13x^{3} + 7x^{4} + x^{5}, & if n = 3, \\ x + 15x^{2} + 57x^{3} + 87x^{4} + 57x^{5} + 15x^{6} + x^{7}, & if n = 4, \\ x + 31x^{2} + 201x^{3} + 551x^{4} + 761x^{5} + 551x^{6} + 201x^{7} + 31x^{8} + x^{9}, & if n = 5. \end{cases}

The symmetry of f_{n,r}(x) is nearly obvious (see [6, Proposition 2.5]); its unimodality was shown in [79, Theorem 2.4.11] [116, Corollary 4] (where the first reference offers a generalization and q-analog as well). The connection between the generating polynomials for exc and fexc, respectively, over ℤ_{r} ≀ 𝔖_{n} and D_{n,r} are the formulas

(58)  A_{n,r}(x) = Ẽ_{r}(A_{n,r}^{fexc}(x)),
(59)  d_{n,r}(x) = Ẽ_{r}(f_{n,r}(x)),

where Ẽ_{r} : ℝ[x] → ℝ[x] is the linear operator defined by setting Ẽ_{r}(x^{m}) = x^{⌈m/r⌉} for m ∈ ℕ; see [6, Proposition 2.3] and its proof. Equation (59) implies (see [6, Section 5]) that

(60)  d_{n,r}^{+}(x) = ∑_{w∈(D_{n,r})^{b}} x^{fexc(w)/r},

(61)  d_{n,r}^{−}(x) = ∑_{w∈D_{n,r}∖(D_{n,r})^{b}} x^{⌈ \frac{fexc(w)}{r} ⌉},

where (D_{n,r})^{b} stands for the set of derangements w ∈ D_{n,r} such that fexc(w) is divisible by r (colored permutations with this property are sometimes called balanced).

The polynomial f_{n,r}(x) is not γ-positive for r ≥ 3, the case r = 2 being more interesting. As discussed in [6, Section 5], it follows from Equations (60) and (61) that d_{n,2}(x) and f_{n,2}(x) determine one another in a simple way. The γ-positivity of f_{n,2}(x) (which is not real-rooted for all n) follows from the formula in [86, Proposition 3.4]

(62)  f_{n,2}(x) = ∑_{k=0}^{n} \binom{n}{k}x^{k}(1 + x)^{n−k} d_{n−k}(x)

and the γ-positivity of d_{n}(x) (Mongelli [86, Conjecture 8.1] further conjectured that f_{n,2}(x) is log-concave for all n). The corresponding γ-coefficients for the first few values of n are given by

f_{n,2}(x) = \begin{cases}x, & if n = 1, \\ x(1 + x)^{2} + x^{2}, & if n = 2, \\ x(1 + x)^{4} + 3x^{2}(1 + x)^{2} + x^{3}, & if n = 3, \\ x(1 + x)^{6} + 9x^{2}(1 + x)^{4} + 6x^{3}(1 + x)^{2} + x^{4}, & if n = 4, \\ x(1 + x)^{8} + 23x^{2}(1 + x)^{6} + 35x^{3}(1 + x)^{4} + 10x^{4}(1 + x)^{2} + x^{5}, & if n = 5. \end{cases}

The following elegant combinatorial interpretation for these coefficients was found by Shin and Zeng [116].

Theorem 2.31 (Shin–Zeng [116, Cor. 5]). We have f_{n,2}(x) = ∑_{i=0}^{⌊n/2⌋} ξ̂_{n,i}x^{i}(1 + x)^{2n−2i}, where ξ̂_{n,i} is equal to the number of permutations w ∈ 𝔖_{n} with i weak excedances and no double excedance. In particular, f_{n,2}(−1) = (−1)^{n} for n ≥ 1.

2.2. Coxeter–Narayana polynomials. Let W be a finite Coxeter group with set of simple generators S, and let ℓ_{T} : W → ℕ be the length (known as absolute length) function with respect to the generating set T = {wsw^{−1} : s ∈ S, w ∈ W } of all reflections in W. Choose a Coxeter element c ∈ W and set

NC_{W} = NC_{W} (c) := {w ∈ W : ℓ_{T} (w) + ℓ_{T} (w^{−1}c) = ℓ_{T} (c)}.

This set, endowed with a natural partial order which is graded by absolute length, was introduced by D. Bessis [16] and independently by T. Brady and C. Watt [23] as the poset of noncrossing partitions associated to W; see [3, Chapter 2] for more information (the isomorphism type of this poset does not depend on the choice of c). The generating polynomial

(63)  Cat(W, x) := ∑_{w∈NC_{W}} x^{ℓ_{T} (w)}

of the absolute length function over NC_{W} admits numerous algebraic, combinatorial and geometric interpretations and plays an important role in the subject of Catalan combinatorics of Coxeter groups [3, Chapter 5]. For the symmetric group 𝔖_{n}, its coefficients, known as Narayana numbers, refine the nth Catalan number; explicitly, we have:

(64)  Cat(W, x) = \begin{cases}∑_{i=0}^{n} \frac{1}{i + 1} \binom{n}{i}\binom{n + 1}{i}x^{i}, & if W = 𝔖_{n+1}, \\ ∑_{i=0}^{n} \binom{n}{i}^{2}x^{i}, & if W = B_{n} \\ ∑_{i=0}^{n} \binom{n}{i} (\binom{n − 1}{i} + \binom{n − 2}{i − 2}) x^{i}, & if W = B_{n}^{e}, \end{cases}

where (to avoid confusion with our notation for the set of derangements in 𝔖_{n}) B_{n}^{e} stands for the group of even-signed permutations of Ω_{n} (which is a Coxeter group of type D_{n}).

The symmetry of Cat(W, x) is a simple consequence of the definition. The following result can be verified with case-by-case computations; it is due essentially to R. Simion and D. Ullman [117, Corollary 3.1] [102, Proposition 11.14] for the group 𝔖_{n}, to A. Postnikov, V. Reiner and L. Williams [102, Proposition 11.15] for the group B_{n} and to M. Gorsky [67] for the group B_{n}^{e} (see also Remark 2.34). Theorem 2.32. The polynomial Cat(W, x) is γ-positive for every finite Coxeter group W. Moreover, writing

(65)  Cat(W, x) = ∑_{i=0}^{⌊n/2⌋} γ_{i}(W) x^{i}(1 + x)^{n−2i},

where n is the rank of W, we have the explicit formulas

(66)  γ_{i}(W) = \begin{cases}\frac{1}{i + 1}\binom{n}{i, i, n − 2i}, & if W = 𝔖_{n+1}, \\ \binom{n}{i, i, n − 2i}, & if W = B_{n}, \\ \frac{n − i − 1}{n − 1}\binom{n}{i, i, n − 2i}, & if W = B_{n}^{e}, \end{cases}

for 0 ≤ i ≤ ⌊n/2⌋.

For an extension of the γ-positivity of Cat(W, x) to well-generated complex reflection groups, see [88, Theorem 1.3]. Elegant q-analogs of the γ-positivity of Cat(𝔖_{n}, x) are given in [22, Theorem 1.2] and [82, Theorem 4].

As is usual in Catalan combinatorics, the polynomial Cat(W, x) has a positive analog, defined as

(67)  Cat^{+}(W, x) := ∑_{J⊆S} (−x)^{|S∖J|} Cat(W_{J}, x),

where W_{J} is the standard parabolic subgroup of W associated to J ⊆ S; we have the explicit formulas:

(68) Cat^{+}(W, x) = \begin{cases}∑_{i=0}^{n} \frac{1}{i + 1} \binom{n − 1}{i}\binom{n}{i}x^{i}, & if W = 𝔖_{n+1}, \\ ∑_{i=0}^{n} \binom{n − 1}{i}\binom{n}{i}x^{i}, & if W = B_{n}, \\ ∑_{i=0}^{n} (\binom{n − 2}{i}\binom{n}{i} + \binom{n − 2}{i − 2}\binom{n − 1}{i}) x^{i}, & if W = B_{n}^{e}. \end{cases}

This polynomial is not symmetric, except for the case of the symmetric groups. However, the polynomial

(69)  Cat^{++}(W, x) := ∑_{J⊆S} (−1)^{|S∖J|} Cat^{+}(W_{J}, x)

turns out to be symmetric and to have nonnegative coefficients for all W. This polynomial was first considered in an enumerative-geometric context in [10], explained in Section 3.3, and more recently in a different context in [14], where our notation comes from. For the symmetric and hyperoctahedral groups, the work [10] provides combinatorial interpretations for the coefficients of Cat^{++}(W, x) and the corresponding γ-coefficients ξ_{i}(W), in terms of noncrossing partitions with restrictions.

Theorem 2.33 (Athanasiadis–Savvidou [10]). The polynomial Cat^{++}(W, x) is γpositive for every finite Coxeter group W. Moreover, writing

(70)  Cat^{++}(W, x) = ∑_{i=0}^{⌊n/2⌋} ξ_{i}(W) x^{i}(1 + x)^{n−2i},

where n is the rank of W, we have ξ_{0}(W) = 0 and the explicit formulas

(71)  ξ_{i}(W) = \begin{cases}\frac{1}{n − i + 1}\binom{n}{i}\binom{n − i − 1}{i − 1}, & if W = 𝔖_{n+1}, \\ \binom{n}{i}\binom{n − i − 1}{i − 1}, & if W = B_{n}, \\ \frac{n − 2}{i}\binom{2i − 2}{i − 1}\binom{n − 2}{2i − 2}, & if W = B_{n}^{e}, \end{cases}

for 1 ≤ i ≤ ⌊n/2⌋.

Remark 2.34. Equations (67) and (69) can be inverted to give

(72)  Cat(W, x) = ∑_{J⊆S} x^{|S∖J|} Cat^{+}(W_{J}, x),
(73)  Cat^{+}(W, x) = ∑_{J⊆S} Cat^{++}(W_{J}, x),

respectively. Hence,

Cat(W, x) = ∑_{J⊆S} x^{|S∖J|} Cat^{+}(W_{J}, x) = ∑_{J⊆S} x^{|S∖J|} ∑_{I⊆J} Cat^{++}(W_{I}, x)

= ∑_{I⊆S} (x + 1)^{n−|I|} Cat^{++}(W_{I}, x),

where n is the rank of W. Setting

γ(W, x) = ∑_{i=0}^{⌊n/2⌋} γ_{i}(W)x^{i}, ξ(W, x) = ∑_{i=0}^{⌊n/2⌋} ξ_{i}(W)x^{i},

we see that the previous formula for Cat(W, x) translates into the equation

(74)  γ(W, x) = ∑_{J⊆S} ξ(W_{J}, x).

Alternatively, given the geometric interpretations of Cat(W, x) and Cat^{++}(W, x) discussed in Section 3.3, Equation (74) is a special case of [5, Corollary 5.5] [7, Equation (6)]; see also Theorem 3.15 in the sequel.

In particular, the γ-positivity statement of Theorem 2.33 is stronger than that of Theorem 2.32. □

The numbers γ_{1}(W) and ξ_{1}(W) are equal to the number of nonsimple reflections in W and the number of reflections in W which do not belong to any proper standard parabolic subgroup, respectively; see the first remark in [10, Section 5].

Problem 2.35. Find a proof of the γ-positivity of Cat(W, x) and Cat^{++}(W, x), as well as algebraic or combinatorial interpretations for the numbers γ_{i}(W) and ξ_{i}(W), which do not depend on the classification of finite Coxeter groups.

2.3. Polynomials arising from enriched poset partitions. Let (P, ω) be a labeled poset with n elements, as in Section 2.1.2, and recall that Ω_{m} := {1, −1, 2, −2, …, m, −m}. For m ∈ ℕ, denote by Ω′_{P,ω}(m) the number of maps f : P → Ω_{m} which are such that for all x, y ∈ P with x <_{P} y:

• |f(x)| ≤ |f(y)|,

• |f(x)| = |f(y)| implies f(x) ≤ f(y),
• f(x) = f(y) > 0 implies ω(x) < ω(y),
• f(x) = f(y) < 0 implies ω(x) > ω(y),

where Ω′_{P,ω}(0) := 0. These maps are called enriched (P, ω)-partitions; their theory was developed by Stembridge [133], in analogy with Stanley’s theory of (P, ω)-partitions. The function Ω′_{P,ω}(m), studied in [133, Section 4], turns out to be a polynomial in m of degree at most n and hence

(75)  ∑_{m≥0} Ω′_{P,ω}(m)x^{m} = \frac{A′_{P,ω}(x)}{(1 − x)^{n+1}}

for some polynomial A′_{P,ω}(x) of degree at most n. As pointed out by Stembridge to the author, the more explicit formula

(76)  A′_{P,ω}(x) = x ∑_{ε:P→{−1,1}} A_{P,εω}(x)

follows from [133, Theorem 3.6], where A_{P,εω}(x) is the ordinary (P, εω)-Eulerian polynomial defined as in Section 2.1.2, with labels taken from the totally ordered set ℤ.

The following result is a restatement of [133, Theorem 4.1]; it appeared several years before the work on γ-positivity of Brändén [24, 26] and Gal [61]. A peak of a permutation w ∈ 𝔖_{n} is any index 2 ≤ i ≤ n − 1 such that w(i − 1) < w(i) > w(i + 1).

Theorem 2.36 (Stembridge [133]). For every n-element labeled poset (P, ω)

(77)  A′_{P,ω}(x) = ∑_{i=0}^{⌊(n−1)/2⌋} p_{n,i} 2^{2i+1} x^{i+1}(1 + x)^{n−1−2i},

where p_{n,i} is the number of permutations w ∈ L(P, ω) (see Definition 2.6) with i peaks. In particular, A′_{P,ω}(x) is γ-positive.

This theorem reduces to the γ-positivity of the Eulerian polynomial A_{n}(x) when P is the n-element antichain, since in this case A′_{P,ω}(x) = x 2^{n}A_{n}(x).

2.4. Polynomials arising from poset homology. A γ-positivity theorem, due to S. Linusson, J. Shareshian and M. Wachs [84], which captures as special cases some of the basic examples we have seen so far, comes from the study of the homology of the Rees product of posets, a construction due to A. Björner and V. Welker [21]. Given finite graded posets P and Q with rank functions ρ_{P} and ρ_{Q}, respectively, their Rees product is defined in [21] as P ∗Q = {(p, q) ∈ P ×Q : ρ_{P}(p) ≥ ρ_{Q}(q)}, partially ordered by setting (p_{1}, q_{1}) ⪯ (p_{2}, q_{2}) if all of the following conditions are satisfied:

• p_{1} ⪯ p_{2} holds in P,

• q_{1} ⪯ q_{2} holds in Q and
• ρ_{P}(p_{2}) − ρ_{P}(p_{1}) ≥ ρ_{Q}(q_{2}) − ρ_{Q}(q_{1}).

The poset P ∗ Q is graded with rank function given by ρ(p, q) = ρ_{P}(p) for (p, q) ∈ P ∗ Q.

To state the result of [84], we need to recall a few more definitions. Let P be a finite graded poset, as before, and assume further that P is bounded, with minimum element ˆ0 and maximum element ˆ1, and that it has rank n + 1. For S ⊆ [n], we denote by a_{P}(S) the number of maximal chains of the rank-selected subposet

(78)  P_{S} := {p ∈ P : ρ_{P}(p) ∈ S} ∪ {ˆ0, ˆ1}

of P, and set

(79)  b_{P}(S) := ∑_{T ⊆S}(−1)^{|S−T |} a_{P}(T).

The numbers a_{P}(S) and b_{P}(S) are important enumerative invariants of P; see [127, Section 3.13]. The numbers b_{P}(S) are nonnegative, if P is Cohen–Macaulay over some field, and afford a simple combinatorial interpretation, if P admits an R-labeling. The number (−1)^{n−1}b_{P}([n]) is the Möbius number of the poset P̄, obtained from P by removing ˆ0 and ˆ1; it is denoted by μ(P̄). The posets obtained from P by removing ˆ0 or ˆ1 are denoted by P_{−} or P^{−}, respectively. The poset whose Hasse diagram is a complete x-ary tree of height n, rooted at the minimum element, is denoted by T_{x,n}. For the notion of EL-shellability, the reader is referred to [84, Section 2] and references therein. The following theorem is a restatement of [84, Corollary 3.8].

Theorem 2.37 (Linusson–Shareshian–Wachs [84]). Let P be a finite bounded graded poset of rank n + 1. If P is EL-shellable, then

(80) μ ((P^{−} ∗ T_{x,n})_{−}) = ∑_{S∈Stab([n−1])} b_{P}([n]∖S) x^{|S|}(1 + x)^{n−2|S|}

+ ∑_{S∈Stab([n−2])} b_{P}([n − 1]∖S) x^{|S|+1}(1 + x)^{n−1−2|S|}

and

(81) μ (P̄ ∗ T_{x,n−1}) = ∑_{S∈Stab([2,n−2])} b_{P}([n − 1]∖S) x^{|S|+1}(1 + x)^{n−2−2|S|}

+ ∑_{S∈Stab([2,n−1])} b_{P}([n]∖S) x^{|S|}(1 + x)^{n−1−2|S|}

for every positive integer x.

This theorem turns out to be valid without the assumption of EL-shellability; see [9]. When P^{−} has a maximum element, the first and the second summand of the right-hand sides of Equations (80) and (81), respectively, vanishes and hence the left-hand sides are γ-positive polynomials in x, provided P is Cohen–Macaulay over some field.

Example 2.38. Suppose that P^{−} is the Boolean lattice of subsets of the set [n], ordered by inclusion. Then, the left-hand sides of Equations (80) and (81) are equal to xA_{n}(x) and d_{n}(x), respectively (this is the content of [110, Equation (3.1)] in the former case, and is implicit in [110] in the latter). The number b_{P}(S) is known to count permutations w ∈ 𝔖_{n} such that Des(w) = S [127, Corollary 3.13.2]. Thus, Theorem 2.37 reduces to the γ-positivity of A_{n}(x) and d_{n}(x) (specifically, to the third interpretations given for γ_{n,i} and ξ_{n,i} in Theorems 2.1 and 2.13, respectively) in this case. □

The p = 1 specializations of Theorems 2.3 and 2.15 can be viewed as the special case of Theorem 2.37 in which P^{−} is the lattice of subspaces of an n-dimensional vector space over a field with q elements. This follows from Equations (1.3) and (1.4) in [84] and from the known interpretation [127, Theorem 3.13.3] of b_{P}(S) for this poset. Theorem 2.26 is derived in [6, Section 4] from the special case of Theorem 2.37 in which P^{−} is the set of r-colored subsets of [n], ordered by inclusion.

Similarly, Theorem 2.25 can be viewed as the special case of Theorem 2.37 in which P^{−} is the product of chains whose lengths are the parts of λ; see [84, Section 5]. The proof of Theorem 2.25 given there, however, involves a different approach and thus, it would be interesting to prove directly that the left-hand sides of Equations (80) and (81) are equal to those of Equations (50) and (51), respectively, in this case.

Remark 2.39. Theorem 2.25 can be applied, more generally, when P is the distributive lattice of order ideals of an n-element poset Q, since then b_{P}(S) counts linear extensions of Q with descent set equal to S [127, Theorem 3.13.1]. Are there combinatorial interpretations for the coefficients of the left-hand sides of Equations (80) and (81) which reduce to those of Theorem 2.25 when Q is a disjoint union of chains of cardinalities equal to the parts of λ? □

2.5. Polynomials arising from symmetric functions. Let x = (x_{1}, x_{2}, …) be a sequence of commuting independent indeterminates (to avoid confusion with this notation, in this section we consider polynomials in the variable t, rather than x). For integer partitions λ, consider the polynomials P_{λ}(t) and R_{λ}(t) which are defined by the equations

(82) \frac{(1 − t)H(x; z)}{H(x; tz) − tH(x; z)} = \frac{∑_{k≥0} h_{k}(x)z^{k}}{1 − ∑_{k≥2} (t + t^{2} + ⋯ + t^{k−1}) h_{k}(x)z^{k}} = ∑_{λ} P_{λ}(t)s_{λ}(x) z^{|λ|}

and

(83) \frac{1 − t}{H(x; tz) − tH(x; z)} = \frac{1}{1 − ∑_{k≥2} (t + t^{2} + ⋯ + t^{k−1}) h_{k}(x)z^{k}} = ∑_{λ} R_{λ}(t)s_{λ}(x) z^{|λ|},

where H(x; z) = ∑_{n≥0} h_{n}(x)z^{n} is the generating function for the complete homogeneous symmetric functions in x, and λ ranges over all partitions (including the one without any parts). The left-hand sides of Equations (82) and (83) were first considered by Stanley [122, Propositions 12 and 13] and, since then, they have appeared in various algebraicgeometric and combinatorial contexts; see the relevant discussions in [111, Section 7] [84, Section 4] [113], as well as Section 5 in the sequel. Stanley [122] observed that for λ ⊢ n, the polynomials P_{λ}(t) and R_{λ}(t) have nonnegative and symmetric coefficients, with centers of symmetry (n − 1)/2 and n/2, respectively, which satisfy

(84)  ∑_{λ⊢n} f^{λ}P_{λ}(t) = A_{n}(t)

and

(85)  ∑_{λ⊢n} f^{λ}R_{λ}(t) = d_{n}(t),

where f^{λ} is the number of standard Young tableaux of shape λ. This shows that the coefficients of z^{n} in the functions appearing in Equations (82) and (83) correspond, via Frobenius characteristic, to graded 𝔖_{n}-representations whose graded dimensions are equal to A_{n}(t) and d_{n}(t), respectively. Thus, the left-hand sides of Equations (82) and (83) can be considered as representation-theoretic analogs of A_{n}(t) and d_{n}(t), respectively. Combinatorial interpretations for the coefficients of P_{λ}(t) and R_{λ}(t) were provided by Stembridge [131, Section 4]; a different one for P_{λ}(t) can be derived as a special case of [112, Theorem 6.3].

The unimodality of P_{λ}(t) and R_{λ}(t), which refines that of A_{n}(t) and d_{n}(t), was proved by Stanley [122, Proposition 12] and Brenti [30, Corollary 1], respectively. Given that A_{n}(t) and d_{n}(t) are γ-positive, it is natural to ask whether P_{λ}(t) and R_{λ}(t) have the same property. An affirmative answer follows from explicit formulas which refine Theorems 2.1 and 2.13. These formulas are essentially equivalent to the following unpublished result of Gessel, stated without proof in [84, Section 4] [111, Section 7] [114, Section 3]. We write E(x; z) = ∑_{n≥0} e_{n}(x)z^{n} for the generating function for the elementary symmetric functions in x. For a map w : [n] → ℤ_{>0} we set x_{w} := x_{w(1)}x_{w(2)} ⋯ x_{w(n)} and, as usual, define by Asc(w) := [n − 1]∖Des(w) and Des(w) := {i ∈ [n − 1] : w(i) > w(i + 1)} the set of ascents and descents of w and denote by asc(w) and des(w) the cardinalities of these sets, respectively.

Theorem 2.40 (Gessel, unpublished). We have

\frac{(1 − t)H(x; z)}{H(x; tz) − tH(x; z)} = 1 + ∑_{n≥1} z^{n} ∑_{\begin{matrix}w : [n] → ℤ_{>0} \\ Des(w) ∈ Stab([n − 2]) \end{matrix}} t^{des(w)}(1 + t)^{n−1−2des(w)} x_{w}, (86)

\frac{1 − t}{H(x; tz) − tH(x; z)} = 1 + ∑_{n≥2} z^{n} ∑_{\begin{matrix}w : [n] → ℤ_{>0} \\ Des(w) ∈ Stab([2, n − 2]) \end{matrix}} t^{des(w)+1}(1 + t)^{n−2−2des(w)} x_{w}, (87)

\frac{(1 − t)E(x; z)}{E(x; tz) − tE(x; z)} = 1 + ∑_{n≥1} z^{n} ∑_{\begin{matrix}w : [n] → ℤ_{>0} \\ Asc(w) ∈ Stab([n − 2]) \end{matrix}} t^{asc(w)}(1 + t)^{n−1−2asc(w)} x_{w}, (88)

and (89)

\frac{1 − t}{E(x; tz) − tE(x; z)} = 1 + ∑_{n≥2} z^{n} ∑_{\begin{matrix}w : [n] → ℤ_{>0} \\ Asc(w) ∈ Stab([2, n − 2]) \end{matrix}} t^{asc(w)+1}(1 + t)^{n−2−2asc(w)} x_{w}.

Equations (86) and (87) can be shown to be equivalent to (88) and (89), respectively, via an application of the standard involution ω on symmetric functions. Perhaps not surprisingly, Equations (88) and (89) can be deduced [9, Corollary 4.1] as special cases of an equivariant version of Theorem 2.37; see [9, Theorem 1.2] and Theorem 5.3 in the sequel. A direct combinatorial proof of (88) will be sketched in Section 4.1.

Corollary 2.41. For λ ⊢ n,

(90)  P_{λ}(t) = ∑_{i=0}^{⌊(n−1)/2⌋} γ_{i}^{λ} t^{i}(1 + t)^{n−1−2i}

and

(91)  R_{λ}(t) = ∑_{i=0}^{⌊n/2⌋} ξ_{i}^{λ} t^{i}(1 + t)^{n−2i},

where

• γ_{i}^{λ} is the number of tableaux Q ∈ SYT(λ) for which Des(Q) ∈ Stab([n − 2]) has i elements, and

• ξ_{i}^{λ} is the number of tableaux Q ∈ SYT(λ) for which Des(Q) ∈ Stab([2, n − 2]) has i − 1 elements.

In particular, P_{λ}(t) and R_{λ}(t) are γ-positive for every partition λ.

Proof. For B ⊆ [n − 1], we consider the skew hook shape whose row lengths, read from bottom to top, form the composition of n corresponding to B and denote by s_{B}(x) the skew Schur function associated to this shape. As in the proof of [114, Corollary 3.2], we note that, because of the obvious correspondence between monomials x_{w} and semistandard Young tableaux of skew hook shape, Equation (86) may be rewritten as

(92)  \frac{(1 − t)H(x; z)}{H(x; tz) − tH(x; z)} = 1 + ∑_{n≥1} z^{n} ∑_{i=0}^{⌊(n−1)/2⌋} γ_{n,i}(x) t^{i}(1 + t)^{n−1−2i},

where

(93)  γ_{n,i}(x) = ∑_{\begin{matrix}B ∈ Stab([n − 2]) \\ |B| = i \end{matrix}} s_{B}(x).

Expanding s_{B}(x) by the well known rule

(94)  s_{B}(x) = ∑_{λ⊢n} |{Q ∈ SYT(λ) : Des(Q) = B}| · s_{λ}(x)

in the basis of Schur functions and comparing the coefficients of s_{λ}(x) on the two sides of (92), we obtain the desired formula for P_{λ}(t). A similar argument works for R_{λ}(t). □

The author is not aware of any results in the literature concerning the roots of P_{λ}(t) and R_{λ}(t).

2.6. Polynomials arising from trees. This section discusses two more instances of γ-positivity in combinatorics. For further examples, see [26, 81] and Sections 3.3 and 4.2.

A tree T on the vertex set [n] is called rooted if it has a distinguished vertex, called root. An edge {a, b}, with a < b, of such a tree T is called a descent if the unique path in T which connects a with the root passes through b. Let t_{n}(x) be the polynomial in which the coefficient of x^{k} equals the number of rooted trees on the vertex set [n] with exactly k descents. The following elegant x-analog

(95)  t_{n}(x) = ∏_{i=1}^{n−1} ((n − i) + ix)

of Cayley’s formula, which is a specialization of results of Ö. Eğecioğlu and J. Remmel [50], implies the γ-positivity of t_{n}(x). Several explicit combinatorial interpretations for the corresponding γ-coefficients were found by R. González D’León [66].

A tree T on the vertex set [n] is called alternating, or intransitive [100], if every vertex of T is either less than all its neighbors, in which case it is called a left vertex, or greater than all its neighbors, in which case it is called a right vertex. Let g_{n}(x) be the polynomial in which the coefficient of x^{k} equals the number of alternating trees on the vertex set [n] with exactly k left vertices. These polynomials were considered in [63, 100]; for the first few values of n, we have

g_{n}(x) = \begin{cases}1, & if n = 1, \\ x, & if n = 2, \\ x + x^{2}, & if n = 3, \\ x + 5x^{2} + x^{3}, & if n = 4, \\ x + 17x^{2} + 17x^{3} + x^{4}, & if n = 5, \\ x + 49x^{2} + 146x^{3} + 49x^{4} + x^{5}, & if n = 6, \\ x + 129x^{2} + 922x^{3} + 922x^{4} + 129x^{5} + x^{6}, & if n = 7. \end{cases}

Theorem 2.42 (Gessel–Griffin–Tewari [64, Theorem 5.9]). The polynomial g_{n}(x) is γ-positive for every positive integer n.

The proof, which uses symmetric functions, yields a combinatorial formula for the γcoefficients involving certain plane binary trees. An explicit combinatorial interpretation has also been found by V. Tewari [138].

\begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ • \\ • \end{matrix}

Figure 2. A two-dimensional simplicial complex

3. Gamma-positivity in geometry

This section discusses the main geometric contexts in which γ-positivity occurs. Many of the examples treated in Section 2 reappear here as interesting special cases of more general phenomena. Familiarity with basic notions on simplicial complexes and their geometric realizations is assumed; see [19] [36, Chapter 2] [77] [140, Lecture 1] for detailed expositions. All simplicial complexes considered here are assumed to be finite. To keep our discussion as elementary as possible, we work with triangulations of spheres and balls, rather than with the more general classes of homology spheres and homology balls.

We first review some basic definitions and background related to the face enumeration of simplicial complexes. For i ≥ 0 we denote by f_{i−1}(Δ) the number of (i−1)-dimensional faces of a simplicial complex Δ, where (unless Δ is empty) f_{−1}(Δ) := 1.

Definition 3.1. The h-polynomial of a simplicial complex Δ of dimension n−1 is defined as

(96)  h(Δ, x) := ∑_{i=0}^{n} f_{i−1}(Δ)x^{i}(1 − x)^{n−i} := ∑_{i=0}^{n} h_{i}(Δ)x^{i}.

The sequence h(Δ) = (h_{0}(Δ), h_{1}(Δ), …, h_{n}(Δ)) is the h-vector of Δ.

The polynomial h(Δ, x) can be thought of as an x-analog of the number f_{n−1}(Δ) of facets (meaning, faces of maximum dimension n − 1) of Δ, since h(Δ, 1) = f_{n−1}(Δ). We refer the reader to [126] for the significance of the h-polynomial, as well as for important algebraic and combinatorial interpretations which are valid for special classes of simplicial complexes.

Example 3.2. The simplicial complex Δ shown in Figure 2 triangulates a two-dimensional simplex with eight vertices, fifteen edges and eight two-dimensional faces. Thus, f_{−1}(Δ) = 1, f_{0}(Δ) = 8, f_{1}(Δ) = 15 and f_{2}(Δ) = 8 and we may compute that h(Δ, x) = (1 − x)^{3} + 8x(1 − x)^{2} + 15x^{2}(1 − x) + 8x^{3} = 1 + 5x + 2x^{2}. □

The relevance of the h-polynomial to the symmetry and unimodality of real polynomials stems from the following theorem, which combines important results by V. Klee, G. Reisner and R. Stanley [76, 105, 119, 120] in geometric combinatorics; see [126] for more information. The first two parts hold more generally for the classes of Cohen–Macaulay and Eulerian, respectively, simplicial complexes.

Theorem 3.3 (Klee, Reisner, Stanley). Let Δ be (n − 1)-dimensional.

(a) The polynomial h(Δ, x) has nonnegative coefficients, i.e., we have h_{i}(Δ) ≥ 0 for 0 ≤ i ≤ n, if Δ triangulates a ball or a sphere.

(b) The polynomial h(Δ, x) is symmetric, i.e., we have h_{i}(Δ) = h_{n−i}(Δ) for 0 ≤ i ≤ n, if Δ triangulates a sphere.

(c) The polynomial h(Δ, x) is unimodal, i.e., we have

(97)  1 = h_{0}(Δ) ≤ h_{1}(Δ) ≤ ⋯ ≤ h_{⌊n/2⌋}(Δ),

if Δ is the boundary complex of a simplicial polytope.

Part (c), proved by R. Stanley [120], is known as the Generalized Lower Bound Theorem for simplicial polytopes, since the inequalities h_{i}(Δ) ≥ h_{i−1}(Δ) impose a lower bound for each face number f_{i−1}(Δ) in terms of the numbers f_{j−1}(Δ) for 1 ≤ j < i.

3.1. Flag triangulations of spheres. Let Δ be an (abstract) simplicial complex on the vertex set V. We say that Δ is flag if we have F ∈ Δ for every F ⊆ V for which all two-element subsets of F belong to Δ, and refer to [4] [126, Section III.4] for a glimpse of the combinatorial properties of this fascinating class of simplicial complexes. The complex shown in Figure 2, for example, is flag.

The following major open problem in geometric combinatorics was posed by Ś. Gal [61] who disproved a more optimistic conjecture, claiming that h(Δ, x) is real-rooted for every flag triangulation of a sphere.

Conjecture 3.4 (Gal [61, Conjecture 2.1.7]). The polynomial h(Δ, x) is γ-positive for every flag simplicial complex Δ which triangulates a sphere.

This conjecture extends an earlier conjecture of R. Charney and M. Davis [37] on the sign of h(Δ, −1); it is also open for the more restrictive class of flag boundary complexes of simplicial polytopes.

Example 3.5. Consider a triangulation Δ of the one-dimensional sphere with m vertices (cycle of length m). We have f_{−1}(Δ) = 1 and f_{0}(Δ) = f_{1}(Δ) = m and hence h(Δ, x) = (1 − x)^{2} + mx(1 − x) + mx^{2} = 1 + (m − 2)x + x^{2} is γ-positive if and only if m ≥ 4. Note that this is exactly the necessary and sufficient condition for Δ to be flag. □

Conjecture 3.4 can be viewed as a Generalized Lower Bound Conjecture for flag triangulations of spheres Δ. To be more precise, we may write

(98)  h(Δ, x) = ∑_{i=0}^{⌊n/2⌋} γ_{i}(Δ)x^{i}(1 + x)^{n−2i},

where n − 1 = dim(Δ) and γ_{0}(Δ) = 1. The vector γ(Δ) := (γ_{0}(Δ), γ_{1}(Δ), …, γ_{⌊n/2⌋}(Δ)) is known as the γ-vector of Δ and Gal’s conjecture states that γ_{i}(Δ) ≥ 0 for all i. Just as in the case of Theorem 3.3 (c), these inequalities impose a lower bound on each h_{i}(Δ) in terms of the numbers h_{j}(Δ) for 0 ≤ j < i, and hence a lower bound on each face number f_{i−1}(Δ) in terms of the face numbers f_{j−1}(Δ) for 1 ≤ j < i.

For instance, since γ_{1}(Δ) = h_{1}(Δ) − n = f_{0}(Δ) − 2n, the inequality γ_{1}(Δ) ≥ 0 states that every flag triangulation of the (n − 1)-dimensional sphere has at least 2n vertices, a fact which is easy to prove by induction on n. The inequality γ_{2}(Δ) ≥ 0 already provides a challenge. Since

γ_{2}(Δ) = h_{2}(Δ) − (n − 2)γ_{1}(Δ) − \binom{n}{2} = f_{1}(Δ) − (2n − 3)f_{0}(Δ) + 2n(n − 2),

its validity turns out to be equivalent to the following conjectural flag analog of Barnette’s Lower Bound Theorem [15]. We recall that the suspension (simplicial join with a zerodimensional sphere) of a flag triangulation of a sphere is a flag triangulation of a sphere of one dimension higher.

Conjecture 3.6. Among all flag triangulations of the (n − 1)-dimensional sphere with a given number m of vertices, the (n − 2)-fold suspension over the one-dimensional sphere with m − 2n + 4 vertices has the smallest possible number of edges.

For a generalization of this statement, see [90, Conjecture 1.4]. A conjecture concerning the possible vectors which can arise as γ-vectors of flag triangulations of spheres is proposed in [91].

An edge subdivision of a simplicial complex Δ is a stellar subdivision of Δ on any of its edges; we refer to [5, Section 6] [37, Section 5.3] [61, Section 2.4] for the precise definition and Figure 3 for an example. Edge subdivisions preserve flagness and homeomorphism type. We will denote by Σ_{n} the simplicial join of n copies of the zero-dimensional sphere (this simplicial complex is combinatorially isomorphic to the boundary complex of the n-dimensional cross-polytope; it satisfies h(Σ_{n}, x) = (1 + x)^{n} or, equivalently, γ(Σ_{n}) = (1, 0, …, 0)). Apart from the results on barycentric subdivisions and nested complexes, discussed separately in the sequel, Gal’s conjecture is known to hold for flag triangulations of spheres:

• of dimension less than five [44, Theorem 11.2.1] [61, Corollary 2.2.3],

• with at most 2n + 3 vertices, i.e., with γ_{1}(Δ) ≤ 3 [91, Theorem 1.3],

• which can be obtained from Σ_{n} by successive edge subdivisions [61, Section 2.4],

• for other special classes of flag triangulations of spheres, discussed in Section 3.3.

Remark 3.7. The proof of the third statement above is only implicit in [61, Section 2.4]. To make it more explicit, let us denote by Δ_{e} the edge subdivision of Δ on its edge e ∈ Δ. Gal observes [61, Proposition 2.4.3] that

(99)  h(Δ_{e}, x) = h(Δ, x) + x h(link_{Δ}(e), x),

where link_{Δ}(F) = {G∖F : G ∈ Δ, F ⊆ G} is the link of F ∈ Δ in Δ. In particular, if Δ and link_{Δ}(e) satisfy Gal’s conjecture, then so does Δ [61, Corollary 2.4.7]. One can verify that every link of a nonempty face in Δ_{e} is combinatorially isomorphic to either the link of a nonempty face in Δ, or to an edge subdivision or the suspension of the link of a nonempty face in Δ. Thus, it follows by induction and Equation (99) that, if Δ can be

\begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ ⟶ \end{matrix}

Figure 3. An edge subdivision

obtained from Σ_{n} by successive edge subdivisions, then Δ and all links of its faces satisfy Gal’s conjecture. □

3.1.1. Barycentric subdivisions. An important class of flag simplicial complexes is that of order complexes [126, Section III.4]. Recall that the order complex of a poset P is defined as the simplicial complex Δ(P) of all chains (totally ordered subsets) of P. When P is the poset of (nonempty) faces of a regular CW-complex X, the complex Δ(P) is by definition the (first) barycentric subdivision of X. As explained, for instance, in [61, Section 2.3], the following result is a direct consequence of important theorems of K. Karu and R. Stanley on the nonnegativity of the cd-index of Gorenstein* posets [74] (for introductions to the cd-index, see [126, Section III.4] [127, Section 3.17]).

Theorem 3.8 (Karu [74], Stanley [124]; see [61, Corollary 2.3.5]). Conjecture 3.4 holds for every order complex Δ which triangulates a sphere. In particular, it holds for barycentric subdivisions of regular CW-spheres.

As recorded in [37, Section 7.3] [126, p. 103], the connection between the cd-index of an Eulerian poset P and the last entry of the γ-vector of Δ(P) was observed by E. Babson. The nonnegativity of the cd-index was proved for the augmented face posets of certain shellable CW-spheres by Stanley [124, Theorem 2.2] and for arbitrary Gorenstein* posets by Karu [74, Theorem 1.3] (Stanley’s result suffices to conclude the validity of Gal’s conjecture for barycentric subdivisions of boundary complexes of convex polytopes). For barycentric subdivisions of Boolean complexes which triangulate a sphere, more elementary proofs of Theorem 3.8 can be found in [33, 92].

There is an interesting analog of Theorem 3.8 for triangulations of balls, rather than spheres. As explained in [73, Section 4], the following result is a direct consequence of [51, Theorem 2.5]. Here ∂Δ denotes the boundary of a triangulated ball Δ.

Theorem 3.9 (Ehrenborg–Karu [51]; see [73, Theorem 4.6]). The polynomial h(Δ, x) − h(∂Δ, x) is γ-positive for every order complex Δ which triangulates a ball. In particular, this holds for barycentric subdivisions of regular CW-balls.

3.1.2. Flag nested complexes. We begin with a few definitions, following [141]. A building set on the ground set [n] is a collection B of nonempty subsets of [n] such that:

\begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ \{1\} \\ \{2\} \\ \{3\} \\ \{4\} \end{matrix}

Figure 4. A nested complex

• B contains all singletons {i} ⊆ [n], and

• if I, J ∈ B and I ∩ J ≠ ∅, then I ∪ J ∈ B. We denote by B_{max} the set of maximal (with respect to inclusion) elements of B and say that B is connected if [n] ∈ B. A set N ⊆ B∖B_{max} is called nested if for all k ≥ 2 and all I_{1}, I_{2}, …, I_{k} ∈ N such that none of the I_{i} contains another, their union I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k} is not in B. The simplicial complex Δ_{B} on the vertex set B∖B_{max}, consisting of all nested sets, is the nested complex associated to B. For example, if B consists of all nonempty subsets of [n], then Δ_{B} is the barycentric subdivision of the boundary of the simplex 2^{[n]}.

The nested complex Δ_{B} is isomorphic to the boundary complex of a simplicial polytope of dimension n − |B_{max}| [52, Theorem 3.14] [101, Theorem 7.4] [141, Theorem 6.1]; the corresponding polar-dual simple polytope is called a nestohedron. Nestohedra form an important class of Postnikov’s generalized permutohedra [101] which includes permutohedra, graph-associahedra and other well studied simple polytopes in geometric combinatorics. As shown in [53, Theorem 4] and explained in [102, Remark 6.6], the complex Δ_{B} can be constructed as follows. Assume (without loss of generality) that B is connected, and consider the boundary ∂σ of the simplex σ on the vertex set [n]. Choose any ordering of the nonsingleton elements of B∖B_{max} which respects the reverse of the inclusion order. Starting with ∂σ, and following the chosen ordering, for each nonsingleton I ∈ B∖B_{max} perform a stellar subdivision on the face I. The resulting simplicial complex is Δ_{B}.

Example 3.10. For n = 4, consider the building set B consisting of {1}, {2}, {3}, {4}, {3, 4}, {2, 3, 4} and {1, 2, 3, 4}. The nested complex Δ_{B} triangulates the boundary of the three-dimensional simplex on the vertex set {{1}, {2}, {3}, {4}}; it has eight facets, six of which are shown in Figure 4 (the two unlabeled vertices being {3, 4} and {2, 3, 4}). The remaining facets are the nonvisible facets {{1}, {2}, {3}} and {{1}, {2}, {4}} of the simplex. Note that Δ_{B} corresponds indeed to the simplicial complex obtained by stellarly subdividing the boundary complex of the simplex on the vertex set {1, 2, 3, 4} first on the face {2, 3, 4} and then on {3, 4}. □

Gal’s conjecture was verified for flag nested complexes by V. Volodin [139], who showed that they can be obtained from the boundary complex of a cross-polytope by successive edge subdivisions. The main result of [102] provides an explicit combinatorial interpretation of the entries of the γ-vector of a large family of flag nested complexes. To state this result, we need to introduce a few definitions from [102]. Let B be a building set on the ground set [n]. The restriction of B to I ⊆ [n] is defined as the family of all subsets of I which belong to B. The restrictions of B to the elements of B_{max} are the connected components of B. The building set B is called chordal if for every {i_{1}, i_{2}, …, i_{k}} ∈ B with i_{1} < i_{2} < ⋯ < i_{k} and all indices 1 ≤ r ≤ k we have {i_{r}, i_{r+1}, …, i_{k}} ∈ B. Nested complexes of chordal building sets are always flag [102, Proposition 9.7]. We denote by 𝔖_{B} the set of all permutations w ∈ 𝔖_{n} such that w(i) and max{w(1), w(2), …, w(i)} lie in the same connected component of the restriction of B to {w(1), w(2), …, w(i)}, for every i ∈ [n]. The following result combines Corollary 9.6 with Theorem 11.6 in [102] and, as shown in [102, Section 10], provides a common generalization for the γ-positivity of the Eulerian and binomial Eulerian polynomials A_{n}(x) and Ã_{n}(x) and the Narayana polynomials Cat(W, x) for the symmetric and hyperoctahedral groups, discussed in Section 2.

Theorem 3.11 (Postnikov–Reiner–Williams [102]). For every connected, chordal building set B on the ground set [n]

(100)  h(Δ_{B}, x) = ∑_{i=0}^{n} h_{B,i} x^{i} = ∑_{i=0}^{⌊n/2⌋} γ_{B,i} x^{i}(1 + x)^{n−2i},

where

• h_{B,i} is the number of permutations w ∈ 𝔖_{B} with i descents, and

• γ_{B,i} is the number of permutations w ∈ 𝔖_{B} for which Des(w) ∈ Stab([n − 2]) has i elements.

The nested complex Δ_{B} of Example 3.10 has eight facets. The elements of 𝔖_{B}, written in one-line notation, are 1234, 1243, 1342, 1432, 2341, 2431, 3421 and 4321, and h(Δ_{B}, x) = 1 + 3x + 3x^{2} + x^{3} = (1 + x)^{3}, in agreement with Theorem 3.11.

3.2. Flag triangulations of simplices. This section focuses on a variant of the hpolynomial of a triangulation of a sphere, the local h-polynomial, defined for triangulations of simplices (and for more general topological, rather than geometric, simplicial subdivisions of the simplex; see [123, Part I] [5, 7]). The local h-polynomial was introduced by Stanley [123] and plays a key role in his enumerative theory of triangulations of simplicial complexes, developed in order to study their effect on the h-polynomial of a simplicial complex.

Let V be an n-element set and Γ be a triangulation of the simplex 2^{V}. The restriction of Γ to the face F ⊆ V of the simplex is a triangulation of F, denoted by Γ_{F}.

Definition 3.12 (Stanley [123, Definition 2.1]). The local h-polynomial of Γ (with respect to V) is defined as

(101)  ℓ_{V} (Γ, x) := ∑_{F ⊆V}(−1)^{n−|F |} h(Γ_{F} , x) := ℓ_{0} + ℓ_{1}x + ⋯ + ℓ_{n}x^{n}.

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

For example, the complex of Figure 2 is naturally a triangulation Γ of a two-dimensional simplex 2^{V}. Since h(Γ, x) = 1 + 5x + 2x^{2} and the restrictions of Γ on the three edges of the simplex have h-polynomials 1, 1 + x and 1 + 2x, we have ℓ_{V} (Γ, x) = (1 + 5x + 2x^{2}) − 1 − (1 + x) − (1 + 2x) + 1 + 1 + 1 − 1 = 2x + 2x^{2}.

The following theorem shows that the local h-polynomial has properties similar to those of the h-polynomial of a triangulation of the sphere, stated in Theorem 3.3. For the notion of a regular triangulation, we refer to [45, Chapter 5] [123, Definition 5.1].

Theorem 3.13 (Stanley [123]). Let Γ be a triangulation of an (n − 1)-dimensional simplex 2^{V} and set ℓ_{V} (Γ, x) = ℓ_{0} + ℓ_{1}x + ⋯ + ℓ_{n}x^{n}.

(a) The polynomial ℓ_{V} (Γ, x) has nonnegative coefficients.

(b) The polynomial ℓ_{V} (Γ, x) is symmetric, i.e., we have ℓ_{i} = ℓ_{n−i} for 0 ≤ i ≤ n.

(c) The polynomial ℓ_{V} (Γ, x) is unimodal, i.e., we have ℓ_{0} ≤ ℓ_{1} ≤ ⋯ ≤ ℓ_{⌊d/2⌋}, if Γ is regular.

The following analog of Conjecture 3.4 may come as no surprise to some readers; it is stated more generally in [5, Conjecture 5.4] for a class of topological simplicial subdivisions which models combinatorially geometric subdivisions.

Conjecture 3.14 (Athanasiadis [5]). The polynomial ℓ_{V} (Γ, x) is γ-positive for every flag triangulation Γ of the simplex 2^{V}.

Since ℓ_{V} (Γ, x) is symmetric, with center of symmetry n/2, we may write

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

The sequence ξ(Γ) := (ξ_{0}(Γ), ξ_{1}(Γ), …, ξ_{⌊n/2⌋}(Γ)) is termed in [5] as the local γ-vector of Γ (with respect to V) and the polynomial ξ_{V} (Γ, x) := ∑_{i=0}^{⌊n/2⌋} ξ_{i}(Γ)x^{i} as the corresponding local γ-polynomial. Thus, Conjecture 3.14 claims that ξ_{i}(Γ) ≥ 0 for all 0 ≤ i ≤ ⌊n/2⌋ and every flag triangulation Γ of the simplex 2^{V}. Apart from results on barycentric subdivisions, discussed in the sequel, Conjecture 3.14 has been verified for flag triangulations of simplices:

• of dimension less than four [5, Proposition 5.7],

• which can be obtained from the trivial triangulation by successive edge subdivisions [5, Proposition 6.1],

• for other special classes of flag triangulations of simplices, discussed in Section 3.3.

The connection between γ-vectors and their local counterparts is explained by the following result. We recall that Σ_{n} stands for the boundary complex of the n-dimensional cross-polytope and refer to [5] [7, Section 2] for the precise definitions of the more general notions of simplicial subdivision which appear there.

Theorem 3.15 (Athanasiadis [5] [7, Theorem 3.7]). Every flag triangulation Δ of the (n − 1)-dimensional sphere is a vertex-induced simplicial homology subdivision of Σ_{n}. Moreover,

(103)  γ(Δ, x) = ∑_{F ∈Σ_{n}} ξ_{F} (Δ_{F} , x).

The version of Conjecture 3.14 stated as [5, Conjecture 5.4] applies to the summands in the right-hand side of (103). As a result, [5, Conjecture 5.4] implies Gal’s conjecture, as well as its stronger version [61, Conjecture 2.1.7] for flag homology spheres. Moreover, as explained at the end of [8, Section 1], the validity of Conjecture 3.14 for regular flag triangulations of simplices implies Gal’s conjecture for flag boundary complexes of convex polytopes.

The following statement is a direct consequence of Theorem 3.15 and Stanley’s monotonicity theorem [123, Theorem 4.10] (in the form of [7, Corollary 2.9]) for h-vectors of subdivisions of simplicial complexes; it was proved more generally for flag doubly Cohen– Macaulay complexes, using different methods, in [4, Theorem 1.3].

Corollary 3.16. Every flag triangulation Δ of the (n − 1)-dimensional sphere satisfies

(104)  h_{i}(Δ) ≥ \binom{n}{i}

for 0 ≤ i ≤ n.

3.2.1. Barycentric subdivisions. Barycentric subdivisions of polyhedral subdivisions of the simplex form a natural class of its flag triangulations. The question of the validity of Conjecture 3.14 for them was raised in [5, Question 6.2] [7, Problem 3.8] and answered in the affirmative by Juhnke-Kubitzke, Murai and Sieg [73, Theorem 1.3]. The last statement in the following theorem is a consequence of Equation (105), Theorem 3.9 and the γpositivity of the derangement polynomials d_{n}(x).

Theorem 3.17 (Kubitzke–Murai–Sieg [73]). For every triangulation Γ of an (n−1)- dimensional simplex 2^{V},

(105)  ℓ_{V} (Γ, x) = ∑_{F ⊆V} (h(Γ_{F} , x) − h(∂(Γ_{F}), x)) d_{n−|F |}(x).

In particular, Conjecture 3.14 holds for barycentric subdivisions of regular CW-complexes which subdivide the simplex.

3.2.2. Nested subdivisions. Let B be a connected building set on the ground set [n]. We denote by Γ_{B} the cone of the nested complex Δ_{B}. Alternatively, Γ_{B} is the simplicial complex on the vertex set B, consisting of all nested subsets of B (rather than B∖B_{max}), defined by the condition described in Section 3.1.2. Since Δ_{B} triangulates the boundary of an (n − 1)-dimensional simplex, the complex Γ_{B} is a triangulation of this simplex (for example, it is the barycentric subdivision, if B consists of all nonempty subsets of [n]). We call Γ_{B} the nested subdivision associated to B.

No doubt, just as is the case with Δ_{B}, one can show that whenever Γ_{B} is a flag complex, it can be obtained from the trivial subdivision of the (n − 1)-dimensional simplex by successive edge subdivisions. Thus, the γ-positivity of the local h-polynomial of Γ_{B} follows from [5, Proposition 6.1]. In view of Theorem 3.11, it seems natural to pose the following problem.

Problem 3.18. Find a combinatorial interpretation for the local γ-polynomial of Γ_{B}, for any connected chordal building set B.

3.3. Examples. This section discusses further examples of flag triangulations of spheres or simplices, which appear naturally in algebraic-geometric contexts, and the γ-positivity of their h-polynomials or local h-polynomials. These examples provide algebraic-geometric interpretations for several of the γ-positive polynomials discussed in Section 2.

3.3.1. Barycentric and edgewise subdivisions. As noted in Section 3.1.1, the barycentric subdivision of a regular CW-complex X, denoted here by sd(X), is defined as the simplicial complex of all chains in the poset of nonempty faces of X.

Let V be an n-element set, and consider the barycentric subdivision sd(2^{V}) of the simplex 2^{V}. The facets of sd(2^{V}) are in one-to-one correspondence with the permutations of V. Thus, the h-polynomial of sd(2^{V}) is an x-analog of the number n!; it is well known, in fact, that

(106)  h(sd(2^{V}), x) = A_{n}(x).

Since coning a simplicial complex does not affect its h-polynomial, A_{n}(x) is also equal to the h-polynomial of the barycentric subdivision sd(∂(2^{V})) of the boundary complex of 2^{V}. Moreover, given that sd(2^{V}) restricts to the barycentric subdivision sd(2^{F}) for every F ⊆ V, Stanley [123, Proposition 2.4] showed that

(107)  ℓ_{V} (sd(2^{V}), x) = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}A_{k}(x) = ∑_{w∈D_{n}} x^{exc(w)} = d_{n}(x).

Consequently, the unimodality of A_{n}(x) and d_{n}(x) follows from parts (c) of Theorems 3.3 and 3.13, and their γ-positivity is an instance of Conjectures 3.4 and 3.14, respectively. A part of the barycentric subdivision of the boundary complex of the three-dimensional simplex is shown in Figure 5. The restrictions on the facets of the simplex are barycentric subdivisions of two-dimensional simplices.

The r-fold edgewise subdivision, denoted here by esd_{r}(Δ), is another elegant (but not as well known as barycentric subdivision) triangulation of a simplicial complex Δ with Figure 5. Two Coxeter complexes

Figure 6. An edgewise subdivision

a long history in mathematics; see [8, Section 1] and references therein. To describe it in a geometrically intuitive way, consider positive integers n, r and the geometric simplex σ_{n,r} = {(x_{1}, x_{2}, …, x_{n−1}) ∈ ℝ^{n−1} : 0 ≤ x_{n−1} ≤ ⋯ ≤ x_{2} ≤ x_{1} ≤ r}. The r-fold edgewise subdivision esd_{r}(2^{V}) of an (n − 1)-dimensional simplex 2^{V} is realized as the triangulation of σ_{n,r} whose facets are the (n − 1)-dimensional simplices into which σ_{n,r} is dissected by the affine hyperplanes in ℝ^{n−1} with equations

• x_{i} = k, where 1 ≤ i ≤ n − 1,

• x_{i} − x_{j} = k, where 1 ≤ i < j ≤ n − 1

for k ∈ {1, 2, …, r −1}. This triangulation has exactly r^{n−1} facets; it is shown in Figure 6 for n = 3 and r = 4. For an arbitrary simplicial complex Δ, the r-fold edgewise subdivision esd_{r}(Δ) restricts to esd_{r}(2^{F}) for every F ∈ Δ; for a formal definition, see, for instance, [6, Section 4] [34, Section 4].

The triangulation esd_{r}(Δ) is flag for every flag simplicial complex Δ; in particular, esd_{r}(2^{V}) is a flag triangulation of the simplex. Combinatorial interpretations for its local h-vector and local γ-vector can be given as follows. Let us denote by W(n, r) the set of sequences w = (w_{0}, w_{1}, …, w_{n}) ∈ {0, 1, …, r − 1}^{n+1} satisfying w_{0} = w_{n} = 0, and by S(n, r) the set of those elements of W(n, r) (known as Smirnov words) having no two consecutive entries equal. As usual, we call i ∈ {0, 1, …, n−1} an ascent of w ∈ W(n, r) if w_{i} ≤ w_{i+1} and i ∈ [n−1] a double ascent if w_{i−1} ≤ w_{i} ≤ w_{i+1} (descents and double descents are defined similarly, using strict inequalities). We also denote by E_{r} the linear operator on the space ℝ[x] of polynomials in x with real coefficients defined by setting E_{r}(x^{m}) = x^{m/r},

Figure 7. The triangulation K_{3}

if m is divisible by r, and E_{r}(x^{m}) = 0 otherwise. For the second interpretation of ξ_{n,r,i} which appears in the following result (but not in [7, 8]), see Remark 4.1.

Theorem 3.19 (Athanasiadis [7, Theorem 4.6] [8]). The local h-polynomial of the rfold edgewise subdivision esd_{r}(2^{V}) of the (n − 1)-dimensional simplex on the vertex set V can be expressed as

ℓ_{V} (esd_{r}(2^{V}), x) = E_{r} (x + x^{2} + ⋯ + x^{r−1})^{n} = ∑_{w∈S(n,r)} x^{asc(w)}

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

where asc(w) is the number of ascents of w ∈ S(n, r) and ξ_{n,r,i} equals each of the following:

• the number of sequences w = (w_{0}, w_{1}, …, w_{n}) ∈ S(n, r) with exactly i ascents which have the following property: for every double ascent k of w there exists a double descent ℓ > k such that w_{k} = w_{ℓ} and w_{k} ≤ w_{j} for all k < j < ℓ,

• the number of w ∈ W(n, r) for which Asc(w) ∈ Stab([n−2]) has i elements, where Asc(w) is the set of ascents of w.

The interpretations of the polynomials A_{n}(x) and d_{n}(x), described in this section, have interesting hyperoctahedral group analogs. Let C_{n} denote the boundary complex of the standard n-dimensional unit cube. The facets of the barycentric subdivision sd(C_{n}) are in one-to-one correspondence with the signed permutations w ∈ B_{n}. As a result, the h-polynomial of sd(C_{n}) is an x-analog of the number 2^{n}n! and, in fact (see our discussion in Section 3.3.2),

(108)  h(sd(C_{n}), x) = B_{n}(x),

where B_{n}(x) is the B_{n}-Eulerian polynomial, discussed in Section 2.1.3. Consider now the cubical barycentric subdivision of an (n − 1)-dimensional simplex 2^{V}. This is a cubical complex whose face poset is isomorphic to the set of nonempty closed intervals in the poset of nonempty subsets of V, partially ordered by inclusion. Its (simplicial) barycentric subdivision, denoted by K_{n}, is a triangulation of 2^{V} with exactly 2^{n−1}n! facets. Figure 7

Figure 8. Barycentric and edgewise subdivisions

shows these subdivisions for n = 3 (note that K_{3} is combinatorially isomorphic to the visible part of the complex sd(C_{3}) which is shown in Figure 5). We then have [7, Remark 4.5] [108, Theorem 3.1.4]

(109)  ℓ_{V} (K_{n}, x) = d_{n,2}^{+}(x),

where d_{n,2}(x) = d_{n,2}^{+}(x) + d_{n,2}^{−}(x) is the decomposition of the derangement polynomial for B_{n} discussed in Section 2.1.7. Thus, the γ-positivity of B_{n}(x) and d_{n,2}^{+}(x), discussed in Section 2, are again instances of Conjectures 3.4 and 3.14, respectively.

The problem to interpret the polynomial d_{n,r}^{+}(x), discussed in Section 2.1.7, as a local h-polynomial for all r ≥ 1 was studied in [6] and provided much of the motivation for that paper. It is not clear how to generalize the triangulation K_{n} for this purpose. However, one can show directly (see [7, Remark 4.5]) that ℓ_{V} (K_{n}, x) = ℓ_{V} (esd_{2}(sd(2^{V})). Thus, the r-fold edgewise subdivision esd_{r}(sd(2^{V})) of the barycentric subdivision of the simplex 2^{V} is a reasonable candidate to replace K_{n} and, indeed, [6, Theorem 1.2] shows that

(110)  ℓ_{V} (esd_{r}(sd(2^{V})), x) = d_{n,r}^{+}(x).

The barycentric subdivision of the two-dimensional simplex and its 2-fold edgewise subdivision are shown in Figure 8. Further examples of barycentric and edgewise subdivisions appear in Section 4.2.

3.3.2. Coxeter complexes. Let W be a finite Coxeter group. Then W can be realized as a reflection group in an n-dimensional Euclidean space, where n is the rank of W. The reflecting hyperplanes form a simplicial arrangement, known as the Coxeter arrangement, whose face poset is isomorphic to that of a simplicial complex Cox(W), called the Coxeter complex. This complex is combinatorially isomorphic to the barycentric subdivision of the boundary complex of the n-dimensional simplex or cube (see Figure 5 for two threedimensional pictures), when W is the symmetric group 𝔖_{n+1} or the hyperoctahedral group B_{n}, respectively.

The facets of Cox(W) are in a natural one-to-one correspondence with the elements of W. Thus, the h-polynomial of Cox(W) is an x-analog of the order of the group W and, in fact, as was essentially shown by A. Björner [18] (see [31, Theorem 2.3]), we have

(111)  h(Cox(W), x) = W (x),

where W (x) is the W -Eulerian polynomial, discussed in Section 2.1.3.

Clearly, Cox(W) is a triangulation of the (n − 1)-dimensional sphere and, as explained in [97, Section 8.5], this triangulation is flag. Thus, the γ-positivity of W (x) (Theorem 2.8) verifies Gal’s conjecture in a special case.

3.3.3. Cluster complexes. Let W be a finite Coxeter group of rank n, viewed as a reflection group in an n-dimensional Euclidean space. Consider the root system Φ defined by the Coxeter arrangement associated to W and a choice Φ^{+} of a positive system, along with corresponding simple system Π. The cluster complex Δ_{W} is a flag simplicial complex on the vertex set Φ^{+} ∪ (−Π), defined by S. Fomin and A. Zelevinsky [60]; we refer to [59] for an overview of the relevant theory and its connections to cluster algebras. This complex triangulates the (n−1)-dimensional sphere; its restriction on the vertex set Φ^{+} is naturally a flag triangulation of the simplex 2^{Π}, termed in [10] as the cluster subdivision. One then has [59, Theorem 5.9]

(112)  h(Δ_{W} , x) = Cat(W, x)

and [10, Section 1.1]

(113)  ℓ_{Π}(Γ_{W} , x) = Cat^{++}(W, x),

where Cat(W, x) and Cat^{++}(W, x) were defined in Section 2.2. Thus, the γ-positivity of these polynomials (Theorems 2.32 and 2.33) verifies Conjectures 3.4 and 3.14, respectively, in special cases.

4. Methods

A remarkable variety of methods has been employed to prove γ-positivity and often to describe the γ-coefficients in some explicit way. This section reviews in some detail three such methods, namely valley hopping, methods of geometric combinatorics stemming from Stanley’s seminal work [123], and (quasi)symmetric function methods. Although it seems difficult to provide an exhaustive list, or attempt some kind of classification, the author is aware of the following methodological approaches which have been followed successfully to prove the γ-positivity of a polynomial f(x):

• Combinatorial decompositions: Assuming f(x) enumerates a set of combinatorial objects according to some statistic, one may try to combinatorially decompose this set into parts, each contributing a binomial x^{i}(1 + x)^{n−2i} to this enumeration. One instance of this approach is valley hopping (see Section 4.1), and another is symmetric Boolean decompositions of posets [88, 95, 117]. Other instances appear in [10, Section 3] [48] [135, Appendix A] (see also [97, Section 13.2]).

• Explicit combinatorial formulas: One may try to express f(x) explicitly as a sum of products of polynomials known to be γ-positive, all products having the same center of symmetry, using direct combinatorial arguments, generating functions, continued fraction expansions, and so on. The prototypical example of this approach is Brändén’s [24] beautiful proof of Theorem 2.7; see also [39, 115, 116, 135].

• The theory of the cd-index of an Eulerian poset: see Section 3.1.1 and [48] [135, Appendix A] for related approaches.

• Poset shellability and homology methods: The prototypical example is the use of shellability of Rees products of posets in [84], leading to Theorem 2.37 and related results discussed in Section 2.4; see also Theorem 5.3 in the sequel.

• Geometric methods: Apart from those discussed in Section 4.2, geometric methods are employed in [2, 91], where the γ-positivity of f(x) is proved by constructing a simplicial complex whose f-vector is shown to equal the γ-vector of f(x).

• Recursive methods: One can prove positivity of the γ-coefficients via recursions, without providing any explicit interpretations or formulas. This is the case with the proof of Theorem 2.12 in [80] and the γ-positivity of the restricted Eulerian polynomials of [92, Section 4].

• Symmetric and quasisymmetric function methods: see Section 4.3.

4.1. Valley hopping. The idea of valley hopping is due to D. Foata and V. Strehl [57, 58], who used it to interpret combinatorially the γ-coefficients for the Eulerian polynomials (see Theorem 2.1). It was rediscovered by L. Shapiro, W. Woan and S. Getu [109] and has found numerous applications to the enumeration of classes of permutations [10, Section 4] [26, 83] [102, Section 11] [137] and related combinatorial objects [8, Section 3].

To explain this idea, let w = (w_{1}, w_{2}, …, w_{n}) ∈ 𝔖_{n}, where w_{i} = w(i) for 1 ≤ i ≤ n, be a permutation and set w_{0} = w_{n+1} = ∞ and w̃ = (w_{0}, w_{1}, …, w_{n+1}). Given a double ascent or double descent i of w̃ (meaning, an index i ∈ [n] such that w_{i−1} < w_{i} < w_{i+1} or w_{i−1} > w_{i} > w_{i+1}, respectively), we define the permutation ψ_{i}(w) ∈ 𝔖_{n} as follows: If i is a double ascent of w̃, then ψ_{i}(w) is the permutation obtained from w̃ by deleting w_{i} and inserting it between w_{j} and w_{j+1}, where j is the largest index satisfying 0 ≤ j < i and w_{j} > w_{i}. Similarly, if i is a double descent of w̃, then ψ_{i}(w) is the permutation obtained from w̃ by deleting w_{i} and inserting it between w_{j} and w_{j+1}, where j is the smallest index satisfying i < j ≤ n and w_{i} < w_{j+1}. For the example of Figure 9 we have ψ_{1}(w) = (3, 2, 5, 4, 7, 8, 1, 6) and ψ_{8}(w) = (7, 3, 2, 5, 4, 8, 6, 1).

We call two permutations in 𝔖_{n} equivalent if one can be obtained from the other by a sequence of moves of the form w ↦ ψ_{i}(w). We leave to the reader to verify that this defines an equivalence relation on 𝔖_{n}, each equivalence class of which contains a unique permutation u such that ũ has no double ascent. Moreover, if ũ has k double descents for such u ∈ 𝔖_{n}, then the equivalence class O(u) of u has 2^{k} elements and exactly \binom{k}{j} of them have j ascents more than u. Therefore,

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

Summing over all equivalence classes, we obtain the first combinatorial interpretation for γ_{n,i}, given in Theorem 2.1.

\begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ 7 \\ 3 \\ 2 \\ 5 \\ 4 \\ 8 \\ 6 \\ 1 \end{matrix}

Figure 9. Valley hopping for w = (7, 3, 2, 5, 4, 8, 1, 6)

To illustrate the power of this method, let us modify it to prove Gessel’s identity (88). We will use Stanley’s interpretation (see [111, Theorem 7.2])

(115)  \frac{(1 − t)E(x; z)}{E(x; tz) − tE(x; z)} = 1 + ∑_{n≥1} z^{n} ∑_{w∈S(n)} t^{asc(w)} x_{w}

of the left-hand side of (88), where we have used notation of Section 2.5 and S(n) stands for the set of maps w : [n] → ℤ_{>0} satisfying w(i) ≠ w(i + 1) for every i ∈ [n − 1].

Proof of Equation (88). Given Equation (115), it suffices to show that

(116)  ∑_{w∈S(n)} t^{asc(w)} x_{w} = ∑_{\begin{matrix}u : [n] → ℤ_{>0} \\ Asc(u) ∈ Stab([n − 2]) \end{matrix}} t^{asc(u)}(1 + t)^{n−1−2asc(u)} x_{u}

for all n ≥ 1. For w ∈ S(n) we write w = (w_{1}, w_{2}, …, w_{n}) and define w̃, as we did for permutations. For a double ascent i of w̃, we denote by ψ_{i}(w) the sequence obtained from w̃ by deleting w_{i} and inserting it between positions j and j + 1, where j is the largest index satisfying 0 ≤ j < i and w_{j} > w_{i}. We define ψ_{i}(w) in a similar way for double descents i of w̃ and say that a move w ↦ ψ_{i}(w) is valid if i is a double ascent or descent of w̃ and ψ_{i}(w) ∈ S(n). For the example of Figure 10 we have ψ_{4}(w) = (3, 2, 3, 2, 4, 3, 2, 1, 2), ψ_{6}(w) = (2, 3, 2, 3, 4, 2, 1, 2, 3), ψ_{7}(w) = (2, 3, 2, 3, 4, 3, 1, 2, 2) and ψ_{9}(w) = (2, 3, 2, 3, 4, 3, 2, 2, 1). The move w ↦ ψ_{i}(w) is valid for i ∈ {4, 6} and invalid for i ∈ {7, 9}.

We call two elements of S(n) equivalent if one can be obtained from the other by a sequence of valid moves of the form w ↦ ψ_{i}(w). We leave again to the reader to verify that this defines an equivalence relation on S(n), each equivalence class of which contains a unique element v, call it the minimal representative, such that ṽ has a minimum number of double ascents. For example, the minimal representative of the equivalence class of the sequence shown in Figure 10 is ψ_{4}(w). The reasoning which led to Equation (114) also

\begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ 2 \\ 3 \\ 2 \\ 3 \\ 4 \\ 3 \\ 2 \\ 1 \\ 2 \end{matrix}

Figure 10. Valley hopping for w = (2, 3, 2, 3, 4, 3, 2, 1, 2)

shows that the equivalence class O(v) of a minimal representative v satisfies

(117)  ∑_{w∈O(v)} t^{asc(w)} x_{w} = x^{asc(v)}(1 + x)^{n−1−2asc(v)} x_{v}.

Summing over all equivalence classes, we get

(118)  ∑_{w∈S(n)} t^{asc(w)} x_{w} = ∑ t^{asc(v)}(1 + t)^{n−1−2asc(v)} x_{v},

where the sum on the right-hand side runs over all minimal representatives v of equivalence classes. Application of all possible invalid moves to such an element v which shift entries to the left (the order not making a difference) results in a map u = f(v) : [n] → ℤ_{>0} such that Asc(u) ∈ Stab([n − 2]) and x_{u} = x_{v}. Moreover, the map f is a bijection from the set of minimal representatives v to the set of such maps u which preserves the weight x_{v} and the proof follows. □

Remark 4.1. The variant of valley hopping which was employed in the previous proof appeared in [8, Section 3] to derive the first interpretation for ξ_{n,r,i}, given in Theorem 3.19. The last part of the argument in this proof yields the second interpretation. □

4.2. Methods of geometric combinatorics. The enumerative theory of [123, Part I], developed by Stanley in order to study h-vectors of triangulations of simplicial complexes, together with recent developments [5], provides a powerful method to prove γ-positivity of polynomials which can often be defined purely in combinatorial terms. This point of view, which is implicit in [7, Section 4] [108, Chapter 3], is further explained in this section. Familiarity with basic definitions from Section 3 is assumed.

The following statement explains the significance of the concept of local h-vector in the theory of [123].

Theorem 4.2 (Stanley [123, Theorem 3.2]). For every triangulation Δ′ of a pure simplicial complex Δ,

(119)  h(Δ′, x) = ∑_{F ∈Δ} ℓ_{F} (Δ′_{F} , x) h(link_{Δ}(F), x).

This result implies that h(Δ′, x) is γ-positive (as a sum of γ-positive polynomials with the same center of symmetry), if so are ℓ_{F} (Δ′_{F} , x) and h(link_{Δ}(F), x) for every F ∈ Δ. For instance, we have the following statement.

Corollary 4.3. Suppose Δ is either:

• the simplicial join Σ_{n} of n copies of the zero-dimensional sphere, or

• the barycentric subdivision of the boundary of a simplex. Then, h(Δ′, x) is γ-positive for every triangulation Δ′ of Δ for which ℓ_{F} (Δ′_{F} , x) is γpositive for every F ∈ Δ.

Proof. As already discussed, it suffices to confirm that h(link_{Δ}(F), x) is γ-positive for all F ∈ Δ. This is obvious if Δ = Σ_{n}, since then link_{Δ}(F) is isomorphic to Σ_{n−|F |} and hence h(link_{Δ}(F), x) = (1 + x)^{n−|F |} for every F ∈ Δ.

Suppose now that Δ = sd(∂(2^{V})) is the barycentric subdivision of the boundary complex of an n-dimensional simplex 2^{V}. Then, faces of Δ have the form F = {S_{1}, S_{2}, …, S_{k}}, where S_{1} ⊂ S_{2} ⊂ ⋯ ⊂ S_{k} are nonempty proper subsets of V. Setting S_{0} := ∅ and S_{k+1} := V, we have that link_{Δ}(F) is the simplicial join of the complexes sd(∂(2^{S_{i}∖S_{i−1}})) for i ∈ [k + 1] and hence

(120)  h(link_{Δ}(F), x) = ∏_{i=1}^{k+1} A_{n_{i}}(x),

where n_{i} = |S_{i}∖S_{i−1}| for i ∈ [k + 1]. This polynomial is indeed γ-positive, as a product of γ-positive polynomials. Alternatively, h(link_{Δ}(F), x) can be shown to be γ-positive for the barycentric subdivision Δ of any regular CW-sphere by a stronger version of Theorem 3.8 (applying to Gorenstein* order complexes). □

Example 4.4. The following explicit formula for the h-polynomial of the r-fold edgewise subdivision of an (n − 1)-dimensional simplicial complex Δ is a consequence of [34, Corollary 1.2] and [35, Corollary 6.8]:

(121)  h(esd_{r}(Δ), x) = E_{r} ((1 + x + x^{2} + ⋯ + x^{r−1})^{n} h(Δ, x)) ,

where the linear operator E_{r} : ℝ[x] → ℝ[x] was defined before Theorem 3.19. Thus, Corollary 4.3, combined with Theorem 3.19, implies the γ-positivity of

(122)  h(esd_{r}(Σ_{n}), x) = E_{r} ((1 + x + x^{2} + ⋯ + x^{r−1})^{n} (1 + x)^{n})

and

(123)  h(esd_{r}(sd(∂(2^{V}))), x) = E_{r} ((1 + x + x^{2} + ⋯ + x^{r−1})^{n} A_{n+1}(x)) ,

where 2^{V} is an n-dimensional simplex. It would be interesting to find explicit combinatorial interpretations for the coefficients of the right-hand sides of Equations (122) and (123) and their corresponding γ-polynomials. Similar remarks apply to the second barycentric subdivision of the boundary complex of a simplex. □

We now consider the following generalization of the concept of local h-polynomial. Let V be an n-element set, Γ be a triangulation of the simplex 2^{V} and E ∈ Γ.

Definition 4.5 (Athanasiadis [5, Remark 3.7] [7, Definition 2.14], Nill–Schepers [93, Section 3]). The relative local h-polynomial of Γ (with respect to V) at E ∈ Γ is defined as

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

where σ(E) is the smallest face of 2^{V} containing E.

This polynomial, which reduces to ℓ_{V} (Γ, x) for E = ∅, has properties similar to those of ℓ_{V} (Γ, x). Specifically, it has nonnegative and symmetric coefficients, with center of symmetry (n − |E|)/2 (see [7, Theorem 2.15]) and, moreover, it is unimodal if Γ is a regular triangulation [75, Remark 6.5] (see [7, Section 2.3] for more information). The significance of the relative local h-polynomial for us stems from the following statement. Note that, if Γ is a triangulation of the simplex 2^{V}, then every triangulation Γ′ of Γ induces a triangulation of 2^{V} whose local h-polynomial is denoted by ℓ_{V} (Γ′, x).

Proposition 4.6 (Athanasiadis [5, Section 3] [7, Proposition 2.15 (a)]). For every triangulation Γ of the simplex 2^{V} and every triangulation Γ′ of Γ,

(124)  ℓ_{V} (Γ′, x) = ∑_{E∈Γ} ℓ_{E}(Γ′_{E}, x) ℓ_{V} (Γ, E, x).

As a result, ℓ_{V} (Γ′, x) is γ-positive if so are ℓ_{E}(Γ′_{E}, x) and ℓ_{V} (Γ, E, x) for every E ∈ Γ. Using an argument similar to the one employed in the proof of Equation (120), one can show (see [108, Example 3.5.2]) that

(125)  ℓ_{V} (sd(2^{V}), E, x) = d_{n_{0}}(x) · ∏_{i=1}^{k} A_{n_{i}}(x),

where E = {S_{1}, S_{2}, …, S_{k}} with ∅ ⊂ S_{1} ⊂ S_{2} ⊂ ⋯ ⊂ S_{k} ⊆ V is a face of sd(2^{V}), d_{n_{0}}(x) is a derangement polynomial, n_{0} = |V ∖S_{k}| and n_{i} = |S_{i}∖S_{i−1}| for 1 ≤ i ≤ k (with the convention that S_{0} = ∅).

Corollary 4.7. The polynomial ℓ_{V} (Γ′, x) is γ-positive for every triangulation Γ′ of sd(2^{V}) for which ℓ_{E}(Γ′_{E}, x) is γ-positive for every E ∈ sd(2^{V}).

The special case for which Γ′ is the r-fold edgewise subdivision proves the γ-positivity of the polynomial d_{n,r}^{+}(x) discussed in Section 2.1.7; see [7, Example 4.8]. We give another interesting application.

Example 4.8. Suppose that Γ′ is the barycentric subdivision of sd(2^{V}) and that V is an n-element set. Then, the induced triangulation of 2^{V} is the second barycentric subdivision sd^{(2)}(2^{V}). An explicit, but rather complicated, formula for ℓ_{V} (sd^{(2)}(2^{V}), x) can be derived from the definition of local h-polynomial and [33, Theorem 1]. Proposition 4.6, combined with Equations (107) and (125), implies that

(126)  ℓ_{V} (sd^{(2)}(2^{V}), x) = ∑ \binom{n}{n_{0}, n_{1}, …, n_{k}} d_{k}(x) d_{n_{0}}(x) A_{n_{1}}(x) ⋯ A_{n_{k}}(x),

where the sum ranges over all k ≥ 0 and over all sequences (n_{0}, n_{1}, …, n_{k}) of integers which satisfy n_{0} ≥ 0, n_{1}, …, n_{k} ≥ 1 and sum to n. The γ-positivity of the polynomial ℓ_{V} (sd^{(2)}(2^{V}), x) follows from this formula (equivalently, from Corollary 4.7).

Using the principle of inclusion-exclusion, one can show that the sum of the coefficients of ℓ_{V} (sd^{(2)}(2^{V}), x) equals the number of pairs of permutations u, v ∈ 𝔖_{n} which have no common fixed point. The problem to interpret combinatorially the coefficients of this polynomial and its corresponding local γ-polynomial was posed in [7, Problem 4.12]. □

4.3. Symmetric/quasisymmetric function methods. Symmetric and quasisymmetric functions provide standard tools for enumeration problems; see, for instance, [17, 85] [125, Chapter 7]. Given a polynomial f(t), to be shown to be γ-positive, one may attempt to find a (quasi)symmetric function which gives f(t) via appropriate specialization. Expansion of this function in some basis of (quasi)symmetric functions may lead to a different formula for f(t) for which γ-positivity is easier to prove. The first instance of this approach seems to be Stembridge’s proof of Theorem 2.36 (although a more direct proof, based on Equation (76), is also possible), where the role of the basis of quasisymmetric functions is played by Gessel’s basis of fundamental quasisymmetric functions (41).

To illustrate this approach, we sketch proofs of Theorems 2.3, 2.15 and 2.16 which derive these statements from the main result on Eulerian quasisymmetric functions [111] of Shareshian and Wachs, following the reasoning of [114, Section 4]. We use the notation introduced in the beginning of the proof of Proposition 2.22 and set

(127)  F_{n,S}^{∗}(x) := F_{n,n−S}(x) = ∑_{\begin{matrix}i_{1}≥i_{2}≥···≥i_{n}≥1 \\ j∈S ⇒ i_{j}>i_{j+1} \end{matrix}} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}}

for S ⊆ [n − 1]. The principal specializations of this function are given by the formula (see [65, Lemma 5.2])

(128)  ∑_{m≥1} F_{n,S}^{∗}(1, q, …, q^{m−1})p^{m−1} = \frac{p^{|S|}q^{sum(S)}}{(1 − p)(1 − pq) ⋯ (1 − pq^{n})}

which refines Equation (42), where sum(S) stands for the sum of the elements of S. We also recall the formula (see [125, Proposition 7.19.12])

(129)  ∑_{m≥1} s_{λ}(1, q, …, q^{m−1})p^{m−1} = \frac{f^{λ}(p, q)}{(1 − p)(1 − pq) ⋯ (1 − pq^{n})}

for the principal specializations of s_{λ}(x), where

(130)  f^{λ}(p, q) := ∑_{P ∈SYT(λ)} p^{des(P)}q^{maj(P)}

and maj(P) := sum(Des(P)) is the major index of P.

Proof of Theorems 2.3 and 2.15. Let us denote by A_{n}(p, q, t) the left-hand side of Equation (9). Combining the special case r = 1 of [111, Theorem 1.2] with Equation (82) and extracting the coefficient of z^{n}, we see that

(131)  ∑_{w∈𝔖_{n}} F_{n,DEX(w)}(x) t^{exc(w)} = ∑_{λ⊢n} P_{λ}(t)s_{λ}(x)

for n ≥ 1. We refer to [111, Section 2] for the definition of DEX(w); the only properties of this set which are essential here are the facts that |DEX(w)| = des^{∗}(w) and that sum(DEX(w)) = maj(w) − exc(w) for w ∈ 𝔖_{n}; see [111, Lemma 2.2]. Thus, taking the generating function of the principal specialization of order m on both sides of (131) and using Equations (128) and (129), we arrive at the identity

(132)  A_{n}(p, q, t) = ∑_{λ⊢n} P_{λ}(t)f^{λ}(p, q).

By the γ-expansion of P_{λ}(t), given in Corollary 2.41, and the definition of f^{λ}(p, q), this formula implies that

(133)  A_{n}(p, q, t) = ∑_{λ⊢n} ∑_{P, Q ∈ SYT(λ) Des(Q) ∈ Stab([n − 2])} p^{des(P)}q^{maj(P)} t^{des(Q)}(1 + t)^{n−1−des(Q)}.

Use of the Robinson–Schensted correspondence and its properties [125, Lemma 7.23.1] to replace the pair (P, Q) of standard Young tableaux of the same shape with a permutation w ∈ 𝔖_{n} shows that the right-hand sides of Equations (133) and (9) are equal and the proof of Theorem 2.3 follows.

To prove Theorem 2.15, one combines the special case r = 0 of [111, Theorem 1.2] with Equation (83) instead to show that

(134)  ∑_{w∈D_{n}} F_{n,DEX(w)}(x) t^{exc(w)} = ∑_{λ⊢n} R_{λ}(t)s_{λ}(x)

and then takes principal specialization, as before. □

For the proof of Theorem 2.16 we need the formulas (see [125, Section 7.19]) for the stable principal specializations

(135)  F_{n,S}^{∗}(1, q, q^{2}, …) = \frac{q^{sum(S)}}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})}

and

(136)  s_{λ}(1, q, q^{2}, …) = \frac{f^{λ}(q)}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})},

where f^{λ}(q) := f^{λ}(1, q) = ∑_{P ∈SYT(λ)} q^{maj(P)}.

Proof of Theorem 2.16. Let us denote by A_{n,k}(q, t) the left-hand side of Equation (31). Comparing the coefficients of r^{k}z^{n} on both sides of [111, Equation (1.3)] and applying Equation (83), we get

∑_{w∈𝔖_{n}: fix(w)=k} F_{n,DEX(w)}(x) t^{exc(w)} = h_{k}(x) [z^{n−k}] \frac{1 − t}{H(x; tz) − tH(x; z)}

= h_{k}(x) ∑_{λ⊢n−k} R_{λ}(t)s_{λ}(x).

Taking stable principal specialization, we get

\frac{A_{n,k}(q, t)}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})} = \frac{1}{(1 − q) ⋯ (1 − q^{k})} ∑_{λ⊢n−k} R_{λ}(t)\frac{f^{λ}(q)}{(1 − q) ⋯ (1 − q^{n−k})}.

Finally, we solve for A_{n,k}(q, t) and specialize to p = 1 the expression already obtained for the sum ∑_{λ⊢n−k} R_{λ}(t)f^{λ}(p, q) in the proof of Theorem 2.15 and the proof follows. □

For other instances of the use of symmetric functions in γ-positivity, see the proof of Theorem 2.42 in [64] and [66, Section 4].

5. Generalizations

This section discusses three possible generalizations of γ-positivity, namely nonsymmetric γ-positivity, equivariant γ-positivity and q-γ-positivity, which may provide interesting directions for future research.

5.1. Nonsymmetric γ-positivity. Nonsymmetric polynomials which can be written as a sum of two γ-positive polynomials, whose centers of symmetry differ by 1/2, have appeared in Section 2. We formalize this situation here as follows.

A nonzero polynomial f(x) ∈ ℝ[x] is said to have center (i+j)/2, where i (respectively,

j) is the smallest (respectively, largest) integer k for which the coefficient of x^{k} in f(x) is nonzero. One can verify that, if f(x) has center n/2, then it can be written uniquely as a sum

(137)  f(x) = f_{α}^{+}(x) + f_{α}^{−}(x)

of two symmetric polynomials f_{α}^{+}(x), f_{α}^{−}(x) with centers of symmetry (n − 1)/2 and n/2, respectively. Similarly, f(x) can be written uniquely as a sum

(138)  f(x) = f_{β}^{+}(x) + f_{β}^{−}(x)

of two symmetric polynomials f_{β}^{+}(x), f_{β}^{−}(x) with centers of symmetry (n + 1)/2 and n/2, respectively. We call f(x) left γ-positive (respectively, right γ-positive) if both f_{α}^{+}(x) and f_{α}^{−}(x) (respectively, f_{β}^{+}(x) and f_{β}^{−}(x)) are γ-positive. We leave it to the reader to verify that f(x) is γ-positive if and only if it is both left and right γ-positive. Clearly, every left γ-positive or right γ-positive polynomial is unimodal, with a peak at its center n/2, or at (n ± 1)/2. The derangement polynomials d_{n,r}(x) are left γ-positive by Theorem 2.26, while the left-hand sides of Equations (80) and (81) and h-polynomials of order complexes which triangulate a ball are right γ-positive by Theorems 2.37 and 3.9, respectively. It would be interesting to find other classes of nonsymmetric γ-positive polynomials.

5.2. Equivariant γ-positivity. Let f(t) = ∑_{i} a_{i}t^{i} ∈ ℕ[t] be a γ-positive polynomial. It often happens that a_{i} = dim_{ℂ}(A_{i}) for some non-virtual representations A_{i} of a finite group G (all representations considered in this section are finite dimensional and defined over the field of complex numbers). Then, it is natural to consider the polynomial F (t) := ∑_{i} A_{i}t^{i}, whose coefficients belong to the representation ring of G, as an equivariant analog of f(t) and ask whether

(139)  F (t) = ∑_{i=0}^{⌊n/2⌋} Γ_{i} t^{i}(1 + t)^{n−2i}

for some non-virtual G-representations Γ_{i}, where n/2 is the center of symmetry of f(t). We then say that F (t) is γ-positive. For the symmetric group 𝔖_{n}, this concept reduces, via the Frobenius characteristic map, to that of Schur γ-positivity [114, Section 3].

Especially interesting is the case where f(t) is the h-polynomial of a flag triangulation of the sphere, or the local h-polynomial of a flag triangulation of the simplex, as pointed out by Shareshian and Wachs [114, Sections 5–6]. The following general discussion assumes familiarity with face rings of simplicial complexes [126, Chapter II] and local face modules of triangulations of simplices [123, Section 4] [126, Section III.10] and avoids technicalities:

• Let Δ be a flag triangulation of the (n − 1)-dimensional sphere, on which a finite group G acts simplicially. Suppose that Θ is a linear system of parameters for the face ring ℂ[Δ] such that the linear span of the elements of Θ is G-invariant. Then G acts on each homogeneous component of the graded vector space

(140)  ℂ(Δ) := ℂ[Δ]/⟨Θ⟩ = ⨁_{i=0}^{n} ℂ(Δ)_{i},

whose graded dimension is equal to the h-vector of Δ. The pair (Δ, G) exhibits the equivariant Gal phenomenon if there exists Θ for which ∑_{i=0}^{n} ℂ(Δ)_{i} t^{i} is γ-positive.

• Let Γ be a flag triangulation of the (n − 1)-dimensional simplex 2^{V}, on which a subgroup G of the automorphism group of 2^{V} acts simplicially. Suppose that Θ is a special linear system of parameters, in the sense of [123, Definition 4.2], for the face ring of Γ such that the linear span of the elements of Θ is G-invariant. Then G acts on each homogeneous component of the local face module

(141)  L_{V} (Γ) = ⨁_{i=0}^{n} L_{V} (Γ)_{i}

defined by Θ, whose graded dimension is equal to the local h-vector of Γ. The pair (Γ, G) exhibits the local equivariant Gal phenomenon if there exists Θ for which ∑_{i=0}^{n} L_{V} (Γ)_{i} t^{i} is γ-positive.

When Δ is the boundary complex of an n-dimensional simplicial polytope (more generally, the simplicial complex associated to a complete simplicial fan in ℝ^{n}), there exists Θ for which (140) is isomorphic to the cohomology ring of the projective toric variety associated to Δ, as a graded G-representation [43, Section 10]. Shareshian and Wachs [114, Section 5] speculate that, in interesting situations (but not in general) in which Δ is flag, the pair (Δ, G) exhibits the equivariant Gal phenomenon for such linear system of parameters. For example, as pointed out by these authors, and in view of results of C. Procesi [103] and R. Stanley [122, Proposition 12] [123, Proposition 4.20], the Schur γ-positivity of the coefficient of z^{n} in the left-hand sides of Equations (82) and (83), already discussed in Section 2.5, are instances of the equivariant Gal phenomenon and its local analog, with corresponding flag triangulations the barycentric subdivisions of the boundary of the (n − 1)-dimensional simplex and the simplex itself. Another instance of the equivariant Gal phenomenon is the Schur γ-positivity of the coefficient of z^{n} in

(142)  \frac{(1 − t)H(x; z)H(x; tz)}{H(x; tz) − tH(x; z)},

established in [114, Theorem 3.4], with corresponding flag triangulation the boundary complex of the n-dimensional simplicial stellohedron. This result provides an equivariant analog for the γ-positivity of the binomial Eulerian polynomials, discussed in Section 2.1.

A very interesting example is the Coxeter complex Cox(W), discussed in Section 3.3.2, on which the finite Coxeter group W acts. When W is crystallographic, its representation on the cohomology of the projective toric variety associated to Cox(W) was studied by C. Procesi [103], R. Stanley [122, p. 529], I. Dolgachev and V. Lunts [49], J. Stembridge [132], G. Lehrer [78] and A. Stapledon [128, Section 8]. Given the evidence provided in the sequel, it is expected that the following conjectural equivariant analog of Theorem 2.8 can be shown using the classification of finite Coxeter groups (a proof which does not use the classification is certainly more desirable).

Conjecture 5.1. The pair (Cox(W), W) exhibits the equivariant Gal phenomenon for every finite crystallographic Coxeter group W.

As mentioned earlier, in the symmetric group case the conjecture follows from the γpositivity of the polynomials P_{λ}(t), shown in Corollary 2.41. In the case of the hyperoctahedral group B_{n}, by [49, Theorem 6.3] or [132, Theorem 7.6], the Frobenius characteristic of the graded B_{n}-representation on the (even degree) cohomology of the projective toric variety associated to Cox(B_{n}) is equal to the coefficient of z^{n} in

(143)  \frac{(1 − t)H(x; z)H(x; tz)}{H(x, y; tz) − tH(x, y; z)},

where y = (y_{1}, y_{2}, …) is another sequence of commuting independent indeterminates and H(x, y; z) = ∑_{n≥0} h_{n}(x, y)z^{n} = H(x; z)H(y; z) is the generating function of the complete homogeneous symmetric functions h_{n}(x, y) in the variable z. Thus, Conjecture 5.1 in this case is implied by the following result (the proof, which uses Theorem 5.3 stated in the sequel, will appear in the final version of [9] or elsewhere).

Proposition 5.2. The coefficient of z^{n} in (143) is Schur γ-positive for every n ∈ ℕ.

For example, writing

\frac{(1 − t)H(x; z)H(x; tz)}{H(x, y; tz) − tH(x, y; z)} = 1 + ∑_{n≥1} z^{n} ∑_{i=0}^{⌊n/2⌋} γ_{n,i}^{B}(x, y) t^{i}(1 + t)^{n−2i},

we have

γ_{1,0}^{B}(x, y) = s_{(1)}(x),
γ_{2,0}^{B}(x, y) = s_{(2)}(x),
γ_{2,1}^{B}(x, y) = s_{(1,1)}(x) + s_{(1)}(x)s_{(1)}(y) + s_{(2)}(y),
γ_{3,0}^{B}(x, y) = s_{(3)}(x),
γ_{3,1}^{B}(x, y) = 2s_{(2,1)}(x) + s_{(1,1)}(x)s_{(1)}(y) + 2s_{(2)}(x)s_{(1)}(y) + 2s_{(1)}(x)s_{(2)}(y) + s_{(3)}(y).

At present, a combinatorial interpretation of the coefficients of the functions γ_{n,i}^{B}(x, y) in the Schur basis is lacking.

Other evidence for the validity of Conjecture 5.1 is provided by the computation of the graded multiplicity of the trivial [132, Section 3] and of the sign [78, Theorem 3.5 (iii)] and reflection representation [78, Section 4] of W in the cohomology of the toric variety associated to Cox(W); see also [128, Remark 8.3].

A general result on equivariant (nonsymmetric) γ-positivity is the following equivariant version of Theorem 2.37. Let P be a finite graded poset, as in Section 2.4, and assume that a finite group G acts on P by order preserving bijections. Then G defines a permutation representation α_{P}(S), induced by its action on the set of maximal chains of the rankselected subposet P_{S}, for every S ⊆ [n]. One can consider the virtual G-representation

(144)  β_{P}(S) = ∑_{T ⊆S}(−1)^{|S−T |} α_{P}(T),

introduced by Stanley [121]. When P is Cohen–Macaulay over ℂ, β_{P}(S) coincides with the non-virtual G-representation induced on the top homology group of P̄_{S} (see [121] [140, Section 3.4]); the dimensions of α_{P}(S) and β_{P}(S) are equal to the numerical invariants a_{P}(S) and b_{P}(S), respectively, defined in Section 2.4.

Theorem 5.3 (Athanasiadis [9, Theorem 1.2]). Let G be a finite group acting on a finite bounded graded poset P of rank n + 1 by order preserving bijections. If P is Cohen– Macaulay over ℂ, then

(145) H̃_{n−1}((P^{−} ∗ T_{t,n})_{−}; ℂ) ≅_{G} ∑_{S∈Stab([n−1])} β_{P}([n]∖S) t^{|S|}(1 + t)^{n−2|S|}

+ ∑_{S∈Stab([n−2])} β_{P}([n − 1]∖S) t^{|S|+1}(1 + t)^{n−1−2|S|}

and

(146) H̃_{n−1}(P̄ ∗ T_{t,n−1}; ℂ) ≅_{G} ∑_{S∈Stab([2,n−2])} β_{P}([n − 1]∖S) t^{|S|+1}(1 + t)^{n−2−2|S|}

+ ∑_{S∈Stab([2,n−1])} β_{P}([n]∖S) t^{|S|}(1 + t)^{n−1−2|S|}

for every positive integer t, where ≅_{G} denotes isomorphism of G-representations.

In particular, the left-hand sides of (145) and (146) are right γ-positive.

As shown in [9, Corollary 4.1], the Schur γ-positivity of the coefficients of the left-hand sides of Equations (86) and (87) follows from the special case of Theorem 5.3 in which P^{−} is the Boolean lattice of subsets of [n]. Two more applications, establishing the Schur γ-positivity of the coefficients of two close relatives to (143), are given in [9, Section 4]. We state these results here in a form similar to that of Gessel’s identities (86)–(89) as follows (a more elementary proof should be possible). For a map w : [n] → ℤ∖{0} we write z_{w} := z_{w(1)}z_{w(2)} ⋯ z_{w(n)}, where z_{w(i)} = x_{w(i)} if w(i) > 0 and z_{w(i)} = y_{w(i)} otherwise, and define Asc_{B}(w) as the set of indices i ∈ [n] such that w(i) >_{r} w(i + 1) in the total order (17), where w(n + 1) := 0.

Theorem 5.4 (cf. [9, Corollaries 4.4 and 4.7]). We have

(147) \frac{(1 − t)E(x; z)E(x; tz)E(y; tz)}{E(x, y; tz) − tE(x, y; z)} = 1 + ∑_{n≥1} z^{n} ∑_{w} t^{asc(w)}(1 + t)^{n+1−2asc(w)} z_{w}

+ ∑_{n≥1} z^{n} ∑_{w} t^{asc(w)}(1 + t)^{n−2asc(w)} z_{w},

where, in the two sums, w : [n] → ℤ∖{0} runs through all maps for which Asc_{B}(w) ∈ Stab([n]) contains (respectively, does not contain) n, and

(148)  \frac{(1 − t)E(x; z)}{E(x, y; tz) − tE(x, y; z)} = 1 + ∑_{n≥1} z^{n} ∑_{w} t^{asc(w)}(1 + t)^{n−2asc(w)} z_{w}

+ ∑_{n≥1} z^{n} ∑_{w} t^{asc(w)}(1 + t)^{n−1−2asc(w)} z_{w},

where, in the two sums, w : [n] → ℤ∖{0} runs through all maps for which Asc_{B}(w) ∈ Stab([2, n]) contains (respectively, does not contain) n.

5.3. q-γ-positivity. Let a, b ∈ ℕ. A polynomial f(q, x) ∈ ℝ[q, x] is called q-γ-positive of type (a, b) if

(149)  f(q, x) = ∑_{i=0}^{⌊n/2⌋} γ_{i}(q) x^{i} ∏_{k=i}^{n−1−i}(1 + xq^{ka+b})

for some polynomials γ_{i}(q) ∈ ℝ[q] with nonnegative coefficients. This concept, which reduces to that of γ-positivity for q = 1, was formally introduced by K. Dilks [47, Chapter 4] and, in more restrictive form, by C. Krattenthaler and M. Wachs (unpublished), after such expansions were found for certain q-analogs of the Eulerian polynomials for symmetric and hyperoctahedral groups by G. Han, F. Jouhet and J. Zeng [70]. Other polynomials which admit q-analogs which are q-γ-positive include binomials and Narayana polynomials for symmetric and hyperoctahedral groups; see [47, Chapter 4].

Acknowledgements. The author wishes to thank Francesco Brenti, Persi Diaconis, Satoshi Murai, Kyle Petersen, Richard Stanley, John Stembridge, Vasu Tewari and Jiang Zeng for useful comments and information and the SLC organizers Christian Krattenthaler, Volker Strehl and Jean-Yves Thibon for their invitation.

Note added in revision. Conjecture 2.30 has been proven by P. Brändén and L. Solus [28, Section 3.3] and, independently, by N. Gustafsson and L. Solus [69, Section 5.1].

References

[1] R.M. Adin, C.A. Athanasiadis, S. Elizalde and Y. Roichman, Character formulas and descents for the hyperoctahedral group, Adv. Appl. Math. 87 (2017), 128–169.

[2] N. Aisbett, Frankl–Füredi–Kalai inequalities for the γ-vectors of flag nestohedra, Discrete Comput. Geom. 51 (2014), 323–336.

[3] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202 (2009), no. 949.

[4] C.A. Athanasiadis, Some combinatorial properties of flag simplicial pseudomanifolds and spheres, Ark. Mat. 49 (2011), 17–29.

[5] C.A. Athanasiadis, Flag subdivisions and γ-vectors, Pacific J. Math. 259 (2012), 257–278.

[6] C.A. Athanasiadis, Edgewise subdivisions, local h-polynomials and excedances in the wreath product ℤ_{r} ≀ 𝔖_{n}, SIAM J. Discrete Math. 28 (2014), 1479–1492.

[7] C.A. Athanasiadis, A survey of subdivisions and local h-vectors, in The Mathematical Legacy of Richard P. Stanley (P. Hersh, T. Lam, P. Pylyavskyy, V. Reiner, eds.), Amer. Math. Society, Providence, R.I., 2016, pp. 39–51.

[8] C.A. Athanasiadis, The local h-polynomial of the edgewise subdivision of the simplex, Bull. Hellenic Math. Soc. (N.S.) 60 (2016), 11–19.

[9] C.A. Athanasiadis, Some applications of Rees products of posets to equivariant gamma-positivity,

arXiv:1707.08297.

[10] C.A. Athanasiadis and C. Savvidou, The local h-vector of the cluster subdivision of a simplex, Sém. Lothar. Combin. 66 (2012), Article B66c, 21 pp. (electronic).

[11] E. Bagno and R. Biagioli, Colored descent representations for complex reflection groups, Israel J. Math. 160 (2007), 317–347.

[12] E. Bagno and D. Garber, On the excedance number of colored permutation groups, Sém. Lothar. Combin. 53 (2006), Article B53f, 17 pp. (electronic).

[13] M. Barnabei, F. Bonetti and M. Silimbani, The descent statistic in involutions is not log-concave, European J. Combin. 30 (2009), 11–16.

[14] R. Barnard and N. Reading, Coxeter-biCatalan combinatorics, J. Algebr. Combin. 47 (2018), 241– 300.

[15] D. Barnette, A proof of the lower bound conjecture for convex polytopes, Pacific J. Math. 46 (1973), 349–354.

[16] D. Bessis, The dual braid monoid, Ann. Sci. Ecole Norm. Sup. 36 (2003), 647–683.

[17] S.C. Billey and P.R.W. McNamara, The contributions of Stanley to the fabric of symmetric and quasisymmetric functions, in The Mathematical Legacy of Richard P. Stanley (P. Hersh, T. Lam, P. Pylyavskyy, V. Reiner, eds.), Amer. Math. Society, Providence, R.I., 2016, pp. 83–104.

[18] A. Björner, Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings, Adv. Math. 52 (1984), 173–212.

[19] 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.

[20] A. Björner and F. Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics 231, Springer, 2005.

[21] A. Björner and V. Welker, Segre and Rees products of posets, with ring-theoretic applications, J. Pure Appl. Algebra 198 (2005), 43–55.

[22] S. Blanco and T.K. Petersen, Counting Dyck paths by area and rank, Ann. Combin. 18 (2014), 171–197.

[23] T. Brady and C. Watt, K(π, 1)’s for Artin groups of finite type, in Proceedings of the Conference on Geometric and Combinatorial group theory, Part I (Haifa 2000), Geom. Dedicata 94 (2002), 225–250.

[24] P. Brändén, Sign-graded posets, unimodality of W -polynomials and the Charney-Davis conjecture, in Stanley Festschrift (B.E. Sagan, ed.), Electron. J. Combin. 11 (2004), no. 2, Research Paper 9, 15 pp. (electronic).

[25] P. Brändén, Counterexamples to the Neggers-Stanley conjecture, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 155–158 (electronic).

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

[27] P. Brändén, Unimodality, log-concavity, real-rootedness and beyond, in Handbook of Combinatorics (M. Bona, ed.), CRC Press, 2015, pp. 437–483.

[28] P. Brändén and L. Solus, Symmetric decompositions and real-rootedness, arXiv:1808.04141.

[29] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc., no. 413, 1989.

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

[31] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994), 417–441.

[32] F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics and geometry: an update, in Jerusalem Combinatorics ’93 (H. Barcelo and G. Kalai, eds.), Contemp. Math. 178, Amer. Math. Society, Providence, R.I., 1994, pp. 71–89.

[33] F. Brenti and V. Welker, f-Vectors of barycentric subdivisions, Math. Z. 259 (2008), 849–865.

[34] F. Brenti and V. Welker, The Veronese construction for formal power series and graded algebras, Adv. Appl. Math. 42 (2009), 545–556.

[35] M. Brun and T. Römer, Subdivisions of toric complexes, J. Algebr. Combin. 21 (2005), 423–448.

[36] V.M. Buchstaber and T.E. Panov, Toric Topology, Mathematical Surveys and Monographs 204, Amer. Math. Society, 2015.

[37] R. Charney and M. Davis, The Euler characteristic of a nonpositively curved, piecewise Euclidean manifold, Pacific J. Math. 171 (1995), 117–137.

[38] 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, 16 pp. (electronic).

[39] C.-O. Chow, On certain combinatorial expansions of the Eulerian polynomials, Adv. Appl. Math. 41 (2008), 133–157.

[40] C.-O. Chow, On derangement polynomials of type B. II, J. Combin. Theory Ser. A 116 (2009), 816–830.

[41] C.-O. Chow and T. Mansour, Counting derangements, involutions and unimodal elements in the wreath product C_{r} ≀ 𝔖_{n}, Israel J. Math. 179 (2010), 425–448.

[42] F. Chung, R. Graham and D. Knuth, A symmetrical Eulerian identity, J. Combin. 1 (2010), 29–38.

[43] V.I. Danilov, The geometry of toric varieties, Russian Math. Surveys 33 (1978), 97–154; translated from Uspekhi Mat. Nauk. 33 (1978), 85–134.

[44] M. Davis and B. Okun, Vanishing theorems and conjectures for the L^{2}-homology of right-angled Coxeter groups, Geom. Topol. 5 (2001), 7–74.

[45] J.A. De Loera, J. Rambau and F. Santos, Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics 25, Springer, 2010.

[46] J. Désarménien and D. Foata, Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France 113 (1985), 3–22.

[47] K. Dilks, Involutions on Baxter objects, and q-gamma nonnegativity, Ph.D. thesis, University of Minnesota, 2015.

[48] K. Dilks, T.K. Petersen and J.R. Stembridge, Affine descents and the Steinberg torus, Adv. Appl. Math. 42 (2009), 423–444.

[49] I. Dolgachev and V. Lunts, A character formula for the representation of a Weyl in the cohomology of the associated toric variety, J. Algebra 168 (1994), 741–772.

[50] Ö. Eğecioğlu and J.B. Remmel, Bijections for Cayley trees, spanning trees, and their q-analogues, J. Combin. Theory Ser. A 42 (1986), 15–30.

[51] R. Ehrenborg and K. Karu, Decomposition theorem for the cd-index of Gorenstein* posets, J. Algebr. Combin. 26 (2007), 225–251.

[52] E.-M. Feichtner and B. Sturmfels, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.) 62 (2005), 437–468.

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

[54] D. Foata and G.-N. Han, The decrease value theorem with an application to permutation statistics, Adv. Appl. Math. 46 (2011), 296–311.

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

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

[57] 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.

[58] D. Foata and V. Strehl, Euler numbers and variations of permutations, in Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I, Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 119–131.

[59] 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, R.I., 2007.

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

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

[62] V. Gasharov, On the Neggers–Stanley conjecture and the Eulerian polynomials, J. Combin. Theory Ser. A 82 (1998), 134–146.

[63] I.M. Gessel, Counting forests by descents and leaves, Electron. J. Combin. 3(2) (1996), Research Paper 8, 5 pp. (electronic).

[64] I.M. Gessel, S. Griffin and V. Tewari, Labeled plane binary trees and Schur-positivity,

arXiv:1706.03055.

[65] I.M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), 189–215.

[66] R.S. González D’León, A note on the γ-coefficients of the tree Eulerian polynomial, Electron. J. Combin. 23 (2016), Research Paper 1.20, 13 pp. (electronic).

[67] M.A. Gorsky, Proof of Gal’s conjecture for the D series of generalized associahedra, Russian Math. Surveys 65 (2010), 1178–1180.

[68] V.W.J. Guo and J. Zeng, The Eulerian distribution on involutions is indeed unimodal, J. Combin. Theory Ser. A 113 (2006), 1061–1071.

[69] N. Gustafsson and L. Solus, Derangements, Ehrhart theory and local h-polynomials,

arXiv:1807.05246.

[70] G. Han, F. Jouhet and J. Zeng, Two new triangles of q-integers via q-Eulerian polynomials of type A and B, Ramanujan J. 31 (2013), 115–127.

[71] A. Hultman, The combinatorics of twisted involutions in Coxeter groups, Trans. Amer. Math. Soc. 359 (2007), 2787–2798.

[72] I.M. Isaacs, Character Theory of Finite Groups, Pure and Applied Mathematics, Academic Press, 1976.

[73] M. Juhnke-Kubitzke, S. Murai and R. Sieg, Local h-vectors of quasi-geometric and barycentric subdivisions, Discrete Comput. Geom. (to appear).

[74] K. Karu, The cd-index of fans and posets, Compos. Math. 142 (2006), 701–718.

[75] E. Katz and A. Slapledon, Local h-polynomials, invariants of subdivisions and mixed Ehrhart theory, Adv. Math. 286 (2016), 181–239.

[76] V. Klee, A combinatorial analogue of Poincaré’s duality theorem, Canad. J. Math. 16 (1964), 517– 531.

[77] D. Kozlov, Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics 21, Springer, 2008.

[78] G.I. Lehrer, Rational points and Coxeter group actions on the cohomology of toric varieties, Ann. Inst. Fourier (Grenoble) 58 (2008), 671–688.

[79] Z. Lin, Eulerian calculus arising from permutation statistics, Doctoral Dissertation, Université Claude Bernard-Lyon 1, 2014.

[80] Z. Lin, Proof of Gessel’s γ-positivity conjecture, Electron. J. Combin. 23 (2016), Research Paper 3.15, 9 pp. (electronic).

[81] Z. Lin, On γ-positive polynomials arising in pattern avoidance, Adv. Appl. Math. 82 (2017), 1–22.

[82] Z. Lin and S. Fu, On 1212-avoiding restricted growth functions, Electron. J. Combin. 24 (2017), Research Paper 1.53, 20 pp. (electronic).

[83] Z. Lin and J. Zeng, The γ-positivity of basic Eulerian polynomials via group actions, J. Combin. Theory Ser. A 135 (2015), 112–129.

[84] S. Linusson, J. Shareshian and M.L. Wachs, Rees products and lexicographic shellability, J. Combin. 3 (2012), 243–276.

[85] A. Mendes and J. Remmel, Counting with Symmetric Functions, Developments in Mathematics 43, Springer, 2015.

[86] P. Mongelli, Excedances in classical and affine Weyl groups, J. Combin. Theory Ser. A 120 (2013), 1216–1234.

[87] V-D.P. Moustakas, The Eulerian distribution on the involutions of the hyperoctahedral group (in Greek), Master Thesis, University of Athens, 2017.

[88] H. Mühle, Symmetric decompositions and the strong Sperner property for noncrossing partition lattices, J. Algebr. Combin. 45 (2017), 745–775.

[89] J. Neggers, Representations of finite partially ordered sets, J. Combin. Inform. Syst. Sci. 3 (1978), 113–133.

[90] E. Nevo, Remarks on missing faces and generalized lower bounds on face numbers, Electron. J. Combin. 16 (2009), no. 2, Research Paper 8, 11 pp. (electronic).

[91] E. Nevo and T.K. Petersen, On gamma vectors satisfying the Kruskal–Katona inequalities, Discrete Comput. Geom. 45 (2011), 503–521.

[92] E. Nevo, T.K. Petersen and B.E. Tenner, The gamma-vector of a barycentric subdivision, J. Combin. Theory Ser. A 118 (2011), 1364–1380.

[93] B. Nill and J. Schepers, Combinatorial questions related to stringy E-polynomials of Gorenstein polytopes, in Toric Geometry (K. Altmann et al., eds.), Oberwolfach Reports (2012), no. 21, pp. 62– 64.

[94] T.K. Petersen, Enriched P -partitions and peak algebras, Adv. Math. 209 (2007), 561–610.

[95] T.K. Petersen, On the shard intersection order of a Coxeter group, SIAM J. Discrete Math. 27 (2013), 1880–1912.

[96] T.K. Petersen, Two-sided Eulerian numbers via balls in boxes, Math. Mag. 86 (2013), 159–176.

[97] T.K. Petersen, Eulerian Numbers, Birkhäuser Advanced Texts, Birkhäuser, 2015.

[98] T.K. Petersen, A two-sided analogue of the Coxeter complex, arXiv:1607.00086.

[99] S. Poirier, Cycle type and descent set in wreath products, Discrete Math. 180 (1998), 315–343.

[100] A. Postnikov, Intransitive trees, J. Combin. Theory Ser. A 79 (1997), 360–366.

[101] A. Postnikov, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. 2009 (2009), 1026– 1106.

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

[103] C. Procesi, The toric variety associated to Weyl chambers, in Mots (M. Lothaire, ed.), Hermés, Paris, 1990, pp. 153–161.

[104] V. Reiner and V. Welker, On the Charney–Davis and Neggers–Stanley conjectures, J. Combin. Theory Ser. A 109 (2005), 247–280.

[105] G. Reisner, Cohen–Macaulay quotients of polynomial rings, Adv. Math. 21 (1976), 30–49.

[106] Y. Roichman, A note on the number of k-roots in S_{n}, Sém. Lothar. Combin. 70 (2014), Article B70i, 5 pp. (electronic).

[107] C.D. Savage and M. Visontai, The s-Eulerian polynomials have only real roots, Trans. Amer. Math. Soc. 367 (2015), 763–788.

[108] C. Savvidou, Barycentric subdivisions, clusters and permutation enumeration (in Greek), Doctoral Dissertation, University of Athens, 2013.

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

[110] J. Shareshian and M.L. Wachs, Poset homology of Rees products and q-Eulerian polynomials, Electron. J. Combin. 16 (2) (2009), Research Paper 20, 29 pp. (electronic).

[111] J. Shareshian and M.L. Wachs, Eulerian quasisymmetric functions, Adv. Math. 225 (2010), 2921– 2966.

[112] J. Shareshian and M.L. Wachs, Chromatic quasisymmetric functions, Adv. Math. 295 (2016), 497– 551.

[113] J. Shareshian and M.L. Wachs, From poset topology to q-Eulerian polynomials to Stanley’s chromatic symmetric functions, in The Mathematical Legacy of Richard P. Stanley (P. Hersh, T. Lam, P. Pylyavskyy and V. Reiner, eds.), pp. 301–321, Amer. Math. Society, Providence, R.I., 2016.

[114] J. Shareshian and M.L. Wachs, Gamma-positivity of variations of Eulerian polynomials,

    arXiv:1702.06666v3.

[115] H. Shin and J. Zeng, The symmetric and unimodal expansion of Eulerian polynomials via continued fractions, European J. Combin. 33 (2012), 111–127.

[116] H. Shin and J. Zeng, Symmetric unimodal expansions of excedances in colored permutations, European J. Combin. 52 (2016), 174–196.

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

[118] R.P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc., no. 119, 1972.

[119] R.P. Stanley, The Upper Bound Conjecture and Cohen–Macaulay rings, Studies in Appl. Math. 54 (1975), 135–142.

[120] R.P. Stanley, The number of faces of a simplicial convex polytope, Adv. Math. 35 (1980), 236–238.

[121] R.P. Stanley, Some aspects of groups acting on finite posets, J. Combin. Theory Ser. A 32 (1982), 132–161.

[122] R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, in Graph Theory and its Applications: East and West, Annals of the New York Academy of Sciences 576, New York Acad. Sci., New York, 1989, pp. 500–535.

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

[124] R.P. Stanley, Flag f-vectors and the cd–index, Math. Z. 216 (1994), 483–499.

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

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

[127] R.P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, second edition, Cambridge, 2011.

[128] A. Stapledon, Equivariant Ehrhart theory, Adv. Math. 226 (2011), 3622–3654.

[129] E. Steingrímsson, Permutation statistics of indexed and poset permutations, Ph.D. thesis, MIT, 1992.

[130] E. Steingrímsson, Permutation statistics of indexed permutations, European J. Combin. 15 (1994), 187–205.

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

[132] J.R. Stembridge, Some permutation representations of Weyl groups associated with the cohomology of toric varieties, Adv. Math. 106 (1994), 244–301.

[133] J.R. Stembridge, Enriched P -partitions, Trans. Amer. Math. Soc. 349 (1997), 763–788.

[134] J.R. Stembridge, Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge, Trans. Amer. Math. Soc. 359 (2007), 1115–1128.

[135] J.R. Stembridge, Coxeter cones and their h-vectors, Adv. Math. 217 (2008), 1935–1961.

[136] V. Strehl, Symmetric Eulerian distributions for involutions, Sém. Lothar. Combin. 1 (1980), 1 pp.

[137] H. Sun and Y. Wang, A group action on derangements, Electron. J. Combin. 21 (2014), Research Paper 1.67, 5 pp. (electronic).

[138] V. Tewari, personal communication, October 2017.

[139] V.D. Volodin, Cubical realizations of flag nestohedra and a proof of Gal’s conjecture for them, Uspekhi Mat. Nauk. 65 (2010), 188–190.

[140] M. Wachs, Poset Topology: Tools and Applications, in Geometric Combinatorics (E. Miller, V. Reiner and B. Sturmfels, eds.), IAS/Park City Mathematics Series 13, pp. 497–615, Amer. Math. Society, Providence, R.I., 2007.

[141] A. Zelevinsky, Nested complexes and their polyhedral realizations, Pure Appl. Math. Quart. 2 (2006), 655–671.

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

Department of Mathematics, National and Kapodistrian University of Athens, Panepistimioupolis, 15784 Athens, Greece

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