# On Bruhat posets associated to compositions*

Mahir Bilen Can† and Yonah Cherniavsky‡

Department of Mathematics, Tulane University, New Orleans, USA
Department of Computer Science and Mathematics, Ariel University, Israel

**Abstract.** The purpose of this work is to initiate a combinatorial study of the Bruhat-Chevalley ordering on certain sets of permutations obtained by omitting the parentheses from their standard cyclic notation. In particular, we show that these sets form bounded, graded, unimodal, rank-symmetric and EL-shellable posets. Moreover, we determine the homotopy types of the associated order complexes.

**Résumé.** Le but de ce travail est de lancer une tude combinatoire de l'ordre de Bruhat-Chevalley sur certains ensembles de permutations obtenues en omettant les parenthses de leur notation cyclique standard. En particulier, nous montrons que ces ensembles forment born, class, unimodale, rang-symtrique et posets EL-shellable. De plus, nous dterminons les types de complexes d'ordre associs d'homotopie.

**Keywords:** Bruhat order, graded posets, unimodality, EL-shellability

## 1 Introduction

Let $n$ be a positive integer, and let $S_n$ denote the symmetric group of permutations on the set $[n] := \{1, \dots, n\}$. A fixed-point-free involution is a permutation $\pi \in S_n$ such that $\pi \circ \pi = \text{id}$ and $\pi(i) \neq i$ for all $i \in [n]$. In their interesting paper [6], Deodhar and Srinivasan define and study an analog of the Bruhat-Chevalley ordering on the set of all fixed-point-free involutions of $S_{2n}$. In [13], Upperman and Vinroot investigate the natural extension of this partial ordering on the set of products of $n$ disjoint cycles of length $m$ in $S_{mn}$. In this note we present a construction generalizing both of these works. We achieve this by studying a self-map on $S_n$, which is in some sense very classical.

The standard cyclic form of a permutation $\pi \in S_n$ is the representation of $\pi$ as a product of disjoint cycles

$$ \pi = (a_{1,1}, \dots, a_{k_1,1}) (a_{1,2}, \dots, a_{k_1,2}) \dots (a_{1,m}, \dots, a_{k_1,m}) $$

where $a_{1,1} < a_{1,2} < \dots < a_{1,m}$ and $a_{1,j} < a_{i,j}$ for every $1 \le j \le m$ and $2 \le i \le k_j$. Here, contrary to the commonly used convention, we do not suppress cycles of length one from our notation.

Recall that the one-line notation for $x \in S_n$ is defined by $x = [a_1, a_2, \dots, a_n]$, where $x(j) = a_j$ for $1 \le j \le n$. We define the mapping $\Omega: S_n \to S_n$ as follows: write $x \in S_n$ in the standard form

<footnote>*Full text can be found at [3]</footnote>

<footnote>†Email: mcan@tulane.edu</footnote>

<footnote>‡Email: yonahch@ariel.ac.il</footnote>
and then omit the parentheses. We view the resulting word as a permutation of $S_n$ written in one-line notation. For example, let $x = (1, 2)(3)(4, 5)$ be a permutation given in its standard cyclic form. Then $\Omega(x) = [1, 2, 3, 4, 5]$, which is the identity permutation in $S_5$.

Notice that our map $\Omega$ is somewhat similar to the fundamental bijection $w \mapsto \hat{w}$ presented in Section 1.3, page 29 of [11]. That fundamental bijection also removes parentheses from a certain cyclic form of a permutation. However, our mapping is rather different from the fundamental bijection.

After we started this project we learned from Y. Roichman that in his Bar-Ilan University M.Sc. Thesis [1], A. Avni used a map (denoted by $\varphi$) that is identical to our $\Omega$. Avni considers this map on the conjugacy class of fixed-point-free involutions of $S_{2n}$, and the order relation on the permutations in the image of the mapping is the weak Bruhat order. Note that we deal with the strong Bruhat order here.

It is clear that $\Omega$ is not injective, however, there are interesting subsets of $S_n$ on which its restriction is one-to-one. Recall that a composition of $n$ is a sequence $\lambda = (\lambda_1, \dots, \lambda_k)$ of positive integers such that $\sum \lambda_i = n$. In this case, it is customary to write $\lambda \vdash n$. We define the composition type of a permutation $x \in S_n$ to be the composition obtained from the standard cyclic form of $x$ by considering the lengths of its cycles. For example, if $x = (1, 2)(3)(4, 5) \in S_5$, then its composition type is $\lambda = (2, 1, 2)$. We denote by $A_\lambda \subset S_n$ the set of all permutations of composition type $\lambda \vdash n$.

