# Bruhat interval polytopes

Emmanuel Tsukerman, Lauren Williams

► To cite this version:

Emmanuel Tsukerman, Lauren Williams. Bruhat interval polytopes. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.13-24, 10.46298/dmtcs.2507 . hal-01337845

HAL Id: hal-01337845

https://hal.science/hal-01337845

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# Bruhat interval polytopes

Emmanuel Tsukerman† and Lauren Williams‡

Department of Mathematics, University of California, Berkeley, CA 94720-3840

**Abstract.** Let $u$ and $v$ be permutations on $n$ letters, with $u \le v$ in Bruhat order. A Bruhat interval polytope $Q_{u,v}$ is the convex hull of all permutation vectors $z = (z(1), z(2), \dots, z(n))$ with $u \le z \le v$. Note that when $u = e$ and $v = w_0$ are the shortest and longest elements of the symmetric group, $Q_{e,w_0}$ is the classical permutohedron. Bruhat interval polytopes were studied recently in the 2013 paper “The full Kostant-Toda hierarchy on the positive flag variety” by Kodama and the second author, in the context of the Toda lattice and the moment map on the flag variety. In this paper we study combinatorial aspects of Bruhat interval polytopes. For example, we give an inequality description and a dimension formula for Bruhat interval polytopes, and prove that every face of a Bruhat interval polytope is a Bruhat interval polytope. A key tool in the proof of the latter statement is a generalization of the well-known lifting property for Coxeter groups. Motivated by the relationship between the lifting property and $R$-polynomials, we also give a generalization of the standard recurrence for $R$-polynomials.

**Résumé.** Soient $u$ et $v$ des permutations sur $n$ lettres, avec $u \le v$ dans l'ordre de Bruhat. Un polytope d'intervalles de Bruhat $Q_{u,v}$ est l'enveloppe convexe de tous les vecteurs de permutations $z = (z(1), z(2), \dots, z(n))$ avec $u \le z \le v$. Notons que lorsque $u = e$ et $v = w_0$ sont respectivement le plus court et le plus long élément du groupe symétrique, $Q_{e,w_0}$ est le permutoèdre classique. Les polytopes d'intervalles de Bruhat ont été étudiés récemment dans le papier de 2013 "The full Kostant-Toda hierarchy on the positive flag variety" par Kodama et le deuxième auteur, dans le contexte du treillis de Toda et la carte des moments sur la variété de drapeaux. Dans ce papier nous étudions des aspects combinatoires des polytopes d'intervalles de Bruhat. Par exemple, nous donnons une description par inégalités et une formule dimensionnelle pour les polytopes d'intervalles de Bruhat, et provons que chaque face d'un polytope d'intervalles de Bruhat est un polytope d'intervalles de Bruhat. Un outil essentiel dans la preuve de cette dernière affirmation est une généralisation de la célèbre propriété de lifting pour les groupes de Coxeter. Motivés par la relation entre la propriété de lifting et les $R$-polynômes, nous donnons aussi une généralisation de la récurrence standard pour les $R$-polynômes.

**Keywords:** Bruhat order, symmetric group, $R$-polynomials

## 1 Introduction

The classical *permutohedron* is the convex hull of all permutation vectors $(z(1), z(2), \dots, z(n)) \in \mathbb{R}^n$ where $z$ is an element of the symmetric group $S_n$. It has many beautiful properties: its edges are in bijection with cover relations in the weak Bruhat order; its faces can be described explicitly; it is the Minkowski sum of matroid polytopes; it is the moment map image of the complete flag variety.

The main subject of this paper is a natural generalization of the permutohedron called a Bruhat interval polytope. Let $u$ and $v$ be permutations in $S_n$, with $u \le v$ in (strong) Bruhat order. The *Bruhat interval polytope* (or *pairmutohedron*<sup>(i)</sup>) $Q_{u,v}$ is the convex hull of all permutation vectors $z = (z(1), z(2), \dots, z(n))$ with $u \le z \le v$. Note that when $u = e$ and $v = w_0$ are the shortest and longest elements of the symmetric group, $Q_{e,w_0}$ is the classical permutohedron. Bruhat interval polytopes were recently studied in [KW13] by Kodama and the second author, in the context of the Toda lattice and the moment map on the flag variety $Fl_n$. A basic fact is that $Q_{u,v}$ is the moment map image of the Richardson variety $R_{u,v} \subset Fl_n$. Moreover, $Q_{u,v}$ is a Minkowski sum of matroid polytopes (in fact of *positroid polytopes* [ARW13]) [KW13], which implies that $Q_{u,v}$ is a *generalized permutohedron* (in the sense of Postnikov [Pos09]).

<footnote>†Email: e.tsukerman@berkeley.edu, supported by a NSF Graduate Research Fellowship under Grant No. DGE 1106400.</footnote>

<footnote>‡Email: williams@math.berkeley.edu, partially supported by an NSF CAREER award DMS-1049513.</footnote>

