CHROMATIC QUASISYMMETRIC FUNCTIONS AND
HESSENBERG VARIETIESJOHN SHARESHIAN1 AND MICHELLE L. WACHS2
Abstract. We discuss three distinct topics of independent interest; one in enumerative combinatorics, one in symmetric function
theory, and one in algebraic geometry. The topic in enumerative
combinatorics concerns a q-analog of a generalization of the Eulerian polynomials, the one in symmetric function theory deals witha refinement of the chromatic symmetric functions of Stanley, andthe one in algebraic geometry deals with Tymoczko’s representation of the symmetric group on the cohomology of the regularsemisimple Hessenberg variety of type A. Our purpose is to explore
some remarkable connections between these topics.

Contents
1. Introduction
2. q-Eulerian numbers and toric varieties
3. Rawlings major index and generalized Eulerian numbers
4. Chromatic quasisymmetric functions
5. Hessenberg varieties
Acknowledgments
References

1
7
12
16
23
25
26

1. Introductionn
Let H(z) :=n≥0 hn z , where hn is the complete homogeneous
symmetric function of degree n. The formal power series

P

(1.1)

(1 − t)H(z),H(tz) − tH(z)has occurred in various contexts in the literature, including• the study of a class of q-Eulerian polynomials
Date: June. 11, 2011; version April 1, 2012.
1
Supported in part by NSF Grant DMS 0902142.
2
Supported in part by NSF Grant DMS 0902323.
1

2

SHARESHIAN AND WACHS• the enumeration of Smirnov words by descent number• the study of the toric variety associated with the Coxeter complex of the symmetric group.
We briefly describe these contexts now and give more detail in Section 2 with definitions in Section 1.1. In [ShWa1, ShWa2] Shareshianand Wachs initiated a study of the joint distribution of the Mahonian permutation statistic, major index, and the Eulerian permutation
statistic, excedance number. They showed that the q-Eulerian polynomial defined byX
q maj(σ) texc(σ)σ∈Sn

can be obtained by taking a certain specialization of the coefficient ofz n in (1.1) known as the stable principal specialization. This enabled
them to derive the q-analog of a formula of Euler that is given in (2.9).
The work in [ShWa1] led Stanley to derive a refinement of a formulaof Carlitz, Scoville and Vaughan [CaScVa] for the enumerator of words
over the alphabet P with no adjacent repeats (see [ShWa2]). These
are known as Smirnov words. In Stanley’s refinement the Smirnov
words are enumerated according to their number of descents and theenumerator is equal to the symmetric function obtained by applying
the standard involution ω on the ring of symmetric functions to (1.1).
In another direction, Stanley [St2, Proposition 7.7] used a formulaof Procesi [Pr] to show that (1.1) is the generating function for the
Frobenius characteristic of the representation of the symmetric group
Sn on the cohomology of the toric variety associated with the Coxeter
complex of type An−1 .
The q-Eulerian polynomial, the Smirnov word enumerator, and the
Sn -representation on the cohomology of the toric variety all have very
nice generalizations. In this paper we discuss these generalizations andexplore the relationships among these generalizations and the ramifications of the relationships. The proofs of the results surveyed here
either have appeared in [ShWa2] or will appear in [ShWa4].
The generalization of the q-Eulerian numbers, as defined in [ShWa4],
is obtained by considering the joint distribution of a Mahonian statisticof Rawlings [Ra] that interpolates between inversion number and majorindex, and a generalized Eulerian statistic of De Mari and Shayman[DeSh]. We discuss these generalized q-Eulerian numbers and a moregeneral version of them associated with posets in Section 3.
The generalization of the Smirnov word enumerator, as defined in[ShWa4], is a refinement of Stanley’s well known chromatic symmetric function [St6], which we call a chromatic quasisymmetric function.

CHROMATIC QUASISYMMETRIC FUNCTIONS

3

In Section 3 we report on results on the chromatic quasisymmetricfunctions, which are proved in [ShWa4]. In particular we present a refinement of Gasharov’s [Ga] expansion of certain chromatic symmetricfunctions in the Schur basis and a refinement of Chow’s [Ch] expansion
in the basis of fundamental quasisymmetric functions. We also present
a conjectured refinement of Stanley’s [St5] expansion in the power-sum
basis and a refinement of the conjecture of Stanley and Stembridge (see[StSte, Conjecture 5.5] and [St5, Conjecture 5.1]) on e-positivity.
The generalization of the toric variety associated with the type A
Coxeter complex is the regular semisimple Hessenberg variety of type
A first studied by De Mari and Shayman [DeSh] and further studied
by De Mari, Procesi and Shayman [DePrSh]. Tymoczko [Ty3] defined a representation of the symmetric group on the cohomology ofthis Hessenberg variety, which generalizes the representation studied
by Procesi and Stanley. This generalization is described in more detailin Section 5.
In Section 4 we present the following extension of the relation between q-Eulerian polynomials and Smirnov words. As noted above, we
can associate to a finite poset P a generalized q-Eulerian polynomial,
which will be denoted by AP (q, t). Let XG (x, t) denote the chromatic
quasisymmetric function of a graph G.
Theorem 1.1 (Corollary 4.18). Let G be the incomparability graph ofa poset P on [n]. Then
AP (q, t) = (q; q)n ps(ωXG (x, t)),where ps denotes stable principal specialization.
In Section 5 we discuss the following conjectured generalization ofrelationship between Smirnov words and the representation of the symmetric group on the cohomology of the toric variety.
Conjecture 1.2 (Conjecture 5.3). Let G be the incomparability graphof a natural unit interval order P . Then
|E(G)|ωXG (x, t) =X

chH 2j (H(P ))tj ,j=0

where ch denotes the Frobenius characteristic and H 2j (H(P )) denotes
Tymoczko’s representation of Sn on the degree 2j cohomology of the
Hessenberg variety H(P ) associated with P .
This conjecture has the potential of providing solutions to several
open problems such as,

4

SHARESHIAN AND WACHS(1) Our conjecture that the generalized q-Eulerian polynomials are
unimodal (Conjecture 3.3). This would follow from Theorem 1.1
and the hard Lefschetz theorem applied to Tymoczko’s representation on the cohomology of the Hessenberg variety.
(2) Tymoczko’s problem of finding a decomposition of her representation into irreducibles [Ty3]. Such a decomposition would
be provided by the expansion of the chromatic quasisymmetricfunctions in the Schur function basis given in Theorem 4.13.
(3) Stanley and Stembridge’s well-known conjecture that the chromatic symmetric functions (for unit interval orders) are e-positive[StSte, St5]. This would be equivalent to Conjecture 5.4 that
Tymoczko’s representation is a permutation representation inwhich each point stabilizer is a Young subgroup.
1.1. Preliminaries. We assume that the reader is familiar with somebasic notions from combinatorics and symmetric function theory. All
terms used but not defined in this paper are defined in [St3] or [St4].
Let σ ∈ Sn , where Sn denotes the symmetric group on [n] :={1, 2, . . . , n}. The excedance number of σ is given byexc(σ) := |{i ∈ [n − 1] : σ(i) > i}|.
The descent set of σ is given by
DES(σ) := {i ∈ [n − 1] : σ(i) > σ(i + 1)}
and the descent number and major index aredes(σ) := |DES(σ)| and maj(σ) :=X

i.

i∈DES(σ)

It is well-known that the permutation statistics exc and des are equidistributed on Sn . The common generating functions for these statistics
are called Eulerian polynomials. That is, the Eulerian polynomials aredefined as
XX
An (t) :=tdes(σ) =texc(σ) .
σ∈Sn

σ∈Sn

Any permutation statistic with generating function An (t) is called an
Eulerian statistic. The Eulerian numbers are the coefficients of theEulerian polynomials; they are defined asan,j := {σ ∈ Sn : des(σ) = j} = {σ ∈ Sn : exc(σ) = j},for 0 ≤ j ≤ n − 1.
It is also well-known that the major index is equidistributed with
the inversion index defined asinv(σ) = |{(i, j) ∈ [n] × [n] : i < j and σ(i) > σ(j)}|CHROMATIC QUASISYMMETRIC FUNCTIONS