In the works of Deodhar and Srinivasan [6], and Upperman and Vinroot [13] the authors use a certain restriction of our map $\Omega$ composed with the inverse map $w \mapsto w^{-1}$. Both of these papers use $\phi$ to denote their corresponding map. In [6], $\phi$ operates on the set of fixed-point-free involutions and in [13] $\phi$ operates on the set of products of disjoint $m$-cycles. Here, we apply $\Omega$ to arbitrary $A_\lambda$ for $\lambda \vdash n$, and investigate the “Bruhat-Chevalley ordering” on the resulting set of permutations, which we denote by $C_\lambda := \Omega(A_\lambda)$. To continue, let us recall the definition of this important partial ordering.

The inversion number of a permutation $x = [a_1, \dots, a_n] \in S_n$ is the cardinality of the set of inversions

$$ \mathrm{inv}(x) := |\{(i, j) : 1 \le i < j \le n, x(i) > x(j)\}|. \qquad (1) $$

The Bruhat-Chevalley ordering on $S_n$ is the transitive closure of the following covering relations: $x = [a_1, \dots, a_n]$ is covered by $y = [b_1, \dots, b_n]$, if $\mathrm{inv}(y) = \mathrm{inv}(x) + 1$ and

1. $a_k = b_k$ for $k \in \{1, \dots, \hat{i}, \dots, \hat{j}, \dots, n\}$ (hat means omit those numbers),

2. $a_i = b_j$, $a_j = b_i$, and $a_i < a_j$.

We are now ready to give a brief overview of this work and state our main results. In the next section, we introduce more notation and provide preliminary results for our proofs.

Our first main result, which we give in Section 3 is about the gradedness of $C_\lambda$'s. Recall that a finite poset is called graded, if all maximal chains are of the same length.

**Theorem A.** Given a composition $\lambda \vdash n$, with respect to the restriction of the Bruhat-Chevalley ordering the set $C_\lambda$ is a graded poset with a minimum and a maximum.

Let $q$ be a variable, and for a subset $S \subset S_n$, let $G_S(q)$ denote its “length generating function” $G_S(q) := \sum_{x \in S} q^{\mathrm{inv}(x)}$. The $q$-analog of a natural number $n$ is the polynomial $[n]_q := 1+q+\dots+q^{n-1}$. Our second main result, which we give in Section 4 is

**Theorem B.** The length generating function of $C_\lambda$ is of the form $G_{C_\lambda}(q) = [i_1]_q[i_2]_q \cdots [i_r]_q$ for a suitable sequence $2 \le i_1 < \dots < i_r \le n-1$ determined by $\lambda$.
As a consequence, we see that the length generating functions $G_{C_\lambda}(q)$ are palindromic, and therefore, the posets $C_\lambda$ are unimodal and rank-symmetric.

To state our third main result and its important corollary (our Theorem 4), we need to recall a definition of the notion of lexicographic shellability of a poset: A finite graded poset $P$ with a maximum and a minimum element is called *EL-shellable* (*lexicographically shellable*), if there exists a map $f = f_\Gamma : C(P) \to \Gamma$ between the set of covering relations $C(P)$ of $P$ into a totally ordered set $\Gamma$ satisfying

1. in every interval $[x, y] \subseteq P$ of length $k > 0$ there exists a unique saturated chain $c : x_0 = x < x_1 < \dots < x_{k-1} < x_k = y$ such that the entries of the sequence

$$f(c) = (f(x_0, x_1), f(x_1, x_2), \dots, f(x_{k-1}, x_k)) \quad (2)$$

are weakly increasing.

2. The sequence $f(c)$ of the unique chain $c$ from (1) is the lexicographically smallest among all sequences of the form $(f(x_0, x'_1), f(x'_1, x'_2), \dots, f(x'_{k-1}, x_k))$, where $x_0 < x'_1 < \dots < x'_{k-1} < x_k$.

For Bruhat-Chevalley ordering, in an increasing order of generality, the articles [7], [9], and [2] show that $S_n$ is a lexicographically shellable poset. In Section 3 we prove that

**Theorem C.** For all compositions $\lambda \models n$, the posets $C_\lambda$ are EL-shellable.

The order complex $\Delta(P)$ of a poset $P$ is the abstract simplicial complex consisting of all chains from $P$. An important consequence of EL-shellability is that the associated order complex has the homotopy type of wedge of spheres or balls. For example, when $P = S_n$ (with respect to Bruhat-Chevalley ordering), the order complex of $P$ triangulates a sphere of dimension $n(n-1)/2$. In our final main result, which prove in Section 5, we obtain