<footnote><sup>(i)</sup> While the name “Bruhat interval polytope” is descriptive, it is unfortunately a bit cumbersome. At the Stanley 70 conference, the second author asked the audience for suggestions for alternative names. Russ Woodroofe suggested the name “pairmutohedron”; additionally, Tricia Hersh suggested the name “mutohedron” (because a Bruhat interval polytope is a subset of the permutohedron).</footnote>
The goal of this paper is to study combinatorial aspects of Bruhat interval polytopes. We give a dimension formula for Bruhat interval polytopes, an inequality description of Bruhat interval polytopes, and prove that every face of a Bruhat interval polytope is again a Bruhat interval polytope. In particular, each edge corresponds to some edge in the (strong) Bruhat order. The proof of our result on faces uses the classical result (due to Edelman [Ede81] in the case of the symmetric group, and subsequently generalized by Proctor [Pro82] and then Bjorner-Wachs [BW82]) that the order complex of an interval in Bruhat order is homeomorphic to a sphere. Our proof also uses a generalization of the lifting property, which appears to be new and may be of interest in its own right. This Generalized lifting property says that if $u < v$ in $S_n$, then there exists an inversion-minimal transposition $(ik)$ (see Definition 3.2) such that $u \le v(ik) < v$ and $u \le u(ik) \le v$. One may compare this with the usual lifting property, which says that if $u < v$ and the simple reflection $s_i \in D_r(v) \setminus D_r(u)$ is a right-descent of $v$ but not a right-descent of $u$, then $u \le vs_i \le v$ and $u \le us_i \le v$. Note that in general such a simple reflection $s_i$ need not exist.

The usual lifting property is closely related to the $R$-polynomials $R_{u,v}(q)$. Recall that the $R$-polynomials are used to define Kazhdan-Lusztig polynomials [KL79], and also have an interesting geometric interpretation: the Richardson variety $\mathcal{R}_{u,v}$ may be defined over a finite field $\mathbb{F}_q$, and the number of points it contains is given by the $R$-polynomial $R_{u,v}(q) = \#\mathcal{R}_{u,v}(\mathbb{F}_q)$. A basic result about the $R$-polynomials is that if $s_i \in D_r(v) \setminus D_r(u)$, then $R_{u,v}(q) = qR_{us,vs}(q) + (q-1)R_{u,vs}(q)$. We generalize this result, showing that if $t = (ik)$ is inversion-minimal, then $R_{u,v}(q) = qR_{ut,vt}(q) + (q-1)R_{u,vt}(q)$.

The structure of this paper is as follows. In Section 2 we provide background and terminology for posets, Coxeter groups, permutohedra, matroid polytopes, and Bruhat interval polytopes. In Section 3 we state and prove the Generalized lifting property for the symmetric group. We then use this result in Section 4 to prove that the face of a Bruhat interval polytope is a Bruhat interval polytope. Section 4 also provides a dimension formula for Bruhat interval polytopes, and an inequality description for Bruhat interval polytopes. In Section 5 we give a generalization of the usual recurrence for $R$-polynomials, using the notion of an inversion-minimal transposition on the interval $(u, v)$.

## 2 Background

In this section we will quickly review some notation and background for posets and Coxeter groups. We will also review some basic facts about permutohedra, matroid polytopes, and Bruhat interval polytopes. We will assume knowledge of the basic definitions of Coxeter systems and Bruhat order; we refer the reader to [BB05] for details. Note that throughout this paper, Bruhat order will refer to the strong Bruhat order.

Let $P$ be a poset with order relation $\leq$. We will use the symbol $\leq$ to denote a covering relation in the poset: $u \leq v$ means that $u < v$ and there is no $z$ such that $u < z < v$. Additionally, if $u < v$ then $[u, v]$ denotes the (closed) interval from $u$ to $v$; that is, $[u, v] = \{z \in P \mid u \leq z \leq v\}$. Similarly, $(u, v)$ denotes the (open) interval, that is, $(u, v) = \{z \in P \mid u < z < v\}$.

The natural geometric object that one associates to a poset $P$ is the geometric realization of its order complex (or nerve). The order complex $\Delta(P)$ is defined to be the simplicial complex whose vertices are the elements of $P$ and whose simplices are the chains $x_0 < x_1 < \dots < x_k$ in $P$. Abusing notation, we will also use the notation $\Delta(P)$ to denote the geometric realization of the order complex.

Let $(W, S)$ be a Coxeter group generated by a set of simple reflections $S = \{s_i \mid i \in I\}$. We denote the set of all reflections by $T = \{wsw^{-1} \mid w \in W\}$. Recall that a reduced word for an element $w \in W$ is a minimal length expression for $w$ as a product of elements of $S$, and the length $\ell(w)$ of $w$ is the length of a reduced word. For $w \in W$, we let $D_R(w) = \{s \in S \mid ws \le w\}$ be the right descent set of $w$ and $D_L(w) = \{s \in S \mid sw \le w\}$ the left descent set of $w$. We also let $T_R(w) = \{t \in T \mid \ell(wt) < \ell(w)\}$ and $T_L(w) = \{t \in T \mid \ell(tw) < \ell(w)\}$ be the right associated reflections and left associated reflections of $w$, respectively.

The (strong) Bruhat order on $W$ is defined by $u \leq v$ if some substring of some (equivalently, every) reduced word for $v$ is a reduced word for $u$. The Bruhat order on a Coxeter group is a graded poset, with rank function given by length.

When $W$ is the symmetric group $S_n$, the reflections are the transpositions $T = \{(ij) \mid 1 \leq i < j \leq n\}$, the set of permutations which act on $\{1, \dots, n\}$ by swapping $i$ and $j$. The simple reflections are the reflections of the form $(ij)$ where $j = i+1$. We also denote this simple reflection by $s_i$. An inversion of a permutation $z = (z(1), \dots, z(n)) \in S_n$ is a pair $(ij)$ with $1 \leq i < j \leq n$ such that $z(i) > z(j)$. It is well-known that $\ell(z)$ is equal to the number of inversions of the permutation $z$.

Note that we will often use the notation $(z_1, \dots, z_n)$ instead of $(z(1), \dots, z(n))$.

We now review some facts about permutohedra, matroid polytopes, and Bruhat interval polytopes.
**Definition 2.1** The usual permutohedron Perm$_n$ in $\mathbb{R}^n$ is the convex hull of the $n!$ points obtained by permuting the coordinates of the vector $(1, 2, \dots, n)$.

