# Hecke algebra characters and quantum chromatic symmetric functions

Brittany Shelton and Mark Skandera

Dept. of Mathematics, Lehigh University, 14 East Packer Ave., Bethlehem, PA 18015

**Abstract.** We evaluate induced sign characters of $H_n(q)$ at certain elements of $H_n(q)$ and conjecture an interpretation for the resulting polynomials as generating functions for $P$-tableaux by a certain statistic. Our conjecture relates the quantum chromatic symmetric functions of Shareshian and Wachs to $H_n(q)$ characters.

**Résumé.** Nous évaluons les caractères de signe induits de $H_n(q)$ à certains éléments de $H_n(q)$ et nous conjecturons une interprétation des polynômes résultants comme fonctions génératrices pour les tableaux-$P$ par une certaine statistique. Cette conjecture établit un lien entre les fonctions chromatiques symmétriques de Shareshian et Wachs et les caractères de $H_n(q)$.

**Keywords:** Hecke algebra character, unit interval order, $P$-tableau, chromatic symmetric function, quantum analog.

## 1 Introduction

Let $S_n$ be the symmetric group, let $s_i = (i, i+1), i = 1, \dots, n-1$ denote its standard generators, and for all $v \in S_n$, let $\ell(v)$ denote the length of any reduced (short as possible) expression $s_{i_1} \cdots s_{i_\ell}$ for $v$. (See [12] for more information on this material.) It is well known that each conjugacy class of $S_n$ consists of the permutations whose cycle sizes in weakly decreasing order are equal to some fixed partition $\lambda = (\lambda_1, \dots, \lambda_r) \vdash n$. Define the *Young diagram* of $\lambda$ to be the left-justified array of $n$ boxes having $\lambda_i$ boxes in row $i$. The $\mathbb{Z}$-module of $S_n$ *class functions*, those functions $f: S_n \to \mathbb{Z}$ satisfying $f(w^{-1}vw) = f(v)$ for all $v, w \in S_n$, has several well-studied bases:

1. the irreducible characters $\{\chi^\lambda | \lambda \vdash n\}$,

2. the induced sign characters $\{\epsilon^\lambda = \operatorname{sgn} \uparrow_{S_\lambda}^{S_n} | \lambda \vdash n\}$,

3. the induced trivial characters $\{\eta^\lambda = \operatorname{triv} \uparrow_{S_\lambda}^{S_n} | \lambda \vdash n\}$,

4. the monomial class functions $\{\phi^\lambda | \lambda \vdash n\}$,

where $S_\lambda$ is the Young subgroup of $S_n$ of type $\lambda$. These bases are related to one another just as are the Schur, elementary, (complete) homogeneous, and monomial bases of the space of homogeneous degree $n$.
symmetric functions. Specifically, we have

$$
\begin{align}
h_{\lambda} &= \sum_{\mu} K_{\mu, \lambda} s_{\mu}, \quad e_{\lambda} = \sum_{\mu} K_{\mu^{\top}, \lambda} s_{\mu}, \quad s_{\lambda} = \sum_{\mu} K_{\lambda, \mu} m_{\mu}, \tag{1} \\
\eta^{\lambda} &= \sum_{\mu} K_{\mu, \lambda} \chi^{\mu}, \quad \epsilon^{\lambda} = \sum_{\mu} K_{\mu^{\top}, \lambda} \chi^{\mu}, \quad \chi^{\lambda} = \sum_{\mu} K_{\lambda, \mu} \phi^{\mu}, \nonumber
\end{align}
$$

where $K = (K_{\lambda,\mu})$ is the invertible matrix of *Kostka numbers*, and $\lambda^\top$ is the partition whose Young diagram is transpose (or *conjugate*) to that of $\lambda$. For each of these class functions $f$ which is not an irreducible character, the integer $f(v)$ has a simple combinatorial formula; when $f = \chi^\lambda$, the number $\chi^\lambda(v)$ is computed by a cumbersome algorithm called the Murnaghan-Nakayama rule. This fact is somewhat unfortunate, since the irreducible characters are the most important of the above class functions.

The above class functions extend linearly to the group algebra $\mathbb{Z}[S_n]$. Work of Goulden and Jackson [4] and Greene [5] has led to the study of combinatorially interpreting $f(z)$ for $f$ a class function and $z$ in $\mathbb{Z}[S_n]$. In particular, these authors used $S_n$ subgroups of the form $S_{[i,j]}$, which fix all letters outside of the interval $[i,j] = \{i, \dots, j\}$ of $[n] = \{1, \dots, n\}$, to construct elements

$$ C'_{[i,j]} = \sum_{v \in S_{[i,j]}} v \qquad (2) $$

of $\mathbb{Z}[S_n]$, and products of these. It is not difficult to show that we have

$$ f(C'_{[i_1, j_1]} \cdots C'_{[i_m, j_m]}) \ge 0 \qquad (3) $$

when $f$ is $\eta^\lambda$ or $\epsilon^\lambda$, and to give a combinatorial interpretation of the resulting nonnegative integers in these cases. (See Theorems 2.2-2.3.) Stembridge showed furthermore [19, Cor. 3.3] that the inequality (3) holds for $f = \chi^\lambda$, and conjectured [20, Conj. 2.1] that it holds also for $f = \phi^\lambda$. In neither of these cases is there a proposed combinatorial interpretation, however. Stanley [15] initiated the study of the special case of (3) in which we have $i_1 < \cdots < i_m$ and $j_1 < \cdots < j_m$, relating this special case of the equation to certain *chromatic symmetric functions*, and to posets and graphs which avoid certain substructures. In this special case Gasharov [2, Thm. 2] found an interpretation when $f = \chi^\lambda$, but when $f = \phi^\lambda$ we still have no proof of positivity and no conjectured combinatorial interpretation.