5

and thatXq maj(σ) =

σ∈Sn

X

q inv(σ) = [n]q !,

σ∈Sn

where
[n]q := 1 + q + · · · + q n−1 and [n]q ! := [n]q [n − 1]q . . . [1]q .
Any permutation statistic equidistributed with maj and inv is called a
Mahonian permutation statistic.
Let R be a ring with a partial order relation, e.g., Q with its usual
total order. Given a sequence (a0 , a1 , . . . , an ) of elements of R we saythat the sequence is palindromic with center of symmetry n2 if aj = an−jfor 0 ≤ j ≤ n. The sequence is said to be unimodal if
a0 ≤ a1 ≤ · · · ≤ ac ≥ ac+1 ≥ ac+2 ≥ · · · ≥ anfor some c. The sequence is said to be positive if ai ≥ 0 for each i.
We say that the polynomial A(t) := a0 + a1 t + · · · + an tn ∈ R[t] − {0}is positive, palindromic and unimodal with center of symmetry n2 if(a0 , a1 , . . . , an ) has these properties.
Let ΛQ be the ring of symmetric functions in variables x1 , x2 , . . .
with coefficients in Q and let b be any basis for ΛQ . If f is a symmetric function whose expansion in b has nonnegative coefficients, we saythat f is b-positive. This induces a partial order relation on the ring ΛQgiven by f ≤b g if g −f is b-positive. We use this partial order to define
b-unimodality of sequences of symmetric functions in ΛQ and polynomials in ΛQ [t]. Similarly, when we say that a sequence of polynomialsin Q[q1 , . . . , qm ] or a polynomial in Q[q1 , . . . , qm ][t] is unimodal, we areusing the partial order relation on Q[q1 , . . . , qm ] defined by f (q) ≤ g(q)if g(q) − f (q) has nonnegative coefficients.
The bases for ΛQ that are relevant here are the Schur basis (sλ )λ∈Par ,the elementary symmetric function basis (eλ )λ∈Par , the complete homogeneous symmetric function basis (hλ )λ∈Par , and the power-sum symmetric function basis (zλ−1 pλ )λ∈Par , where Par is the set of all integer
partitions,Yzλ :=mi (λ)! imi (λ)
iand mi (λ) is the number of parts of λ equal to i. These are all integral
bases in that every symmetric function in the ring ΛZ of symmetricfunctions over Z is an integral linear combination of the basis elements.
The next two propositions give basic tools for establishing unimodality.

6

SHARESHIAN AND WACHS

Proposition 1.3 (see [St2, Proposition 1]). Let A(t) and B(t) be positive, palindromic and unimodal polynomials in Q[t] with respective centers of symmetry cA and cB . Then
(1) A(t)B(t) is positive, palindromic and unimodal with center ofsymmetry cA + cB .
(2) If cA = cB then A(t) + B(t) is positive, palindromic and unimodal with center of symmetry cA .
Proposition 1.4. Let b := (bλ )λ be a basis for ΛQ . The polynomial f (t) ∈ ΛQ [t] is b-positive, palindromic and b-unimodal with centerof symmetryc if and only if each coefficient aλ (t) in the expansion
Pf (t) = λ aλ (t)bλ is positive, palindromic and unimodal with center ofsymmetry c.
For example, from Proposition 1.3 (1) we see that [n]t ! is positive, palindromic and unimodal with center of symmetry n(n+1). From4
Propositions 1.3 and 1.4 we have that [5]t [2]t h(5,2) + [4]t [3]t h(4,3) is hpositive, palindromic and h-unimodal with center of symmetry 5/2.
Recall that the Frobenius characteristic ch is a ring isomorphismfrom the ring of virtual representations of the symmetric groups to ΛZ .
It takes the irreducible Specht module S λ to the Schur function sλ . Asis customary, we use ω to denote the involution on ΛQ that takes hi to
ei . Recall ω(sλ ) = sλ0 for all λ ∈ Par, where λ0 denotes the conjugate
shape.
For any ring R, let QR be the ring of quasisymmetric functions invariables x1 , x2 , . . . with coefficients in R. For n ∈ P and S ⊆ [n − 1],
let D(S) be the set of all functions f : [n] → P such that• f (i) ≥ f (i + 1) for all i ∈ [n − 1], and• f (i) > f (i + 1) for all i ∈ S.
Recall Gessel’s fundamental quasisymmetric function
Fn,S :=Xxf ,f ∈D(S)

where xf := xf (1) xf (2) · · · . It is straightforward to confirm that Fn,S ∈QZ . In fact (see [St4, Proposition 7.19.1]), {Fn,S : S ⊆ [n − 1]} is abasis for the free Z-module of homogeneous degree n quasisymmetricfunctions with coefficients in Z.
See [St4] for further information on symmetric functions, quasisymmetric functions and representations.

CHROMATIC QUASISYMMETRIC FUNCTIONS

7

2. q-Eulerian numbers and toric varieties
It is well known that the Eulerian numbers (an,0 , an,1 , . . . , an,n−1 )form the h-vector of the Coxeter complex ∆n of the symmetric group
Sn . Danilov and Jurciewicz (see [St2, eq. (26)]) showed that the jthentry of the h-vector of any convex simplicial polytope P is equal todim H 2j (V(P )) where V(P ) is the toric variety associated with P and
H i (V(P )) is the degree i singular cohomology of V(P ) over C. (In odd
degrees cohomology vanishes.) It follows thatan,j = dim H 2j (V(∆n )),(2.1)

for all j = 0, . . . , n − 1.
It is also well known that the Eulerian numbers are palindromic andunimodal. Although there are elementary ways to prove this result,palindromicity and unimodality can be viewed as consequences of thehard Lefschetz theorem applied to the toric variety V(∆n ).
The classical hard Lefschetz theorem states that if V is a projective
smooth variety of complex dimension n then there is a linear operator φon H ∗ (V) sending each H i (V) to H i+2 (V) such that for 0 ≤ i ≤ 2n − 2,
the map φn−i : H i (V) → H 2n−i (V) is a bijection. It follows from thisthat the sequence of even degree Betti numbers and the sequence of odd
degree Betti numbers are palindromic and unimodal. Since V(∆n ) is asmooth variety, it follows that the Eulerian numbers form a palindromic
and unimodal sequence. See [St1, St2] for further information on theuse of the hard Lefschetz theorem in combinatorics.
2.1. Action of the symmetric group. The symmetric group Sn
acts naturally on the Coxeter complex ∆n and this induces a representation of Sn on cohomology of the toric variety V(∆n ). Procesi[Pr] derived a recursive formula for this representation, which Stanley[St2, see Proposition 12] used to obtain the following formula for the
Frobenius characteristic of the representation,
(2.2)

1+

n−1
XX

chH 2j (V(∆n ))tj z n =n≥1 j=0(1 − t)H(z).
H(tz) − tH(z)(See [Ste1, Ste2, DoLu, Le] for related work on this representation.)
This is a symmetric function analog of the classical formula of Euler,
(2.3)

1+

n−1
XX
n≥1 j=0an,j tjzn(1 − t)ez.
= tz
n!
e − tez

An immediate consequence of (2.2) is that chH 2j (V(∆n )) is h-positive,
which is equivalent to saying that the linear representation of Sn on

8

SHARESHIAN AND WACHS