Bruhat interval polytopes, as defined below, were introduced and studied by Kodama and the second author in [KW13], in connection with the full Kostant-Toda lattice on the flag variety.

**Definition 2.2** Let $u, v \in S_n$ such that $u \le v$ in (strong) Bruhat order. We identify each permutation $z \in S_n$ with the corresponding vector $(z(1), \dots, z(n)) \in \mathbb{R}^n$. Then the Bruhat interval polytope $Q_{u,v}$ is defined as the convex hull of all vectors $(z(1), \dots, z(n))$ for $z$ such that $u \le z \le v$.

See Figure 1 for some examples of Bruhat interval polytopes.

<figure><img src="image_2.png" /><figcaption>Figure 1: The two polytopes are the permutohedron $Q_{e,w_0} = \text{Perm}_4$, and the Bruhat interval polytope $Q_{u,v}$ with $v = (2, 4, 3, 1)$ and $u = (1, 2, 4, 3)$.</figcaption></figure>

We next explain how Bruhat interval polytopes are related to matroid polytopes, generalized permutohedra, and flag matroid polytopes.

**Definition 2.3** Let $\mathcal{M}$ be a nonempty collection of $k$-element subsets of $[n]$ such that: if $I$ and $J$ are distinct members of $\mathcal{M}$ and $i \in I \setminus J$, then there exists an element $j \in J \setminus I$ such that $(I \setminus \{i\}) \cup \{j\} \in \mathcal{M}$. Then $\mathcal{M}$ is called the set of bases of a matroid of rank $k$ on the ground set $[n]$; or simply a matroid.

**Definition 2.4** Given the set of bases $\mathcal{M} \subset \binom{[n]}{k}$ of a matroid, the matroid polytope $\Gamma_{\mathcal{M}}$ of $\mathcal{M}$ is the convex hull of the indicator vectors of the bases of $\mathcal{M}$:

$$ \Gamma_{\mathcal{M}} := \text{Conv}\{e_I \mid I \in \mathcal{M}\} \subset \mathbb{R}^n, $$

where $e_I := \sum_{i \in I} e_i$, and $\{e_1, \dots, e_n\}$ is the standard basis of $\mathbb{R}^n$.

Note that “a matroid polytope" refers to the polytope of a specific matroid in its specific position in $\mathbb{R}^n$.

**Definition 2.5** The flag variety $\text{Fl}_n$ is the variety of all flags

$$ \text{Fl}_n = \{V_{\bullet} = V_1 \subset V_2 \subset \dots \subset V_n = \mathbb{R}^n \mid \dim V_i = i\} $$

of vector subspaces of $\mathbb{R}^n$.

**Definition 2.6** The Grassmannian $\text{Gr}_{k,n}$ is the variety of $k$-dimensional subspaces of $\mathbb{R}^n$

$$ \text{Gr}_{k,n} = \{V \subset \mathbb{R}^n \mid \dim V = k\}. $$

Note that there is a natural projection $\pi_k: \text{Fl}_n \to \text{Gr}_{k,n}$ taking $V_{\bullet} = V_1 \subset \dots \subset V_n$ to $V_k$.

Note also that any element $V \in \text{Gr}_{k,n}$ gives rise to a matroid $\mathcal{M}(V)$ of rank $k$ on the ground set $[n]$. First represent $V$ as the row-span of a full rank $k \times n$ matrix $A$. Given a $k$-element subset $I$ of $\{1, 2, \dots, n\}$, let $\Delta_I(A)$ denote the determinant of the $k \times k$ submatrix of $A$ located in columns $I$. This is called a *Plücker coordinate*. Then $V$ gives rise to a matroid $\mathcal{M}(V)$ whose bases are precisely the $k$-element subsets $I$ such that $\Delta_I(A) \neq 0$.

One result of [KW13, Section 6] (see also [KW13, Appendix]) is the following.
**Proposition 2.7** Choose $u \le v \in S_n$. Let $V_\bullet = V_1 \subset \dots \subset V_n$ be any element in the positive part of the Richardson variety $\mathcal{R}_{u,v;>0}$. Then the Bruhat interval polytope $\mathcal{Q}_{u,v}$ is the Minkowski sum of $n-1$ matroid polytopes:

$$ \mathcal{Q}_{u,v} = \sum_{k=1}^{n-1} \Gamma_{\mathcal{M}(V_k)}. $$

In fact each of the polytopes $\Gamma_{\mathcal{M}(V_k)}$ is a positroid polytope, in the sense of [ARW13], and $\mathcal{Q}_{u,v}$ is a generalized permutohedron, in the sense of Postnikov [Pos09].

We can compute the bases $\mathcal{M}(V_k)$ from the permutations $u$ and $v$ as follows.

$$ \mathcal{M}(V_k) = \{ I \in \binom{[n]}{k} \mid \text{there exists } z \in [u, v] \text{ such that } I = \{z(1), \dots, z(k)\} \}. \quad (1) $$

Therefore we have the following.

**Proposition 2.8** For any $u \le v \in S_n$, the Bruhat interval polytope $\mathcal{Q}_{u,v}$ is the Minkowski sum of $n-1$ matroid polytopes

$$ \mathcal{Q}_{u,v} = \sum_{k=1}^{n-1} \Gamma_{\mathcal{M}_k}, $$

where

$$ \mathcal{M}_k = \{ I \in \binom{[n]}{k} \mid \text{there exists } z \in [u, v] \text{ such that } I = \{z(1), \dots, z(k)\} \}. $$