**Theorem D.** Let $\lambda \models n$ be a composition.

1. If $\lambda = (n)$ or $\lambda = (n-1, 1)$, then the poset $C_\lambda$ is isomorphic to $S_{n-1}$. In this case it is just a copy of $S_{n-1}$ embedded into $S_n$. Similarly, if $\lambda_1 = \lambda_2 = \dots = \lambda_{k-1} = 1$ and $\lambda_k = n-k+1$ or $\lambda_1 = \lambda_2 = \dots = \lambda_{k-2} = 1$, $\lambda_{k-1} = n-k$, $\lambda_k = 1$ (like $(1, 1, 1, 4, 1)$), then the poset $C_\lambda$ is isomorphic to $S_{n-k}$. Therefore, in these cases, the order complex of the proper part of $C_\lambda$ (meaning, one has to remove the minimum and maximum elements) triangulates a sphere.

2. In all other cases the order complex of the proper part of $C_\lambda$ triangulates a ball.

We finish our paper with final comments and future questions in Section 6.

**Acknowledgements.** The first author is partially supported by the Louisiana Board of Regents Research and Development grant. Both authors are grateful to Professors R. P. Stanley, B. Sagan, Y. Roichman, and A. Goldstein for helpful discussions. Also, the authors are grateful to Professor J. Stembridge for sharing publicly his helpful software called **posets**.
## 2 Preliminaries

Recall that in a poset $P$, an element $y$ is said to cover another element $x$, if $x < y$ and if $x \le z \le y$ for some $z \in P$, then either $z = x$ or $z = y$. In this case, we write $x \leftarrow y$. Given $P$, we denote by $C(P)$ the set of all covering relations of $P$.

A poset $P$ is called *bounded* if it has the unique minimal element and the unique maximal element which are usually denoted $\hat{0}$ and $\hat{1}$.

An (increasing) *chain* in $P$ is a sequence of distinct elements such that $x = x_1 < x_2 < \dots < x_{n-1} < x_n = y$. A *chain* in a poset $P$ is called *saturated*, if it is of the form $x = x_1 \leftarrow x_2 \leftarrow \dots \leftarrow x_{n-1} \leftarrow x_n = y$. A *saturated chain* in an interval $[x, y]$ is called *maximal*, if the end points of the chain are $x$ and $y$. Recall also that a poset is called *graded* if all maximal chains between any two comparable elements $x \le y$ have the same length. This amounts to the existence of an integer valued function $\ell_P : P \to \mathbb{N}$ satisfying

$$1. \ell_P(\hat{0}) = 0,$$

$$2. \ell_P(y) = \ell_P(x) + 1 \text{ whenever } y \text{ covers } x \text{ in } P.$$

$\ell_P$ is called the *length function* of $P$. In this case, the length of the interval $[\hat{0}, \hat{1}] = P$ is called the *length* of the poset $P$. For $i \in \mathbb{N}$, the $i$-th level of a graded poset $P$ is defined as the set of elements of $P$ of length $i$. Thus, if $p_i$ denotes the number of elements of the $i$-th level of $P$, then the length-generating function of $P$ is equal to $G_P(q) = \sum_{i \ge 0} p_i q^i$.

We recalled the definition of the notion of EL-shellability in the previous section. There is an elementary but a useful criterion to see if a poset is EL-shellable or not:

**Lemma 1 (Proposition 3.1 [6])** Let $P$ be a finite graded poset with the smallest and the largest elements, denoted by $\hat{0}$ and $\hat{1}$, respectively. (Assume $\hat{0} \neq \hat{1}$.) Let $g: C(P) \to \Gamma$ be an EL-labeling of $P$. Let $Q \subseteq P$ contain $\hat{0}$ and also a maximal element $z \neq \hat{0}$ (in the induced order). Assume that $Q$ satisfies the following property: For all $x < y$, the unique rising chain from $x$ to $y$ in $P$ lies in $Q$. Then $Q$ (with the induced order) is a graded poset with the same rank function as $P$ and $g$ restricted to $C(Q)$ is an EL-labeling for $Q$.

To check the EL-shellability of the posets of our paper, we need to have a concrete way for comparing given two permutations in the Bruhat-Chevalley ordering: For an integer valued vector $a = [a_1, \dots, a_n] \in \mathbb{Z}^n$, let $\tilde{a} = [a_{\alpha_1}, \dots, a_{\alpha_n}]$ be the rearrangement of the entries $a_1, \dots, a_n$ of $a$ in a non-increasing fashion;