H 2j (V(∆n )) is obtained from an action on some set in which each point
stabilizer is a Young subgroup. Formula (2.2) has a number of additional interesting, but not so obvious, consequences. We discuss someof them below.
Stembridge [Ste1] uses (2.2) to characterize the multiplicity of each
irreducible Sn -module in H 2j (V(∆n )) in terms of marked tableaux. A
marked tableau of shape λ is a semistandard tableau of shape λ withentries in {0, 1, . . . , k} for some k ∈ N, such that each a ∈ [k] occurs atleast twice in the tableau, together with a mark on one occurrence ofeach a ∈ [k]; the marked occurrence cannot be the leftmost occurrence.
The index of a marked a is the number of occurrences of a to the left ofthe marked a. The index of a marked tableau is the sum of the indicesof the marked entries of the tableau.
Theorem 2.1 (Stembridge [Ste1]). Let λ ` n. The multiplicity of theirreducible Specht module S λ in H 2j (V(∆n )) is the number of marked
tableaux of shape λ and index j.
Recently, Shareshian and Wachs [ShWa4] obtained a different formula for the multiplicity of S λ in terms of a different type of tableau(see Corollary 4.14).
The character of H 2j (V(∆n )) can be obtained from the following
expansion in the p-basis.
Theorem 2.2 (Stembridge [Ste1], Dolgachev and Lunts [DoLu]). For
all n ≥ 1,
n−1
X
j=0

chH 2j (V(∆n ))tj =XAl(λ) (t)λ`nY[λi ]t zλ−1 pλ .
i2.2. Expansion in the basis of fundamental quasisymmetricfunctions. In their study of q-Eulerian numbers [ShWa1, ShWa2],
Shareshian and Wachs obtain a formula for the expansion of the righthand side of (2.2) in the basis of fundamental quasisymmetric functions. In order to describe this decomposition the notion of DEX setof a permutation is needed. For n ≥ 1, we set[n] := {1, . . . , n}and totally order the alphabet [n] ∪ [n] by(2.4)

1 < . . . < n < 1 < . . . < n.

For a permutation σ = σ1 . . . σn ∈ Sn , we define σ to be the word overalphabet [n] ∪ [n] obtained from σ by replacing σi with σi wheneveri ∈ EXC(σ). For example, if σ = 531462 then σ = 531462. We define

CHROMATIC QUASISYMMETRIC FUNCTIONS

9a descent in a word w = w1 . . . wn over any totally ordered alphabet to
be any i ∈ [n − 1] such that wi > wi+1 and let DES(w) be the set of alldescents of w. Now, for σ ∈ Sn , we define
DEX(σ) := DES(σ).
For example, DEX(531462) = DES(531462) = {1, 4}.
Theorem 2.3 (Shareshian and Wachs [ShWa2, Theorem 1.2]).
(2.5)

1+

XX

Fn,DEX(σ) texc(σ) z n =n≥1 σ∈Sn(1 − t)H(z).
H(tz) − tH(z)Corollary 2.4 ([ShWa2, Theorem 7.4]). For 0 ≤ j ≤ n − 1,X
chH 2j (V(∆n )) =Fn,DEX(σ) .
σ ∈ Snexc(σ) = j

Expansion in the basis of fundamental quasisymmetric functions isuseful because it can yield interesting results about permutation statistics via specialization. For a quasisymmetric function Q(x1 , x2 , . . .) ∈QR , the stable principal specialization ps(Q) ∈ R[[q]] is, by definition,
obtained from Q by substituting q i−1 for xi for each i ∈ P. Now (seefor example [St6, Lemma 7.19.10]), for any n ∈ P and S ⊆ [n − 1], we
have
(2.6)

ps(Fn,S ) = (q; q)−1
n q

P

i∈S i

,

where
n
Y
(p; q)n =(1 − pq j−1 ).
j=1

P
From Corollary 2.4 and the fact that thati∈DEX(σ) i = maj(σ) −exc(σ) (see [ShWa2, Lemma 2.2]) we obtain the following q-analog of(2.1).
Corollary 2.5. For 0 ≤ j ≤ n − 1,(q; q)n ps(chH 2j (V(∆n ))) = an,j (q),
where
(2.7)

an,j (q) :=X
σ ∈ Snexc(σ) = j

q maj(σ)−exc(σ) .

10SHARESHIAN AND WACHS

The q-Eulerian numbers an,j (q) defined in Corollary 2.5 were initiallystudied in [ShWa1, ShWa2] and have been further studied in [ShWa3,
FoHa1, FoHa2, SaShWa, HeWa]. Define the q-Eulerian polynomials,(2.8)

An (q, t) :=n−1
Xan,j (q)tj =j=1

Xq maj(σ)−exc(σ) texc(σ) .

σ∈SnIn [ShWa1, ShWa2], the following q-analog of Euler’s formula (2.3) was
obtained via specialization of (2.5),
X(1 − t) expq (z)
zn
(2.9)
1+
An (q, t)
=
,
[n]
!
exp
(tz)
−
t
exp
(z)
q
q
q
n≥1
where
expq (z) :=

X zn
n≥0

[n]q !

.

