# Shortest path poset of Bruhat intervals

Saúl A. Blanco†

Department of Mathematics, Cornell University, Ithaca, NY, USA

**Abstract.** Let $[u, v]$ be a Bruhat interval and $B(u, v)$ be its corresponding Bruhat graph. The combinatorial and topological structure of the longest $u-v$ paths of $B(u, v)$ has been extensively studied and is well-known. Nevertheless, not much is known of the remaining paths. Here we describe combinatorial properties of the shortest $u-v$ paths of $B(u, v)$. We also derive the non-negativity of some coefficients of the complete cd-index of $[u, v]$.

**Résumé.** Soit $[u, v]$ un intervalle de Bruhat et $B(u, v)$ le graphe de Bruhat associé. La structure combinatoire et topologique des plus longs chemins de $u$ à $v$ dans $B(u, v)$ est bien comprise, mais on sait peu de chose des autres chemins. Nous décrivons ici les propriétés combinatoires des plus courts de chemins de $u$ à $v$. Nous prouvons aussi que certains coefficients du cd-indice complet de $[u, v]$ sont positifs.

**Keywords:** Bruhat interval, shortest-path poset, complete cd-index

# 1 Introduction

While the paths of the Bruhat graph $B(u, v)$ of the Bruhat interval $[u, v]$ only depend on the isomorphism type of $[u, v]$ (see [Dye91]), all of the $u-v$ paths of $B(u, v)$ are needed to compute the $\tilde{R}$-polynomial, as well as the complete cd-index of $[u, v]$. Unfortunately, the structure of $B(u, v)$ is not easy to understand. Thus we focus on the shortest paths of $B(u, v)$, since their combinatorial structure is more manageable. In particular, they form a Hasse diagram of a poset, which we denote by $SP(u, v)$.

The order of the paper is as follows: In Section 2 we summarize the basic properties of $SP(u, v)$, and describe their structure two specific cases: (i) if $W$ is finite, with $u = e$ and $v = w_0^W$ (longest-length element of $W$) and (ii) if the number of rising chains (under a reflection order) is one. In Section 2.3 we provide an algorithm that allows us to separate the chains in $SP(u, v)$ into subposets, each of which has properties resembling properties of $[u, v]$. In Section 3 we derive consequences of the work done to the complete cd-index.

## 1.1 Basic definitions

Let $(W, S)$ be a Coxeter system, and let $T \stackrel{\text{def}}{=} T(W) = \{wsw^{-1} : s \in S, w \in W\}$ be the set of reflections of $(W, S)$. The Bruhat graph of $(W, S)$, denoted by $B(W, S)$ or simply $B(W)$, is the directed graph with vertex set $W$, and a directed edge $w_1 \to w_2$ between $w_1, w_2 \in W$ if $\ell(w_1) < \ell(w_2)$ and there exists $t \in T$ with $tw_1 = w_2$. Here $\ell$ denotes the length function of $(W, S)$. The edges of $B(W)$ are labeled

<footnote>†The author was supported in part by NSF grant DMS-0555268.</footnote>
by reflections; for instance the edge $w_1 \to w_2$ is labeled with $t$. The Bruhat graph of an interval $[u, v]$,
denoted by $B(u, v)$, is the subgraph of $B(W)$ obtained by only considering the elements of $[u, v]$. A *path*
in the Bruhat graph $B(u, v)$, will always mean a *directed path* from $u$ to $v$. As it is the custom, we will
label these paths by listing the edges that are used. Furthermore, we denote the set of paths of length $k$ in
$B(u, v)$ by $B_k(u, v)$.

A *reflection order* $<_T$ is a total order of $T$ so that $r <_T rtr <_T rtrtr <_T \dots <_T trt <_T t$ or $t <_T trt <_T trtrt <_T \dots <_T rtr <_T r$ for each Coxeter system $(\langle r, t \rangle, \{r, t\})$ where $r, t \in T$. Let $\Delta = (t_1, t_2, \dots, t_k)$ be a path in $B(u, v)$, and define the *descent set* of $\Delta$ by $D(\Delta) = \{j : t_{j+1} <_T t_j\} \subset [k-1]$. If $D(\Delta) = \emptyset$, we say that $\Delta$ is rising.