Positroid polytopes are a particularly nice class of matroid polytopes coming from positively oriented matroids. A generalized permutohedron is a polytope which is obtained by moving the vertices of the usual permutohedron in such a way that directions of edges are preserved, but some edges (and higher dimensional faces) may degenerate. See [ARW13] and [Pos09] for more details on positroid polytopes and generalized permutohedra.

There is a generalization of matroid called flag matroid, due to Gelfand and Serganova [GS87], [BGW03, Section 1.7], and a corresponding notion of flag matroid polytope. A convex polytope $\Delta$ in the real vector space $\mathbb{R}^n$ is called a (type $A_{n-1}$) flag matroid polytope if the edges of $\Delta$ are parallel to the roots of type $A_{n-1}$ and there exists a point equidistant from all of its vertices.

The following result follows easily from Proposition 2.7.

**Proposition 2.9** Choose $u \le v \in S_n$. Then the Bruhat interval polytope $\mathcal{Q}_{u,v}$ is a flag matroid polytope.

We can use Proposition 2.9 to prove the following useful result.

**Proposition 2.10** Let $\mathcal{Q}_{u,v}$ be a Bruhat interval polytope. Consider a face $F$ of $\mathcal{Q}_{u,v}$. Let $\mathcal{N}$ be the set of permutations which label vertices of $F$. Then $\mathcal{N}$ contains an element $x$ and an element $y$ such that

$$ x \le z \le y \quad \forall z \in \mathcal{N}. $$

# 3 The generalized lifting property for the symmetric group

The main result of this section is Theorem 3.3, which is a generalization (for the symmetric group) of the classical lifting property for Coxeter groups. This result will be a main tool for proving that every face of a Bruhat interval polytope is a Bruhat interval polytope.

We start by recalling the usual lifting property.

**Proposition 3.1 (Lifting property)** Suppose $u < v$ and $s \in D_R(v) \setminus D_R(u)$. Then $u \le vs \le v$ and $u \le us \le v$.

**Definition 3.2** Let $u, v \in S_n$. A transposition $(ik)$ is inversion-minimal on $(u, v)$ if the interval $[i, k]$ is the minimal interval (with respect to inclusion) which has the property

$$ v_i > v_k, \quad u_i < u_k. $$

**Theorem 3.3 (Generalized lifting property)** Suppose $u < v$ in $S_n$. Choose a transposition $(ij)$ which is inversion-minimal on $(u, v)$. Then $u \le v(ij) < v$ and $u \le u(ij) \le v$.
We note that there are pairs $u < v$ where $D_R(v) \setminus D_R(u)$ is empty, and hence one cannot apply the Lifting property. In contrast, Lemma 3.4 below shows that for any pair $u < v$ in $S_n$, there exists an inversion-minimal transposition $(ij)$. Hence it is always possible to apply the Generalized lifting property.

**Lemma 3.4** Let $(W, S)$ be a Coxeter group. Take $u, v \in W$ distinct. If $\ell(v) \ge \ell(u)$ then there exists a reflection $t \in T$ such that

$$v > vt, \quad u < ut.$$

Lemma 3.4 directly implies the following corollary.

**Corollary 3.5** Let $v, u \in S_n$ be two distinct permutations. If $\ell(v) \ge \ell(u)$ then there exists an inversion-minimal transposition on $(u, v)$.

In preparation for the proof of Theorem 3.3, it will be convenient to make the following definition.

**Definition 3.6** A pattern of length $n$ is an equivalence class of sequences $x_1x_2 \cdots x_n$ of distinct integers. Two such sequences $x_1x_2 \cdots x_n, y_1y_2 \cdots y_n$ are in the same equivalence class ("have the same pattern") if

$$x_i > x_j \iff y_i > y_j \text{ for all } i, j \text{ such that } 1 \le i, j \le n.$$

Denote by $\text{Patt}_n$ the set of patterns of length $n$.

There is a canonical representative for each pattern $x \in \text{Patt}_n$ obtained by replacing each $x_i$ with

$$\bar{x}_i := \#\{j \in [n] : x_j \le x_i\}.$$

For example, the canonical representative of 523 is 312.

**Definition 3.7** Let $x, y \in \text{Patt}_n$ for some $n$. Call $(x, y)$ an Inversion-Inversion pair if the following condition holds:

$$\text{for all } i < j, \quad x_i > x_j \implies y_i > y_j.$$

Notice that this statement is independent of the choice of representatives.

It is easy to see that if $(x, y)$ is an Inversion-Inversion pair, then so is $(x_1 \cdots \hat{x}_k \cdots x_n, y_1 \cdots \hat{y}_k \cdots y_n)$ for any $k$.

In preparation for the proof of Theorem 3.3, we first state and prove Lemmas 3.8, 3.10, and 3.11.

**Lemma 3.8** Let $u, v \in S_n$. The following are equivalent:

(i). The transposition $(ik)$ is inversion-minimal on $(u, v)$

(ii). The patterns $x = x_i \cdots x_k := v_i \cdots v_k$ and $y = y_i \cdots y_k := u_k u_{i+1} u_i \cdots u_{k-2} u_{k-1} u_i$ form an Inversion-Inversion pair $(x, y)$ with $\bar{x}_k = \bar{x}_i + 1$ and $\bar{y}_k = \bar{y}_i + 1$.

Lemma 3.8 implies the following result.

**Corollary 3.9** Let $u, v \in S_n$ and let $(ik)$ be inversion-minimal on $(u, v)$. Then

$$v(ik) < v \quad \text{and} \quad u < u(ik).$$

<figure><img src="image_3.png" /><figcaption>Figure 2: Generalized lifting property</figcaption></figure>