It is conceivable that quantum analogs of $S_n$ characters may aid in the formulation of the unknown combinatorial interpretations mentioned above. In particular, the (type A) Hecke algebra $H_n(q)$ and certain functions $\chi_q^\lambda, \epsilon_q^\lambda, \eta_q^\lambda, \phi_q^\lambda : H_n(q) \to \mathbb{Z}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$, known as $H_n(q)$ traces, serve as analogs of $S_n$ and its class functions. Furthermore, there are well-studied quantum analogs $C'_{[i,j]}(q) \in H_n(q)$ of the elements (2) in $\mathbb{Z}[S_n]$, and Haiman [6, Lem. 1.1] has proved that we have

$$ f_q(C'_{[i_1, j_1]}(q) \cdots C'_{[i_m, j_m]}(q)) \in \mathbb{N}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}] \qquad (4) $$

when $f_q$ is $\eta_q^\lambda, \epsilon_q^\lambda$, or $\chi_q^\lambda$. He conjectured that the same holds for $f_q = \phi_q^\lambda$. Unfortunately, no simple combinatorial formulas are known or even conjectured for the evaluation of $H_n(q)$ traces at standard basis elements of $H_n(q)$ (in general), or at the special elements in (4). We will state and prove the first such formula for elements of the form (4) in the special case that $i_1 < \cdots < i_r, j_1 < \cdots < j_r$, and will relate this to the quantum chromatic symmetric functions introduced recently by Shareshian and Wachs [13].
In Section 2 we associate an element $\beta(P)$ of $\mathbb{Z}[S_n]$ to each labeled poset $P$. We evaluate induced sign characters at $\beta(P)$ and interpret the resulting nonnegative integers in terms of $P$-tableaux. In Section 3 we restrict our attention to special classes of posets $P$, especially unit interval orders. We evaluate other class functions at the associated elements $\beta(P)$, again interpreting the resulting nonnegative integers in terms of $P$-tableaux. We also discuss the appearance of these interpretations in Stanley's chromatic symmetric functions [15]. In Section 4 we present quantum analogs of much of the earlier material, including an element $\beta_q(P)$ of $H_n(q)$ which we associate to each labeled poset $P$. In Section 5 we present our main results. For each unit interval order $P$, we evaluate induced $H_n(q)$ sign characters at $\beta_q(P)$ and interpret the resulting elements of $\mathbb{N}[q]$ as generating functions for $P$-tableaux by a certain inversion statistic. Finally, we express the Shareshian-Wachs quantum chromatic symmetric functions [13] in terms of induced $H_n(q)$ sign characters.

## 2 $P$-tableaux and induced $S_n$ sign characters

Given a poset $P$, define a $P$-tableau of shape $\lambda$ to be a Young diagram of shape $\lambda$ whose boxes contain the elements of $P$. A $P$-tableau is called column-strict if whenever elements $i_1, \dots, i_r$ appear from top to bottom in a column, then we have that $i_1 <_P \dots <_P i_r$ is a chain in $P$. A $P$-tableau is called row-semistRICT if whenever $i_1, i_2$ appear consecutively (from left to right) in a row, then we have $i_1 <_P i_2$ or $i_1$ incomparable to $i_2$ in $P$. A $P$-tableau is called semistandard if it is both column-strict and row-semistRICT. When $P$ is simply the chain of integers $1 < \dots < n$, we will refer to a $P$-tableau as a *Young tableau*.

It is often convenient to label the elements of a poset and to encode the labeled poset as a certain 0-1 matrix. If a labeled poset $P$ has $n$ elements, we will always assume the labels to be $\{1, \dots, n\}$. We call $P$ naturally labeled if whenever $i <_P j$, we have $i < j$ as integers. Every poset has at least one natural labeling. Given a labeled poset $P$, we define the antiadjacency matrix $A = A(P) = (a_{i,j})$ of $P$ by

$$ a_{i,j} = \begin{cases} 0 & \text{if } i <_P j, \\ 1 & \text{otherwise.} \end{cases} \qquad (5) $$

Two different labelings of a poset give antiadjacency matrices which are conjugate to one another by a permutation matrix. If $P$ is naturally labeled, then in its antiadjacency matrix, all entries on or below the diagonal are 1. We may use the antiadjacency matrix of $P$ to count column-strict $P$-tableaux as follows. Call a sequence $(I_1, \dots, I_r)$ of disjoint subsets of $[n]$ an ordered set partition of type $\lambda$ if we have $|I_k| = \lambda_k$ for $k = 1, \dots, r$ and $I_1 \cup \dots \cup I_r = [n]$. For any $n \times n$ matrix $A$ and any subset $I \subset [n]$, define $A_{I,I}$ to be the $|I| \times |I|$ submatrix $(a_{i,j})_{i,j \in I}$ of $A$.

**Proposition 2.1** Let $P$ be a labeled poset with antiadjacency matrix $A$, and let $\lambda$ be a partition of $n = |P|$. Then the number of column-strict $P$-tableaux is given by

$$ \sum_{(I_1, \dots, I_r)} \det(A_{I_1, I_1}) \cdots \det(A_{I_r, I_r}), \qquad (6) $$

where the sum is over all ordered set partitions of $[n]$ of type $\lambda$.

**Proof:** Suppose that $P$ is naturally labeled. It is straightforward to show that each minor in (6) satisfies