Let $w(\Delta) = x_1x_2\cdots x_{k-1}$, where $x_i = \mathbf{a}$ if $t_i < t_{i+1}$, and $x_i = \mathbf{b}$, otherwise. In other words, set $x_i$
to **a** if $i \notin D(\Delta)$ and to **b** if $i \in D(\Delta)$. Billera and Brenti [BB] showed that $\sum_{\Delta \in B(u,v)} w(\Delta)$ becomes
a polynomial in the variables **c** and **d**, where $\mathbf{c} = \mathbf{a} + \mathbf{b}$ and $\mathbf{d} = \mathbf{ab} + \mathbf{ba}$. This polynomial is called the
*complete cd-index* of $[u, v]$, and it is denoted by $\tilde{\psi}_{u,v}(\mathbf{c}, \mathbf{d})$. Notice that the complete cd-index of $[u, v]$
is an encoding of the distribution of the descent sets of each path $\Delta$ in the Bruhat graph of $[u, v]$, and thus
seems to depend on $<_T$. However, it can be shown that this is not the case. For details on the complete
cd-index, see [BB].

As an example, consider $S_3$ with generators $s_1 = (1 \ 2)$ and $s_2 = (2 \ 3)$. Then $t_1 = s_1 <_T t_2 = s_1s_2s_1 <_T t_3 = s_2$ is a reflection ordering. The paths of length 3 are: $(t_1, t_2, t_3)$, $(t_1, t_3, t_1)$, $(t_3, t_1, t_3)$, and $(t_3, t_2, t_1)$, that encode to $\mathbf{a}^2 + \mathbf{ab} + \mathbf{ba} + \mathbf{b}^2 = \mathbf{c}^2$. There is one path of length 1, namely $t_2$, which encodes simply to 1. So $\tilde{\psi}_{u,v}(\mathbf{c}, \mathbf{d}) = \mathbf{c}^2 + 1$.

Given a monomial $m \in \mathbb{Z}\langle\mathbf{c}, \mathbf{d}\rangle$, we denote the coefficient of $m$ in $\tilde{\psi}_{u,v}(\mathbf{c}, \mathbf{d})$ by $[m]_{u,v}$. Notice that $[\mathbf{c}^n]_{u,v}$ is the number of rising paths in $B_{n+1}(u, v)$.

## 2 Shortest path poset

We begin with some basic properties of $SP(u, v)$.

**Proposition 2.1** Let $[u, v]$ be a Bruhat interval, then the undirected edges of the shortest paths of $B(u, v)$ form the Hasse diagram of a poset.

We point out that in general the edges of paths in $B_k(u, v)$ need not form a Hasse diagram of a poset.
Indeed, it is possible to have elements $u \le x_0 < x_1 < x_2 < x_3 \le v$ so that $x_0 \to x_1 \to x_2 \to x_3$ and
$x_0 \to x_3$ are all in $B(u, v)$.

We call the poset of Proposition 2.1, the *shortest path poset* of $[u, v]$, and we denote it by $SP(u, v)$.
Furthermore, the edges of the Hasse diagram of $SP(u, v)$ inherit the labels of the corresponding edges in
$B(u, v)$. In particular, we say that a maximal chain $C$ in $SP(u, v)$ is *rising* if the path corresponding to
$C$ in $B(u, v)$ is *rising*.

**Proposition 2.2** $SP(u, v)$ is a graded poset, and for $x \in SP(u, v)$, the rank of $x$ is the length of the shortest $u-x$ path in $B(u, x)$.

To illustrate the definition consider $B_2$ and $SP(e, \underline{12})$ as depicted in Figure 1. Notice that the rank of $SP(e, \underline{12})$ is 2, the length of the shortest paths in $B(B_2)$.
<figure><img src="image_1.png" /><figcaption>Fig. 1: $B(B_2)$ and $SP(B_2)$.</figcaption></figure>

## 2.1 Finite Coxeter groups

For any finite Coxeter group $W$, there is a word $w_0^W$ of maximal length. It is a well-known fact that $\ell(w_0^W) = |T|$. For any $w \in W$, one can write $t_1t_2 \cdots t_n = w$ for some $t_1, t_2, \dots, t_n \in T$. If $n$ is minimal, then we say that $w$ is *T-reduced*, and that the *absolute length* of $w$ is $n$. We write $\ell_T(w) = n$.

Notice that for $w \in W$, if $\ell_T(w) = m$, then $t_1t_2 \cdots t_m = w$ for some reflections in $T$, but this does not mean that $(t_1, t_2, \dots, t_m)$ is a (directed) path in $B(e, w)$. Nevertheless, for finite $W$ and $w = w_0^W$, $(t_1, t_2, \dots, t_m)$ and any of its permutations $(t_{\tau(1)}, t_{\tau(2)}, \dots, t_{\tau(m)})$, $\tau \in A_{m-1}$, are paths in $B(W)$ (see Theorem 2.3 below).