**Lemma 3.10** Let $x, y \in \text{Patt}_n$ with $\bar{x}_n = \bar{x}_1 + 1$ and $\bar{y}_n = \bar{y}_1 + 1$. If $(x, y)$ is an Inversion-Inversion pair, then $\bar{x}_1 = \bar{y}_1$.
**Lemma 3.11** Suppose that $(ik)$ is inversion-minimal on $(u, v)$. Then for every $i < j < k$, we have

$$u_j > u_i \iff u_j > u_k \iff v_j > v_k \iff v_j > v_i.$$

<figure><img src="image_4.png" /><figcaption>Figure 3: Example of Theorem 3.3</figcaption></figure>

**Example 3.12** The following example shows that the converse to Theorem 3.3 does not hold: it is not necessarily the case that if the Bruhat relations

$$v(ik) \le v \quad u \le u(ik) \quad u \le v(ik) \quad u(ik) \le v$$

hold, then $(ik)$ is inversion-minimal on $(u, v)$. Take $v = 4312$, $u = 1243$ and $(ik) = (24)$. Then

$$v(ik) \le v \quad u \le u(ik) \quad u \le v(ik) \quad u(ik) \le v$$

but also $v_2 > v_3$ and $u_2 < u_3$.

As a corollary of Generalized lifting, we have the following result, which says that in an interval of the symmetric group we may find a maximal chain such that each transposition connecting two consecutive elements of the chain is a transposition that comes from the atoms, and similarly, for the coatoms.

**Corollary 3.13** Let $[u, v] = \subset S_n$ and let $\underline{T}(v) := \{t \in T : v > vt \ge u\}$ and $\overline{T}(u) := \{t \in T : u < ut \le v\}$. There exist maximal chains $C_v : u = x_{(0)} \le x_{(1)} \le x_{(2)} \le \dots \le x_{(l)} = v$ and $C_u : u = y_{(0)} \le y_{(1)} \le y_{(2)} \le \dots \le y_{(l)} = v$ in $I$ such that $x_{(i)}^{-1}x_{(i+1)} \in \underline{T}(v)$ and $y_{(i)}^{-1}y_{(i+1)} \in \overline{T}(u)$ for each $i$.

# 4 Results on Bruhat interval polytopes

In this section we give some results on Bruhat interval polytopes. We show that the face of a Bruhat interval polytope is a Bruhat interval polytope; we give a dimension formula; and we give an inequality description.

## 4.1 Faces of Bruhat interval polytopes are Bruhat interval polytopes

The main result of this section is the following.

**Theorem 4.1** Every face of a Bruhat interval polytope is itself a Bruhat interval polytope.

Our proof of this result uses the following theorem. It was first proved for the symmetric group by Edelman [Ede81], then generalized to classical types by Proctor [Pro82], and then proved for arbitrary Coxeter groups by Bjorner and Wachs [BW82].

**Theorem 4.2** [BW82] Let $(W, S)$ be a Coxeter group. Then for any $u \le v$ in $W$, the order complex $\Delta(u, v)$ of the interval $(u, v)$ is PL-homeomorphic to a sphere $S^{\ell(u,v)-2}$. In particular, the Bruhat order is thin, that is, every rank 2 interval is a diamond. In other words, whenever $u \le v$ with $\ell(v) - \ell(u) = 2$, there are precisely two elements $z_{(1)}, z_{(2)}$ such that $u < z_{(i)} < v$.

We will identify a linear functional $\omega$ with a vector $(\omega_1, \dots, \omega_n) \in \mathbb{R}^n$, where $\omega : \mathbb{R}^n \to \mathbb{R}$ is defined by $\omega(e_i) = \omega_i$ (and extended linearly).

**Proposition 4.3** Choose $u \le v$ in $S_n$, and let $\omega : \mathbb{R}^n \to \mathbb{R}$ be a linear functional which is constant on a maximal chain $C$ from $u$ to $v$. Then $\omega$ is constant on all permutations $z$ where $u \le z \le v$.

**Corollary 4.4** If a linear functional $\omega : \mathbb{R}^n \to \mathbb{R}$, when restricted to $[u, v]$, attains its maximum value on $u$ and $v$, then it is constant on $[u, v]$.
## 4.2 The dimension of Bruhat interval polytopes

In this section we will give a dimension formula for Bruhat interval polytopes. We will then use it to determine which Richardson varieties in $Fl_n$ are toric varieties, with respect to the usual torus action on $Fl_n$. Recall that a Richardson variety $\mathcal{R}_{u,v}$ is the intersection of opposite Schubert (sometimes called Bruhat) cells.

**Definition 4.5** Let $u \le v$ be permutations in $S_n$, and let $\mathcal{C}: u = x_{(0)} \le x_{(1)} \le x_{(2)} \le \dots \le x_{(l)} = v$ be any maximal chain from $u$ to $v$. Define a labeled graph $G^\mathcal{C}$ on $[n]$ having an edge between vertices $a$ and $b$ if and only if the transposition $(ab)$ equals $x_{(i)}^{-1}x_{(i+1)}$ for some $0 \le i \le l-1$. Define $B_{\mathcal{C}} = \{B^1, B^2, \dots, B^r\}$ to be the partition of $[n] = \{1, 2, \dots, n\}$ whose blocks $B^j$ are the connected components of $G^\mathcal{C}$. Let $\#B_{\mathcal{C}}$ denote $r$, the number of blocks in the partition.

We will show in Corollary 4.8 that the partition $B_{\mathcal{C}}$ is independent of $\mathcal{C}$; and so we will denote this partition by $B_{u,v}$.

**Theorem 4.6** The dimension $\dim Q_{u,v}$ of the Bruhat interval polytope $Q_{u,v}$ is

$$ \dim Q_{u,v} = n - \#B_{u,v}. $$

The equations defining the affine span of $Q_{u,v}$ are