$$a_{\alpha_1} \ge a_{\alpha_2} \ge \dots \ge a_{\alpha_n}.$$

The containment ordering, "$\leq_c$", on $\mathbb{Z}^n$ is then defined by

$$a = [a_1, \dots, a_n] \leq_c b = [b_1, \dots, b_n] \iff a_{\alpha_j} \leq b_{\beta_j} \text{ for all } j = 1, \dots, n,$$

$$\text{where } \tilde{a} = [a_{\alpha_1}, \dots, a_{\alpha_n}], \text{ and } \tilde{b} = [b_{\beta_1}, \dots, b_{\beta_n}].$$

**Example 2** Let $x = [4, 5, 0, 3, 1]$, and let $y = [4, 2, 5, 5, 1]$. Then $x \leq_c y$, because $\tilde{x} = [5, 4, 3, 1, 0]$ and $\tilde{y} = [5, 5, 4, 2, 1]$.

For $k \in [n]$, the $k$-th truncation $a[k]$ of $a = [a_1, \dots, a_n]$ is defined to be $a[k] := [a_1, a_2, \dots, a_k]$. A proof of the following lemma can be found in [5].
**Lemma 3** Let $v = [v_1, \dots, v_n]$ and $w = [w_1, \dots, w_n]$ be two permutations from $S_n$. Then $v \le w$ (in Bruhat-Chevalley ordering) if and only if

$$ \tilde{v}[k] \le_c \tilde{w}[k] \text{ for all } k = 1, \dots, n. $$

The EL-shellability of the Bruhat-Chevalley order on symmetric group is first proved by Edelman in [7]. His EL-labeling is as follows: If $\sigma$ covers $\pi$ and the numbers $i$ and $j$, $i < j$, are interchanged in $\pi$ to get $\sigma$, then the covering relation (the edge in the Hasse diagram) between $\pi$ and $\sigma$ is labeled by $(i, j)$. It means that the covering relation between $\pi$ and $\sigma$ is labeled by $(i, j)$ when $\sigma = (i, j) \cdot \pi$, where by $(i, j)$ we mean the transposition which interchanges $i$ and $j$. Edelman proves in [7] that this labeling is indeed an EL-labeling, the transpositions $(i, j)$ are totally ordered by the lexicographic order. We use another EL-labeling of the Bruhat poset of $S_n$: the covering relation between $\pi$ and $\sigma$ is labeled by $(i, j)$ when $\sigma = \pi \cdot (i, j)$. This is also an EL-labeling since the map $\delta \mapsto \delta^{-1}$ is order-preserving and $\sigma = \pi \cdot (i, j)$ if and only if $\sigma^{-1} = (i, j) \cdot \pi^{-1}$.

## 3 Gradedness and EL-shellability

Observe that a maximal set on which $\Omega$ is injective is the set of standard cyclic forms which suit a certain composition of $n$. Indeed, when we know the composition type we can put the parentheses on the one-line notation of the permutation in the image of $\Omega$, and thus, we reconstruct its pre-image.

**Theorems A. & C.** Let $\lambda = (\lambda_1, \dots, \lambda_k)$ be a composition of $n$. Then $C_\lambda$ is a bounded, graded, EL-shellable subposet of the Bruhat-Chevalley poset of $S_n$.

**Sketch of the proof** The unique minimal element of $C_\lambda$ is the identity permutation $id = (1, 2, \dots, n)$. The unique maximal element $\omega_\lambda$ of $C_\lambda$ is obtained as follows. Let $\pi_\lambda = T_1 \dots T_k$ be the permutation given in standard cycle form such that

$$ T_i = \begin{cases} (i) & \text{if } \lambda_i = 1, \\ (i, n - \sum_{j=1}^{i-1} \lambda_j - (i-1), n - \sum_{j=1}^{i-1} \lambda_j - (i-2), \dots, n - \sum_{j=1}^{i-2} \lambda_j) & \text{if } \lambda_i > 1, \end{cases} \quad (3) $$

where $T_i$ is a cycle of length $\lambda_i$. For example, if $\lambda = (4, 2, 3, 5)$, then

$$ \pi_{(4,2,3,5)} = (1, 14, 13, 12)(2, 11)(3, 10, 9)(4, 8, 7, 6, 5). $$

By using Lemma 3, it is easy to verify that $\Omega(\pi_\lambda)$ is the maximal element of $C_\lambda$. So, the poset $C_\lambda$ is bounded.