It is surprising that when one evaluates an,j (q) at any nth root ofunity, one always gets a positive integer.
Theorem 2.6 (Sagan, Shareshian, and Wachs [SaShWa, Corollary6.2]). Let dm = n and let ξd be any primitive dth root of unity. Then
An (ξd , t) = Am (t)[d]mt .
Consequently An (ξd , t) is a positive, palindromic, unimodal polynomialin Z[t].
Theorem 2.2, Corollary 2.5 and the following result, which is implicitin [De] and stated explicitly in [SaShWa], can be used to give a proofof Theorem 2.6.
Lemma 2.7. Suppose u(q) ∈ Z[q] and there exists a homogeneous
symmetric function U of degree n with coefficients in Z such thatu(q) = (q; q)n ps(U ).
If dm = n then u(ξd ) is the coefficient of zd−1
m pdm in the expansion of U
in the power-sum basis.
2.3. Unimodality. Let us now consider what the hard Lefschetz theorem tells us about the sequence (chH 2j (V(∆n )))0≤j≤n−1 . Since theaction of the symmetric group Sn commutes with the hard Lefschetz
map φ (see [St2, p. 528]), we can conclude that for 0 ≤ i ≤ n themap φ : H i (V(∆n )) → H i+2 (V(∆n )) is an Sn -module monomorphism.
Hence, by Schur’s lemma, for each λ ` n, the multiplicity of the Specht
module S λ in H i (V(∆n )) is less than or equal to the multiplicity in
H i+2 (V(∆n )). Equivalently, the coefficient of the Schur function sλ in

CHROMATIC QUASISYMMETRIC FUNCTIONS

11

the expansion of chH i (V(∆n )) in the Schur basis is less than or equal
to the coefficient in chH i+2 (V(∆n )). Hence, it follows from the hard
Lefschetz theorem that the sequence (chH 2j (V(∆n )))0≤j≤n−1 is palindromic and Schur-unimodal.
The following lemma is useful for establishing unimodality of polynomials in Q[q][t].
Lemma 2.8 (see for example [ShWa2, Lemma 5.2]). If U is a Schurpositive homogeneous symmetric function of degree n then(q; q)n ps(U )is a polynomial in q with nonnegative coefficients.
It follows from Lemma 2.8 and Corollary 2.5 that the palindromicity
and Schur-unimodality of (chH 2j (V(∆n )))0≤j≤n−1 can be specialized toyield the following q-analog of the palindromicity and unimodality of
the Eulerian numbers.
Theorem 2.9 (Shareshian and Wachs [ShWa2, Theorem 5.3]). For
any n ∈ P, the sequence (an,j (q))0≤j≤n−1 is palindromic and unimodal.
We remark that it is not really necessary to use the hard Lefschetz
theorem to establish the above mentioned unimodality results. In fact,by manipulating the right hand side of (2.2) we obtain (2.10) below1.
The palindromicity and h-unimodality consequences follow by Propositions 1.3 and 1.4.
Theorem 2.10 (Shareshian and Wachs [ShWa4]). For all n ≥ 1,
(2.10)
n−1
X

b n+1
c
2
2j

j

chH (V(∆n ))t =

j=0

X
m=1

m−1

t

X
kP
1 ,...,km ≥2
ki =n+1mY[ki − 1]t hk1 −1 hk2 · · · hkm
i=1

Consequently, the sequence (chH 2j (V(∆n )))0≤j≤n−1 is h-positive, palindromic and h-unimodal.
By specializing (2.10) we obtain the following result. Recall that theq-analog of the multinomial coefficients is defined by[n]q !
n:=
k1 , . . . , km q
[k1 ]q ! · · · [km ]q !
P
for all k1 , . . . , km ∈ N such that ni=1 ki = n.
1This formula is different from a similar looking formula given in [ShWa2, Corol-lary 4.2].

12

SHARESHIAN AND WACHS

Corollary 2.11. For all n ≥ 1,
c
b n+1
2

An (q, t) =

X

X

m−1

t

kP
1 ,...,km ≥2
ki =n+1m=1

mY[ki − 1]ti=1nk1 − 1, k2 , . . . , km.
qConsequently, An (q, t) is a palindromic and unimodal polynomial in t.
2.4. Smirnov words. The expression on the right hand side of (2.2)
has appeared in several other contexts (see [ShWa2, Section 7]). We
mention just one of these contexts here.
A Smirnov word is a word with no equal adjacent letters. Let Wn be
the set of all Smirnov words of length n over alphabet P. Define theenumerator
X
Yn,j (x1 , x2 , . . . ) :=xw ,w ∈ Wndes(w) = j

where xw := xw(1) · · · xw(n) . (Here we are calculating des(w) using
the standard totalorder on P.) A formula for the generating funcPn−1tion of Yn :=j=0 Yn,j was initially obtained by Carlitz, Scovilleand Vaughan [CaScVa] and further studied by Dollhopf, Goulden andGreene [DoGoGr] and Stanley [St5]. Stanley pointed out to us the following refinement of this formula. This refinement follows from resultsin [ShWa2, Section 3.3] by P-partition reciprocity.
Theorem 2.12 (Stanley (see [ShWa2, Theorem 7.2])).
X(2.11)

Yn,j (x)tj z n =n,j≥0

where E(z) :=of degree n.

Pn≥0 en zn(1 − t)E(z),E(zt) − tE(z)and en is the elementary symmetric function

Corollary 2.13. For 0 ≤ j ≤ n − 1,
chH 2j (V(∆n )) = ωYn,j .
3. Rawlings major index and generalized Eulerian
numbers
In [Ra], Rawlings studies Mahonian permutation statistics that interpolate between the major index and the inversion index. Fix n ∈ P

CHROMATIC QUASISYMMETRIC FUNCTIONS

13

and k ∈ [n]. For σ ∈ Sn , set
DES≥k (σ) := {i ∈ [n − 1] : σ(i) − σ(i + 1) ≥ k},X
maj≥k (σ) :=i,
i∈DES≥k

INV<k (σ) := {(i, j) ∈ [n] × [n] : i < j and 0 < σ(i) − σ(j) < k},
inv<k (σ) := |INV<k (σ)|.
Now define the Rawlings major index to bermajk (σ) := inv<k (σ) + maj≥k (σ).
Note that rmaj1 and rmajn are, respectively, the well studied majorindex maj and inversion number inv. Rawlings shows in [Ra] that eachrmajk is a Mahonian statistic, that is,X(3.1)
q rmajk (σ) = [n]q ! .
σ∈SnFor a proof of (3.1) that is different from that of Rawlings and a generalization of (3.1) from permutations to labeled trees, see [LiWa].
In [DeSh] De Mari and Shayman introduce a class of numbers, closely
related to the Rawlings major index, which they call generalized Eulerian numbers. For k ∈ [n] and 0 ≤ j define the De Mari-Shayman
generalized Eulerian numbers to be(k)an,j := |{σ ∈ Sn : inv<k (σ) = j}|.
(2)

Note that inv<2 (σ) = des(σ −1 ), which implies that an,j = an,j , justifying the name “generalized Eulerian numbers”. De Mari and Shayman
introduce the generalized Eulerian numbers in connection with theirstudy of Hessenberg varieties. It follows from their work and the hard
Lefschetz theorem that for each fixed k ∈ [n], the generalized Eulerian(k)numbers (an,j )j≥0 form a palindromic unimodal sequence of numbers.
In [ShWa4] Shareshian and Wachs consider a q-analog of the De
Mari-Shayman generalized Eulerian numbers defined for k ∈ [n] and0 ≤ j byX(k)an,j (q) :=q maj≥k (σ) .
σ ∈ Sninv<k (σ) = j

Similarly, the generalized q-Eulerian polynomials are defined by
X
A(k)
(q,
t)
=
q maj≥k (σ) tinv<k (σ) .
n
σ∈Sn

14

SHARESHIAN AND WACHS

Now (3.1) is equivalent to,A(k)n (q, q) = [n]q !.
We now consider the question of whether unimodality and other(k)known properties of the generalized Eulerian numbers an,j extend to(k)
the generalized q-Eulerian numbers an,j (q). Although it is not at all
obvious, it turns out that in the case k = 2, the generalized q-Eulerian
numbers are equal to the q-Eulerian numbers defined in (2.7),(2)an,j (q) = an,j (q)(see Theorem 4.19). Hence by Theorem 2.9, unimodality holds whenk = 2. We consider this question in a more general setting, which we
now describe.
Let E(G) denote the edge set of a graph G. For σ ∈ Sn and G agraph with vertex set [n], the G-inversion set of σ is
INVG (σ) := {(i, j) : i < j, σ(i) > σ(j) and {σ(i), σ(j)} ∈ E(G)}and the G-inversion number is
invG (σ) := |INVG (σ)|.
For σ ∈ Sn and P a poset on [n], the P -descent set of σ is
DESP (σ) := {i ∈ [n − 1] : σ(i) >P σ(i + 1)},and the P -major index is
X

majP (σ) :=i.

i∈DESP (σ)

Define the incomparability graph inc(P ) of a poset P on [n] to be thegraph with vertex set [n] and edge set {{a, b} : a 6≤P b and b 6≤P a}.
For 0 ≤ j ≤ |E(inc(P ))| define the (q, P )-Eulerian numbers,
X
aP,j (q) :=q majP (σ) ,σ ∈ Sninvinc(P ) (σ) = j

and the (q, P )-Eulerian polynomials|E(inc(P ))|AP (q, t) :=X
j=0

aP,j (q)tj =Xq majP (σ) tinvinc(P ) (σ) .

σ∈SnDefine Pn,k to be the poset on vertex set [n] such that i < j in Pn,kif and only if j − i ≥ k and let Gn,k be the incomparability graph ofPn,k . ThenDES≥k (σ) = DESPn,k (σ)

CHROMATIC QUASISYMMETRIC FUNCTIONS

15

and
INV<k (σ) = INVGn,k (σ).
(k)

(k)

Hence if P = Pn,k , we have aP,j (q) = an,j (q) and AP (q, t) = An (q.t).
The unimodality property that holds for the (q, P )-Eulerian numbers
in case P = Pn,2 does not hold for general P . Indeed, consider the poset
P on [3] whose only relation is 1 < 2. We have
(3.2)

AP (q, t) := (1 + q) + 2t + (1 + q 2 )t2 ,which is neither palindromic as a polynomial in t, nor unimodal. The
property AP (q, q) = [n]q ! fails as well. However there is a very niceclass of posets for which unimodality seems to hold.
A unit interval order is a poset that is isomorphic to a finite collection
I of intervals [a, a + 1] on the real line, partially ordered by the relation[a, a + 1] <I [b, b + 1] if a + 1 < b. Define a natural unit interval order
to be a poset P on [n] that satisfies (1) x <P y implies x < y in thenatural order on [n] and (2) if the direct sum {x <P z} + {y} is aninduced subposet of P then x < y < z in the natural order on [n]. It
is not difficult to see that every natural unit interval order is a unit
interval order and that every unit interval order is isomorphic to aunique natural unit interval order. The poset Pn,k is an example of anatural unit interval order.
It is a consequence of a result of Kasraoui [Ka, Theorem 1.8] that if
P is a natural unit interval order then invinc(P ) + majP is Mahonian.
In other words, if P is a natural unit interval order on [n] thenAP (q, q) = [n]q ! .
From the work of De Mari, Procesi and Shayman [DePrSh] we havethe following result. The proof is discussed in Section 5.
Theorem 3.1 (see [St3, Exercise 1.50 (f)]). Let P be a natural unit
interval order. Then the P -Eulerian polynomial AP (1, t) is palindromic
and unimodal.
Palindromicity of the q-analog AP (q, t) follows from results discussed
in Section 4 and unimodality is implied by a conjecture discussed in
Section 4.
Theorem 3.2 (Shareshian and Wachs [ShWa4]). Let P be a naturalunit interval order on [n]. Then the sequence (aP,j (q))0≤j≤|E(inc(P ))| ispalindromic.
Conjecture 3.3. Let P be a natural unit interval order on [n]. Thenthe palindromic sequence (aP,j (q))0≤j≤|E(inc(P ))| is unimodal.
The following conjecture generalizes Theorem 2.6.

16

SHARESHIAN AND WACHS

Conjecture 3.4. Let P be a natural unit interval order on [n]. If
dm = n then there is a polynomial BP,d (t) ∈ N[t] such that
AP (ξd , t) = BP,d (t)[d]mt .
Moreover, (aP,j (ξd ))0≤j≤|E(inc(P ))| is a palindromic unimodal sequence of
positive integers.
In addition to the case P = Pn,2 (Theorems 2.9 and 2.6), these
conjectures have been verified for Pn,k when k = 1, n − 2, n − 1, n, andby computer for all k when n ≤ 8. An approach to proving them ingeneral will be presented in Sections 4 and 5.
4. Chromatic quasisymmetric functions
4.1. Stanley’s chromatic symmetric functions.
Let G be a graph[n]with vertex set [n] and edge set E = E(G) ⊆ 2 . A proper P-coloringof G is a function c from [n] to the set P of positive integers suchthat whenever {i, j} ∈ E we have c(i) 6= c(j). Given any function
c : [n] → P, set
n
Y
xc :=
xc(i) .
i=1

Let C(G) be the set of proper P-colorings of G. In [St5], Stanley defined
the chromatic symmetric function of G,X
XG (x) :=xc .
c∈C(G)

It is straightforward to confirm that XG ∈ ΛZ . The chromatic symmetric function is a generalization of the chromatic polynomial χG : P → P,
where χG (n) is the number of proper colorings of G with n colors. Indeed, XG (1n ) = χG (n), where XG (1n ) is the specialization of XG (x)obtained by setting xi = 1 for 1 ≤ i ≤ n and xi = 0 for i > n.
Chromatic symmetric functions are studied in various papers, including [St5, St6, Ga, Ch, MaMoWa].
We recall Stanley’s description of the power sum decomposition of
XG (x), for arbitrary G with vertex set [n]. We call a partition π =π1 | . . . |πl of [n] into nonempty subsets G-connected if the subgraph of
G induced on each block πi of π is connected. The set ΠG,n of all
G-connected partitions of [n] is partially ordered by refinement (thatis, π ≤ θ if each block of π is contained in some block of θ). We
write µG and 0̂, respectively, for the Möbius function on ΠG,n , and theminimum element 1| . . . |n of ΠG,n . For π ∈ ΠG,n , we write par(π) forthe partition of n whose parts are the sizes of the blocks of π.

CHROMATIC QUASISYMMETRIC FUNCTIONS

17

Theorem 4.1 (Stanley [St5, Theorem 2.6]). Let G be a graph withvertex set [n]. ThenX
(4.1)
ωXG (x) =|µG (0̂, π)|ppar(π) .
π∈ΠG,nConsequently ωXG (x) is p-positive.
A poset P is called (r + s)-free if it contains no induced subposet
isomorphic to the direct sum of an r element chain and an s element
chain. A classical result (see [ScSu]) says that a poset is a unit intervalorder if and only if it is both (3 + 1)-free and (2 + 2)-free.
Conjecture 4.2 (Stanley and Stembridge [StSte, Conjecture 5.5],[St5, Conjecture 5.1]). Let G be the incomparability graph of a (3 + 1)free poset. Then XG (x) is e-positive.
This conjecture is still open even for unit interval orders. Gasharov[Ga] obtains the weaker, but still very interesting, result that, under
the assumptions of Conjecture 4.2, XG (x) is Schur-positive. Let P bea poset on n and let λ be a partition if n. Gasharov defines a P -tableauof shape λ to be a filling of a Young diagram of shape λ (in English
notation) with elements of P such that• each element of P appears exactly once,• if y ∈ P appears immediately to the right of x ∈ P , theny >P x, and• if y ∈ P appears immediately below x ∈ P , then y 6<P x.
Given a P -tableau T , let λ(T ) be the shape of T . Let TP be the setof all P -tableaux.
Theorem 4.3 (Gasharov [Ga]). Let P be a (3 + 1)-free poset. Then
X
Xinc(P ) (x) =sλ(T ) .
T ∈TP

4.2. A quasisymmetric refinement. We define the chromatic quasisymmetric function of G as
X
XG (x, t) :=tasc(c) xc ,c∈C(G)

whereasc(c) := |{{i, j} ∈ E(G) : i < j and c(i) < c(j)}|.
It is straightforward to confirm that XG (x, t) ∈ QZ [t].
While the chromatic quasisymmetric function is defined for an arbitrary graph on vertex set [n], our results will concern incomparability

18

SHARESHIAN AND WACHS

graphs of partially ordered sets. The natural unit interval orders are
particularly significant in our theory of chromatic quasisymmetric functions because they yield symmetric functions.
Proposition 4.4 (Shareshian and Wachs [ShWa4]). Let P be a naturalunit interval order. Then
Xinc(P ) (x, t) ∈ ΛZ [t].
Before looking at some examples of Xinc(P ) (x, t) for natural unit interval orders, let us consider the poset P on vertex set [3] whose only
relation is 1 < 2. Clearly P is not a natural unit interval order. (Recall
AP (q, t) is given in (3.2).) Using Theorem 4.17 below we compute
Xinc(P ) (x, t) = (e3 + F3,{2} ) + 2e3 t + (e3 + F3,{1} )t2 ,which is clearly not in ΛZ [t].
Example 4.5. P = Pn,1 . The incomparability graph has no edges.
Hence
(4.2)

Xinc(Pn,1 ) (x, t) = en1 .

Example 4.6. P = Pn,n . The incomparability graph is the completegraph. Each proper coloring c is an injective map which can be associated with a permutation σ ∈ Sn for which inv(σ) = asc(c). It follows
that
X
(4.3)
Xinc(Pn,n ) (x, t) = entinv(σ) = [n]t ! en .
σ∈Sn

Example 4.7. P = Pn,2 . Recall that the incomparability graph ofPn,2 is a path. To each proper coloring c of the path inc(Pn,2 ) one canassociate the word w(c) := c(n), c(n − 1), . . . , c(1). This word is clearlya Smirnov word of length n (c.f. Section 2.4) and des(w(c)) = asc(c).
Since w is a bijection from C(inc(Pn,2 )) to Wn , we haveXinc(Pn,2 ) (x, t) =n−1
XYn,j (x)tj .

j=0

It therefore follows from Corollary 2.13 that
(4.4)

ωXinc(Pn,2 ) (x, t) =n−1
X

chH 2j (V(∆n ))tj .

j=0

The following result is a consequence of Proposition 4.4.
Theorem 4.8 (Shareshian and Wachs [ShWa4]). Let P be a naturalunit interval order. Then Xinc(P ) (x, t) is a palindromic polynomial int.

CHROMATIC QUASISYMMETRIC FUNCTIONS

19

From (4.2), (4.3), (4.4) and Theorem 2.10 we see that the following
conjectured refinement of the unit interval order case of the StanleyStembridge conjecture (Conjecture 4.2) is true for P = Pn,k when k =1, 2, n.
Conjecture 4.9. Let P be a natural unit interval order. Then Xinc(P ) (x, t)
is an e-positive and e-unimodal polynomial in t.
We have verified e-positivity and e-unimodality for several othercases including P = Pn,k when k = n − 1, n − 2, and by computerfor all n ≤ 8. Our computation yields,(4.5)
Xinc(Pn,n−1 ) (x, t) = [n − 2]t ! [n]t [n − 2]t en + tn−2 en−1,1(4.6)
Xinc(Pn,n−2 ) (x, t) = [n − 4]t ! ([n]t [n − 3]3t en + [n − 2]t tn−3 ([n − 3]t +[2]t [n − 4]t )en−1,1 + t2n−7 [2]t en−2,2 ),from which the conjecture is easily verified using Propositions 1.3 and 1.4.
In [St5] Stanley proves that for any graph G on
P[n], the number ofacyclic orientations of G with j sinks is equal to λ∈Par(n,j) cG
λ , whereG
Par(n, j) is the set of partitions of n into j parts and cλ is the coefficient of eλ in the e-basis expansion of the chromatic symmetric function
XG (x). We obtain the following refinement of this result using essentially the same proof as Stanley’s, thereby providing a bit of further
evidence for e-positivity of XG (x, t).
Theorem 4.10 (Shareshian and Wachs [ShWa4]). Let G be the incomparability graph of a natural unit interval order on [n]. For each λ ` n,
let cGλ (t) be the coefficient of eλ in the e-basis expansion of XG (x, t).
Then
X
X
cG
(t)
=
tasc(o) ,λλ∈Par(n,j)