$$ \sum_{i \in B^j} x_i = \sum_{i \in B^j} u_i(= \sum_{i \in B^j} v_i), \quad j = 1, 2, \dots, \#B_{u,v}. \qquad (2) $$

Before proving Theorem 4.6, we need to show that $B_{u,v}$ is well-defined. Given a subset $A \subset [n]$, let $e_A$ denote the 0-1 vector in $\mathbb{R}^n$ with a 1 in position $a$ if and only if $a \in A$.

**Lemma 4.7** Let $\mathcal{C}$ be a maximal chain in $[u, v] \subset S_n$. Let $B_{\mathcal{C}} = \{B^1, \dots, B^r\}$ be the associated partition of $[n]$. Then a linear functional $\omega: \mathbb{R}^n \to \mathbb{R}$ is constant on the interval $[u, v]$ if and only if

$$ \omega = \sum_{j=1}^{r} c_j e_{B^j} $$

for some coefficients $c_j$.

**Corollary 4.8** The partition $B_{\mathcal{C}}$ is independent of the choice of $\mathcal{C}$.

**Definition 4.9** Let $u \le v$ be permutations in $S_n$, and let $\bar{T}(u) := \{t \in T : u \le ut \le v\}$ and $\bar{T}(v) := \{t \in T : v \ge vt \ge u\}$ be the transpositions labeling the cover relations corresponding to the atoms and coatoms in the interval. Define a labeled graph $G^{\text{at}}$ (resp. $G^{\text{coat}}$) on $[n]$ such that $G^{\text{at}}$ (resp. $G^{\text{coat}}$) has an edge between $a$ and $b$ if and only if the transposition $(ab) \in \bar{T}(u)$ (resp. $(ab) \in \bar{T}(v)$). Let $B_{u,v}^{\text{at}}$ be the partition of $[n]$ whose blocks are the connected components of $G^{\text{at}}$. Similarly, define partition $B_{u,v}^{\text{coat}}$ whose blocks are the connected components of $G^{\text{coat}}$.

**Proposition 4.10** Let $[u, v] \subset S_n$. The partitions $B_{u,v}^{\text{at}}$ and $B_{u,v}^{\text{coat}}$ are equal to $B_{u,v}$. Consequently, the labeled graphs $G^\mathcal{C}$, $G^{\text{at}}$ and $G^{\text{coat}}$ all have the same connected components.

**Example 4.11** Consider the intervals $[1234, 1432]$ and $[1234, 3412]$ in Figures 4 and 5. We see that $B_{1234,1432} = |1|B_{1234,1432} = |1234|$, so that the dimensions are 2 and 3, respectively.

<figure><img src="image_5.png" /><figcaption>Figure 4</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 5</figcaption></figure>

We now turn to the question of when the Richardson variety $\mathcal{R}_{u,v}$ is a toric variety.

**Proposition 4.12** The Richardson variety $\mathcal{R}_{u,v}$ in $\mathrm{Fl}_n$ is a toric variety if and only if the number of blocks $\#B_{u,v}$ of the partition $B_{u,v}$ satisfies $\#B_{u,v} = n - \ell(v) + \ell(u)$. Equivalently, $\mathcal{R}_{u,v}$ is a toric variety if and only if the labeled graph $G^C$ is a forest (with no multiple edges).

Given a labeled graph $G$, we will say that a cycle $(v_0, v_1, \dots, v_k)$ with $v_k = v_0$ is increasing if $v_0 < v_1 < \dots < v_{k-1}$. We shall call a labeled graph with no increasing cycles an increasing-cycle-free labeled graph.

**Lemma 4.13** The labeled graphs $G^{at}$ and $G^{coat}$ are increasing-cycle-free. In particular, they are simple and triangle-free.

Following Björner and Brenti [BB05], we call the face poset of a $k$-gon a $k$-crown. Any length 3 interval in a Coxeter group is a $k$-crown [BB05, Corollary 2.7.8]. It is also known that in $S_n$, the values of $k$ can only be 2, 3 or 4.

**Remark 4.14** Using Proposition 4.10 and Lemma 4.13, it is easy to show that any $k$-crown must have $k \le 4$. Indeed, the graph $G^C$ has 3 edges, and therefore at least $n - 3$ connected components. By Proposition 4.10, the graph $G^{at}$ has the same connected components as $G^C$ and $k$ edges. By Lemma 4.13 it is simple and triangle-free. Consequently, if $k > 4$ then $G^{at}$ must have at most $n - 4$ components.

**Lemma 4.15** Let $[u, v]$ be a 4-crown and let $\mathcal{C}$: $u = x_{(0)} \ll x_{(1)} \ll x_{(2)} \ll x_{(3)} = v$ be any maximal chain. The graph $G^C$ is a forest. In particular, if we set $t_i := x_{(i)}^{-1} x_{(i+1)}$ for $0 \le i \le 2$, then $t_0 \ne t_2$ since there are no multiple edges.

**Corollary 4.16** A Richardson variety $\mathcal{R}_{u,v}$ in $\mathrm{Fl}_n$ with $\ell(v) - \ell(u) = 3$ is a toric variety if and only if $[u, v]$ is a 3-crown or a 4-crown.

## 4.3 An inequality description of Bruhat interval polytopes

Using Proposition 2.8, which says that Bruhat interval polytopes are Minkowski sums of matroid polytopes, we will provide an inequality description of Bruhat interval polytopes.

We first need to recall the notion of the rank function $r_M$ of a matroid $\mathcal{M}$. Suppose that $\mathcal{M}$ is a matroid of rank $k$ on the ground set $[n]$. Then the *rank function* $r_M: 2^{[n]} \to \mathbb{Z}_{\ge 0}$ is the function defined by

