# From Bruhat intervals to intersection lattices and a conjecture of Postnikov

Axel Hultman¹, Svante Linusson¹†, John Shareshian²‡, and Jonas Sjöstrand³

¹Department of Mathematics, KTH, SE-100 44, Stockholm, Sweden

²Department of Mathematics, Washington University, St Louis, MO 63130, USA

³Department of Mathematics and Physics, Mälardalen University, Box 883, SE-721 23, Västerås, Sweden

**Abstract.** We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation $w \in \mathfrak{S}_n$ is at most the number of elements below $w$ in the Bruhat order, and (B) that equality holds if and only if $w$ avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups.

**Résumé.** Nous prouvons la conjecture de A. Postnikov que (A) le nombre de régions dans l’arrangement d’hyperplans inverses associés à la permutation $w \in \mathfrak{S}_n$ est au plus égal au nombre d’éléments en dessous de $w$ dans l’ordre de Bruhat, et (B) il y a égalité si et seulement si $w$ évite les motifs 4231, 35142, 42513 et 351624. De plus, l’affirmation (A) est généralisée à tous les groupes de réflexion finis.

**Keywords:** Bruhat order, inversion arrangements, intersection lattices

## 1 Introduction

We confirm a conjecture of A. Postnikov (6, Conjecture 24.4(1)), relating the interval below a permutation $w \in \mathfrak{S}_n$ in the Bruhat order and a hyperplane arrangement determined by the inversions of $w$. Definitions of key objects discussed but not defined in this introduction can be found in Section 2.

Fix $n \in \mathbb{N}$ and $w \in \mathfrak{S}_n$. An inversion of $w$ is a pair $(i, j)$ such that $1 \le i < j \le n$ and $iw > jw$. (Here we write $w$ as a function acting from the right on $[n] := \{1, \dots, n\}$.) We write $\text{INV}(w)$ for the set of inversions of $w$.

For $1 \le i < j \le n$, set

$$H_{ij} := \{(v_1, \dots, v_n) \in \mathbb{R}^n \mid v_i = v_j\},$$

so $H_{ij}$ is a hyperplane in $\mathbb{R}^n$. Set

$$A'_{w} := \{H_{ij} \mid (i, j) \in \text{INV}(w)\},$$

<footnote>†Royal Swedish Academy of Sciences Research Fellow supported by a grant from the Knut and Alice Wallenberg Foundation</footnote>

<footnote>‡Supported by NSF grant DMS-0604233</footnote>
so $\mathcal{A}'_w$ is a central hyperplane arrangement in $\mathbb{R}^n$. Let $\mathrm{re}(w)$ be the number of connected components of $\mathbb{R}^n \setminus \cup \mathcal{A}'_w$. Let $\mathrm{br}(w)$ be the size of the ideal generated by $w$ in the Bruhat order on $\mathfrak{S}_n$.

The first part of Postnikov's conjecture is that

(A) for all $n \in \mathbb{N}$ and all $w \in \mathfrak{S}_n$ we have $\mathrm{re}(w) \le \mathrm{br}(w)$.

In Theorem 3.3 below, we give a generalization of (A) that holds for all finite reflection groups.

Let $m \le n$, let $p \in \mathfrak{S}_m$ and let $w \in \mathfrak{S}_n$. We say $w$ avoids $p$ if there do not exist $1 \le i_1 < i_2 < \dots < i_m \le n$ such that for all $j, k \in [m]$ we have $i_j w < i_k w$ if and only if $jp < kp$. The second part of Postnikov's conjecture is that

(B) for all $n \in \mathbb{N}$ and all $w \in \mathfrak{S}_n$, we have $\mathrm{br}(w) = \mathrm{re}(w)$ if and only if $w$ avoids all of 4231, 35142, 42513 and 351624.

Here we have written the four permutations to be avoided in one line notation, that is, we write $w \in \mathfrak{S}_n$ as $1w\cdots nw$. As is standard, we call the permutations to be avoided patterns. With Theorem 4.1 we show that avoidance of the four given patterns is necessary for the equality of $\mathrm{br}(w)$ and $\mathrm{re}(w)$ and with Corollary 5.7 we show that this avoidance is sufficient, thus proving all of Postnikov's conjecture.

We remark that the avoidance of the four given patterns has arisen in work of Postnikov on total positivity (6), work of Gasharov and Reiner on Schubert varieties in partial flag manifolds (4) and work of Sjöstrand (7) on the Bruhat order.

The present paper is an extended abstract. In the full length version (5) more details are given, and several applications of our main results (and their proofs) are presented. For example, inequalities are deduced that relate the Betti numbers of the complement of the complexification of $\mathcal{A}'_w$ to the Betti numbers of the Schubert variety indexed by $w$.

## 2 Prerequisites

In this section, we review basic material on hyperplane arrangements and Coxeter groups that we will use in the sequel. For more information on these subjects the reader may consult, for example, (8) and (2), respectively.

A Coxeter group is a group $W$ generated by a finite set $S$ of involutions subject only to relations of the form $(ss')^{m(s,s')} = 1$, where $m(s, s') = m(s', s) \ge 2$ if $s \ne s'$. The pair $(W, S)$ is referred to as a Coxeter system.