$$ \det(A_{I_k, I_k}) = \begin{cases} 1 & \text{if } I_k \text{ is a chain in } P, \\ 0 & \text{otherwise,} \end{cases} \qquad (7) $$
and thus the claim is true in this case. (See, e.g., [16].) Furthermore, it is also straightforward to show that the polynomial function $\mathrm{Mat}_{n \times n}(\mathbb{Z}) \to \mathbb{Z}$ defined by the expression (6) is invariant under conjugation by a permutation matrix. $\square$

This relationship between the antiadjacency matrix and P-tableaux allows us to state a relationship between induced sign characters of $S_n$ and P-tableaux. To any labeled n-element poset P we may associate an element $\beta(P)$ of $\mathbb{Z}[S_n]$ by

$$ \beta(P) = \sum_{v} v, \qquad (8) $$

where the sum is over all permutations $v$ satisfying $i \not\prec_P v_i$ for all $i$. Equivalently, $\beta(P)$ is a sum of permutations which correspond to the placement of $n$ nonattacking rooks on entries of $A(P)$ which are equal to 1 [18]. Now we have the following [1, Cor. 4.2]. (See also [18, Eqn. (5.1)].)

**Theorem 2.2** Let P be a labeled poset and let $\lambda$ be a partition of $|P|$. Then $\epsilon^{\lambda}(\beta(P))$ equals the number of column-strict P-tableaux of shape $\lambda^{\top}$.

**Proof:** Let $n = |P|$ and let $x = (x_{i,j})_{i,j \in [n]}$ be a matrix of $n^2$ variables. The Littlewood-Merris-Watkins identity for induced sign characters [10, Sec. 6.5], [11, Sec. 1] states that in $\mathbb{Z}[x_{1,1}, \dots, x_{n,n}]$ we have

$$ \sum_{(I_1, \dots, I_r)} \det(x_{I_1, I_1}) \cdots \det(x_{I_r, I_r}) = \sum_{v \in S_n} \epsilon^{\lambda}(v) x_{1, v_1} \cdots x_{n, v_n}. \qquad (9) $$

Now let $A$ be the antiadjacency matrix of P and evaluate (9) at $x = A$. Since $a_{1,v_1} \cdots a_{n,v_n} = 1$ precisely when $i \not\prec_P v_i$ for all $i$, we obtain

$$ \epsilon^{\lambda}\left(\sum_{v \in S_n} a_{1, v_1} \cdots a_{n, v_n} v\right) = \epsilon^{\lambda}(\beta(P)), $$

and our result follows from Proposition 2.1. $\square$

A similar argument using permanents of submatrices applies to the induced trivial characters of $S_n$.

**Theorem 2.3** Let P be a labeled poset and let $\lambda$ be a partition of $|P|$. Then $\eta^{\lambda}(\beta(P))$ equals the number of row-semistrict P-tableaux of shape $\lambda$.

**Proof:** Omitted. $\square$

## 3 (3 + 1)-free posets and chromatic symmetric functions

To state more results and conjectures concerning the interpretation of $S_n$ class functions, we restrict our attention to special classes of posets. The following standard definitions concerning posets may be found in [17, Ch. 3] and [21, Sec. 9.2]. Given posets P, Q, let $P \oplus Q$ be the $(|P| + |Q|)$-element poset whose Hasse diagram is that for P written below that for Q, i.e., with every element of P being less than every element of Q. Letting $n$ denote an $n$-element chain $x_1 <_P \cdots <_P x_n$, we have, e.g., $4 \cong 1 \oplus 1 \oplus 1 \oplus 1$. Let $P + Q$ be the $(|P| + |Q|)$-element poset which is a disjoint union of P and Q, i.e., the poset whose Hasse diagrams is that for P written beside that for Q, with all elements of P being incomparable to all
elements of $Q$. Thus $a + b$ is the disjoint union of an $a$-element chain and a $b$-element chain. We say that $P$ is ($a + b$)-free if no induced subposet of $P$ is isomorphic to $a + b$. Call $P$ an interval order if it is $(2+2)$-free, and a unit interval order if it is $(2+2)$-free and $(3+1)$-free.

While no true analog of Theorem 2.2 and 2.3 is known for $\chi^{\lambda}(\beta(P))$ and $\phi^{\lambda}(\beta(P))$, some results exist for special cases of $\lambda$ and for $P$ belonging to one of the above classes of posets.

**Proposition 3.1** Let $P$ be a labeled $(3+1)$-free poset and let $\lambda$ be a partition of $|P|$.

(1) $\chi^{\lambda}(\beta(P))$ equals the number of standard $P$-tableaux of shape $\lambda$ [2, Thm. 2].

(2) If $P$ is a unit interval order and $\lambda_1 \le 2$, then $\phi^{\lambda}(\beta(P))$ equals zero if there exists a column-strict $P$-tableaux of shape $\mu < \lambda$ in the dominance order; otherwise it equals the number of column-strict $P$-tableaux of shape $\lambda$ [1, Thm. 5.7].

(3) If $P$ is a unit interval order and $\lambda = (k, \dots, k)$, then $\phi^{\lambda}(\beta(P))$ equals the number of ways to cover $P$ with certain cycles [20, Thm. 2.8].

Furthermore, Stembridge's [20, Conj. 2.1] has the following special case.

**Conjecture 3.2** Let $P$ be a labeled unit interval order and let $\lambda$ be a partition of $|P|$. Then we have $\phi^{\lambda}(\beta(P)) \ge 0$.

Even with this restriction on $P$, there is no conjectured combinatorial interpretation for $\phi^{\lambda}(\beta(P))$ which applies to all $\lambda$.

