# The Bruhat order on conjugation-invariant sets of involutions in the symmetric group

Mikael Hansson

► To cite this version:

Mikael Hansson. The Bruhat order on conjugation-invariant sets of involutions in the symmetric group. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.547-558, 10.46298/dmtcs.2472. hal-01337794

HAL Id: hal-01337794

https://hal.science/hal-01337794

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
# The Bruhat order on conjugation-invariant sets of involutions in the symmetric group

Mikael Hansson†

Department of Mathematics, Linköping University, Sweden

**Abstract.** Let $I_n$ be the set of involutions in the symmetric group $S_n$, and for $A \subseteq \{0, 1, \dots, n\}$, let

$$F_n^A = \{\sigma \in I_n \mid \sigma \text{ has a fixed points for some } a \in A\}.$$

We give a complete characterisation of the sets $A$ for which $F_n^A$, with the order induced by the Bruhat order on $S_n$, is a graded poset. In particular, we prove that $F_n^{\{1\}}$ (i.e., the set of involutions with exactly one fixed point) is graded, which settles a conjecture of Hultman in the affirmative. When $F_n^A$ is graded, we give its rank function. We also give a short new proof of the EL-shellability of $F_n^{\{0\}}$ (i.e., the set of fixed point-free involutions), which was recently proved by Can, Cherniavsky, and Twelbeck.

**Résumé.** Soit $I_n$ l'ensemble d'involutions dans le groupe symétrique $S_n$, et pour $A \subseteq \{0, 1, \dots, n\}$, soit

$$F_n^A = \{\sigma \in I_n \mid \sigma \text{ a points fixes pour quelque } a \in A\}.$$