$$r_M(A) = \max_{I \in \mathcal{M}} |A \cap I| \quad \text{for all } A \in 2^{[n]}. $$

There is an inequality description of matroid polytopes, using the rank function.
**Proposition 4.17 ([Wel76])** Let $\mathcal{M}$ be any matroid of rank $k$ on the ground set $[n]$, and let $r_{\mathcal{M}} : 2^{[n]} \to \mathbb{Z}_{\ge 0}$ be its rank function. Then the matroid polytope $\Gamma_{\mathcal{M}}$ can be described as

$$ \Gamma_{\mathcal{M}} = \left\{ \mathbf{x} \in \mathbb{R}^n \mid \sum_{i \in [n]} x_i = k, \sum_{i \in A} x_i \le r_{\mathcal{M}}(A) \text{ for all } A \subset [n] \right\}. $$

Using Proposition 4.17 we obtain the following result.

**Proposition 4.18** Choose $u \le v \in S_n$, and for each $1 \le k \le n-1$, define the matroid

$$ \mathcal{M}_k = \{ I \in \binom{[n]}{k} \mid \text{there exists } z \in [u, v] \text{ such that } I = \{z(1), \dots, z(k)\} \}. $$

Then

$$ Q_{u,v} = \left\{ \mathbf{x} \in \mathbb{R}^n \mid \sum_{i \in [n]} x_i = \binom{n+1}{2}, \sum_{i \in A} x_i \le \sum_{j=1}^{n-1} r_{\mathcal{M}_j}(A) \text{ for all } A \subset [n] \right\}. $$

**Example 4.19** Consider $u = 1324$ and $v = 2431$ in $S_4$. We will compute the inequality description of $Q_{u,v}$. First note that $[u, v] = \{1324, 1342, 1423, 1432, 2314, 2341, 2413, 2431\}$. We then compute:

* $\mathcal{M}_1 = \{\{1\}, \{2\}\}$, a matroid of rank 1 on [4].

* $\mathcal{M}_2 = \{\{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}\}$, a matroid of rank 2 on [4].

* $\mathcal{M}_3 = \{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}\}$, a matroid of rank 3 on [4].

Now using Proposition 4.18, we get

$$ \begin{aligned} Q_{u,v} = \{ \mathbf{x} \in \mathbb{R}^4 \mid & \sum_{i \in [4]} x_i = 10, x_1 + x_2 + x_3 \le 6, x_1 + x_2 + x_4 \le 6, x_1 + x_3 + x_4 \le 6, x_2 + x_3 + x_4 \le 6, \\ & x_1 + x_2 \le 4, x_1 + x_3 \le 5, x_1 + x_4 \le 5, x_2 + x_3 \le 5, x_2 + x_4 \le 5, x_3 + x_4 \le 3, \\ & x_1 \le 3, x_2 \le 3, x_3 \le 2, x_4 \le 2. \} \end{aligned} $$

# 5 A generalization of the recurrence for R-polynomials

The well-known R-polynomials were introduced by Kazhdan and Lusztig as a useful tool for computing Kazhdan-Lusztig polynomials [KL79]. R-polynomials also have a geometric interpretation in terms of Richardson varieties. More specifically, the Richardson variety $\mathcal{R}_{u,v}$ may be defined over a finite field $\mathbb{F}_q$, and the number of points it contains is given by the R-polynomial $R_{u,v}(q) = \#\mathcal{R}_{u,v}(\mathbb{F}_q)$.

The R-polynomials may be defined by the following recurrence.

**Theorem 5.1 [BB05, Theorem 5.1.1]** There exists a unique family of polynomials $\{R_{u,v}(q)\}_{u,v \in W} \subset \mathbb{Z}[q]$ satisfying the following conditions:

1. $R_{u,v}(q) = 0$, if $u \not\le v$.

2. $R_{u,v}(q) = 1$, if $u = v$.

3. If $s \in D_R(v)$, then

$$ R_{u,v}(q) = \begin{cases} R_{us,vs}(q) & \text{if } s \in D_R(u), \\ qR_{us,vs}(q) + (q-1)R_{u,vs}(q) & \text{if } s \notin D_R(u). \end{cases} $$

It is natural to wonder whether one can replace $s$ with a transposition $t$ whenever the Generalized lifting property holds. More precisely, suppose that $t$ is a transposition such that

$$ vt \le v \quad u \le ut \quad u \le vt \quad ut \le v. \qquad (3) $$
Is it true that

$$R_{u,v}(q) = qR_{ut,vt}(q) + (q-1)R_{u,vt}(q) \quad (4)$$

In general, the answer is no. For example, one can check that $u = 1324$, $v = 4231$ and $t = (24)$ give a counterexample. However, when $t$ is an inversion-minimal transposition on $(u, v)$, (4) does hold. We'll use the next lemma to prove this.

**Lemma 5.2** Let $u, v \in S_n$ and suppose that $(ik)$ is inversion-minimal on $(u, v)$. Assume further that $v_j > v_{j+1}$ and $u_j > u_{j+1}$ for some $j$ such that $i < j < k - 1$. Then $(ik)$ is inversion-minimal on $(vs_j, us_j)$.

**Proposition 5.3** Let $u, v \in S_n$ with $v \ge u$. Let $t = (ij)$ be inversion-minimal on $(u, v)$. Then

$$R_{u,v}(q) = qR_{ut,vt}(q) + (q-1)R_{u,vt}(q).$$

**Remark 5.4** The above statement holds mutatis mutandis for the $\tilde{R}$-polynomials, which are a renormalization of the $R$-polynomials.

**Example 5.5** Take $u = 21345$, $v = 53421$ and $t = (13)$. We have