One property of unit interval orders $P$ which facilitates combinatorial interpretation is the fact that certain labelings of $P$ cause the antiadjacency matrix $A(P)$ and the $\mathbb{Z}[S_n]$ element $\beta(P)$ to have particularly nice forms. Define the *altitude* of a poset element $i$ to be $\alpha(i) = \#\{x | x <_P i\} - \#\{x | x >_P i\}$. Call a labeling an *altitude respecting* or *ar-labeling* if $i < j$ whenever $\alpha(i) < \alpha(j)$. It is known that every *ar-labeling* of a $(3+1)$-free poset is natural. It is also known that in the antiadjacency matrix corresponding to an *ar-labeling* of an $n$-element unit interval order, the zero entries form a right justified Young diagram which fits inside the right justified shape $(n-1, \dots, 1)$. (See [21, Sec. 8.2].) In Proposition 4.1 we will prove that this special form of the antiadjacency matrix implies a nice expression for $\beta(P)$,

$$ \beta(P) = \frac{C'_{[i_1, j_1]} \cdots C'_{[i_m, j_m]}}{k}, \quad i_1 < \cdots < i_m, \quad j_1 < \cdots < j_m, \quad k \in \mathbb{N}. \quad (10) $$

$S_n$ class functions may be used to define Stanley's chromatic symmetric function [15] for a poset $P$,

$$ X_P = \sum_{\lambda \vdash n} c_{\lambda} m_{\lambda}, \quad (11) $$

where $c_{\lambda}$ is the number of ways to partition $P$ into a sequence of $r$ chains of sizes $(\lambda_1, \dots, \lambda_r)$ respectively, and to assign color $k$ to the $k$th chain. Equivalently, we have $c_{\lambda} = \epsilon^{\lambda}(\beta(P))$. The transition matrices of Kostka numbers in (1) imply furthermore that we have

$$ X_P = \sum_{\lambda \vdash n} \epsilon^{\lambda}(\beta(P)) m_{\lambda} = \sum_{\lambda \vdash n} \chi^{\lambda^{\top}}(\beta(P)) s_{\lambda} = \sum_{\lambda \vdash n} \phi^{\lambda}(\beta(P)) e_{\lambda}. \quad (12) $$
Monomial nonnegative by definition, the chromatic symmetric functions are sometimes Schur nonnegative and even elementary nonnegative as well. For example, the four posets $P = 3, 2+1, (1+1) \oplus 1, 1+1+1$ and their chromatic symmetric functions $X_P$ are

<figure><img src="image_1.png" /></figure>

$$ 
\begin{aligned}
X_P &= 6m_{111} + 3m_{21} + m_3 \\
&= s_{111} + 2s_{21} + s_3 \\
&= e_{111},
\end{aligned}
 $$

<figure><img src="image_2.png" /></figure>

$$ 
\begin{aligned}
X_P &= 6m_{111} + m_{21} \\
&= 4s_{111} + s_{21} \\
&= 3e_3 + e_{21},
\end{aligned}
 $$

<figure><img src="image_3.png" /></figure>

$$ 
\begin{aligned}
X_P &= 6m_{111} + 2m_{21} \\
&= 2s_{111} + 2s_{21} \\
&= 2e_{21},
\end{aligned}
 $$

<figure><img src="image_4.png" /></figure>

$$ 
\begin{aligned}
X_P &= 6m_{111} \\
&= 6s_{111} \\
&= 6e_3.
\end{aligned}
 $$

These nonnegativity phenomena are addressed in the following result of Gasharov [2, Thm. 2] and conjecture of Stanley and Stembridge [15, Conj. 5.1], [18, Conj. 5.5].

**Theorem 3.3** If $P$ is $(3+1)$-free, then $X_P$ is Schur nonnegative.

**Conjecture 3.4** If $P$ is $(3+1)$-free, then $X_P$ is elementary nonnegative.

By (12), Theorem 3.3 is equivalent to Proposition 3.1 (1), Conjecture 3.4 is stronger than Conjecture 3.2, and two special cases of Conjecture 3.4 have been proved in Proposition 3.1 (2)-(3).

# 4 The Hecke algebra and quantum polynomial ring in $n^2$ variables

Let $H_n(q)$ be the (type A) Hecke algebra, the noncommutative $\mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-algebra with multiplicative identity $T_e = 1$, generated by $T_{s_1}, \dots, T_{s_{n-1}}$, subject to relations

$$ 
\begin{aligned}
T_{s_i}^2 &= (q-1)T_{s_i} + qT_e, && \text{for } i=1, \dots, n-1, \\
T_{s_i}T_{s_j}T_{s_i} &= T_{s_j}T_{s_i}T_{s_j}, && \text{if } |i-j|=1, \\
T_{s_i}T_{s_j} &= T_{s_j}T_{s_i}, && \text{if } |i-j| \ge 2.
\end{aligned}
 \quad (14) $$

If $s_{i_1} \cdots s_{i_l}$ is (any) reduced expression for $v \in S_n$ we define $T_v = T_{s_{i_1}} \cdots T_{s_{i_l}}$. The $n!$ elements $\{T_v | v \in S_n\}$ are a basis of $H_n(q)$ as a $\mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-module.