Nous caractérisons tous les ensembles $A$ dont les $F_n^A$, avec l'ordre induit par l'ordre de Bruhat sur $S_n$, est un poset gradué. En particulier, nous démontrons que $F_n^{\{1\}}$ (c'est-à-dire, l'ensemble d'involutions avec précis en point fixe) est gradué, ce qui résout une conjecture d'Hultman à l'affirmative. Lorsque $F_n^A$ est gradué, nous donnons sa fonction de rang. En plus, nous donnons une nouvelle démonstration courte l'EL-shellability de $F_n^{\{0\}}$ (c'est-à-dire, l'ensemble d'involutions sans points fixes), établie récemment par Can, Cherniavsky et Twelbeck.

**Keywords:** Bruhat order, symmetric group, involution, conjugacy class, graded poset, EL-shellability

## 1 Introduction

Partially ordered by the Bruhat order, the symmetric group $S_n$ is a graded poset whose rank function is given by the number of inversions, and Edelman [4] proved that it is EL-shellable. Richardson and Springer [10] proved that the set $I_n$ of involutions in $S_n$ and the set $F_n^0$ of fixed point-free involutions are graded. Incitti [9] proved that the rank function of $I_n$ can be expressed as the average of the number of inversions and the number of exceedances, and that $I_n$ is EL-shellable. Hultman [8] studied (in a more general setting, which we shall describe shortly) $F_n^0$ and $F_n^1$, the set of involutions with exactly one

<footnote>†Email: mikael.hansson@liu.se</footnote>
fixed point. It follows that $F_n^0$ is graded and Hultman conjectured that the same is true for $F_n^1$. Can, Cherniavsky, and Twelbeck [3] recently proved that $F_n^0$ is EL-shellable.

We consider the following generalisation. For $a \in \{0, 1, \dots, n\}$, let $F_n^a$ be the conjugacy class in $S_n$ consisting of the involutions with $a$ fixed points, and for $A \subseteq \{0, 1, \dots, n\}$, let

$$F_n^A = \bigcup_{a \in A} F_n^a.$$

Both $I_n$ and $F_n^A$ are regarded as posets with the order induced by the Bruhat order on $S_n$. Note that

$$F_n^A = \{\sigma \in I_n \mid \sigma \text{ has } a \text{ fixed points for some } a \in A\}.$$

Also note that for all elements in $I_n$, the number of fixed points is congruent to $n$ modulo 2. Hence, we may assume that all members of $A$ have the same parity as $n$.

Depicted in Figures 1 and 2, are the Hasse diagrams of $I_4$, $F_4^0$, and $F_4^2$.

<figure><img src="image_2.png" /><figcaption>**Figure 1:** Hasse diagram of $I_4$ with the involutions with zero (○), two (●), and four (◇) fixed points indicated.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Figure 2:** Hasse diagrams of $F_4^0$ (left) and $F_4^2$ (right).</figcaption></figure>

Our main result is a complete characterisation of the sets $A$ for which $F_n^A$ is graded. In particular, we prove that $F_n^1$ is graded.

Informally, $F_n^A$ is graded precisely when $A - \{n\}$ is empty or an “interval,” which may consist of a single element if it is 0, 1, or $n-2$. The following theorem, which is our main result, makes the above precise. It also gives the rank function of $F_n^A$ when it exists.
**Theorem 1** The poset $F_n^A$ is graded if and only if $A - \{n\} = \emptyset$ or $A - \{n\} = \{a_1, a_1 + 2, \dots, a_2\}$ with $a_1 \in \{0, 1\}$, $a_2 = n - 2$, or $a_2 - a_1 \ge 2$. Furthermore, when $F_n^A$ is graded, its rank function $\rho$ is given by

$$ \rho(\sigma) = \frac{\mathrm{inv}(\sigma) + \mathrm{exc}(\sigma) - n + \tilde{a}}{2} + \begin{cases} 1 & \text{if } n \in A \\ 0 & \text{otherwise,} \end{cases} $$

where $\mathrm{inv}(\sigma)$ and $\mathrm{exc}(\sigma)$ denote the number of inversions and exceedances, respectively, of $\sigma$, and $\tilde{a} = \max(A - \{n\})$. In particular, $F_n^A$ has rank

$$ \rho(F_n^A) = \frac{n^2 - a^2 - 2n + 2\tilde{a}}{4} + \begin{cases} 1 & \text{if } n \in A \\ 0 & \text{otherwise,} \end{cases} $$

where $a = \min A$.

The following result is direct consequence of Theorem 1.

**Corollary 2** The posets $F_n^0$, $F_n^1$, $F_n^{n-2}$, and $F_n^n$ are the only graded conjugacy classes of involutions in $S_n$. Furthermore, the rank function $\rho$ of $F_n^0$ and $F_n^1$ is given by

$$ \rho(\sigma) = \frac{\mathrm{inv}(\sigma) - \lfloor n/2 \rfloor}{2}, $$

and the rank function $\rho$ of $F_n^{n-2}$ is given by

$$ \rho(\sigma) = \frac{\mathrm{inv}(\sigma) - 1}{2}. $$

It is well known that $F_n^{n-2}$ is graded (in fact, it coincides with the root poset of the Weyl group $A_{n-1} \cong S_n$). As was mentioned above, the gradedness of $F_n^0$ was proved by Richardson and Springer, and that of $F_n^1$ was conjectured by Hultman. These two posets are special cases of a more general construction from Hultman's paper [8], which we now describe. (i)

Given a finitely generated Coxeter system $(W, S)$ and an involutive automorphism $\theta$ of $(W, S)$ (i.e., a group automorphism $\theta$ of $W$ such that $\theta(S) = S$ and $\theta^2 = \mathrm{id}$), let

$$ \iota(\theta) = \{\theta(w^{-1})w \mid w \in W\} $$

and

$$ \mathcal{I}(\theta) = \{w \in W \mid \theta(w) = w^{-1}\} $$

be the sets of *twisted identities* and *twisted involutions*, respectively. Clearly, $\iota(\theta) \subseteq \mathcal{I}(\theta) \subseteq W$. Note that when $\theta = \mathrm{id}$, $\iota(\theta)$ and $\mathcal{I}(\theta)$ reduce to the sets of the (ordinary) identity and (ordinary) involutions in $W$. Each subset of $W$ is regarded as a poset with the order induced by the Bruhat order on $W$. When $W$ is the symmetric group $S_n$, there is a unique non-trivial automorphism of $(W, S)$, mapping $s_i = (i, i+1)$ to $s_{n-i}$.

<footnote>(i) The results below are taken from [6, 7, 8]. In general, we do not indicate which results are from which paper. For general Coxeter group terminology and results, see [2].</footnote>
We say that $\theta$ has the no odd flip property if the order of $s\theta(s)$ is even or infinite for all $s \in S$ with $s \neq \theta(s)$. If $W$ is finite and irreducible, then $\theta$ has the no odd flip property, unless $W$ is of type $A_{2n} \cong S_{2n+1}$ or $I_2(2n+1)$ for some $n \ge 1$, and $\theta$ is the unique non-trivial automorphism. The poset $\mathcal{I}(\theta)$ is always graded. Furthermore, we have the following result, from which it follows that $F_n^0$ is graded, as we shall see.

**Theorem A ([8, Theorem 4.6 and Proposition 6.7])** If $\theta$ has the no odd flip property, then $\iota(\theta)$ is graded with the same rank function as $\mathcal{I}(\theta)$.

If $W$ is finite, it contains a greatest element $w_0$, and $\theta(w) = w_0ww_0$ defines an involutive automorphism of $(W, S)$. Since $\iota(\theta) = \{w_0w^{-1}w_0w \mid w \in W\}$ and $\mathcal{I}(\theta) = \{w \in W \mid w_0ww_0 = w^{-1}\}$,

$$w_0 \cdot \iota(\theta) = \{w^{-1}w_0w \mid w \in W\}$$

and

$$w_0 \cdot \mathcal{I}(\theta) = \{w_0w \mid w_0ww_0 = w^{-1}\} = \{w_0w \mid (w_0w)^2 = e\}.$$

Since left (as well as right) multiplication by $w_0$ is a poset anti-automorphism (i.e., an order-reversing bijection whose inverse is order-reversing), $\iota(\theta)$ is isomorphic to the dual of $[w_0]$, where $[w_0]$ is the conjugacy class of $w_0$, and $\mathcal{I}(\theta)$ is isomorphic to the dual of $I(W)$, where $I(W)$ is the set of involutions in $W$.

When $W$ is the symmetric group $S_n$, this $\theta$ is the unique non-trivial automorphism of $(W, S)$, and $I(W) = I_n$. For $n$ even, $[w_0] = F_n^0$, and for $n$ odd, $[w_0] = F_n^1$. Thus, it follows from Theorem A that $F_n^0$ is graded.

It was conjectured by Hultman [8, Conjecture 6.1] that $\iota(\theta)$ is graded when $W = A_{2n}$. As we have seen, this is equivalent to $F_n^1$ being graded, which is the case (see Corollary 2). Since $\iota(\theta)$ is graded whenever $W$ is dihedral, as is easily seen, it therefore follows that $\iota(\theta)$ is graded whenever $W$ is finite and irreducible. From this, we get the following (we omit the proof):

**Theorem 3** If $W$ is finite, then $\iota(\theta)$ is graded.

Let us also mention a connection to work by Richardson and Springer [10, 11], who studied a graded poset $V$ of orbits of certain symmetric varieties (depending on, inter alia, a group $G$). They did so by defining an order-preserving function $\varphi : V \to \mathcal{I}(\theta) \subseteq W$ (where the Weyl group $W$ depends on, inter alia, $G$).

When $W = S_n$, $\mathcal{I}(\theta)$ is the image of an injective $\varphi$ (for details, see [10, Example 10.2]). When $n$ is even, the same is true for $\iota(\theta)$ (see [10, Example 10.4] or [8, Example 3.1]). Thus, $I_n$ and $F_n^0$ are isomorphic to the duals of such posets $V$. Hence, $I_n$ and $F_n^0$ are graded.

However, these are not the only $F_n^A$ that occur as the image of a $\varphi$. To describe these sets, and for later purposes, define

$$F_n^{\le a} = \bigcup_{i \ge 0} F_n^{a-2i} \quad \text{and} \quad F_n^{\ge a} = \bigcup_{i \ge 0} F_n^{a+2i},$$

and for $a_2 = a_1 + 2m$, where $m$ is a positive integer, let

$$F_n^{a_1:a_2} = F_n^{\ge a_1} \cap F_n^{\le a_2}.$$
As described in [10], the image of $\varphi$ can be read off from the corresponding Satake diagram. It follows from Satake diagrams A III and A IV in Helgason [5, Table VI] that for each $a \le n-2$, $F_n^{\ge a}$ is the image of a $\varphi$. (From Satake diagrams A I and A II, it follows that $\mathfrak{I}(\theta)$ and $\mathfrak{I}(\theta)$, respectively, are the images of such functions).

The remainder of this extended abstract is organised as follows. In Section 2, we agree on notation and gather the necessary definitions and previous results. Then, in Section 3, we sketch the proof of our main result (Theorem 1). Finally, in Section 4, we give a short new proof of the following result, which was recently proved by Can, Cherniavsky, and Twelbeck.

**Theorem B ([3, Theorem 1])** The poset $F_n^0$ is EL-shellable.

## 2 Notation and preliminaries

Poset notation and terminology will follow [12]. In particular, if $P$ is a poset and $x \le y$ in $P$, then $[x, y] = \{z \in P \mid x \le z \le y\}$ and $(x, y) = \{z \in P \mid x < z < y\}$. Furthermore, in a finite poset $P$, $\triangleleft$ denotes the covering relation, a chain $x_0 < x_1 < \dots < x_k$ is saturated if $x_{i-1} \triangleleft x_i$ for all $i \in [k]$, $P$ is bounded if it has a minimum (denoted by $\hat{0}$) and a maximum (denoted by $\hat{1}$), and $P$ is graded of rank $n$ if every maximal chain has length $n$. In this case, there is a unique rank function $\rho : P \to \{0, 1, \dots, n\}$ such that $\rho(x) = 0$ if $x$ is a minimal element of $P$, and $\rho(y) = \rho(x) + 1$ if $x \triangleleft y$ in $P$; $x$ has rank $i$ if $\rho(x) = i$. An x-y-chain is a saturated chain from $x$ to $y$.

Let $P$ be a finite, bounded, and graded poset. An edge-labelling of $P$ is a function $\lambda : \{(x, y) \in P^2 \mid x \triangleleft y\} \to Q$, where $Q$ is a totally ordered set. If $\lambda$ is an edge-labelling of $P$ and $x_0 \triangleleft x_1 \triangleleft \dots \triangleleft x_k$ is a saturated chain, let $\lambda(x_0, x_1, \dots, x_k) = (\lambda(x_0, x_1), \lambda(x_1, x_2), \dots, \lambda(x_{k-1}, x_k))$. The chain is said to be increasing if $\lambda(x_{i-1}, x_i) \le \lambda(x_i, x_{i+1})$ for all $i \in [k-1]$, and decreasing if $\lambda(x_{i-1}, x_i) > \lambda(x_i, x_{i+1})$ for all $i \in [k-1]$. An edge-labelling $\lambda$ of $P$ is an EL-labelling if, for all $x < y$ in $P$, there is exactly one increasing $x$-y-chain, say $x_0 \triangleleft x_1 \triangleleft \dots \triangleleft x_k$, and this chain is lexicographically minimal, or lex-minimal, among the $x$-y-chains in $P$ (i.e., if $y_0 \triangleleft y_1 \triangleleft \dots \triangleleft y_k$ is any other $x$-y-chain, then $\lambda(x_{j-1}, x_j) < \lambda(y_{j-1}, y_j)$, where $j = \min\{i \in [k] \mid \lambda(x_{i-1}, x_i) \ne \lambda(y_{i-1}, y_i)\}$; this is known as the lexicographic order). If $P$ has an EL-labelling, $P$ is said to be EL-shellable. The reason for this is the following result, due to Björner.

**Theorem C ([1, Theorem 2.3])** Let $P$ be a finite, bounded, and graded poset. If $P$ is EL-shellable, then its order complex $\Delta(P)$ is shellable.

For $\sigma \in S_n$ and $(k, l) \in [n]^2$, let $\sigma[k, l] = |\{i \le k \mid \sigma(i) \ge l\}|$. The Bruhat order on $S_n$ may be defined as follows (see, e.g., [2, Theorem 2.1.5]):

**Definition 4** Let $\sigma, \tau \in S_n$. Then $\sigma \le \tau$ if and only if $\sigma[k, l] \le \tau[k, l]$ for all $(k, l) \in [n]^2$.

Let us turn to involutions in the symmetric group. Here, notation will follow [9].

Let $\sigma \in S_n$. A rise of $\sigma$ is a pair $(i, j) \in [n]^2$ such that $i < j$ and $\sigma(i) < \sigma(j)$. A rise $(i, j)$ is called free if there is no $i < k < j$ such that $\sigma(i) < \sigma(k) < \sigma(j)$. An inversion is a pair $(i, j) \in [n]^2$ such that $i < j$ and $\sigma(i) > \sigma(j)$. An element $i \in [n]$ is a fixed point of $\sigma$ if $\sigma(i) = i$, an exceedance if $\sigma(i) > i$, and a deficiency if $\sigma(i) < i$. Let inv($\sigma$) and exc($\sigma$) denote the number of inversions and exceedances, respectively, of $\sigma$.
Let $\sigma \in I_n$. A free rise $(i, j)$ of $\sigma$ is suitable if it is an $ff$-rise (Type 1), an $fe$-rise (Type 2), an $ef$-rise (Type 3), a non-crossing $ee$-rise (Type 4), a crossing $ee$-rise (Type 5), or an $ed$-rise (Type 6). Here $fe$, e.g., means that $i$ is a fixed point of $\sigma$ while $j$ is an exceedance, and an $ee$-rise is crossing if $\sigma(i) < j$ and non-crossing otherwise.

The following definition is very important.

**Definition 5** Let $\sigma \in I_n$ and let $(i, j)$ be a suitable rise of $\sigma$. We define a new involution $ct_{(i,j)}(\sigma)$ as follows:

If $(i, j)$ is of Type 1, then $ct_{(i,j)}(\sigma) = \sigma(i, j)$.

If $(i, j)$ is of Type 2, then $ct_{(i,j)}(\sigma) = \sigma(i, j, \sigma(j))$.

If $(i, j)$ is of Type 3, then $ct_{(i,j)}(\sigma) = \sigma(i, j, \sigma(i))$.

If $(i, j)$ is of Type 4, then $ct_{(i,j)}(\sigma) = \sigma(i, j)(\sigma(i), \sigma(j))$.

If $(i, j)$ is of Type 5, then $ct_{(i,j)}(\sigma) = \sigma(i, j, \sigma(j), \sigma(i))$.

If $(i, j)$ is of Type 6, then $ct_{(i,j)}(\sigma) = \sigma(i, j)(\sigma(i), \sigma(j))$.

See [9, Table 1] for pictures describing the action of $ct_{(i,j)}$ on the diagram of $\sigma$.

Incitti characterised the covering relation in $I_n$ as follows.

**Lemma 6 ([9, Theorem 5.1])** Let $\sigma, \tau \in I_n$. Then $\sigma \triangleleft \tau$ in $I_n$ if and only if $\tau = ct_{(i,j)}(\sigma)$ for some (necessarily unique) suitable rise $(i, j)$ of $\sigma$.

If $\tau = ct_{(i,j)}(\sigma)$ for some suitable rise $(i, j)$ of $\sigma$, let $\lambda(\sigma, \tau) = (i, j)$. By Lemma 6, this defines an edge-labelling of $I_n$ (with $\{(i, j) \in [n]^2 \mid i < j\}$ totally ordered by the lexicographic order, i.e., $(i_1, j_1) < (i_2, j_2)$ if and only if $i_1 < i_2$, or $i_1 = i_2$ and $j_1 < j_2$). Whenever we consider an edge-labelling of $I_n$, it is this one. If $\lambda(\sigma, \tau) = (i, j)$, then $(i, j)$ is the label on the cover $\sigma \triangleleft \tau$; $(i, j)$ is a label on a chain if it is the label on some cover of the chain.

Let $\tau \in I_n$ and let $(i, j)$ be an inversion of $\tau$. If $(i, j)$ is a suitable rise of some $\sigma \in I_n$ and $ct_{(i,j)}(\sigma) = \tau$, then $\sigma$ is unique, and we write $\sigma = \text{ict}_{(i,j)}(\tau)$.

For $\sigma < \tau$ in $I_n$, let $\text{di}(\sigma, \tau) = \min\{i \in [n] \mid \sigma(i) \neq \tau(i)\}$.

We shall need the following results, due to Incitti:

**Lemma 7 ([9, Theorem 5.2])** The poset $I_n$ is graded with rank function $\rho$ given by

$$ \rho(\sigma) = \frac{\text{inv}(\sigma) + \text{exc}(\sigma)}{2}. $$

**Lemma 8 ([9, Theorem 6.2])** Let $\sigma < \tau$ in $I_n$. Then there is exactly one increasing $\sigma$-$\tau$-chain, and it is lex-minimal.

**Lemma 9 ([9, Theorem 7.3])** Let $\sigma < \tau$ in $I_n$. Then there is exactly one decreasing $\sigma$-$\tau$-chain.

**Remark 1** Since $ct_{(i,j)}(\sigma)(i) > ct_{(i,j)}(\sigma)(j)$, there is also exactly one “weakly” decreasing $\sigma$-$\tau$-chain. This fact is used in Section 4.
### 3 Sketch of the proof of the main result

In this section, we prove, sketch the proofs of, or simply state, a number of lemmas and propositions, from which Theorem 1 easily follows.

The strategy for proving that a poset $F_n^A$ is graded is as follows. We first prove that $F_n^A$ has a maximum and that all its minimal elements have the same rank in $I_n$ (see Propositions 11 and 12). We then prove that if $\sigma, \tau \in F_n^A$, then $\sigma \triangleleft \tau$ in $F_n^A$ if and only if $\sigma \triangleleft \tau$ in $I_n$ (one implication is obvious). This is done in Lemmas 15, 16, and 17. Since $I_n$ is graded, it thus follows that $F_n^A$ is graded.

In particular, when $F_n^A \in \{F_n^{\le a}, F_n^{\ge a}\}$, to prove that $\sigma \triangleleft \tau$ in $I_n$ if $\sigma \triangleleft \tau$ in $F_n^A$, we assume that $\sigma \triangleleft \tau$ in $I_n$, and consider the increasing and the decreasing $\sigma$-$\tau$-chains in $I_n$. We then prove that either the element in the increasing chain that covers $\sigma$, or the element in the decreasing chain that is covered by $\tau$, has to belong to $F_n^A$. This contradicts the fact that $\sigma \triangleleft \tau$ in $F_n^A$.

To prove that a poset $F_n^A$ is not graded, we consider an interval $[\sigma, \tau]$, and then construct two $\sigma$-$\tau$-chains in $F_n^A$ of different lengths (see Propositions 19 and 20).

Let us first note the following fact:

**Lemma 10** For all $n$ and all $A$, $F_n^A$ is graded if and only if $F_n^{A-\{n\}}$ is graded.

**Proof:** This is obvious if $n \notin A$. Otherwise, deleting the identity permutation gives a bijection between maximal chains in $F_n^A$ of length $k$ and maximal chains in $F_n^{A-\{n\}}$ of length $k-1$. $\square$

In the next two results, we describe the maximal and minimal elements of $F_n^A$. The proofs are not given here.

**Proposition 11** For all $n$ and all $A$, $F_n^A$ has a $\hat{1}$. Furthermore, $\mathrm{inv}(\hat{1}) = \frac{n-a}{2}(n+a-1)$ and $\mathrm{exc}(\hat{1}) = \frac{n-a}{2}$, where $a = \min A$.

**Proposition 12** For all $n$ and all $A$, all minimal elements of $F_n^A$ have rank $(n - \max A)/2$ in $I_n$.

Recall that

$$F_n^{\le a} = \bigcup_{i \ge 0} F_n^{a-2i}, \quad F_n^{\ge a} = \bigcup_{i \ge 0} F_n^{a+2i}, \quad \text{and} \quad F_n^{a_1:a_2} = F_n^{\ge a_1} \cap F_n^{\le a_2},$$

where $a_2 = a_1 + 2m$ for some positive integer $m$. Note that $F_n^{a_1:a_2}$ is not defined for $a_1 = a_2$.

The following lemma will eventually allow us to conclude that $F_n^{\le a}$, $F_n^{\ge a}$, and $F_n^{a_1:a_2}$ are graded.

**Lemma 13** If every cover in $F_n^A$ is a cover in $I_n$, then $F_n^A$ is graded.

**Proof:** This follows from Lemma 7 and Propositions 11 and 12. $\square$

The next lemma is used in the proofs of Lemmas 15, 16, and 17, which, together with Lemma 13, show that $F_n^{\le a}$, $F_n^{\ge a}$, and $F_n^{a_1:a_2}$ are graded.

**Lemma 14** Let $\sigma < \tau$ in $I_n$. Then the label $(i, j)$ on any cover in $[\sigma, \tau]$ satisfies $i \ge \mathrm{di}(\sigma, \tau)$.

**Proof:** Suppose $i < \mathrm{di}(\sigma, \tau)$ for the label $(i, j)$ on $\sigma \triangleleft \pi \le \tau$. Then $\pi(k) = \tau(k)$ for $k < i$ and $\sigma(i) = \tau(i)$. However, it follows from Definition 5 that $\pi(i) > \sigma(i)$. Hence, $\pi[i, \sigma(i)+1] > \tau[i, \sigma(i)+1]$. By Definition 4, this contradicts the fact that $\pi \le \tau$. Thus $i \ge \mathrm{di}(\sigma, \tau)$. The result follows by induction. $\square$
**Lemma 15** Let $\sigma \triangleleft \tau$ in $F_n^{\le a}$. Then $\sigma \triangleleft \tau$ in $I_n$.

**Proof:** Assume that $\sigma \not\triangleleft \tau$ in $I_n$, and let $C_I = \sigma \triangleleft \sigma_1 \triangleleft \cdots \triangleleft \sigma_k \triangleleft \tau$ be the increasing $\sigma$-$\tau$-chain in $I_n$ and $C_D = \sigma \triangleleft \tau_k \triangleleft \cdots \triangleleft \tau_1 \triangleleft \tau$ the decreasing $\sigma$-$\tau$-chain in $I_n$. Since $\sigma \triangleleft \tau$ in $F_n^{\le a}$, neither $\sigma_1$ nor $\tau_1$ belongs to $F_n^{\le a}$.

Let $h = \mathrm{di}(\sigma, \tau)$, and let $(i_\sigma, j_\sigma)$ and $(i_\tau, j_\tau)$ be the labels on $\sigma \triangleleft \sigma_1$ and $\tau_1 \triangleleft \tau$, respectively. Since $\sigma(h) \neq \tau(h)$, it follows from Lemma 14 that $h$ is in some label on $C_I$ and some label on $C_D$. Since $C_I$ is increasing, $i_\sigma = h$, and since $\sigma_1 \notin F_n^{\le a}$, $h$ is an exceedance of $\sigma$ (Type 5). Since $C_D$ is decreasing, $i_\tau = h$, and since $\tau_1 \notin F_n^{\le a}$, $h$ is a fixed point of $\tau_1$ (Type 1). Hence, $\sigma[h, h+1] > \tau_1[h, h+1]$. By Definition 4, this contradicts the fact that $\sigma \le \tau_1$. $\square$

**Lemma 16** Let $\sigma \triangleleft \tau$ in $F_n^{\ge a}$. Then $\sigma \triangleleft \tau$ in $I_n$.

**Proof:** Assume that $\sigma \not\triangleleft \tau$ in $I_n$, and let $C_I = \sigma \triangleleft \sigma_1 \triangleleft \cdots \triangleleft \sigma_k \triangleleft \tau$ be the increasing $\sigma$-$\tau$-chain in $I_n$ and $C_D = \sigma \triangleleft \tau_k \triangleleft \cdots \triangleleft \tau_1 \triangleleft \tau$ the decreasing $\sigma$-$\tau$-chain in $I_n$. Since $\sigma \triangleleft \tau$ in $F_n^{\ge a}$, neither $\sigma_1$ nor $\tau_1$ belongs to $F_n^{\ge a}$.

Let $h = \mathrm{di}(\sigma, \tau)$, and let $(i_\sigma, j_\sigma)$ and $(i_\tau, j_\tau)$ be the labels on $\sigma \triangleleft \sigma_1$ and $\tau_1 \triangleleft \tau$, respectively. Since $\sigma(h) \neq \tau(h)$, it follows from Lemma 14 that $h$ is in some label on $C_I$ and some label on $C_D$. Since $C_I$ is increasing, $i_\sigma = h$, and since $\sigma_1 \notin F_n^{\ge a}$, $h$ is a fixed point of $\sigma$ (Type 1). Since $C_D$ is decreasing, $i_\tau = h$, and since $\tau_1 \notin F_n^{\ge a}$, $h$ is an exceedance of $\tau_1$ (Type 5).

Let $m$ be such that $h$ is an exceedance of $\tau_1, \dots, \tau_{m-1}$ and a fixed point of $\tau_m$ (with $\tau_{k+1} = \sigma$). Then the labels on $\tau \triangleright \tau_1 \triangleright \dots \triangleright \tau_m$ are $(h, j_1), \dots, (h, j_m)$, where $j_1 < j_2 < \dots < j_m$. Since $\tau_1 > \tau_2 > \dots > \tau_{m-1}$, $\tau_1(h) > \tau_2(h) > \dots > \tau_{m-1}(h)$. Since $h$ is a fixed point of $\tau_m$ but an exceedance of $\tau_{m-1}$, the cover $\tau_m \triangleleft \tau_{m-1}$ is of Type 1 or 2, whence $\tau_{m-1}(h) = j_m$ or $\tau_{m-1}(h) = \tau_m(j_m) > j_m$, respectively; hence, $\tau_{m-1}(h) \ge j_m$. Therefore, $j_1 < j_m \le \tau_{m-1}(h) \le \tau_1(h)$. However, since the cover $\tau_1 \triangleleft \tau$ is of Type 5, $\tau_1(h) < j_1$, which is a contradiction. $\square$

**Lemma 17** Let $\sigma \triangleleft \tau$ in $F_n^{a_1:a_2}$. Then $\sigma \triangleleft \tau$ in $I_n$.

The proof, which is omitted here, is largely a combination of the proofs of Lemmas 15 and 16.

**Proposition 18** The posets $F_n^{\le a}$, $F_n^{\ge a}$, and $F_n^{a_1:a_2}$ are graded.

**Proof:** This follows from Lemmas 13, 15, 16, and 17. $\square$

In the following two results, we consider the sets $A$ for which $F_n^A$ is not graded.

**Proposition 19** If there is an $i \in [2, n-4]$ such that $i \in A$ but $i-2, i+2 \notin A$, then $F_n^A$ is not graded.

The proof, which is not given here, is similar to, but easier than, the proof of Proposition 20.

**Proposition 20** If there is an $i \notin A$ and a positive integer $m$ such that $i-2, i+2m \in A - \{n\}$, then $F_n^A$ is not graded.

**Proof sketch:** We first prove that $F_k^{\{0,k-2\}}$, where $k \ge 6$ is even, is not graded. Let $\sigma = 12 \cdots (k-2)k(k-1)$ and $\tau = k23 \cdots (k-1)1$, and consider the interval $[\sigma, \tau]$. We obtain a $\sigma$-$\tau$-chain $C$ in $I_k$ by $k-2$ fe-rises with labels $(k-2, k-1), (k-3, k-2), \dots, (1, 2)$ (from $\sigma$ to $\tau$). We also obtain a
$\sigma$-$\tau$-chain in $I_n$ by $(k-2)/2$ ff-rises with labels $(1, 2), (3, 4), \dots, (k-3, k-2)$, followed by $(k-2)/2$ crossing ee-rises with labels $(k-3, k-1), (k-5, k-3), \dots, (1, 3)$.

Let $\pi$ be the fixed point-free involution obtained after the ff-rises. Since each ff-rise decreases the number of fixed points and $I_k$ is graded, $(\sigma, \pi) \cap F_k^{\{0,k-2\}} = \emptyset$, and since each crossing ee-rise increases the number of fixed points and $I_k$ is graded, $(\pi, \tau) \cap F_k^{\{0,k-2\}} = \emptyset$. Hence, $C$ is a $\sigma$-$\tau$-chain in $F_k^{\{0,k-2\}}$ of length $k-2$, while $\sigma \triangleleft \pi \triangleleft \tau$ is a $\sigma$-$\tau$-chain in $F_k^{\{0,k-2\}}$ of length 2. Thus $F_k^{\{0,k-2\}}$ is not graded. Figure 3 illustrates the situation when $k=6$.

Now we have to obtain the right number of fixed points. The details are not given here. $\square$

<figure><img src="image_4.png" /><figcaption>**Figure 3:** Two $\sigma$-$\tau$-chains in $I_6$ of length 4, and two $\sigma$-$\tau$-chains in $F_6^{\{0,4\}}$ of length 4 (right) and length 2 (left); the involutions marked by a $\bullet$ belong to $F_6^{\{0,4\}}$, and the involutions marked by a $\circ$ belong to $I_6 - F_6^{\{0,4\}}$. On the edges (covers in $I_6$) are the labels $(i, j)$.</figcaption></figure>

We are now ready to prove our main result:

**Proof of Theorem 1:** The first claim follows from Lemma 10 and Propositions 18, 19, and 20. (It is readily checked that if $F_n^{A-\{n\}}$ does not belong to $\{\emptyset, F_n^{\le a}, F_n^{\ge a}, F_n^{a_1:a_2}\}$, then either there is an $i \in [2, n-4]$ such that $i \in A$ but $i-2, i+2 \notin A$, or there are an $i \notin A$ and a positive integer $m$ such that $i-2, i+2m \in A - \{n\}$.) The second claim follows from Lemma 7, Proposition 12, and Lemmas 15, 16, and 17. The third claim follows from the second claim and Proposition 11. $\square$

# 4 EL-shellability of $F_n^0$

In this section, we give a new proof of Theorem B, due to Can, Cherniavsky, and Twelbeck [3]. Our proof is largely based on the same main idea as their proof, together with the technique used in the proof of Lemma 15. The proof in [3] goes as follows:

Let $\sigma < \tau$ in $F_n^0$. It follows from, e.g., Theorem A and the paragraphs following it, that there exists a $\sigma$-$\tau$-chain in $I_n$ that is contained in $F_n^0$. Let $C$ be the lex-maximal such chain. The idea of the proof is to show that $C$ is decreasing. Then, by reversing the lexicographic order on the set $\{(i, j) \in [n]^2 | i < j\}$ (i.e., by letting $(i_1, j_1) < (i_2, j_2)$ if and only if $i_1 > i_2$, or $i_1 = i_2$ and $j_1 > j_2$), one obtains an edge-labelling of $F_n^0$ such that in each interval, there is an increasing $\sigma$-$\tau$-chain which is lex-minimal. By Lemma 9 and the remark following it, this is an EL-labelling of $F_n^0$.
We use the same main idea, namely, to show that the decreasing $\sigma$-$\tau$-chain in $I_n$ is contained in $F_n^0$, and then reverse the lexicographic order. However, we give a direct proof of this fact. By using the same technique as in the proof of Lemma 15, we get a very short argument.

**Lemma 21** Let $\sigma < \tau$ in $F_n^0$ and let $C_D = \sigma \triangleleft \tau_k \triangleleft \cdots \triangleleft \tau_1 \triangleleft \tau$ be the decreasing $\sigma$-$\tau$-chain in $I_n$, where $k \ge 1$. Then $\tau_1, \dots, \tau_k \in F_n^0$.

**Proof:** Since the decreasing $\sigma$-$\tau_1$-chain in $I_n$ is $\sigma \triangleleft \tau_k \triangleleft \cdots \triangleleft \tau_2 \triangleleft \tau_1$, it suffices to prove that $\tau_1 \in F_n^0$. Let $h = \text{di}(\sigma, \tau)$, let $C_I = \sigma \triangleleft \sigma_1 \triangleleft \cdots \triangleleft \sigma_k \triangleleft \tau$ be the increasing $\sigma$-$\tau$-chain in $I_n$, and let $(i_\sigma, j_\sigma)$ and $(i_\tau, j_\tau)$ be the labels on $\sigma \triangleleft \sigma_1$ and $\tau_1 \triangleleft \tau$, respectively. Since $\sigma(h) \neq \tau(h)$, it follows from Lemma 14 that $h$ is in some label on $C_I$ and some label on $C_D$. Since $C_I$ is increasing, $i_\sigma = h$, and since $\sigma$ has no fixed points, $h$ is an exceedance of $\sigma$ (Type 4, 5, or 6). Since $C_D$ is decreasing, $i_\tau = h$, and were $\tau_1 \notin F_n^0$, $h$ would be a fixed point of $\tau_1$ (Type 1). Hence, by Definition 4, $\tau_1 \in F_n^0$. $\square$

We can now complete the proof of Theorem B:

**Proof of Theorem B:** Let $\sigma < \tau$ in $F_n^0$. By Lemma 21, the decreasing $\sigma$-$\tau$-chain in $I_n$ is contained in $F_n^0$. If we can show that this chain is lex-maximal, then by reversing the lexicographic order and invoking Lemma 9, we are done.

In order to obtain a contradiction, let $C = \sigma_1 \triangleleft \cdots \triangleleft \sigma_k$ be the lex-maximal $\sigma$-$\tau$-chain in $I_n$, and assume that it is not decreasing; say that $\lambda(\sigma_1, \sigma_2) \le \lambda(\sigma_2, \sigma_3)$. By Lemma 8, $\sigma_1 \triangleleft \sigma_2 \triangleleft \sigma_3$ is lex-minimal among the $\sigma_1$-$\sigma_3$-chains in $I_n$. Hence, $\sigma_1 \triangleleft \sigma'_2 \triangleleft \sigma_3 \triangleleft \cdots \triangleleft \sigma_k$, where $\sigma_1 \triangleleft \sigma'_2 \triangleleft \sigma_3$ is the decreasing $\sigma_1$-$\sigma_3$-chain, is lex-larger than $C$, which is a contradiction. $\square$

Is it possible to use the same idea to prove that every interval in $F_n^A \subset I_n$ is EL-shellable for some $A \neq \{0\}$? Unfortunately, the answer is no, since for all $A \neq \{0\}$ (except the trivial cases $A = \emptyset$ and $A = \{n\}$), it is possible to find $\sigma_1 < \tau_1$ and $\sigma_2 < \tau_2$ in $F_n^A$, such that the increasing $\sigma_1$-$\tau_1$-chain and the decreasing $\sigma_2$-$\tau_2$-chain in $I_n$, are of length 2 and are not contained in $F_n^A$.

# Acknowledgements

The author thanks Axel Hultman for helpful comments and fruitful discussions.

# References

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

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

[3] M. B. Can, Y. Cherniavsky, and T. Twelbeck. Lexicographic shellability of the Bruhat-Chevalley order on fixed-point-free involutions. *Israel J. Math.*, to appear.

[4] P. H. Edelman. The Bruhat order of the symmetric group is lexicographically shellable. *Proc. Amer. Math. Soc.*, 82:355–358, 1981.
[5] S. Helgason. *Differential geometry, Lie groups, and symmetric spaces*, volume 80 of *Pure and Applied Mathematics*. Academic Press, New York, 1978.

[6] A. Hultman. Fixed points of involutive automorphisms of the Bruhat order. *Adv. Math.*, 195:283–296, 2005.

[7] A. Hultman. The combinatorics of twisted involutions in Coxeter groups. *Trans. Amer. Math. Soc.*, 359:2787–2798, 2007.

[8] A. Hultman. Twisted identities in Coxeter groups. *J. Algebraic Combin.*, 28:313–332, 2008.

[9] F. Incitti. The Bruhat order on the involutions of the symmetric group. *J. Algebraic Combin.*, 20:243–261, 2004.

[10] R. W. Richardson and T. A. Springer. The Bruhat order on symmetric varieties. *Geom. Dedicata*, 35:389–436, 1990.

[11] R. W. Richardson and T. A. Springer. Complements to: The Bruhat order on symmetric varieties. *Geom. Dedicata*, 49:231–238, 1994.

[12] R. P. Stanley. *Enumerative combinatorics. Vol. 1*, volume 49 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1997.