The length, denoted $\ell(w)$, of $w \in W$ is the smallest $k$ such that $w = s_1 \cdots s_k$ for some $s_1, \dots, s_k \in S$. If $w = s_1 \cdots s_k$ and $\ell(w) = k$, then the sequence $s_1 \cdots s_k$ is called a reduced expression for $w$.

Every Coxeter group admits a partial order called the Bruhat order.

**Definition 2.1** Given $u, w \in W$, we say that $u \le w$ in the Bruhat order if every reduced expression (equivalently, some reduced expression) for $w$ contains a subword representing $u$. In other words, $u \le w$ if whenever $w = s_1 \cdots s_k$ with each $s_i \in S$ and $\ell(w) = k$, there exist $1 \le i_1 < \cdots < i_j \le k$ such that $u = s_{i_1} \cdots s_{i_j}$.

Although it is not obvious from Definition 2.1, the Bruhat order is a partial order on $W$. Observe that the identity element $e \in W$ is the unique minimal element with respect to this order.
Given $u, w \in W$, the definition is typically not very useful for determining whether $u \le w$. When $W = \mathfrak{S}_n$ is a symmetric group, with $S$ being the set of adjacent transpositions $(i \ i+1)$, the following nice criterion exists. For a permutation $w \in \mathfrak{S}_n$ and $i, j \in [n] = \{1, \dots, n\}$, let

$$w[i, j] = |\{m \in [i] \mid mw \ge j\}|.$$

Let $P(w) = (a_{ij})$ be the permutation matrix corresponding to $w \in \mathfrak{S}_n$ (so $a_{ij} = 1$ if $iw = j$ and $a_{ij} = 0$ otherwise). Then $w[i, j]$ is simply the number of ones weakly above and weakly to the right of position $(i, j)$ in $P(w)$, that is, the number of pairs $(k, l)$ such that $k \le i, j \le l$ and $a_{kl} = 1$.

A proof of the next proposition can be found in (2).

**Proposition 2.2 (Standard criterion)** Given $u, v \in \mathfrak{S}_n$, we have $u \le w$ in the Bruhat order if and only if $u[i, j] \le w[i, j]$ for all $(i, j) \in [n]^2$.

In fact, it is only necessary to compare $u[i, j]$ and $w[i, j]$ for certain pairs $(i, j)$; see Lemma 5.1 below.

Each finite Coxeter group $W$ can be embedded in some $GL_n(\mathbb{R})$ in such a way that the elements of $S$ act as reflections. That is, having fixed such an embedding, for each $s \in S$ there is some hyperplane $H_s$ in $\mathbb{R}^n$ such that $s$ acts on $\mathbb{R}^n$ by reflection through $H_s$. Thus a reflection in $W$ is defined to be an element conjugate to an element of $S$. Letting $T$ denote the set of reflections in $W$, we therefore have $T = \{w^{-1}sw \mid s \in S, w \in W\}$. Every finite subgroup of $GL_n(\mathbb{R})$ generated by reflections is a Coxeter group. A natural geometric representation of a Coxeter group $W$ is an embedding of the type just described in which no point in $\mathbb{R}^n \setminus \{0\}$ is fixed by all of $W$.

Sometimes we work with the generating set $T$ rather than $S$. We define the absolute length $\ell'(w)$ as the smallest number of reflections needed to express $w \in W$ as a product. In the case of finite Coxeter groups, i.e. finite reflection groups, a nice formula for the absolute length follows from work of Carter (3, Lemma 2).

**Proposition 2.3 (Carter (3))** Let $W$ be a finite reflection group in a natural geometric representation. Then, the absolute length of $w \in W$ equals the codimension of the space of fixed points of $w$.

Next, we recall a convenient interaction between reflections and (not necessarily reduced) expressions. For a proof, the reader may consult (2, Theorem 1.4.3). By a hat over an element, we understand deletion of that element.

**Proposition 2.4 (Strong exchange property)** Suppose $w = s_1 \dots s_k$ for some $s_i \in S$. If $t \in T$ has the property that $\ell(tw) < \ell(w)$, then $tw = s_1 \dots \hat{s_i} \dots s_k$ for some $i \in [k]$.

A real hyperplane arrangement is a set $\mathcal{A}$ of affine hyperplanes in some real vector space $V \cong \mathbb{R}^n$. We will assume that $\mathcal{A}$ is finite. The arrangement $\mathcal{A}$ is called linear if each $H \in \mathcal{A}$ is a linear subspace of $\mathbb{R}^n$. The intersection lattice of a linear arrangement $\mathcal{A}$ is the set $L_{\mathcal{A}}$ of all subspaces of $V$ that can be obtained by intersecting some elements of $\mathcal{A}$, ordered by reverse inclusion. (The minimal element $V$ of $L_{\mathcal{A}}$ is obtained by taking the intersection of no elements of $\mathcal{A}$ and will be denoted by $\hat{0}$.)

A crucial property of $L_{\mathcal{A}}$ is that it admits a so-called EL-labelling. The general definition of such labellings is not important to us; see (1) for details. Instead, we focus on the properties of a particular EL-labelling of $L_{\mathcal{A}}$, the standard labelling $\lambda$, which we now describe.

Let $\triangleleft$ denote the covering relation of $L_{\mathcal{A}}$. Choose some total ordering of the hyperplanes in $\mathcal{A}$. To each covering $A \triangleleft B$ we associate the label