In order to prove that $C_\lambda$ is graded and EL-shellable we use Lemma 1. We take two permutations $\delta, \tau \in C_\lambda$ such that $\delta < \tau$ in the Bruhat-Chevalley order of $S_n$, and show that unique increasing chain (which is lexicographically smallest) between $\delta$ and $\tau$ lies completely inside $C_\lambda$. $\square$

Computing the length of the maximal element $\omega_\lambda$ in $C_\lambda$ we find the length of the poset $C_\lambda$:

**Proposition 4** For $\lambda = (\lambda_1, \dots, \lambda_k) \models n$, the length of $C_\lambda$ is equal to $\binom{n-1}{2} + k - 1 - \sum_{r=1}^k (r-1)\lambda_r$.

## 4 Unimodality and rank symmetry

Let $Comp(n)$ denote the set of all compositions of $n$. Define the operator $ST: Comp(n) \to Comp(n)$ as follows: For $\lambda = (\lambda_1, \dots, \lambda_k) \in Comp(n)$, $ST(\lambda)$ is the composition of $n$ obtained from $\lambda$ by
splitting the part $\lambda_j$ into two parts $\lambda_j - 1, 1$, where $\lambda_j$ is the rightmost part of $\lambda$ which is greater than 1. For example, $\mathcal{ST}(4, 3) = (4, 2, 1)$ and $\mathcal{ST}(1, 2, 1, 3, 1, 1) = (1, 2, 1, 2, 1, 1, 1)$. Notice that for any composition $\lambda$ if we keep applying the operation $\mathcal{ST}$, then eventually we arrive at the composition with all parts equal to 1.

Our first important observation regarding the relationship between $C_\lambda$ and $C_{\mathcal{ST}(\lambda)}$ is that if $\lambda_k > 1$, then $C_\lambda = C_{\mathcal{ST}(\lambda)}$. Indeed, this is easy to verify and does not need a proof. If, on the contrary, $\lambda_k = 1$, then there is a natural embedding of $C_{\mathcal{ST}(\lambda)}$ in $C_\lambda$. Moreover, as we show below, $C_\lambda$ is a union of several copies of $C_{\mathcal{ST}(\lambda)}$ glued together in a certain way. Also, as we are going to explain in the sequel, it follows from these observations that the poset $C_\lambda$ is rank-symmetric and unimodal. In other words, if $r_i$ denotes the number of elements of length $i$ in $C_\lambda$ and $M$ denotes the length of $\omega_\lambda$, the maximal element of $C_\lambda$, then

* $r_i = r_{M-i}$, for all $i = 0, \dots, \lfloor M/2 \rfloor$,

* $r_0 \le r_1 \le \dots \le r_{\lfloor M/2 \rfloor} \ge r_{\lfloor M/2 \rfloor+1} \ge \dots \ge r_M$.

Exploring in detail the example of $C_{(4,2)}$, whose Hasse diagram is depicted in Figure 1 below, we see that the poset $C_{(4,2)} = C_{(4,1,1)}$ is a union of three copies of $C_{(3,1,1,1)}$, shifted by one-level each. Each of those copies of $C_{(3,1,1,1)}$ is a union of four copies of $C_{(2,1,1,1,1)}$, each of which is a union of five singletons $C_{(1,1,1,1,1,1)}$. See [3] for more details.

We paraphrase pictorially starting from $C_{(2,1,1,1,1)}$:

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

Here, we read the rows of the array starting from top towards bottom. Each of the first five rows corresponds to a copy of $C_{(1,1,1,1,1,1)}$. Each of them has the unique entry 1 since these come from one-element posets. Each next row is shifted one unit towards right because each copy of $C_{(1,1,1,1,1,1)}$ is placed one level above the previous copy in $C_{(2,1,1,1,1)}$. The sixth row is the sequence of numbers of elements at each level of $C_{(2,1,1,1,1,1)}$.

We repeat the same process for the four copies of $C_{(2,1,1,1,1)}$ in $C_{(3,1,1,1)}$:

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

The top first four rows are sequences of numbers of elements at each level of $C_{(2,1,1,1,1)}$. There is a shifting because each next copy starts one level above the previous copy of $C_{(2,1,1,1,1)}$ in $C_{(3,1,1,1)}$. The last row is the sequence of the cardinalities of the levels of $C_{(3,1,1,1)}$. Clearly, each entry of the sequence is the sum of the terms lying above in its column.
<figure><img src="image_3.png" /><figcaption>Fig. 1: $C_{(3,1,1,1)}$ in $C_{(4,2)} = C_{(4,1,1)}$</figcaption></figure>
In the same way we display what happens when three copies of the poset $C_{(3,1,1,1)}$ form the poset $C_{(4,1,1)}$.