o∈O(G,j)where O(G, j) is the set of acyclic orientations of G with j sinks andasc(o) is the number of directed edges (i, j) of o for which i < j.
Theorem 4.10 gives a combinatorial description of the coefficient of
en in the e-basis expansion of XG (x, t). In Theorem 4.11 and Conjecture 4.12 below we give alternative descriptions. Let P be a poset on[n]. We say that σ ∈ Sn has a left-to-right P -maximum at r ∈ [n] if
σ(r) >P σ(s) for 1 ≤ s < r. The left-to-right P -maximum at 1 will bereferred to as trivial. (The notion of (trivial) left-to-right P -maximum
can be extended in an obvious way to permutations of any subset of20

SHARESHIAN AND WACHS

P .) Let(4.7)

cP (t) :=X

tinvinc(P ) (σ) ,σwhere σ ranges over the permutations in Sn with no P -descents andno nontrivial left-to-right P -maxima.
Theorem 4.11 (Shareshian and Wachs [ShWa4]). Let P be a naturalunit interval order on [n]. The coefficient of en in the expansion of
Xinc(P ) (x, t) in the e-basis of ΛZ[t] is equal to cP (t).
Conjecture 4.12. Let P be a natural unit interval order on [n]. ThennYcP (t) = [n]t [ai ]t ,i=2where ai = |{j ∈ [i − 1] : {i, j} ∈ E(inc(P ))}|. Consequently cP (t) ispalindromic and unimodal.
In the case that P = Pn,2 , this conjecture is true by Theorem 4.11
and equations (2.10) and (4.4). It is also true for Pn,k when k =1, n, n − 1, n − 2 by Theorem 4.11 and equations (4.2), (4.3), (4.5) and(4.6), respectively.
4.3. Schur and power sum decompositions. When P is a naturalunit interval order, we have the following refinement of Gasharov’s
Schur positivity result (Theorem 4.3). For a P -tableau T and a graph
G with vertex set [n], let invG (T ) be the number of edges {i, j} ∈ E(G)such that i < j and i appears to the south of j in T .
Theorem 4.13 (Shareshian and Wachs [ShWa4]). Let P be a naturalunit interval order poset on [n] and let G be the incomparability graphof P . ThenX
XG (x, t) =tinvG (T ) sλ(T ) .
T ∈TP