Let $SP(W)$ denote the poset $SP(e, w_0^W)$. The combinatorial structure of $SP(W)$ was described in [Bla09]. For the sake of completeness, we include the main results therein.

**Theorem 2.3** Let $W$ be a finite Coxeter group and $\ell_0 = \ell_T(w_0^W)$, the absolute length of the longest element of $W$. Then $SP(W)$ is isomorphic to the union of Boolean posets of rank $\ell_0$. Each copy of $B(\ell_0)$ share at least $e$ and $w_0^W$

We summarize the number of Boolean posets that form $SP(W)$ and the rank of $SP(W)$ for each finite Coxeter group in Table 1.

where

$$b_n = 1 + \sum_{j=1}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{j!} \prod_{i=0}^{j-1} \binom{n-2i}{2}.$$

and

$$d_m = \frac{1}{\lfloor \frac{m}{2} \rfloor!} \prod_{i=0}^{\lfloor \frac{m}{2} \rfloor - 1} \binom{m-2i}{2}$$

where $m = n$ if $n$ is even, and $m = n - 1$ if $n$ is odd.

We point out that the union of the Boolean posets could share more elements than $e$ and $w_0^W$. For instance, consider $SP(B_3)$ below.
<table><caption>**Tab. 1:** Finite coxeter groups $W$, rank($SP(W)$), and the number of Boolean posets in $SP(W)$</caption><thead><tr><th>W</th><th>rank(SP(W))</th><th>α<sub>W</sub> = # of Boolean posets in SP(W)</th></tr></thead><tbody><tr><td>A<sub>n-1</sub></td><td>$$\lfloor \frac{n-1}{2} \rfloor$$</td><td>1</td></tr><tr><td>B<sub>n</sub></td><td>n</td><td>b<sub>n</sub></td></tr><tr><td>D<sub>n</sub></td><td>n if n is even; n - 1 if n is odd</td><td>d<sub>n</sub></td></tr><tr><td>I<sub>2</sub>(m)</td><td>2 if m is even; 1 if m is odd</td><td>$$\frac{m}{2}$$ if m is even; 1 if m is odd</td></tr><tr><td>F<sub>4</sub></td><td>4</td><td>24</td></tr><tr><td>H<sub>3</sub></td><td>3</td><td>5</td></tr><tr><td>H<sub>4</sub></td><td>4</td><td>75</td></tr><tr><td>E<sub>6</sub></td><td>4</td><td>3</td></tr><tr><td>E<sub>7</sub></td><td>7</td><td>135</td></tr><tr><td>E<sub>8</sub></td><td>8</td><td>2025</td></tr></tbody></table>

While some elements other than $e$ and $w_0^{B_3}$ are shared by more than one Boolean poset, each maximal chain belongs to a *unique* Boolean poset.

## 2.2 One rising chain

Since $[u, v]$ is EL-shellable (see [BW82] and [Dye93]), then $[u, v]$ has a unique maximal chain that is rising. So it is reasonable to study the structure of $SP(u, v)$ under the assumption that there is a unique rising chain. Even though this seems to be a strong assumption, there are several examples of Bruhat intervals where $SP(u, v)$ has a unique rising chain; for instance, [21435, 53241].

An important tool in our study are the $\tilde{R}$-polynomials, defined below.

**Definition 2.4 (R-polynomials)** Let $s \in S$ so that $\ell(\text{vs}) < \ell(\text{v})$. Then define $\tilde{R}_{u,v}(\alpha)$ by

$$ \tilde{R}_{u,v}(\alpha) = \begin{cases} \tilde{R}_{us,vs}(\alpha) & \text{if } \ell(\text{us}) < \ell(\text{u}), \\ \tilde{R}_{us,vs}(\alpha) + \alpha \tilde{R}_{u,vs}(\alpha) & \text{if } \ell(\text{us}) > \ell(\text{vs}). \end{cases} $$

Dyer [Dye01] provided an interpretation of $\tilde{R}_{u,v}(\alpha)$ in terms of the number of rising paths of $B(u, v)$. Namely,

$$ \tilde{R}_{u,v}(\alpha) = \sum_{\substack{\Delta \in B(u,v) \\ D(\Delta) = \emptyset}} \alpha^{\ell(\Delta)}. $$

With this interpretation in mind, we have