Using these observations we easily compute $\sum_{\pi \in C_{(4,1,1)}} q^{\mathrm{inv}(\pi)}$: The length-generating function of the chain of five elements $C_{(2,1,1,1,1)}$ is just $1 + q + q^2 + q^3 + q^4 = [5]_q$. Four copies of $C_{(2,1,1,1,1)}$ form $C_{(3,1,1,1)}$ in the way that we described, so the length-generating function of $C_{(3,1,1,1)}$ is $[4]_q[5]_q$, which is equal to $1 + 2q + 3q^2 + 4q^3 + 4q^4 + 3q^5 + 2q^6 + q^7$. Three copies of $C_{(3,1,1,1)}$ form $C_{(4,1,1)}$ in the way that we described, so the length-generating function of $C_{(4,1,1)}$ is

$$ \sum_{\pi \in C_{(4,1,1)}} q^{\mathrm{inv}(\pi)} = [3]_q[4]_q[5]_q = 1 + 3q + 6q^2 + 9q^3 + 11q^4 + 11q^5 + 9q^6 + 6q^7 + 3q^8 + q^9. $$

Generalizing the above investigation of the example, we get:

**Lemma 5** Let $\lambda = (\lambda_1, \dots, \lambda_k) \models n$ be a composition of $n$, and let $\lambda_j$ be the rightmost part of $\lambda$ which is greater than 1. Then

$$ C_{\lambda} = \bigcup_{i=0}^{k-j} C_{ST(\lambda)}^{(i)}, $$

where $C_{ST(\lambda)}^{(i)} \subseteq C_{\lambda}$, $i = 1, \dots, k-j$ is a subposet isomorphic to $C_{ST(\lambda)}$, and defined as follows: $C_{ST(\lambda)}^{(0)}$ is just the natural embedding of $C_{ST(\lambda)}$ into $C_{\lambda}$. To build $C_{ST(\lambda)}^{(1)}$ from $C_{ST(\lambda)}^{(0)}$, pick an element $\pi^{(0)} \in C_{ST(\lambda)}^{(0)}$ and notice that $\pi_t^{(0)} < \pi_{t+1}^{(0)}$, where $t = \lambda_1 + \lambda_2 + \dots + \lambda_j$. Define $\pi_{(1)} \in C_{ST(\lambda)}^{(1)}$ by interchanging $\pi_t^{(0)}$ and $\pi_{t+1}^{(0)}$ in the one-line notation of $\pi^{(0)}$, i.e., $\pi^{(1)} = [1, \pi_2^{(0)}, \dots, \pi_{t-1}^{(0)}, \pi_{t+1}^{(0)}, \pi_t^{(0)}, \dots, \pi_n^{(0)}]$. To build $C_{ST(\lambda)}^{(2)}$ from $C_{ST(\lambda)}^{(1)}$, we start with an element $\pi^{(1)}$ of $C_{ST(\lambda)}^{(1)}$. Then the permutation $\pi^{(2)}$ is defined by interchanging t-th and $(t+2)$-th entries in the one-line notation of $\pi^{(1)}$, and so on.

**Theorems B.** Let $\lambda = (\lambda_1, \dots, \lambda_k)$ be a composition of $n$. The poset $C_{\lambda}$ is unimodal and rank-symmetric and moreover its length-generating function is equal to

$$ \sum_{\pi \in C_{\lambda}} q^{\mathrm{inv}(\pi)} = [i_1]_q[i_2]_q \cdots [i_m]_q $$

for a certain sequence $2 \le i_1 < i_2 < \dots < i_m \le n-1$.

# 5 The order complex of $C_{\lambda}$

The Möbius function of a poset $P$ is defined recursively by the formula

$$ \begin{aligned} \mu([x, x]) &= 1 \\ \mu([x, y]) &= - \sum_{x \le z < y} \mu([x, z]) \end{aligned} $$

for all $x \le y$ in $P$.

Let $\hat{0}$ and $\hat{1}$ denote the smallest and the largest elements of $P$, respectively. It is well known that $\mu(\hat{0}, \hat{1})$ is equal to the “reduced Euler characteristic” $\tilde{\chi}(\Delta(P))$ of the topological realization of the order complex of the proper part of $P$. See Proposition 3.8.6 in [11].
Let $\Gamma$ denote a finite, totally ordered set and let $g$ be a $\Gamma$-valued function defined on $C(P)$. Then $g$ is called an $R$-labeling for $P$, if for every interval $[x, y]$ in $P$, there exists a unique saturated chain $x = x_1 \leftarrow x_2 \leftarrow \dots \leftarrow x_{n-1} \leftarrow x_n = y$ such that