Let $\chi_q^\lambda$ be the irreducible $H_n(q)$ character indexed by $\lambda$, and let $\epsilon_q^\lambda$ and $\eta_q^\lambda$ be the sign and trivial characters induced from Young subalgebras of type $\lambda$. All of these $H_n(q)$ characters are $H_n(q)$ traces, i.e., they satisfy $f_q(gh) = f_q(hg)$ for $g, h \in H_n(q)$. Like a class function, a trace $f_q$ satisfies $f_q(g^{-1}hg) = f_q(h)$ whenever $g$ is invertible. Define $\phi_q^\lambda = \sum_\mu K_{\lambda,\mu} \chi_q^\mu$ to be the monomial trace indexed by $\lambda$. These sets of traces form four bases for the space of $H_n(q)$ traces and are related to one another by the same transition matrices of Kostka numbers (1) that relate the $S_n$ class function bases used in Sections 1-3:

$$ \eta_q^\lambda = \sum_{\mu \vdash n} K_{\mu, \lambda} \chi_q^\mu, \quad \epsilon_q^\lambda = \sum_{\mu \vdash n} K_{\mu, \lambda} \chi_q^\mu, \quad \chi_q^\lambda = \sum_{\mu \vdash n} K_{\lambda, \mu} \phi_q^\mu. \quad (15) $$

(See, e.g., [3].) For none of these traces $f_q$ do we have a known combinatorial interpretation of $f_q(T_v)$ for all $v \in S_n$. Neither do we have a known combinatorial interpretation of

$$ f_q(C'_{[i_1, j_1]}(q) \cdots C'_{[i_m, j_m]}(q)), \quad (16) $$
where

$$C'_{[i,j]}(q) = \underset{\text{def}}{q^{-\frac{\ell(w)}{2}}} \sum_{v \in S_{[i,j]}} T_v,$$

and $w$ is the longest element in $S_{[i,j]}$. We therefore consider special cases of the elements (16) which are quantum analogs of the elements $\beta(P)$ in $\mathbb{Z}[S_n]$. To any labeled $n$-element poset $P$ we may associate an element $\beta_q(P)$ of $H_n(q)$ by

$$\beta_q(P) = \sum_{v \in S_n} T_v, \qquad (17)$$

where the sum is over all permutations $v \in S_n$ satisfying $i \prec_P v_i$ for all $i$. The ar-labeling of a unit interval order $P$ gives a nice expression for $\beta_q(P)$.

**Proposition 4.1** Let $P$ be an ar-labeled $n$-element unit interval order. Then there exist subintervals $[i_1, j_1], \dots, [i_m, j_m]$ of $[n]$ with $i_1 < \dots < i_m, j_1 < \dots < j_m$, a polynomial $p \in \mathbb{N}[q]$, a 3412-avoiding, 4231-avoiding permutation $w = w(P)$ in $S_n$, and a nonnegative integer $c$ such that

$$\beta_q(P) = \frac{q^{\frac{\ell(w)+c}{2}} C'_{[i_1, j_1]}(q) \cdots C'_{[i_m, j_m]}(q)}{p(q)} = \sum_{v \le w} T_v. \qquad (18)$$

**Proof:** (Idea.) The $n$-element unit interval orders correspond bijectively to certain planar networks $G$ having $n$ source and $n$ sink vertices, with each such network being composed of smaller networks indexed by intervals $[i_1, j_1], \dots, [i_m, j_m]$. For each such planar network $G$, one defines a matrix $B = (b_{i,j})$ by setting $b_{i,j} = 1$ if there exists a path from source $i$ to sink $j$, and $b_{i,j} = 0$ otherwise. One also defines an element $\beta_q(G) = \sum_v b_{1,v_1} \cdots b_{n,v_n} T_v$ of $H_n(q)$. If in the above bijection $G$ corresponds to $P$, then one can show that the adjacency matrix $A$ of $P$ satisfies $a_{1,v_1} \cdots a_{n,v_n} = b_{1,v_1} \cdots b_{n,v_n}$ for all $v \in S_n$ (although $A$ and $B$ are not in general equal). Thus we have $\beta_q(P) = \beta_q(G)$.

By [14, Thm. 4.3], there exist a certain nonnegative integer $c$ and a 3412-, 4231-avoiding permutation $w \in S_n$ associated to $G$ such that $q^{-\frac{\ell(w)}{2}} \beta_q(G)$ is equal to $q^{\frac{c}{2}} C'_{[i_1, j_1]}(q) \cdots C'_{[i_m, j_m]}(q)$ divided by a polynomial in $\mathbb{N}[q]$. By [14, Lem. 5.3], $w$ also satisfies

$$b_{1,v_1} \cdots b_{n,v_n} = \begin{cases} 1 & \text{if } v \le w \\ 0 & \text{otherwise.} \end{cases} \qquad (19)$$

Thus we have $\beta_q(P) = \beta_q(G) = \sum_{v \le w} T_v$. $\square$

For $P$ an ar-labeled unit interval order, let $w(P)$ denote the permutation appearing in the above proposition. We remark that by results in [9], $\beta_q(P)$ is equal to $q^{-\frac{\ell(w)}{2}}$ times the Kazhdan-Lusztig basis element $C'_{w(P)}(q)$ of $H_n(q)$ [7], and the factors $C'_{[i,j]}(q)$ also are Kazhdan-Lusztig basis elements.

Even for the special case (18) of (16), there is no published combinatorial interpretation for $f_q(\beta_q(P))$ when $f_q \in \{\chi_q^\lambda, \eta_q^\lambda, \epsilon_q^\lambda, \phi_q^\lambda\}$. On the other hand, Haiman's [6, Lem. 1.1, Conj. 2.1] have the following special cases which suggest that combinatorial interpretations for some of these expressions should exist.