Now by (4.4) we have the following.
Corollary 4.14. Let λ ` n. The multiplicity of the irreducible Specht
module S λ in H 2j (V(∆n )) is equal to the number of Pn,2 -tableaux ofshape λ0 with invinc(Pn,2 ) (T ) = j.
By comparing this decomposition to Stembridge’s decomposition(Theorem 2.1) we see that the number of marked tableaux of shape
λ and index j equals the number of Pn,2 -tableaux of shape λ0 and
invinc(Pn,2 ) (T ) = j. It would be interesting to find a bijective proof ofthis fact.

CHROMATIC QUASISYMMETRIC FUNCTIONS

21

Theorem 4.13 shows that when G is the incomparability graph ofa natural unit interval order, the coefficient of each power of t in
ωXG (x, t) is a nonnegative integer combination of Schur functions andtherefore the Frobenius characteristic of an actual representation of
Sn . Conjecture 4.9 says that this linear representation arises from apermutation representation in which each point stabilizer is a Young
subgroup. In Section 5 we present a very promising concrete candidate
for the desired permutation representation.
Next we attempt to refine Stanley’s p-basis decomposition of thechromatic symmetric functions (Theorem 4.1). In Conjectures 4.15
and 4.16 below, we provide two proposed formulae for this power sum
decomposition. With µ = (µ1 ≥ µ2 ≥ · · · ≥ µl ) a partition of n andP a natural unit interval order on [n], we call a permutation σ ∈ Sn ,(P, µ, 1)-compatible if, when we break σ (in one line notation) into
consecutive segments of lengths µ1 , . . . , µl , the segments have no P descents and no nontrivial left-to-right P -maxima. We call σ ∈ Sn ,(P, µ, 2)-compatible if, when we break σ into consecutive segments oflengths µ1 , . . . , µl , the segments have no P -ascents and they begin with
the numerically smallest letter of the segment. We write SP,µ,i , wherei = 1, 2, for the set of all (P, µ, i)-compatible elements of Sn .
Conjecture 4.15. Let P be a natural unit interval order on [n] withincomparability graph G. Then
X
X
tinvG (σ) .
zµ−1 pµωXG (x, t) =σ∈SP,µ,1µ`nConjecture 4.16. Let P be a natural unit interval order on [n] withincomparability graph G. ThenωXG (x, t) =Xµ`nzµ−1 pµ

l(µ)
Y
i=1

[µi ]tX

tinvG (σ) .

σ∈SP,µ,2

It can be shown that both conjectures reduce to the formula in Theo−1
rem 4.1 when t = 1. Conjecture 4.15 says that the coefficient of z(n)p(n)
is equal to cP (t) defined in (4.7). Since the coefficient of h(n) in the h−1basis decomposition must equal the coefficient of z(n)p(n) in the p-basis
decomposition, by Theorem 4.11, Conjecture 4.15 gives the correct co−1
efficient of z(n)p(n) . When P = Pn,2 it is not difficult to see that bothconjectures reduce to Theorem 2.2.
4.4. Fundamental quasisymmetric function basis decomposition.

22

SHARESHIAN AND WACHS

Theorem 4.17 (Shareshian and Wachs [ShWa4]). Let G be the incomparability graph of a poset P on [n]. ThenXωXG (x, t) =tinvG (σ) Fn,DESP (σ) ,σ∈Snwhere ω is the involution on QZ that maps Fn,S to Fn,[n−1]\S for eachn ∈ N and S ⊆ [n−1]. (This extends the involution ω on ΛZ that maps
hn to en )Theorem 4.17 refines Corollary 2 in Chow’s paper [Ch]. Indeed, one
obtains Chow’s result by setting t = 1 in Theorem 4.17. Our proof of
Theorem 4.17 follows the same path as Chow’s proof of his Corollary 2.
We use Theorem 4.17 and (2.6) to compute the principal stable specialization of ωXG (x, t).
Corollary 4.18. Let G be the incomparability graph of a poset P on[n]. Then(q; q)n ps(ωXG (x, t)) = AP (q, t).
Recall that for P = Pn,2 we have a formulation for the expansion of
ωXinc(P ) (x, t) in the fundamental quasisymmetric function basis that isdifferent from that of Theorem 4.17. It is obtained by combining (2.5)
and (2.11). By equating these formulations, we obtain the identity,
X
X
−1
(4.8)
tdes(σ ) Fn,DES≥2 (σ) =texc(σ) Fn,DEX(σ) .
σ∈Sn

σ∈Sn

Taking the stable principle specialization of both sides of (4.8) yields
the following new Euler-Mahonian result.
Theorem 4.19 (Shareshian and Wachs [ShWa4]). For all n ∈ P,
X
X
−1
q rmaj2 (σ) tdes(σ ) =q maj(σ) texc(σ) .
σ∈Sn

σ∈Sn

It would be interesting to find bijective proofs of (4.8) and Theorem 4.19.
Theorem 3.2, asserting palindromicity of AP (q, t), is proved by taking stable principal specializations in Theorem 4.8, by means of Corollary 4.18. Conjecture 3.3, asserting unimodality of AP (q, t), can beobtained by taking stable principal specializations in Conjecture 4.9(see Lemma 2.8). By taking a specialization called (nonstable) principal specialization, a stronger unimodality conjecture follows from Conjecture 4.9. For a poset P on [n] and σ ∈ Sn , define desP (σ) :=|DESP (σ)|.

CHROMATIC QUASISYMMETRIC FUNCTIONS

23

Conjecture 4.20. Let P a natural unit interval order on [n]. ThenX
AP (q, p, t) :=q majP (σ) pdesP (σ) tinvinc(P ) (σ)σ∈Snis a palindromic unimodal polynomial in t.
It follows from Corollary 4.18 and Lemma 2.7 that AP (ξd , t) is thecoefficient of zd−1
m pdm in the p-basis expansion of ωXinc(P ) (x, t) when P isa natural unit interval order on [dm]. Hence Conjecture 3.4 on the evaluation of AP (q, t) at roots of unity is a consequence of Conjectures 4.9
and 4.16.
5. Hessenberg varieties
Let G = GLn (C) and let B be the set of upper triangular matrices
in G. The (type A) flag variety is the quotient space G/B. Fix now
a natural unit interval order P and let Mn,P be the set of all n × ncomplex matrices (aij ) such that aij = 0 whenever i >P j. Fix anonsingular diagonal n × n matrix s with n distinct eigenvalues. The
regular semisimple Hessenberg variety of type A associated to P is
H(P ) := {gB ∈ G/B : g −1 sg ∈ Mn,P }.
(Note that H(P ) is well defined, since the group B normalizes the set
Mn,P .)
Certain regular semisimple Hessenberg varieties of type A were studied initially by De Mari and Shayman in [DeSh]. Hessenberg varieties
for other Lie types are defined and studied by De Mari, Procesi andShayman in [DePrSh]. Such varieties are determined by certain subsets
of a root system. In [DePrSh, Theorem 11] it is noted that, for arbitrary Lie type, the Hessenberg variety associated with the set of simple
roots is precisely the toric variety associated with the corresponding
Coxeter complex. In particular, in Lie type A, the poset giving rise to
the regular semisimple Hessenberg variety associated with simple roots
is Pn,2 since E(inc(Pn,2 )) = {{i, i + 1} : i ∈ [n − 1]}. Thus
(5.1)

H(Pn,2 ) = V(∆n ).

De Mari, Procesi and Shayman also show that the cohomology ofH(P ) is concentrated in even degrees and that for 0 ≤ j ≤ |E(inc(P ))|,
(5.2)

dim H 2j (H(P )) = aP,j (1).

Hence unimodality of the P -Eulerian polynomials AP (1, t) (Theorem
3.1) follows from the hard Lefschetz theorem since H(P ) is smooth.
Our approach to establishing the unimodality of the (q, P )-Eulerian
polynomial AP (q, t) is to find a representation of the symmetric group

24

SHARESHIAN AND WACHS

on H 2j (H(P )) such that the stable principal specialization of its Frobenius characteristic yields aP,j (q). If the hard Lefschetz map commuteswith the action of the symmetric group then it follows from Schur’slemma and Lemma 2.8 that AP (q, t) is unimodal.
For the cases P = Pn,k , where k=1,2, we already have the desired representations. Indeed, H(Pn,1 ) consists of n! isolated points and the representation of Sn on H 0 (H(Pn,1 )) is the regular representation. For k =2, we can use the representation of Sn on H ∗ (H(Pn,2 )) = H ∗ (V(∆n ))discussed in Section 2.
For general natural unit interval orders P , Tymoczko [Ty2], [Ty3] hasdefined a representation of Sn on H ∗ (H(P )) via a theory of Goresky,
Kottwitz and MacPherson known as GKM theory (see [GoKoMacP],and see [Ty1] for an introductory description of GKM theory). The centralizer T = CG (s) consists of the diagonal matrices in G := GLn (C).
It follows that the torus T acts (by left translation) on H(P ). The technical conditions required for application of GKM theory are satisfied
by this action, and it follows that one can describe the cohomology ofH(P ) using the moment graph associated to this action. The moment
graph M is a subgraph of the Cayley graph of Sn with generating
set consisting of the transpositions. The vertex set of M is Sn andthe edges connect pairs of elements that differ by a transposition (i, j)such that {i, j} ∈ E(inc(P )). Thus M admits an action of Sn , andthis action can be used to define a linear representation of Sn on thecohomology H ∗ (H(P )).
Tymoczko’s representation of Sn on H ∗ (H(P )) in the cases P = Pn,k ,k = 1, 2, is the same as the respective representations of Sn discussed
above. In the case that P = Pn,n , it follows from [Ty3, Proposition 4.2]
(n)that for all j, Tymoczko’s representation is isomorphic to an,j copiesof the trivial representation.
By applying the hard Lefschetz theorem, MacPherson and Tymoczko
obtain the following result.
Theorem 5.1 (MacPherson and Tymoczko [MacTy]). For all natural unit interval orders P , the sequence (chH 2j (H(P )))0≤j≤|E(inc(P )| ispalindromic and Schur-unimodal.
Tymoczko poses the following problem.
Problem 5.2 (Tymoczko [Ty3]). Given any natural unit interval order
P on vertex set [n], describe the decomposition of the representationof Sn on H 2j (H(P )) into irreducibles.
We finally come to the conjecture that ties together the three topicsof this paper.

CHROMATIC QUASISYMMETRIC FUNCTIONS

25

Conjecture 5.3. Let P be a natural unit interval order on [n]. Then
|E(inc(P ))|

(5.3)

X

chH 2j (H(P ))tj = ωXinc(P ) (x, t).

j=0

By (5.1) and (4.4) the conjecture is true in the case that P = Pn,2 .
It is straightforward to verify in the case P = Pn,k , when k = 1, n −1, n, and for all natural unit interval orders on [n] when n ≤ 4. The
conjecture is also true for the parabolic Hessenberg varieties studied
by Teff [Te]. It follows from (5.2) that the coefficient of the monomial
symmetric function m1n in the expansion of the left hand side of (5.3)
in the monomial symmetric function basis equals the coefficient of m1n
in the expansion of the right hand side of (5.3).
Conjecture 5.3, if true, would have many important ramifications. It
would allow us to transfer what we know about chromatic quasisymmetric functions to Tymoczko’s representation and vice-versa. For instance Theorem 4.13 would provide a solution to Tymoczko’s problem.
Conjecture 5.3 provides an approach to proving the Stanley-Stembridge
conjecture (Conjecture 4.2) for unit interval orders. Indeed one would
only have to prove the following conjecture.
Conjecture 5.4. For all natural interval orders P , Tymoczko’s representation of Sn on H ∗ (H(P )) is a permutation representation in which
each point stabilizer is a Young subgroup.
Our refinement of the Stanley-Stembridge conjecture (Conjecture 4.9)
would be equivalent to the following strengthening of the result of
MacPherson and Tymoczko.
Conjecture 5.5. For all natural unit interval orders P , the palindromic sequence (chH 2j (H(P )))0≤j≤|E(inc(P )| is h-unimodal.
To establish the unimodality of the (q, P )-Eulerian numbers (Conjecture 3.3) one would only need to prove Conjecture 5.3. Indeed Conjecture 5.3, Theorem 5.1, Corollary 4.18 and Lemma 2.8 together imply
the unimodality result. The more general unimodality conjecture for
AP (q, p, t) (Conjecture 4.20) is also a consequence of Conjecture 5.3.
Acknowledgments
We are grateful to Richard Stanley for informing us of Theorem 2.12,
which led us to introduce the chromatic quasisymmetric functions. We
also thank Julianna Tymoczko for useful discussions and the anonymous referee for helpful comments.

26

SHARESHIAN AND WACHS

References[CaScVa]

L. Carlitz, R. Scoville, and T. Vaughan, Enumeration of pairs ofsequences by rises, falls and levels, Manuscripta Math. 19 (1976),
211-243.
[Ch]
T. Chow, Descents, quasi-symmetric functions, Robinson-Schensted
for posets, and the chromatic symmetric function, J. Algebraic Combin. 10 (1999), no. 3, 227-240.
[DePrSh]
F. De Mari, C. Procesi and M. Shayman, Hessenberg varieties, Trans.
Amer. Math. Soc. 332 (1992), no. 2, 529-534.
[DeSh]
F. De Mari and M. Shayman, Generalized Eulerian numbers and the
topology of the Hessenberg variety of a matrix, Acta Appl. Math. 12(1988), no. 3, 213-235.
[De]
J. Désarménien, Fonctions symétriques associées à des suites classiques de nombres, Ann. scient. Éc. Norm. Sup. 16 (1983) 271-304.
[DoLu]
I. Dolgachev and V. Lunts, A character formula for the representationof a Weyl group in the cohomology of the associated toric variety, J.
Algebra 168 (1994), 741-772.
[DoGoGr]J. Dollhopf, I. Goulden, and C. Greene, Words avoiding a reflexive
acyclic relation, Electron. J. Combin. 11 (2006) #R28.
[FoHa1]
D. Foata and G.-N. Han, Fix Mahonian calculus III; A quadruple
distribution, Monatshefte für Mathematik 154 (2008), 177-197.
[FoHa2]
D. Foata and G.-N. Han, The q-tangent and q-secant numbers via
basic Eulerian polynomials, Proc. Amer. Math. Soc. 138 (2010) 385393.
[Ga]
V. Gasharov, Incomparability graphs of (3 + 1)-free posets are spositive, Proceedings of the 6th Conference on Formal Power Series
and Algebraic Combinatorics (New Brunswick, NJ, 1994), Discrete
Math. 157 (1996), no. 1-3, 193-197.
[GoKoMacP] M. Goresky, R. Kottwitz and R. MacPherson, Equivariant cohomology, Koszul duality, and the localization theorem, Invent. Math. 131(1998), no. 1, 25-83.
[HeWa]
A. Henderson and M. L. Wachs, Unimodality of Eulerian quasisymmetric functions, preprint, arXiv:1101.444.
[Ka]
A. Kasraoui, A classification of Mahonian maj-inv statistics. Adv. in
Appl. Math. 42 (2009), no. 3, 342-357.
[Le]
G. I. Lehrer, Rational points and Coxeter group actions on the cohomology of toric varieties, Ann. Inst. Fourier (Grenoble) 58 (2008),
no. 2, 671-688.
[LiWa]
K. Liang and M. L. Wachs, Mahonian statistics on labeled forests,
Discrete Math. 99 (1992), 181-197.
[MacTy]R. MacPherson and J. Tymoczko, personal communication.
[MaMoWa] J. Martin, M. Morin and J. Wagner, On distinguishing trees by
their chromatic symmetric functions, J. Combin. Theory Ser. A 115(2008), no. 2, 237-253.
[Pr]
C. Procesi, The toric variety associated to Weyl chambers, in Mots,
153-161, Lang. Raison. Calc., Herms, Paris, 1990.
[Ra]
D. Rawlings, The r-major index, J. Combin. Theory Ser. A 31
(1981), no. 2, 175-183.

CHROMATIC QUASISYMMETRIC FUNCTIONS[SaShWa][ScSu][ShWa1][ShWa2][ShWa3][ShWa4]
[St1]

[St2]

[St3]

[St4]

[St5]
[St6]

[StSte][Ste1][Ste2]

[Te]
[Ty1]

[Ty2]

27

B. Sagan, J. Shareshian and M. L. Wachs, Eulerian quasisymmetricfunctions and cyclic sieving, Adv. Applied Math 46 (2011), 536-562.
D. Scott and P. Suppes, Foundational aspects of theories of measurement, J. Symb. Logic 23 (1958), 113-128.
J. Shareshian and M. L. Wachs, q-Eulerian polynomials: excedance
number and major index, Electron. Res. Announc. Amer. Math. Soc.
13 (2007), 33-45.
J. Shareshian and M. L. Wachs, Eulerian quasisymmetric functions,Adv. Math. 225 (2010), no. 6, 2921-2966.
J. Shareshian and M. L. Wachs, Poset homology of Rees products
and q-Eulerian polynomials, Elect. J. Combin. 16 (2009), R20.
J. Shareshian and M. L. Wachs, Chromatic quasisymmetric functions,in preparation.
R. P. Stanley, Combinatorial Applications of the Hard Lefschetz Theorem, Proceedings of the International Congress of Mathematicians
1983, Warszawa.
R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: Eastand West (Jinan, 1986), 500-535, Ann. New York Acad. Sci., 576,
New York Acad. Sci., New York, 1989.
R. P. Stanley, Enumerative Combinatorics, Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, 49, Cambridge University
Press, Cambridge, 2011.
R. P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge
Studies in Advanced Mathematics, 62, Cambridge University Press,
Cambridge, 1999.
R. P. Stanley, A symmetric function generalization of the chromatic
polynomial of a graph, Adv. Math. 111 (1995), no. 1, 166-194.
R. P. Stanley, Graph colorings and related symmetric functions: ideas
and applications: a description of results, interesting applications, &notable open problems, Selected papers in honor of Adriano Garsia(Taormina, 1994), Discrete Math. 193 (1998), no. 1-3, 267-286.
R. P. Stanley and J. R. Stembridge, On immanants of Jacobi Trudi
matrices and permutations with restricted positions, J. Combin. Theory Ser. A 62 (1993), 261-279.
J. R. Stembridge, Eulerian numbers, tableaux, and the Betti numbersof a toric variety, Discrete Math. 99 (1992), 307-320.
J. R. Stembridge, Some permutation representations of Weyl groups
associated with the cohomology of toric varieties, Adv. Math. 106(1994), 244-301.
N. Teff, Representations on Hessenberg Varieties and Youngs Rule,
Proceedings of FPSAC 2011, Reykjavik.
J. Tymoczko, An introduction to equivariant cohomology and homology, following Goresky, Kottwitz, and MacPherson, Snowbird lectures in algebraic geometry, 169-188, Contemp. Math., 388, Amer.
Math. Soc., Providence, RI, 2005.
J. Tymoczko, Permutation representations on Schubert varieties,
Amer. J. Math. 130 (2008), no. 5, 1171-1194.

28

[Ty3]

SHARESHIAN AND WACHS

J. Tymoczko, Permutation actions on equivariant cohomology, Toric
topology, 365-384, Contemp. Math. 460, Amer. Math. Soc., Providence, RI, 2008.

Department of Mathematics, Washington University, St. Louis, MO
63130
E-mail address: shareshi@math.wustl.edu
Department of Mathematics, University of Miami, Coral Gables,
FL 33124
E-mail address: wachs@math.miami.edu