**Proposition 2.5** $\tilde{R}_{u,v}(\alpha)\tilde{R}_{y,v}(\alpha) \le \tilde{R}_{u,v}(\alpha)$.

We point out, in passing, that the above proposition generalizes Theorem 5.4, Corollary 5.5 and Theorem 5.6 in [Bre97].

Proposition 2.5 yields the following theorem.
<figure><img src="image_2.png" /><figcaption>**Fig. 2:** $SP(B_3)$ has 4 copies of $B(3)$. Notice these copies intersect, but each maximal chain is in a unique Boolean poset.</figcaption></figure>

**Theorem 2.6** If $SP(u, v)$ has a unique rising chain, then

(a) $SP(u, v)$ is EL-shellable.

(b) $SP(u, v)$ is thin, i.e., every subinterval of length two of $SP(u, v)$ has four elements.

These topological properties will have consequences on the complete cd-index, and it will be discussed in Section 3.

## 2.3 FLIP algorithm

Let $k + 1 \stackrel{\text{def}}{=} \text{rank}(SP(u, v))$. An important distinction between $[u, v]$ and $SP(u, v)$ is that $[u, v]$ has a unique maximal, rising chain whereas $SP(u, v)$ could have more than one. So we propose an algorithm that splits the chains of $SP(u, v)$ into $[c^k]_{u,v}$ posets $P_i$, $i = 1, \dots, [c^k]_{u,v}$. The structure of each $P_i$ is easier to understand than $SP(u, v)$. So far we have been shown that the $P_i$ have properties that resemble those of $[u, v]$.

We now follow [BB] to define the flip of $\Gamma \in B_2(u, v)$. Let $(t_1, t_2)$ and $(r_1, r_2)$ be in $B_2(u, v)$. We say that $(t_1, t_2) \le_{lex} (r_1, r_2)$ if $t_1 <_T r_1$ or if $t_1 = r_1$ and $t_2 <_T r_2$, or $t_2 = r_2$. The existence of the complete cd-index implies that there are as many paths with empty descent set in $B_2(u, v)$ as those with descent set $\{1\}$. Order all the paths in $B_2(u, v)$ lexicographically and let

$$r(\Gamma) = |\{\Delta \in B_2(u, v) : D(\Delta) = D(\Gamma), \Delta \le_{lex} \Gamma\}|.$$

**Definition 2.7** With everything as above, we define the flip of $\Gamma$ is the $r(\Gamma)$-th Bruhat path in $\{\Delta \in B_2(u, v) | D(\Delta) \neq D(\Gamma)\}$ ordered by $\le_{lex}$. We denote this path by $\text{flip}(\Gamma)$.

Given $\Delta = (t_1, t_2, \dots, t_i, t_{i+1}, \dots, t_k) \in B_k(u, v)$, we denote the path $(t_1, t_2, \dots, t'_i, t'_{i+1}, \dots, t_k)$, where $\text{flip}(t_i, t_{i+1}) = (t'_i, t'_{i+1})$, by $\text{FLIP}_i(\Delta)$. We are now ready to describe our algorithm.