**Proposition 4.2** Let $P$ be an ar-labeled unit interval order and let $\lambda$ be a partition of $|P|$. Then we have $\chi_q^\lambda(\beta_q(P)) \in \mathbb{N}[q]$, and therefore $\epsilon_q^\lambda(\beta_q(P)) \in \mathbb{N}[q]$ and $\eta_q^\lambda(\beta_q(P)) \in \mathbb{N}[q]$.
**Conjecture 4.3** Let $P$ be an ar-labeled unit interval order and let $\lambda$ be a partition of $|P|$. Then we have $\phi_q^\lambda(\beta_q(P)) \in \mathbb{N}[q]$.

In Section 5 we give a combinatorial interpretation for the polynomial $\epsilon_q^\lambda(q_{e,w}\beta_q(P))$ for $P$ an ar-labeled unit interval order. To do this, we employ a quantum analog of the identity (9) which holds in the quantum polynomial ring $\mathcal{A}_n(q)$. Let $\mathcal{A}_n(q)$ be the noncommutative $\mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-algebra generated by $n^2$ variables $x = (x_{1,1}, \dots, x_{n,n})$, subject to the relations

$$ 
\begin{align} 
x_{i,\ell}x_{i,k} &= q^{\frac{1}{2}}x_{i,k}x_{i,\ell}, & x_{j,k}x_{i,\ell} &= x_{i,\ell}x_{j,k}, \tag{20} \\ 
x_{j,k}x_{i,k} &= q^{\frac{1}{2}}x_{i,k}x_{j,k}, & x_{j,\ell}x_{i,k} &= x_{i,k}x_{j,\ell} + (q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}})x_{i,\ell}x_{j,k}, 
\end{align} 
$$

for all indices $1 \le i < j \le n$ and $1 \le k < \ell \le n$.

$\mathcal{A}_n(q)$ is a multigraded $\mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-module whose components $\mathcal{A}_{L,M}(q)$ are spanned by monomials having a fixed multiset $L$ of row indices and a fixed multiset $M$ of column indices. In particular, the component $\mathcal{A}_{[n],[n]}(q)$ contains monomials having total degree $n$, with all row indices and all column indices appearing exactly once. Defining $x^{u,v} = x_{u_1,v_1} \cdots x_{u_n,v_n}$ for $u, v \in S_n$, we thus have

$$ \mathcal{A}_{[n],[n]}(q) = \operatorname{span}\{x^{u,v} \mid u, v \in S_n\}. $$

By the relations (20), each multigraded component has a $\mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-basis of monomials in which variables appear in lexicographic order. Thus the component $\mathcal{A}_{[n],[n]}(q)$ has the natural basis $\{x^{e,v} \mid v \in S_n\}$, and contains the quantum determinant, defined by

$$ \det_q(x) = \sum_{v \in S_n} (-\bar{q}^{\frac{1}{2}})^{\ell(v)} x^{e,v}. $$

The quantized Littlewood-Merris-Watkins identity, due to Konvalinka and the second author [8, Thm. 5.4], gives generating functions for the induced sign characters of $H_n(q)$.

**Theorem 4.4** Fix any partition $\lambda \vdash n$. Then in $\mathcal{A}_{[n],[n]}(q)$ we have the identity

$$ \sum_{(I_1, \dots, I_r)} \det_q(x_{I_1, I_1}) \cdots \det_q(x_{I_r, I_r}) = \sum_{v \in S_n} \epsilon_q^\lambda (q^{\frac{\ell(v)}{2}} T_v) x^{e,v}, \quad (21) $$

where the first sum is over all ordered set partitions of $[n]$ of type $\lambda$.

# 5 Main results

Recall that for $P$ a unit interval order with antiadjacency matrix $A$, the combinatorial interpretation of $\beta(P)$ in Theorem 2.2 follows immediately from the evaluation of both sides of the classical Littlewood-Merris-Watkins identity (9) at $x = A$. However, the quantum analog (21) of this identity does not allow us to compute $\epsilon^\lambda(\beta_q(P))$ as the evaluation of the left-hand side at $x = A$, since the noncommuting variables $(x_{i,j})$ satisfy nontrivial relations. If we are to use the left-hand side of (21) to understand $\epsilon^\lambda(\beta_q(P))$, we must first express it in terms of the natural basis $\{x^{e,v} \mid v \in S_n\}$. We therefore define a family of maps as follows. For each matrix $A \in \operatorname{Mat}_{n \times n}(\mathbb{Z})$, let $\sigma_A : \mathcal{A}_{[n],[n]}(q) \to \mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$ be the $\mathbb{Z}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-linear map defined by

$$ \sigma_A(x^{e,v}) = q^{\frac{\ell(v)}{2}} a_{1,v_1} \cdots a_{n,v_n}. $$

This definition has the following immediate consequence.
**Proposition 5.1** Let $P$ be an ar-labeled poset with antiadjacency matrix $A$, let $w = w(P)$, and let $\lambda$ be a partition of $n = |P|$. Then we have

$$ \sum_{(I_1, \dots, I_r)} \sigma_A(\det_q(x_{I_1, I_1}) \cdots \det_q(x_{I_r, I_r})) = \epsilon_q^{\lambda}(\beta_q(P)), \qquad (22) $$

where the sum is over all ordered set partitions of $[n]$ of type $\lambda$.

**Proof:** The left-hand side of (22) equals

$$ \sigma_A \left( \sum_{v \in S_n} \epsilon_q^{\lambda} \left( q^{\frac{-\ell(v)}{2}} T_v \right) x^{e,v} \right) = \sum_{v \in S_n} \epsilon_q^{\lambda} (T_v) q^{\frac{-\ell(v)}{2}} \sigma_A(x^{e,v}) = \epsilon_q^{\lambda} \left( \sum_{v \le w} T_v \right) = \epsilon_q^{\lambda} (\beta_q(P)), $$