$$R_{u,v}(q) = q^8 - 4q^7 + 7q^6 - 8q^5 + 8q^4 - 8q^3 + 7q^2 - 4q + 1$$

$$R_{ut,vt}(q) = q^6 - 4q^5 + 7q^4 - 8q^3 + 7q^2 - 4q + 1$$

and

$$R_{u,vt}(q) = q^7 - 4q^6 + 7q^5 - 8q^4 + 8q^3 - 7q^2 + 4q - 1.$$

**Definition 5.6** A matching of a graph $G = (V, E)$ is an involution $M : V \to V$ such that $\{v, M(v)\} \in E$ for all $v \in V$.

**Definition 5.7** Let $P$ be a graded poset. A matching $M$ of the Hasse diagram of $P$ is a special matching if for all $x, y \in P$ such that $x \le y$, we have $M(x) = y$ or $M(x) \le M(y)$.

It is known that special matchings can be used to compute $R$-polynomials:

**Theorem 5.8** [BCM06, Theorem 7.8] Let $(W, S)$ be a Coxeter system, let $w \in W$, and let $M$ be a special matching of the Hasse diagram of the interval $[e, w]$ in Bruhat order. Then

$$R_{u,w}(q) = q^c R_{M(u),M(w)}(q) + (q^c - 1)R_{u,M(w)}(q)$$

for all $u \le w$, where $c = 1$ if $M(u) \ge u$ and $c = 0$ otherwise.

One might guess that the Generalized lifting property is compatible with the notion of special matching. More precisely, one might speculate that if $[u, v] \subset S_n$ and $t$ is inversion-minimal on $(u, v)$ then there is a special matching $M$ of $[u, v]$ such that $M(u) = ut$ and $M(v) = vt$. The following gives an example of this.

**Example 5.9** Take $u = 143265$ and $v = 254163$. Then $t = (36)$ is inversion-minimal on $(u, v)$. Suppose that a special matching $M$ of $[u, v]$ (see Figure 6) satisfies $M(v) = vt$ and $M(u) = ut$. Then we must have $M(154263) = 153264$ and $M(243165) = 245163$. Observe that the result is a multiplication matching. Similarly, if we take $t = (14)$, another inversion-minimal transposition on $(u, v)$, we again obtain a multiplication matching.

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

The following example shows that it is not the case that an inversion-minimal transposition must be compatible with a special matching. This makes Proposition 5.3 all the more surprising, and shows that it cannot be deduced using special matchings.

**Example 5.10** Take $u = 1324$ and $v = 4312$. Then $t = (24)$ is inversion-minimal on $(u, v)$. Suppose that a special matching $M$ of $[u, v]$ (Figure 7) satisfies $M(v) = vt$, i.e., sends 4312 to 4213. Then

$$M(4132) = 4123, M(1432) = 1423, M(1342) = 1324, M(3142) = 3124, M(3412) = 3214, M(2413) = 2314.$$

But $M(2314) = 2413 \not\geq 1342 = M(1324)$, which is a contradiction.

<figure><img src="image_8.png" /><figcaption>Figure 7</figcaption></figure>

## Acknowledgements

E.T. is grateful to Francesco Brenti for sending his Maple code for computing R-polynomials. L.W. would like to thank Yuji Kodama for their joint work on the Toda lattice, which provided motivation for this project. She is also grateful to Konni Rietsch and Robert Marsh for generously sharing their ideas about the Gelfand-Serganova stratification. Finally, we would like to thank Fabrizio Caselli, Allen Knutson, Thomas Lam, Robert Proctor, and Alex Woo for helpful conversations.

This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 1106400, and the National Science Foundation CAREER Award DMS-1049513. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the authors(s) and do not necessarily reflect the views of the National Science Foundation.

## References

[ARW13] F. Ardila, F. Rincon, and L. Williams. Positroids and non-crossing partitions. To appear in the *Trans. Amer. Math. Soc.*, 2013.

[BB05] A. Björner and F. Brenti. *Combinatorics of Coxeter groups*, volume 231 of *Graduate Texts in Mathematics*. Springer, New York, 2005.

[BCM06] Francesco Brenti, Fabrizio Caselli, and Mario Marietti. Special matchings and Kazhdan-Lusztig polynomials. *Adv. Math.*, 202(2):555-601, 2006.
[BGW03] Alexandre V. Borovik, I. M. Gelfand, and Neil White. *Coxeter matroids*, volume 216 of *Progress in Mathematics*. Birkhäuser Boston, Inc., Boston, MA, 2003.

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

[Ede81] Paul H. Edelman. The Bruhat order of the symmetric group is lexicographically shellable. *Proc. Amer. Math. Soc.*, 82(3):355–358, 1981.

[GS87] I. M. Gel'fand and V. V. Serganova. Combinatorial geometries and the strata of a torus on homogeneous compact manifolds. *Uspekhi Mat. Nauk*, 42(2(254)):107–134, 287, 1987.

[KL79] David Kazhdan and George Lusztig. Representations of Coxeter groups and Hecke algebras. *Invent. Math.*, 53(2):165–184, 1979.

[KW13] Y. Kodama and L. Williams. The full Kostant-Toda hierarchy on the positive flag variety, 2013. To appear in *Comm. Math. Phys*.

[Pos09] A. Postnikov. Permutohedra, associahedra, and beyond. *Int. Math. Res. Not.* IMRN, (6):1026–1106, 2009.

[Pro82] Robert A. Proctor. Classical Bruhat orders and lexicographic shellability. *J. Algebra*, 77(1):104–126, 1982.

[Wel76] Dominic J. A. Welsh. *Matroid theory*. Academic Press [Harcourt Brace Jovanovich Publishers], London, 1976. L. M. S. Monographs, No. 8.