$$\lambda(A \triangleleft B) = \min\{H \in \mathcal{A} \mid H \le B \text{ and } H \not\le A\}.$$
The complement $V \setminus \bigcup \mathcal{A}$ of the arrangement $\mathcal{A}$ is a disjoint union of contractible connected components called the regions of $\mathcal{A}$. The number of regions can be computed from $\lambda$. Given any saturated chain $C = \{A_0 \subsetneq \dots \subsetneq A_m\}$ in $L_{\mathcal{A}}$, say that $C$ is $\lambda$-decreasing if $\lambda(A_{i-1} \subsetneq A_i) > \lambda(A_i \subsetneq A_{i+1})$ for all $i \in [m-1]$.

**Proposition 2.5 (Björner (1), Zaslavsky (9))** The number of regions of $\mathcal{A}$ is the same as the number of $\lambda$-decreasing saturated chains that contain $\hat{0}$.

**Proof:** It follows from the theory of EL-labellings (1) that the number of chains with the asserted properties is

$$ \sum_{A \in L_{\mathcal{A}}} |\mu(\hat{0}, A)|, $$

where $\mu$ is the Möbius function of $L_{\mathcal{A}}$. By a result of Zaslavsky (9), this number is precisely the number of regions of $\mathcal{A}$. $\square$

## 3 From intersection lattices to Bruhat intervals

Let $(W, S)$ be a finite Coxeter system. Fix a reduced expression $s_1 \cdots s_k$ for some $w \in W$. Given $i \in [k]$, define the reflection

$$ t_i = s_1 \cdots s_{i-1} s_i s_{i-1} \cdots s_1 \in T. $$

The set $T_w = \{t_i | i \in [k]\}$ only depends on $w$ and not on the chosen reduced expression. In fact, $T_w = \{t \in T | \ell(tw) < \ell(w)\}$. We call $T_w$ the inversion set of $w$. If $W = \mathfrak{S}_n$ and $T$ is the set of transpositions, then the transposition $(ij)$ lies in $T_w$ if and only if $(i, j) \in \text{INV}(w)$. Being reflections, the various $t_i$ correspond to reflecting hyperplanes $H_i$ in a standard geometric representation of $W$. Thus, $w$ determines an arrangement of real linear hyperplanes

$$ \mathcal{A}_w = \{H_i | i \in [k]\} $$

which we call the inversion arrangement of $w$.

Let us order the hyperplanes in $\mathcal{A}_w$ by $H_1 > H_2 > \dots > H_k$. We denote by $\lambda$ the standard EL-labelling of the intersection lattice $L_w = L_{\mathcal{A}_w}$ induced by this order. In particular, $\lambda$ depends on the choice of reduced expression for $w$.

Let $C^\downarrow$ be the set of $\lambda$-decreasing saturated chains in $L_w$ that include the minimum element $\hat{0}$. By Proposition 2.5, $C^\downarrow$ is in bijection with the set of regions of $\mathcal{A}_w$. We will construct an injective map from $C^\downarrow$ to the Bruhat interval $[e, w]$.

Let $C = \{\hat{0} = X_0 \subsetneq X_1 \subsetneq \dots \subsetneq X_m\} \subset L_w$ be a saturated chain. Suppose, for each $i \in [m]$, we have $\lambda(X_{i-1} \subsetneq X_i) = H_{j_i}$. Define

$$ p(C) = t_{j_1} \cdots t_{j_m} \in W. $$

**Proposition 3.1** If $C \in C^\downarrow$, then $p(C)w \le w$ in the Bruhat order. Thus, $C \mapsto p(C)w$ defines a map $\phi: C^\downarrow \to [e, w]$.

**Proof:** When $C = \{\hat{0} = X_0 \subsetneq X_1 \subsetneq \dots \subsetneq X_m\} \subset L_w$ is $\lambda$-decreasing, we have

$$ p(C)w = \prod_{i \in [k] \setminus \{j_1, \dots, j_m\}} s_i. $$
Thus, $p(C)w$ can be represented by an expression which is a subword of the chosen reduced expression for $w$. $\square$

In order to deduce injectivity of $\phi$, we need the following lemma.

**Lemma 3.2** For every saturated chain $C = \{\hat{0} = X_0 \triangleleft X_1 \triangleleft \cdots \triangleleft X_m\} \subset L_w$, we have $\ell'(p(C)) = m$. $\square$

**Proof:** Induction on $m$ using Proposition 2.3. We refer to (5) for the details. $\square$

We are now in position to prove the main result of this section.

**Theorem 3.3** The map $\phi: C^{\downarrow} \to [e, w]$ is injective.

**Proof:** If $C$ is the saturated chain $\hat{0} = X_0 \triangleleft \cdots \triangleleft X_m$ in $L_w$, then $X_m$ is contained in the fixed point space of $p(C)$ (since $p(C)$ is a product of reflections through hyperplanes, all of which contain $X_m$). Lemma 3.2 and Proposition 2.3 therefore imply that $X_m$ is the fixed point space of $p(C)$. In particular, if two chains have the same image under $p$, then their respective maximum elements coincide.