since the proof of Proposition 4.1 implies that $a_{1,v_1} \cdots a_{n,v_n}$ is 1 if $v \le w$ and is 0 otherwise. $\square$

To combinatorially interpret each term on the left-hand side of (22), we introduce the following statistic on $P$-tableaux. Given a $P$-tableau $U$, define an inversion in $U$ to be a pair $(i, j)$ of incomparable elements in $P$ satisfying $i < j$, with $i$ appearing in a column of $U$ to the right of the column containing $j$. Let $\text{INV}(U)$ denote the number of inversions in $U$.

**Lemma 5.2** Let $P$ be a labeled unit interval order with antiadjacency matrix $A$, let $\lambda$ be a partition of $n = |P|$, let $(I_1, \dots, I_r)$ be an ordered set partition of $[n]$ of type $\lambda$, and let $U$ be the $P$-tableau whose $j$th column contains the poset elements labeled by $I_j$, with labels increasing upward in that column. If $U$ is a column-strict $P$-tableau, then we have

$$ \sigma_A(\det_q(x_{I_1, I_1}) \cdots \det_q(x_{I_r, I_r})) = q^{\text{INV}(U)}. \qquad (23) $$

**Proof:** Omitted. $\square$

The authors believe that if we keep the hypotheses of Lemma 5.2, but assume that the $P$-tableau $U$ is not column-strict, then $\sigma_A(\det_q(x_{I_1, I_1}) \cdots \det_q(x_{I_r, I_r}))$ vanishes. In light of Proposition 5.1, we thus have the following conjecture.

**Conjecture 5.3** Let $P$ be an ar-labeled unit interval order, and let $\lambda$ be a partition of $|P|$. Then we have

$$ \epsilon_q^{\lambda}(\beta_q(P)) = \sum_{U} q^{\text{INV}(U)}, \qquad (24) $$

where the sum is over all column-strict $P$-tableaux of shape $\lambda^T$.

For example, let $P$ be the poset $2+1$ with its unique ar-labeling

<figure><img src="image_5.png" /></figure>

and its two pairs of incomparable elements $(1, 2)$ and $(2, 3)$. Then there are six column-strict $P$-tableaux of shape $111^T = 3$, one of shape $21^T = 21$, and none of shape $3^T = 111$. Enumerating these and indicating inversions by arrows, we have

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>
Comparing these tableaux with the known evaluations

$$ \epsilon_q^{111}(\beta_q(P)) = 1 + 4q + q^2, \quad \epsilon_q^{21}(\beta_q(P)) = q, \quad \epsilon_q^3(\beta_q(P)) = 0, \qquad (26) $$

we see that Conjecture 5.3 holds in this case.

Shaeshian and Wachs [13] defined a quantum analog of Stanley's chromatic symmetric function. Given a labeled poset P, their quantum chromatic quasisymmetric function for P is the sum

$$ X_{P,q} = \sum_{\kappa} q^{\#\{(i,j) \mid i \not\le_P j, j \not\le_P i, i < j, \kappa(i) > \kappa(j)\}} \prod_{k \in \mathbb{P}} x_k^{\#\{i \in P \mid \kappa(i) = k\}} \qquad (27) $$

over all colorings $\kappa: P \to \mathbb{N}$ of P, where a function $\kappa$ is termed a coloring if it satisfies $\kappa(i) \neq \kappa(j)$ whenever i and j are incomparable in P. By [13, Prop. 4.4], when P is an n-element ar-labeled unit interval order then $X_{P,q}$ is in fact symmetric,

$$ X_{P,q} = \sum_{\lambda \vdash n} c_{\lambda,q} m_{\lambda}, \qquad (28) $$

and it follows that $c_{\lambda,q} = \sum_U q^{\mathrm{INV}(U)}$, where the sum is over all column-strict P-tableaux of shape $\lambda^\top$. For example, when the four unit interval orders in (13) are ar-labeled, their quantum chromatic symmetric functions are

$$ \begin{aligned} X_{3,q} &= 6m_{111} + 3m_{21} + m_3 & X_{2+1,q} &= (1 + 4q + q^2)m_{111} + qm_{21} \\ &= s_{111} + 2s_{21} + s_3 & &= (1 + 2q + q^2)s_{111} + qs_{21} \\ &= e_{111}, & &= (1 + q + q^2)e_3 + qe_{21}, \end{aligned} $$

$$ \begin{aligned} X_{(1+1)\oplus 1,q} &= (3+3q)m_{111} + (1+q)m_{21} & X_{1+1+1,q} &= (1+2q+2q^2+q^3)m_{111} \\ &= (1+q)s_{111} + (1+q)s_{21} & &= (1+2q+2q^2+q^3)s_{111} \\ &= (1+q)e_{21}, & &= (1+2q+2q^2+q^3)e_3. \end{aligned} $$

Now Conjecture 5.3 and Equation (15) imply the following.

**Conjecture 5.4** If P is an n-element ar-labeled unit interval order then the Shaeshian-Wachs quantum chromatic symmetric function satisfies

$$ X_{P,q} = \sum_{\lambda \vdash n} \epsilon_q^{\lambda}(\beta_q(P)) m_{\lambda} = \sum_{\lambda \vdash n} \chi_q^{\lambda^\top}(\beta_q(P)) s_{\lambda} = \sum_{\lambda \vdash n} \phi_q^{\lambda}(\beta_q(P)) e_{\lambda}. $$

Shaeshian and Wachs have formulated the following quantum analog [13, Conj. 4.8] of Stanley and Stembridge's [15, Conj. 5.1] ([18, Conj. 5.5]).

**Conjecture 5.5** If P is an ar-labeled unit interval order, then the coefficients arising in the elementary expansion of $X_{P,q}$ belong to $\mathbb{N}[q]$.

By Conjecture 5.4, the authors believe this to be equivalent to the special case of Haiman's [6, Conj. 2.1] which we have stated in Conjecture 4.3. Furthermore, Shaeshian and Wachs have proved the following weaker result [13, Thm. 4.11], which is a quantum analog of the special case of Gasharov's [2, Thm. 2] stated in Theorem 3.3.
**Theorem 5.6** If $P$ is an ar-labeled unit interval order, then the coefficient of $s_\lambda$ in the Schur expansion of $X_{P,q}$ is $\sum_U q^{\mathrm{INV}(U)}$, where the sum is over all semistandard $P$-tableaux of shape $\lambda^\top$.

This coincides with the authors' conjectured interpretation of the irreducible $H_n(q)$ characters.

**Conjecture 5.7** If $P$ is an ar-labeled unit interval order and $w = w(P)$, then $\chi_q^\lambda(\beta_q(P)) = \sum_U q^{\mathrm{INV}(U)}$, where the sum is over all semistandard $P$-tableaux of shape $\lambda^\top$.

Since Theorem 3.3 and Conjecture 3.4 apply to $(\mathfrak{3} + \mathfrak{1})$-free posets, it would be interesting to see if the symmetry of $X_{P,q}$ holds more generally for ar-labeled $(\mathfrak{3} + \mathfrak{1})$-free posets, and to interpret $\epsilon_q^\lambda(\beta_q(P))$, $\eta_q^\lambda(\beta_q(P))$, and $\chi_q^\lambda(\beta_q(P))$ in these cases.

## References

[1] S. CLEARMAN, B. SHELTON, AND M. SKANDERA. Path tableaux and combinatorial interpretations of immanants for class functions of $S_n$. In *23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)*, Discrete Math. Theor. Comput. Sci. Proc., AO. Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2011), pp. 233–244.