$$g(x_1, x_2) \leq g(x_2, x_3) \leq \dots \leq g(x_{n-1}, x_n). \qquad (4)$$

Thus, $P$ is EL-shellable, if it has an $R$-labeling $g : C(P) \to \Gamma$ such that for each interval $[x, y]$ in $P$ the sequence (4) is lexicographically smallest among all sequences of the form

$$(g(x, x'_2), g(x'_2, x'_3), \dots, g(x'_{k-1}, y)),$$

where $x \leftarrow x_2 \leftarrow' \dots \leftarrow x'_{k-1} \leftarrow y$.

Suppose $P$ is of length $n \in \mathbb{N}$ with the length function $\ell = \ell_P : P \to \mathbb{N}$. For $S \subseteq [n]$, let $P_S$ denote the subset $P_S = \{x \in P : \ell(x) \in S\}$. We denote by $\mu_S$ the Möbius function of the poset $\hat{P}_S$ that is obtained from $P_S$ by adjoining a smallest and a largest element, if they are missing. Suppose also that $g : C(P) \to \Gamma$ is an $R$-labeling for $P$. In this case it is well known that $(-1)^{|S|-1}\mu_S(\hat{0}_{\hat{P}_S}, \hat{1}_{\hat{P}_S})$ is equal to the number of maximal chains $x_0 = \hat{0} \leftarrow x_1 \leftarrow \dots \leftarrow x_n = \hat{1}$ in $P$ for which the descent set of the sequence $(g(x_0, x_1), \dots, g(x_{n-1}, x_n))$ is equal to $S$, or equivalently, $\{i \in [n] : g(x_{i-1}, x_i) > g(x_{i+1}, x_i)\} = S$. See Theorem 3.14.2 in [11].

**Theorems D.** Let $\lambda = (\lambda_1, \dots, \lambda_k)$ be a composition of $n$.

1. If $\lambda = (n)$, or $\lambda = (n-1, 1)$, then $C_\lambda$ is isomorphic to the Bruhat-Chevalley poset on $S_{n-1}$, embedded into $S_n$ as the set of permutations fixing 1. Similarly, if $\lambda_1 = \lambda_2 = \dots = \lambda_{k-1} = 1$ and $\lambda_k = n-k+1$ or $\lambda_1 = \lambda_2 = \dots = \lambda_{k-2} = 1$, $\lambda_{k-1} = n-k$, $\lambda_k = 1$ (like $(1, 1, 1, 4, 1)$), then $C_\lambda$ is isomorphic to the Bruhat-Chevalley poset $S_{n-k}$ suitably embedded into $S_n$.

2. In all other cases the order complex of the proper part of $C_\lambda$ triangulates a ball.

**Sketch of the proof.** The first statement is obvious. We know from Section 3 that the poset $C_\lambda$ is EL-shellable. In order to show that its order complex triangulates a ball, by the discussion at the beginning of this section it is enough to show that there does not exist a decreasing chain going from $id$ to $\omega_\lambda$ so that $\mu_{C_\lambda}([id, \omega_\lambda]) = 0$.

# 6 Conclusion

This work can be continued in several directions. For example, one can investigate the poset $\Omega(\text{Conj}(\nu))$, where $\text{Conj}(\nu)$ is the conjugacy class of the symmetric group which corresponds to the partition $\nu$. Obviously, $\Omega$ is not necessarily a one-to-one mapping when we consider it on $\text{Conj}(\nu)$ and $\Omega(\text{Conj}(\nu)) = \cup_{\lambda} C_{\lambda}$, where $\lambda$ runs over all compositions obtained by permuting the parts of the partition $\nu$. The computer calculations performed for few examples suggest that such posets are bounded, graded and unimodal. However, they are not necessarily rank-symmetric. The natural question is to understand whether they are EL-shellable, and to determine their order complexes.

Another possibly interesting direction is to understand whether the posets presented here are related in some nice combinatorial way to representations of $S_n$ or of the type A 0-Hecke algebra along the lines of [8].
Richard Stanley pointed out to us that the posets $C_\lambda$ may possess the symmetric-chain properly [Page 182, [12]], and guessed that his arguments could be modified to this end. Indeed, the following modification of the order preserving bijection that Stanley uses [cf. [12]] for proving the symmetric-chain property for $S_n$ proves that $C_\lambda$ also has the symmetric-chain property.