Now suppose $\phi(C) = \phi(D)$, i.e. $p(C) = p(D)$, for some $C, D \in C^{\downarrow}$. We shall show that $C = D$. Write $C = \{\hat{0} = X_0 \triangleleft \cdots \triangleleft X_m\}$ and $D = \{\hat{0} = Y_0 \triangleleft \cdots \triangleleft Y_m'\}$. We have shown that $m = m'$ and $X_m = Y_m$. Since both $C$ and $D$ are $\lambda$-decreasing, the construction of $\lambda$ implies $\lambda(X_{m-1} \triangleleft X_m) = \lambda(Y_{m-1} \triangleleft Y_m) = H$, where $H$ is the smallest hyperplane below $X_m = Y_m$ in $L_w$. With $t$ denoting the reflection corresponding to $H$, we thus have $p(C \setminus X_m) = p(D \setminus Y_m) = p(C)t = p(D)t$. Our theorem is proved by induction on $m$. $\square$

Let us explain how the first part of Postnikov's conjecture, statement (A) in the Introduction, follows from Theorem 3.3. The symmetric group $\mathfrak{S}_n$ acts on $\mathbb{R}^n$ by permuting coordinates. Under this action, the transposition $(i \ j)$ acts by a reflection in the hyperplane given by $x_i = x_j$. However, this is not quite a natural geometric representation of $\mathfrak{S}_n$ because the entire line given by $x_1 = \cdots = x_n$ is fixed by all elements. To rectify the situation we may study the restriction of the action to the subspace $V^{(n-1)} \subset \mathbb{R}^n$ that consists of the points in $\mathbb{R}^n$ whose coordinates sum to zero. Thus, $A_w$ is a hyperplane arrangement in $V^{(n-1)}$.

Recalling our convention that $uw$ means "first $u$, then $w$" for $u, w \in \mathfrak{S}_n$ we see that $(i \ j) \in T_w$ if and only if $(i, j)$ is an inversion of $w$ in the ordinary sense. Thus, for $w \in \mathfrak{S}_n$,

$$A_w = \{H \cap V^{(n-1)} \mid H \in A'_w\}.$$

In the language of (8), $A_w$ is the essentialization of $A'_w$. The regions in the complements of $A_w$ and $A'_w$ are in an obvious bijective correspondence and statement (A) follows.

Although we do not know when $\phi$ is surjective for an arbitrary finite reflection group, for symmetric groups we have the following result, whose proof is contained in the next two sections.

**Theorem 3.4** If $w \in \mathfrak{S}_n$, the map $\phi$ is surjective (and hence bijective) if and only if $w$ avoids the patterns 4231, 35142, 42513 and 351624.
# 4 A necessity criterion for surjectivity in symmetric groups

We now confine our attention to the type A case when $W = \mathfrak{S}_n$ is a symmetric group. Depending on what is most convenient, either one-line notation or cycle notation is used to represent a permutation $w \in \mathfrak{S}_n$. In this setting, as we have seen, $T$ becomes the set of transpositions in $\mathfrak{S}_n$ and $T_w = \{(ij) \mid i < j \text{ and } iw > jw\}$ can be identified with $\mathrm{INV}(w)$.

**Theorem 4.1** Suppose $W$ is a symmetric group. If $\phi : C^\downarrow \to [e, w]$ is surjective, then $w$ avoids the patterns 4231, 35142, 42513 and 351624.

**Proof:** It follows from Lemma 3.2 that if $u \le w$ is in the image of $\phi$, then $uw^{-1}$ can be written as a product of $l'(uw^{-1})$ inversions of $w$. Below we construct, for $w$ containing each of the four given patterns, elements $u \le w$ that fail to satisfy this property.

**Case 4231.** Suppose $w$ contains the pattern 4231 in positions $n_1, n_2, n_3$, and $n_4$, meaning that $n_1w > n_3w > n_2w > n_4w$. Then, let $u = (n_1n_4)(n_2n_3)w$. Invoking the standard criterion, Proposition 2.2, it suffices to check $(14)(23)4231 = 1324 < 4231$ in order to conclude $u < w$. Now, $uw^{-1} = (n_1n_4)(n_2n_3)$ has absolute length 2. However, $uw^{-1}$ cannot be written as a product of two inversions of $w$, because $(n_2n_3)$ is not an inversion.

**Case 35142.** Now assume $w$ contains 35142 in positions $n_1, \dots, n_5$. Define $u = (n_1n_3n_4)(n_2n_5)w$. Again we have $u < w$; this time since $(134)(25)35142 = 12435 < 35142$. We have $uw^{-1} = (n_1n_3n_4)(n_2n_5)$ which is of absolute length 3. Neither $(n_1n_4)$ nor $(n_3n_4)$ is an inversion of $w$, so $u$ cannot be written as a product of three members of $T_w$.

**Case 42513.** Next, suppose $w$ contains 42513 in $n_1$ through $n_5$. Then, we let $u = (n_2n_5n_3)(n_1n_4)w$ and argue as in the previous cases.

**Case 351624.** Finally, if $w$ contains 351624 in positions $n_1$ through $n_6$, use $u = (n_1n_3n_6n_4)(n_2n_5)w$ and argue as before. $\square$

# 5 Pattern avoidance implies $\mathrm{br}(w) = \mathrm{re}(w)$

Let $\tilde{\mathfrak{S}}_n \subseteq \mathfrak{S}_n$ denote the set of permutations that avoid the four patterns 4231, 35142, 42513, 351624.

In this section we will represent permutations $\pi \in \mathfrak{S}_n$ by rook diagrams. These are $n$ by $n$ square boards with a rook in entry $(i, j)$, i.e. row $i$ and column $j$, if $i\pi = j$. If $x$ is a rook, we will write $x_i$ for its row number and $x_j$ for its column number.

The inversion graph of $\pi$, denoted by $G_\pi$, is a simple undirected graph with the rooks as vertices and an edge between two rooks if they form an inversion of $\pi$, i.e. if one of them is south-west of the other one. Let $\mathrm{ao}(\pi) = \mathrm{ao}(G_\pi)$ denote the number of acyclic orientations of $G_\pi$. Note that $\mathrm{ao}(\pi)$ equals the number of regions $\mathrm{re}(\pi)$ of the hyperplane arrangement $\mathcal{A}'_\pi$.

Following Postnikov (6), we will call a permutation $\pi$ *chromobruhatic* if $\mathrm{br}(\pi) = \mathrm{ao}(\pi)$. Our goal in this section is to prove that all $\pi \in \tilde{\mathfrak{S}}_n$ are chromobruhatic. This will be accomplished as follows: First we show that if $\pi$ (or its inverse) has something called a *reduction pair*, which is a pair of rooks with certain properties, then there is a recurrence relation for $\mathrm{br}(\pi)$ in terms of $\mathrm{br}(\rho)$ for some permutations $\rho \in \tilde{\mathfrak{S}}_n \cup \tilde{\mathfrak{S}}_{n-1}$ that are “simpler” than $\pi$ in a sense that will be made precise later. It turns out that the very same recurrence relation also works for expressing $\mathrm{ao}(\pi)$ in terms of a few $\mathrm{ao}(\rho)$. Finally, we show
<figure><img src="image_1.png" /><figcaption>Fig. 1: The shaded region constitutes the right hull of the permutation 35124.</figcaption></figure>

that every $\pi \in \hat{\mathfrak{S}}_n$ except the identity permutation has a reduction pair, and hence $\mathrm{br}(\pi) = \mathrm{ao}(\pi)$ by induction.

We will need two useful lemmas about the Bruhat order on the symmetric group. The first is a well-known variant of Proposition 2.2 (see e.g. (4)). A square that has a rook strictly to the left in the same row and strictly below it in the same column is called a *bubble*.

**Lemma 5.1** Let $\pi, \sigma \in \mathfrak{S}_n$. Then $\sigma \le \pi$ in the Bruhat order if and only if $\sigma[i, j] \le \pi[i, j]$ for every bubble $(i, j)$ of $\pi$.

If $\pi$ avoids the forbidden patterns, there is an even simpler criterion. Define the right hull of $\pi$, denoted by $H_R(\pi)$, as the set of squares in the rook diagram of $\pi$ that have at least one rook weakly south-west of them and at least one rook weakly north-east of them. Figure 1 shows an example. The following lemma is due to Sjöstrand (7).

**Lemma 5.2** Let $\pi \in \hat{\mathfrak{S}}_n$ and $\sigma \in \mathfrak{S}_n$. Then $\sigma \le \pi$ in the Bruhat order if and only if all rooks of $\sigma$ lie in the right hull of $\pi$.

For a permutation $\pi \in \mathfrak{S}_n$, the rook diagram of the inverse permutation $\pi^{-1}$ is obtained by transposing the rook diagram of $\pi$. Define $\pi^{\circ} = \pi_0\pi\pi_0$, where $\pi_0 = n(n-1)\cdots 1$ denotes the maximum element (in the Bruhat order) of $\mathfrak{S}_n$. Note that the rook diagram of $\pi^{\circ}$ is obtained by a 180 degree rotation of the rook diagram of $\pi$.

**Observation 5.3** The operations of transposition and rotation of the rook diagram of a permutation have the following properties.

(a) They are automorphisms of the Bruhat order, i.e.

$$ \sigma \le \tau \Leftrightarrow \sigma^{-1} \le \tau^{-1} \Leftrightarrow \sigma^{\circ} \le \tau^{\circ} \Leftrightarrow (\sigma^{\circ})^{-1} \le (\tau^{\circ})^{-1}. $$

(b) They induce isomorphisms of inversion graphs, so

$$ G_{\sigma} \cong G_{\sigma^{-1}} \cong G_{\sigma^{\circ}} \cong G_{(\sigma^{\circ})^{-1}}. $$

(c) The set of the four forbidden patterns is closed under transposition and rotation, so

$$ \sigma \in \hat{\mathfrak{S}}_n \Leftrightarrow \sigma^{-1} \in \hat{\mathfrak{S}}_n \Leftrightarrow \sigma^{\circ} \in \hat{\mathfrak{S}}_n \Leftrightarrow (\sigma^{\circ})^{-1} \in \hat{\mathfrak{S}}_n. $$

From (a) and (b) it follows that $\sigma, \sigma^{-1}, \sigma^{\circ}$ and $(\sigma^{\circ})^{-1}$ are either all chromobruhatic or all non-chromobruhatic.
<figure><img src="image_2.png" /><figcaption>**Fig. 2:** (a) A light reduction pair. (b) A heavy reduction pair. The shaded areas are empty. The size of the lighter shaded areas depends on the underlying permutation.</figcaption></figure>

If $x$ is a rook in the diagram of $\pi$ then the image of $x$ under any composition of transpositions and rotations is a rook in the diagram of the resulting permutation. In what follows, we sometimes discuss properties that the image rook (also called $x$) has in the resulting diagram, while still thinking of $x$ as lying in its original position in the diagram of $\pi$.

**Definition 5.4** Let $\pi \in \mathfrak{S}_n$ and let $x, y$ be a pair of rooks that is a descent, i.e. $y_i = x_i - 1$ and $x_j < y_j$. Then, $x, y$ is a light reduction pair if we have the situation in Figure 2(a), i.e.

* there is no rook $a$ with $a_i < y_i$ and $a_j > y_j$, and

* there is no rook $a$ with $a_i > x_i$ and $x_j < a_j < y_j$.

The pair $x, y$ is called a heavy reduction pair if we have the situation in Figure 2(b), i.e.

* there is no rook $a$ with $a_i > x_i$ and $a_j < x_j$,

* there is no rook $a$ with $a_i < y_i$ and $a_j > y_j$, and

* there is no pair of rooks $a, b$ such that $a_i < y_i$ and $b_i > x_i$ and $x_j < a_j < b_j < y_j$ (or, equivalently, there is some $x_j \le j < y_j$ such that the regions $[1, y_i - 1] \times [x_j + 1, j]$ and $[x_i + 1, n] \times [j + 1, y_j - 1]$ are both empty).

**Lemma 5.5** Let $\pi \in \hat{\mathfrak{S}}_n$ and assume that

(a) all $\rho \in \hat{\mathfrak{S}}_n$ below $\pi$ in Bruhat order, and

(b) all $\rho \in \hat{\mathfrak{S}}_{n-1}$ are chromobruhatic.

Then, $\pi$ is chromobruhatic if at least one of $\pi, \pi^{-1}, \pi^{\circ}$ and $(\pi^{\circ})^{-1}$ has a reduction pair.

**Proof:** If one of $\pi, \pi^{-1}, \pi^{\circ}$ and $(\pi^{\circ})^{-1}$ has a light reduction pair, then by Observation 5.3, $\pi, \pi^{-1}, \pi^{\circ}$ and $(\pi^{\circ})^{-1}$ all satisfy conditions (a) and (b), so we may assume that $\pi$ has a light reduction pair $x, y$. On the other hand, if none of $\pi, \pi^{-1}, \pi^{\circ}$ and $(\pi^{\circ})^{-1}$ has a light reduction pair, then one of them has a heavy reduction pair $x, y$ and we may assume that it is $\pi$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: The four forbidden patterns.</figcaption></figure>

In either case, replace $x$ by a rook $x'$ immediately above it, and replace $y$ by a rook $y'$ immediately below it. The resulting permutation $\rho$ is below $\pi$ in the Bruhat order. Note that $\rho \in \mathfrak{S}_n$ — a forbidden pattern in $\rho$ must include both of $x'$ and $y'$ but an inspection of the forbidden patterns in Figure 3 and the reduction pair situations in Figure 2 reveals that this is impossible. Thus, by the assumption in the lemma we conclude that $\rho$ is chromobruhatic.

**Case 1:** $x, y$ is a light reduction pair in $\pi$. What permutations are below $\pi$ but not below $\rho$ in the Bruhat order? Note that $\rho$ has the same bubbles as $\pi$, plus an additional bubble immediately above $y'$, i.e. at the position of $y$. Now, Lemma 5.1 yields that the only permutations below $\pi$ that are not below $\rho$ are the ones with a rook at the position of $y$. These are in one-one correspondence with the permutations weakly below the permutation $\pi - y \in \mathfrak{S}_{n-1}$ that we obtain by deleting $y$ from $\pi$ together with its row and column. Thus, we have

$$ \mathrm{br}(\pi) = \mathrm{br}(\rho) + \mathrm{br}(\pi - y). \qquad (1) $$

Now consider the inversion graphs of $\pi$, $\rho$ and $\pi - y$. It is not hard to show that $G_{\rho}$ is isomorphic to the graph $G_{\pi} \setminus \{x, y\}$ obtained by deletion of the edge $\{x, y\}$. Since all neighbors of $y'$ are also neighbors of $x'$ in $G_{\rho}$, the graph $G_{\pi - y} = G_{\rho - y'}$ is isomorphic to the graph $G_{\pi} / \{x, y\}$ obtained by contraction of the edge $\{x, y\}$. It is a well-known fact that, for any edge $e$ in any simple graph $G$, the number of acyclic orientations satisfies the recurrence relation $\mathrm{ao}(G) = \mathrm{ao}(G \setminus e) + \mathrm{ao}(G/e)$. Thus, in our case we get

$$ \mathrm{ao}(\pi) = \mathrm{ao}(\rho) + \mathrm{ao}(\pi - y). \qquad (2) $$

The right-hand sides of equations (1) and (2) are equal since $\rho$ and $\pi - y$ are chromobruhatic. We conclude that $\mathrm{br}(\pi) = \mathrm{ao}(\pi)$ so that $\pi$ also is chromobruhatic.

**Case 2:** $x, y$ is a heavy reduction pair in $\pi$, and none of $\pi, \pi^{-1}, \pi^{\ominus}$ and $(\pi^{\ominus})^{-1}$ has a light reduction pair. Since $y, x$ is not a light reduction pair in $\pi^{\ominus}$, there exists a rook $a$ in the region $A = [1, y_i - 1] \times [x_j + 1, y_j - 1]$. Analogously, since $x, y$ is not a light reduction pair in $\pi$, there exists a rook $b$ in the region $B = [x_i + 1, n] \times [x_j + 1, y_j - 1]$. As can be seen in Figure 4, the right hulls of $\pi$ and $\rho$ are the same except for the two squares containing $x$ and $y$, which belong to $H_R(\pi)$ but not to $H_R(\rho)$.

By Lemma 5.2 and inclusion-exclusion, we get

$$ \mathrm{br}(\pi) = \mathrm{br}(\rho) + \mathrm{br}(\pi - x) + \mathrm{br}(\pi - y) - \mathrm{br}(\pi - x - y) \qquad (3) $$

where $\pi - x - y \in \mathfrak{S}_{n-2}$ is the permutation whose rook diagram is obtained by deleting both of $x$ and $y$ together with their rows and columns.
<figure><img src="image_4.png" /><figcaption>Fig. 4: (a) The heavy reduction pair $x, y$ in $\pi$. The shaded areas are empty and the thick lines show segments of the border of the right hull of $\pi$. (b) The right hull of $\rho$ is the same as that of $\pi$, except for the two squares of $x$ and $y$.</figcaption></figure>

Now, for any permutation $\sigma$, let $\chi_{\sigma}(t) = \chi_{G_{\sigma}}(t)$ denote the chromatic polynomial of the inversion graph $G_{\sigma}$ (so for each positive integer $n$, $\chi_{G_{\sigma}}(n)$ is the number of vertex colorings with at most $n$ colors such that neighboring vertices get distinct colors. The following argument is based on an idea by Postnikov. It is a well-known fact that $ao(G) = (-1)^n \chi_G(-1)$ for any graph $G$ with $n$ vertices. Since $G_{\rho} = G_{\pi} \setminus \{x, y\}$, the difference $\chi_{\rho}(t) - \chi_{\pi}(t)$ is the number of $t$-colorings of $G_{\rho}$ where $x'$ and $y'$ have the same color.

Let $\mathcal{C}$ be any $t$-coloring of $G_{\pi-x-y}$ using, say, $\alpha$ different colors for the vertices in $A$ and $\beta$ different colors for those in $B$. Since the subgraph of $G_{\pi}$ induced by $A \cup B$ is a complete bipartite graph, the coloring $\mathcal{C}$ must use $\alpha + \beta$ different colors for the vertices in $A \cup B$. We can extend $\mathcal{C}$ to a coloring of $G_{\pi-y}$ by coloring the vertex $x$ with any of the $t - \alpha$ colors that are not used for the vertices in $A$. Analogously, we can extend $\mathcal{C}$ to a coloring of $G_{\pi-x}$ by coloring the vertex $y$ with any of the $t - \beta$ colors that are not used in $B$. Finally, we can extend $\mathcal{C}$ to a coloring of $G_{\rho}$ where $x'$ and $y'$ have the same color, by choosing this color among the $t - \alpha - \beta$ colors that are not used for the vertices in $A \cup B$. Summing over all $t$-colorings $\mathcal{C}$ of $G_{\pi-x-y}$ yields

$$ \begin{aligned} \chi_{\rho}(t) - \chi_{\pi}(t) &= \sum_{C} (t - \alpha - \beta) \\ &= \sum_{C} (t - \beta) + \sum_{C} (t - \alpha) - \sum_{C} t \\ &= \chi_{\pi-x}(t) + \chi_{\pi-y}(t) - t\chi_{\pi-x-y}(t). \end{aligned} $$

Using that $ao(G) = (-1)^n \chi_G(-1)$ for a graph $G$ with $n$ vertices, we finally obtain

$$ ao(\pi) = ao(\rho) + ao(\pi - x) + ao(\pi - y) - ao(\pi - x - y). \quad (4) $$

The right-hand sides of equations 3 and 4 are equal by the assumption in the lemma. Thus, $br(\pi) = ao(\pi)$ and we conclude that $\pi$ is chromobruhatic. $\square$
Let $\pi \in \mathfrak{S}_n$ be any nonidentity permutation. Then there is a pair of rooks $x, y$ that is the first descent of $\pi$, i.e. $x_i = \min\{i : i\pi < (i-1)\pi\}$ and $y_i = x_i - 1$. Analogously, let $\bar{x}, \bar{y}$ be the first descent of $\pi^{-1}$, i.e. $\bar{x}_j = \min\{j : j\pi^{-1} < (j-1)\pi^{-1}\}$ and $\bar{y}_j = \bar{x}_j - 1$.

**Proposition 5.6** For any nonidentity $\pi \in \tilde{\mathfrak{S}}_n$, either $x, y$ is a reduction pair in $\pi$ or $\bar{x}, \bar{y}$ is a reduction pair in $\pi^{-1}$, or both.

**Proof:** Under the assumption that neither of $x, y$ and $\bar{x}, \bar{y}$ is a reduction pair, we detect forbidden patterns in $\pi$. See (5) for details. $\square$

Combining Lemma 5.5 and Proposition 5.6, yields the following two corollaries via induction.

**Corollary 5.7** A permutation is chromobruhatic if it avoids the patterns 4231, 35142, 42513 and 351624.

Recall that the right and left weak orders on $\mathfrak{S}_n$ are defined by $u \le_R w \Leftrightarrow \mathrm{INV}(u) \subseteq \mathrm{INV}(w)$ and $u \le_L w \Leftrightarrow \mathrm{INV}(u^{-1}) \subseteq \mathrm{INV}(w^{-1})$. The two-sided weak order is the transitive closure of the union of the right and left weak orders.

**Corollary 5.8** Every chromobruhatic permutation is connected to the identity permutation via a saturated chain of chromobruhatic permutations in the two-sided weak order.

# 6 Open problems

In this last section, we present some ideas for future research. Some of the open problems are intentionally left vague, while others are more precise.

In Theorem 3.3, we showed that the map $\phi : C^\downarrow \to [e, w]$ is injective for any finite Coxeter group, but it is not surjective in general. When the forbidden patterns are avoided, we use an inductive counting argument showing that the finite sets $C^\downarrow$ and $[e, w]$ have the same cardinality — then surjectivity of $\phi$ follows from injectivity.

**Open problem 6.1** Is there a direct proof of the surjectivity of $\phi$ or, if not, is there another bijection $C^\downarrow \leftrightarrow [e, w]$ whose bijectivity can be proved directly?

**Open problem 6.2** When $\phi$ is not surjective, what is its image?

For example by considering Betti numbers (see (5, Section 7)), one can deduce that the number of elements of even length not lying in the image of $\phi$ equals the number of such elements of odd length. In particular, evenly many elements of $[e, w]$ do not lie in the image of $\phi$.

**Open problem 6.3** Find a criterion for the surjectivity of $\phi$ in an arbitrary finite reflection group.

As noted in the introduction, our work (following Postnikov) marks the third appearance of the four patterns 4231, 35142, 42513, and 351624 in the study of flag manifolds and Bruhat order. The first time was in 2002 when Gasharov and Reiner (4) studied the cohomology of smooth Schubert varieties in partial flag manifolds. In their paper, they find a simple presentation for the integral cohomology ring, and it turns out that this presentation holds for a larger class of subvarieties of partial flag manifolds, namely the ones defined by inclusions. They characterize these varieties by the same pattern avoidance condition that appears in our work.

More recently, Sjöstrand (7) used the pattern condition to characterize permutations whose right hull covers exactly the lower Bruhat interval below the permutation; see Lemma 5.2.
Yet another way to characterize the permutations that avoid the four patterns follows from a more
detailed analysis of $\phi$; see (5, Section 6).

As is discussed in (7) there seems to be no direct connection between the “right hull” result and the “defined by inclusions” result. Though we use Sjöstrand’s result in the proof of Lemma 5.5, we have not found any simple reason why the same pattern condition turns up again.

**Open problem 6.4** *Is there a simple reason why the same pattern condition turns up in three different contexts: Gasharov and Reiner’s “defined by inclusions”, Sjöstrand’s “right hull”, and Postnikov’s (now proved) conjecture?*

**Open problem 6.5** *Does the poset structure of the Bruhat interval determine the intersection lattice uniquely? In other words, for any two finite Coxeter systems $(W, S)$ and $(W', S')$ and elements $w \in W$, $w' \in W'$, does $[e, w] \cong [e', w']$ imply $L_w \cong L_{w'}$?*

It is not hard to check that the assertion is true for $\ell(w) \le 4$.

Finally, it would be interesting to know whether our results could be extended to general Bruhat intervals, i.e. $[u, w]$ with $u \neq e$.

**Open problem 6.6** *Given a (finite) Coxeter system $(W, S)$ and $u, w \in W$ with $u \le w$ in Bruhat order, is there a hyperplane arrangement $\mathcal{A}_{u,w}$, naturally associated with $u$ and $w$, which has as many regions as there are elements in $[u, w]$ (at least for $u, w$ in some interesting subset of $W$)?*

References

[1] A. Björner, Shellable and Cohen-Macaulay partially ordered sets, *Trans. Amer. Math. Soc.* **260** (1980), 159–183.

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

[3] R. W. Carter, Conjugacy classes in the Weyl group, *Compositio Math.* **25** (1972), 1–59.

[4] V. Gasharov, V. Reiner, Cohomology of smooth schubert varieties in partial flag manifolds, *J. London Math. Soc.* **(2)** **66** (2002), 550–562.

[5] A. Hultman, S. Linusson, J. Shareshian, J. Sjöstrand, From Bruhat intervals to intersection lattices and a conjecture of Postnikov, arXiv: 0710:1220v1 [math.CO].

[6] A. Postnikov, Total positivity, Grassmannians, and networks, arXiv: math/0609764v1 [math.CO].

[7] J. Sjöstrand, Bruhat intervals as rooks on skew Ferrers boards, *J. Combin. Theory Ser. A* **(7)** **114** (2007), 1182–1198.

[8] R. P. Stanley, *An introduction to hyperplane arrangements*, preprint 2006, available at http://math.mit.edu/~rstan/arrangements/arr.html

[9] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, *Mem. Amer. Math. Soc.*, no. 154, (1975).