The pseudocode of FLIP is given in Algorithm 1. In a few words, FLIP returns a (directed) graph $G$ whose vertices are the maximal chains of $SP(u, v)$ and $(C, C')$ is an edge if $\text{FLIP}_j(C) = C'$, where
**Algorithm 1 FLIP(SP(u, v))**

$G := (V, E)$, with $V$ is the set of chains of $B(SP(u, v))$ and $E := \emptyset$.

$T := V$

**for** $C$ a maximal chain of $SP(u, v)$ **do**

**if** $D(C) \neq \emptyset$ **then**

$i := \min D(C)$

$C' := \text{FLIP}_i(C)$

Add edge $(C, C')$ to $E$.

**end if**

**end for**

**return** $G$

$j = \min\{D(C)\}$. Notice that $G$ has $[c^k]_{u,v}$ connected components, say $G_1, G_2, \dots, G_{[c^k]_{u,v}}$. We define $P_i$ to be the poset $SP(u, v)$ with all the chains (represented by vertices) not in $G_i$ removed.

Let us illustrate FLIP with the following example. Notice that the chains in $SP(u, v)$ are represented by the labels assigned to the corresponding edges in the $B(u, v)$.

**Example 1** Consider the 10 elements of $B_3(1234, 4312)$. Then the output of FLIP is depicted below. In the first column we have the two components of $G$, and in the right column the posets $P_i$ corresponding to each component.

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** On the left, we find the output of FLIP: two connected components. On the right the corresponding posets are depicted.</figcaption></figure>
Each $P_i$ satisfies properties resembling those of Bruhat intervals. Concretely, we have

**Proposition 2.8** (a) $P_i$ is graded.

(b) Every subinterval of $P_i$ has at most one rising chain.

(c) Every subinterval of length two of $P_i$ has at most two coatoms.

Bruhat intervals satisfy the properties above once we replace “at most” with “exactly”.

## 2.4 FLIP applied to $A_n$, $B_n$ and $D_n$

When applied to $A_{n-1}$, the output of FLIP is a unique graph $G$ and the corresponding poset $P$ is simply $SP(A_{n-1})$. Furthermore, one can choose a reflection order for the reflections of $B_n$ (see [Bla11]) so that FLIP outputs $b_n$ copies of $B(n)$ (see Table 1). For instance, $\text{FLIP}(SP(B_3))$ separates $SP(B_3)$ into four copies of $B(3)$ (see Figure 2, where the four copies are drawn with different colors). The same holds, mutatis mutandis, for $D_n$.

So in these cases, FLIP produces the expected results: it divides $SP(W)$ into $\alpha_W$ subposets $P_1, \dots, P_{\alpha_W}$ (where $\alpha_W$ is given in Table 1), and each $P_i$ is a Boolean poset.

# 3 Connections to the complete cd-index

In [Bla09], it is shown that the lowest-degree terms of $\tilde{\psi}_{e,w_0^W}(c, d)$ are non-negative. Thus we have the theorem below.

**Theorem 3.1** If $W$ is a finite Coxeter group, then the lowest degree terms of $\tilde{\psi}_{e,w_0^W}(c, d)$ are nonnegative.

In fact, these terms can be computed quite easily (see [Bla09] for details).

Now under the assumption of Theorem 2.6, $SP(u, v)$ is EL-shellable and thin. Thus Theorem 3.1.12 in [Wac07] yields the following proposition.

**Proposition 3.2** If $SP(u, v)$ has a unique rising chain, then it is a Gorenstein* poset.

Now as a consequence of [Kar06, Theorem 4.10], we have the following theorem.

**Theorem 3.3** If $SP(u, v)$ has a unique rising chain, then the lowest degree terms of $\tilde{\psi}_{u,v}(c, d)$ are non-negative.

Moreover, in the case $\text{rank}(SP(u, v)) = 2$, the posets $P_i$ described before Example 1 contribute a non-negative quantity to the lowest degree terms of $\tilde{\psi}_{u,v}(c, d)$. We hope to extend this result to $\text{rank}(SP(u, v)) = 3$.

# Acknowledgements

I want to thank Louis Billera for many helpful discussions, as well as kind advice and encouragement throughout the years. I also want to thank Matthew Dyer for his hospitality during my visit to Notre Dame and his willingness to discuss his work.
References

[BB] Louis J. Billera and Francesco Brenti. Quasisymmetric functions and Kazhdan-Lusztig polynomials. *Israel J. Math*.

[Bla09] Saúl A. Blanco. Shortest path poset of finite coxeter groups. *DMTCS Proceedings*, 0(01), 2009.

[Bla11] Saúl A. Blanco. *Shortest path poset poset and the complete cd-index*. PhD thesis, Cornell University, 2011.

[Bre97] Francesco Brenti. Combinatorial expansions of Kazhdan-Lusztig polynomials. *J. London Math. Soc.* (2), 55(3):448-472, 1997.

[BW82] Anders Björner and Michelle Wachs. Bruhat order of Coxeter groups and shellability. *Adv. in Math.*, 43(1):87-100, 1982.

[Dye91] Matthew J. Dyer. On the "Bruhat graph" of a Coxeter system. *Compositio Math.*, 78(2):185-191, 1991.

[Dye93] Matthew J. Dyer. Hecke algebras and shellings of Bruhat intervals. *Compositio Math.*, 89(1):91-115, 1993.

[Dye01] Matthew J. Dyer. On minimal lengths of expressions of Coxeter group elements as products of reflections. *Proc. Amer. Math. Soc.*, 129(9):2591-2595 (electronic), 2001.

[Kar06] Kalle Karu. The cd-index of fans and posets. *Compos. Math.*, 142(3):701-718, 2006.

[Wac07] Michelle L. Wachs. Poset topology: tools and applications. In *Geometric combinatorics*, volume 13 of *IAS/Park City Math. Ser.*, pages 497-615. Amer. Math. Soc., Providence, RI, 2007.