For a permutation $\pi = [\pi_1, \dots, \pi_n] \in S_n$ given in one-line-notation, let $A_i$ ($1 \le i \le n$) denote the number of inversions that $\pi_i$ creates. In other words, $A_i := |\{i < j \le n : \pi_i > \pi_j\}|$. Denote the set of numbers $\{0, 1, \dots, k\}$ by $[0, k]$, and define $\tilde{I} : S_n \to [0, n-1] \times [0, n-2] \times [0, 1] \times [0, 0]$ by $\tilde{I}(\pi) = (A_1, \dots, A_n)$. Then it is easy to check that $\tilde{I}$ is an order preserving bijection. Note that on the right hand side we are using the product ordering. Let us mention by passing that Avni uses this bijection in his M.Sc. thesis [1] for some other means. Now, let $\lambda = (\lambda_1, \dots, \lambda_r) \models n$, and let $\pi \in C_\lambda$. Observe that if $1 \le i \le r$, and if $i = 1+\lambda_1+\lambda_2+\dots+\lambda_s$ for some $s \in [r]$, then $A_i = A_i(\pi) = 0$. On the other hand, if $j \in [n]$ is not equal to such an $i$, then $A_i$ is arbitrary and lies in the interval $[0, i-1]$. In other words, the image of the restriction of $\tilde{I}_\lambda$ to $C_\lambda$ is the Cartesian product $\times_{j \in [n]-\{1+\sum_{i=1}^s \lambda_i : s \in [r]\}} [j-1, 0]$. Since any product of chains is a symmetric chain order, $C_\lambda$ is a symmetric chain order, as Stanley predicted.

Let $W$ denote a Coxeter group. In [10], generalizing the notion of parabolic subgroup E. Rains and M. Vazirani introduce the notion of a "quasi-parabolic subgroup" and the associated "quasi-parabolic $W$-set." They show that these $W$-sets carry a partial ordering, similar to strong Bruhat ordering and they are "CL-shellable" and its rank-generating function has a very nice decomposition. Here in our paper, we do not use CL-shellability, however, let us mention that an EL-shellable poset is CL-shellable. In this direction, it is interesting to understand for what composition $\lambda \models n$, the Bruhat-Chevalley poset $C_\lambda$ is a quasi-parabolic set. It is rather obvious that for certain $\lambda$'s it is quasi-parabolic, however, it is interesting to understand whether it is true for any $\lambda$, and if the answer is negative, then it would be nice to give a characterization of those $\lambda$ for which $C_\lambda$ is a quasi-parabolic set.

## References

[1] A. Avni. *Matchings and permutations*. M. Sc. thesis, 2013, Bar-Ilan University, Israel.

[2] A. Björner and M. Wachs. *Bruhat-Chevalley order of Coxeter groups and shellability*. Advances in Mathematics, 43: 87–100 (1982).

[3] M.B. Can and Y. Cherniavsky. *Omitting parentheses from the cyclic notation*. Preprint available from http://arxiv.org/abs/1308.0936.

[4] M.B. Can, Y. Cherniavsky, T. Twelbeck. *Bruhat-Chevalley order on fixed-point-free involutions*. Preprint available from http://arxiv.org/abs/1211.4147.

[5] M.B. Can and L.E. Renner. *Bruhat-Chevalley Order on the Rook Monoid*. Turkish J. Math., 36 (2012), 499-519.

[6] R.S. Deodhar and M.K. Srinivasan. *A statistic on involutions*. J. Algebraic Combin., 13(2):187-198, 2001.

[7] P.H. Edelman. *The Bruhat-Chevalley order of the Symmetric group is lexicographically shellable*. Proc. Amer. Math. Soc. 82 (1981), 355–358.
[8] P. McNamara. *EL-labelings, Supersolvability and 0-Hecke Algebra Actions on Posets*. Journal of Combinatorial Theory (Series A), **101**(1) (2003), 69–89.

[9] R. Proctor. *Classical Bruhat orders and lexicographic shellability*. Journal of Algebra, **77**: 104–126 (1982).

[10] E. Rains and M. Vazirani. *Deformations of Permutation Representations of Coxeter Groups*. J. Algebraic Combin. Volume 37, Issue 3, pp 455–502 (2013).

[11] R.P. Stanley. *Enumerative Combinatorics. Volume 1 (Second Edt.)*. Cambridge Press.

[12] R.P. Stanley. *Weyl Groups, The Hard Lefschetz Theorem, and the Sperner Property*. Siam J. Alg. Disc. Meth. **1**(2); 168–184 (1980).

[13] J. Upperman and C.R. Vinroot. *A weight statistic and partial order on products of m-cycles*. Discrete Math., **315-316**(2014); 9–17.