[2] V. GASHAROV. Incomparability graphs of $(\mathfrak{3} + \mathfrak{1})$-free posets are $s$-positive. *Discrete Math.*, **157** (1996) pp. 211–215.

[3] M. GECK AND G. PFEIFFER. *Characters of finite Coxeter groups and Iwahori-Hecke algebras*, vol. 21 of *London Mathematical Society Monographs. New Series*. The Clarendon Press Oxford University Press, New York (2000).

[4] I. P. GOULDEN AND D. M. JACKSON. Immanants of combinatorial matrices. *J. Algebra*, **148** (1992) pp. 305–324.

[5] C. GREENE. Proof of a conjecture on immanants of the Jacobi-Trudi matrix. *Linear Algebra Appl.*, **171** (1992) pp. 65–79.

[6] M. HAIMAN. Hecke algebra characters and immanant conjectures. *J. Amer. Math. Soc.*, **6**, 3 (1993) pp. 569–595.

[7] D. KAZHDAN AND G. LUSZTIG. Representations of Coxeter groups and Hecke algebras. *Invent. Math.*, **53** (1979) pp. 165–184.

[8] M. KONVALINKA AND M. SKANDERA. Generating functions for Hecke algebra characters. *Canad. J. Math.*, **63**, 2 (2011) pp. 413–435.

[9] V. LAKSHMIBAI AND B. SANDHYA. Criterion for smoothness of Schubert varieties in $SL(n)/B$. *Proc. Indian Acad. Sci. (Math Sci.)*, **100**, 1 (1990) pp. 45–52.

[10] D. E. LITTLEWOOD. *The Theory of Group Characters and Matrix Representations of Groups*. Oxford University Press, New York (1940).

[11] R. MERRIS AND W. WATKINS. Inequalities and identities for generalized matrix functions. *Linear Algebra Appl.*, **64** (1985) pp. 223–242.
[12] B. SAGAN. *The Symmetric Group*. Springer, New York (2001).

[13] J. SHARESHIAN AND M. WACHS. Chromatic quasisymmetric functions and Hessenberg varieties (2011). Preprint math.CO/1106.4287v1 on ArXiv.

[14] M. SKANDERA. On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations. *J. Pure Appl. Algebra*, **212** (2008).

[15] R. STANLEY. A symmetric function generalization of the chromatic polynomial of a graph. *Adv. Math.*, **111** (1995) pp. 166-194.

[16] R. STANLEY. A matrix for counting paths in acyclic digraphs. *J. Combin. Theory Ser. A*, **74** (1996) pp. 169-172.

[17] R. STANLEY. *Enumerative Combinatorics*, vol. 1. Cambridge University Press, Cambridge (1997).

[18] R. STANLEY AND J. R. STEMBRIDGE. On immanants of Jacobi-Trudi matrices and permutations with restricted positions. *J. Combin. Theory Ser. A*, **62** (1993) pp. 261-279.

[19] J. STEMBRIDGE. Immanants of totally positive matrices are nonnegative. *Bull. London Math. Soc.*, **23** (1991) pp. 422-428.

[20] J. STEMBRIDGE. Some conjectures for immanants. *Can. J. Math.*, **44**, 5 (1992) pp. 1079-1099.

[21] W. T. TROTTER. *Combinatorics and Partially Ordered Sets: Dimension Theory*. Johns Hopkins University Press, Baltimore (1992).