# Double homotopy Cohen-Macaulayness for the poset of injective words and the classical NC-partition lattice

Myrto Kallipoliti<fnref n="1" />†and Martina Kubitzke<fnref n="2" />‡

**Abstract.** In this paper we study topological properties of the poset of injective words and the lattice of classical non-crossing partitions. Specifically, it is shown that after the removal of the bottom and top elements (if existent) these posets are doubly Cohen-Macaulay. This extends the well-known result that those posets are shellable. Both results rely on a new poset fiber theorem, for doubly homotopy Cohen-Macaulay posets, which can be considered as an extension of the classical poset fiber theorem for homotopy Cohen-Macaulay posets.

**Résumé.** Dans cet article, nous étudions certaines propriétés topologiques du poset des mots injectifs et du treillis des partitions non-croisées classiques. Plus précisément, nous montrons qu’après suppression des plus petit et plus grand élément (s’ils existent), ces posets sont doublement Cohen-Macaulay. C’est une extension du fait bien connu que ces deux posets sont épluchables (“shellable”). Ces deux résultats reposent sur un nouveau théorème poset-fibre pour les posets doublement homotopiquement Cohen-Macaulay, que l’on peut voir comme extension du théorème poset-fibre classique pour les posets homotopiquement Cohen-Macaulay.

**Keywords:** injective words, non-crossing partitions, strongly constructible, doubly homotopy Cohen-Macaulay, poset fiber theorem

## 1 Introduction and results

This paper focuses on the study of the topology of two different posets – the poset of injective words on $n$ letters (denoted by $I_n$) and the lattice of non-crossing partitions for the symmetric group (denoted by $NC(S_n)$).

The results we obtain for those two posets rely on a new poset fiber theorem for doubly homotopy Cohen-Macaulay posets and intervals. This theorem can be seen as an extension of the classical poset fiber theorem for homotopy Cohen-Macaulay posets by Quillen [19].

<footnote n="1">¹Erwin Schrödinger International Institute for Mathematical Physics, Wien, Austria</footnote>

<footnote n="2">²Fakultät für Mathematik, Universität Wien, Wien, Austria</footnote>

<footnote>†supported by the Junior Research Fellowship at the ESI</footnote>

<footnote>‡supported by the Austrian Science Foundation FWF, grant Y463-N13</footnote>
**Theorem 1.1** Let $P$ be a graded poset, $I = (u, v)$ be an open interval in $P$ and $x \in I$. Assume that $I - \{x\}$ is graded and that $Q$ is a homotopy Cohen-Macaulay poset. Let further $f : P \to Q$ be a surjective rank-preserving poset map which satisfies the following conditions:

(i) For every $q \in Q$ the fiber $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay.

(ii) There exists $q_0 \in Q$ such that

* $f^{-1}(q_0) = \{x\}$ and $f(I) - \{q_0\}$ is homotopy Cohen-Macaulay, and

* for every $q > q_0$ and $p \in f^{-1}(q) \cap I$ the poset $[u, p] - \{x\}$ is homotopy Cohen-Macaulay.

Then $I - \{x\}$ is homotopy Cohen-Macaulay as well. If for all $x \in I$ there exists a map satisfying the above conditions and if $\text{rank}(I - \{x\}) = \text{rank}(I)$, then $I$ is doubly homotopy Cohen-Macaulay.

In the past, the poset of injective words as well as the one of classical non-crossing partitions have attracted the attention of a lot of different researchers and are well-studied objects.

It was shown by Farmer [13] in 1978 that the regular CW-complex $K_n$, whose face poset is $I_n$, is homotopy equivalent to a wedge of spheres of top dimension. Björner and Wachs [9] could strengthen this result by demonstrating that this complex is even CL-shellable. More recently, Reiner and Webb [20] computed the homology of $K_n$ as an $S_n$-module and in [14] Hanlon and Hersh provided a refinement of this result by giving a Hodge type decomposition for the homology of $K_n$. Further generalizations of the complex of injective words $K_n$ are considered in [16].

In this paper we are interested in the topological properties of the poset $I_n - \{\emptyset, x\}$, where $\emptyset$ denotes the empty word of $I_n$ and $x \in I_n$ can be any word different from $\emptyset$. Using Theorem 1.1 we show that this poset, i.e., its order complex, is homotopy Cohen-Macaulay. In particular, this yields the following result.

**Theorem 1.2** Let $n \ge 2$ and let $\emptyset \in I_n$ denote the empty word. Then $I_n - \{\emptyset\}$ is doubly homotopy Cohen-Macaulay.

Our second main object of study is the poset of classical non-crossing partitions $\text{NC}(S_n)$. This poset has been investigated by several people and it has been shown to be a graded, self-dual lattice [5]. Moreover, Björner and Edelman [6] established EL-shellability of $\text{NC}(S_n)$. In personal communication, Athanasiadis proposed to study the problem of whether the proper part of $\text{NC}(S_n)$, i.e., the poset obtained from $\text{NC}(S_n)$ after the removal of the maximum and the minimum element, is doubly homotopy Cohen-Macaulay. Using Theorem 1.1 we can give an affirmative answer to this question.

**Theorem 1.3** The proper part of the lattice of non-crossing partitions $\text{NC}(S_n)$ is doubly homotopy Cohen-Macaulay for $n \ge 3$.

The paper is structured as follows. Section 2.1 reviews background on posets and simplicial complexes. Undefined notions and concepts which were used in the introduction are defined and explained in this or one of the following sections. In Sections 2.2 and 2.3 we recall the definitions and some properties of the poset of injective words and the classical non-crossing partition lattice, respectively. In Section 3 we provide the proof of the poset fiber theorem for doubly homotopy Cohen-Macaulay intervals (Theorem 1.1) and derive another poset fiber theorem for doubly homotopy Cohen-Macaulay posets as a corollary (Corollary 3.3). Those two results are employed in Section 4 in order to show that $I_n - \{\emptyset\}$ and the proper part of $\text{NC}(S_n)$ are both doubly homotopy Cohen-Macaulay posets (Theorems 1.2 and 1.3).
# 2 Preliminaries

## 2.1 Partial orders and simplicial complexes

Let $(P, \leq)$ be a finite partially ordered set (poset for short) and $x, y \in P$. We say that $y$ covers $x$ if $x < y$ and there is no $z \in P$ such that $x < z < y$. The poset $P$ is called *bounded* if there exist elements $\emptyset$ and $\hat{1}$ such that $\emptyset \leq x \leq \hat{1}$ for every $x \in P$. The proper part $\bar{P}$ of a bounded poset $P$ is the subposet $\bar{P} = P - \{\emptyset, \hat{1}\}$ obtained after the removal of $\emptyset$ and $\hat{1}$. A subset $C$ of a poset $P$ is called a *chain* if any two elements of $C$ are comparable in $P$. Throughout this paper, we denote by $\{\emptyset, \hat{1}\}$ the 2-element chain with $\emptyset < \hat{1}$. The *length* of a (finite) chain $C$ is equal to $|C| - 1$. We say that $P$ is *graded* if all maximal chains of $P$ have the same length and call this length the *rank* of $P$. Moreover, there exists a unique function $\text{rank} : P \to \mathbb{N}$, called the *rank function* of $P$, such that $\text{rank}(x) = 0$ if $x$ is a minimal element of $P$, and $\text{rank}(y) = \text{rank}(x) + 1$ if $y$ covers $x$. We say that $x$ has $\text{rank} i$ if $\text{rank}(x) = i$. For $S \subseteq P$ the *order ideal* of $P$ generated by $S$ is the subposet $\langle S \rangle_P = \{x \in P : x \leq y \text{ for some } y \in S\}$. We omit the subscript $P$ when it is clear from the context in which poset we are considering the order ideal. The same convention is used for intervals. For $x \in P$ we set $P_{<x} = \{p \in P : p < x\}$. Given two posets $(P, \leq_P)$ and $(Q, \leq_Q)$, a map $f : P \to Q$ is called a *poset map* if it is order-preserving, i.e., $x \leq_P y$ implies $f(x) \leq_Q f(y)$ for all $x, y \in P$. If, in addition, $f$ is a bijection with order-preserving inverse, then $f$ is said to be a *poset isomorphism*. In this case, the posets $P$ and $Q$ are said to be *isomorphic*, and we write $P \cong Q$. Assuming that $P$ and $Q$ are graded, a map $f : P \to Q$ is called *rank-preserving* if for every $x \in P$ the rank of $f(x)$ in $Q$ is equal to the rank of $x$ in $P$. The *dual* of a poset $P$ is the poset $P^*$ on the same ground set as $P$ with reversed ordering relations, i.e., $x \leq_P^* y$ if and only if $y \leq_P x$. A poset $P$ is called *self-dual* if and only if $P \cong P^*$ and it is locally self-dual if every closed interval of $P$ is self-dual. The *direct product* of two posets $P$ and $Q$ is the poset $P \times Q$ on the set $\{(x, y) : x \in P, y \in Q\}$ for which $(x, y) \leq (x', y')$ holds in $P \times Q$ if $x \leq_P x'$ and $y \leq_Q y'$. The *ordinal sum* $P \oplus Q$ of $P$ and $Q$ is the poset defined on the disjoint union of $P$ and $Q$ with the order relation $x \leq y$ if (i) $x, y \in P$ and $x \leq_P y$, or (ii) $x, y \in Q$ and $x \leq_Q y$, or (iii) $x \in P$ and $y \in Q$. For more information on partially ordered sets we refer the reader to [21, Chapter 3].

An *abstract simplicial complex* $\Delta$ on a finite vertex set $V$ is a collection of subsets of $V$ such that $G \in \Delta$ and $F \subseteq G$ imply $F \in \Delta$. The elements of $\Delta$ are called *faces*. Inclusionwise maximal and 1-element faces are called *facets* and *vertices*, respectively. The dimension of a face $F \in \Delta$ is equal to $|F| - 1$ and is denoted by $\dim F$. The *dimension* of $\Delta$ is the maximum dimension of a face of $\Delta$ and is denoted by $\dim \Delta$. If all facets of $\Delta$ have the same dimension, then $\Delta$ is called *pure*. The *link* of a face $F$ of $\Delta$ is defined as $\text{link}_{\Delta}(F) = \{G : F \cup G \in \Delta, F \cap G = \emptyset\}$. All topological properties of an abstract simplicial complex $\Delta$, we mention, refer to those of its geometric realization $\|\Delta\|$. The complex $\Delta$ is said to be *homotopy Cohen-Macaulay* if for all $F \in \Delta$ the link of $F$ is topologically $(\dim(\text{link}_{\Delta}(F)) - 1)$-connected. For a $d$-dimensional simplicial complex we have the following implications: *shellable* $\Rightarrow$ *constructible* $\Rightarrow$ *homotopy Cohen-Macaulay* $\Rightarrow$ *homotopy equivalent* to a wedge of $d$-dimensional spheres. For background concerning the topology of simplicial complexes we refer to [7] and [22].

To every poset $P$ we associate its *order complex* $\Delta(P)$. The $i$-dimensional faces of $\Delta(P)$ are the chains of $P$ of length $i$. If $P$ is graded of rank $n$, then $\Delta(P)$ is pure of dimension $n$. All topological properties of $P$ refer to those of $\|\Delta(P)\|$. We call a poset $P$ *homotopy Cohen-Macaulay* or *shellable* if $\Delta(P)$ has this property.
## 2.2 The poset of injective words

A word $\omega$ over a finite alphabet $A$ is called *injective* if no letter appears more than once. We denote by $I_n$ the set of injective words on $\{1, \dots, n\}$. The order relation on $I_n$ is given by the containment of subwords, i.e., $\omega_1 \cdots \omega_s \le \sigma_1 \cdots \sigma_r$ if and only if there exist $1 \le i_1 < i_2 < \cdots < i_s \le r$ such that $\omega_j = \sigma_{ij}$ for $1 \le j \le s$. E.g., we have $124 < 12345$ in $I_5$ and $12$ and $23$ are incomparable in each $I_n$ for $n \ge 3$. Figure 1 illustrates the Hasse diagrams of the posets $I_2$ and $I_3$. We note that every closed interval of $I_n$ is isomorphic to a Boolean algebra and as such shellable.

<figure><img src="image_1.png" /><figcaption>Fig. 1: The posets $I_2$ and $I_3$.</figcaption></figure>

## 2.3 Non-crossing partitions

Let $W$ be a finite Coxeter group and let $T$ be its set of reflections. E.g., if $W$ equals the symmetric group $S_n$ on $\{1, \dots, n\}$, then the set $T$ consists of all transpositions $(ij)$ for $1 \le i < j \le n$. The absolute length $\ell_T(w)$ of an element $w \in W$ is the minimal integer $r$ such that $w$ can be written as a product of $r$ reflections. The absolute length of an element of $S_n$ equals $n$ minus the number of cycles in its cycle decomposition. The absolute order on $W$ is the poset $\text{Abs}(W)$ defined by setting

$$ \pi \le_T \mu \iff \ell_T(\mu) = \ell_T(\pi) + \ell_T(\pi^{-1}\mu) $$

for all $\mu, \pi \in W$. This poset is graded with rank function $\ell_T$ and minimum element $e \in W$. It was shown in [12, Section 2] that for all $u, v \in S_n$ we have $u \le_T v$ if and only if

* every cycle in the cycle decomposition of $u$ can be obtained from some cycle in the cycle decomposition of $v$ by deleting elements, and

* any two cycles $a$ and $b$ of $u$ which are obtained from the same cycle $c$ of $v$ are non-crossing with respect to $c$.

Here, disjoint cycles $a$ and $b$ are called *non-crossing* with respect to $c$ if there does not exist a cycle (ijkl) which is obtained from $c$ by deleting elements such that $i, k$ are elements of $a$ and $j, l$ are elements of $b$. Let $c \in W$ be a Coxeter element. The interval

$$ \text{NC}(W, c) = [e, c] = \{w \in W : e \le_T w \le_T c\} $$
is called the poset of non-crossing partitions. It is well-known that for Coxeter elements $c, c' \in W$ it holds that $NC(W, c) \cong NC(W, c')$. We therefore often suppress $c$ from the notation and just write $NC(W)$.

The Coxeter elements of $S_n$ are exactly the $n$-cycles. Figure 2 illustrates the Hasse diagrams of the posets $NC(S_3)$ and $NC(S_4)$.

<figure><img src="image_2.png" /><figcaption>Fig. 2: The posets $NC(S_3)$ and $NC(S_4)$.</figcaption></figure>

It follows from [1, Lemma 2.5.4] that $Abs(W)$ is locally self-dual for every Coxeter group $W$. In particular, this implies the following corollary.

**Corollary 2.1** Let $W$ be a finite Coxeter group with set of reflections $T$. Then, for all $u \in NC(W)$ the principal lower order ideal $\langle u \rangle$ is self-dual. In particular, $NC(W)$ is self-dual.

For more information about Coxeter groups and non-crossing partitions we refer the reader to [1].

## 3 A poset fiber theorem for doubly homotopy Cohen-Macaulay posets

This section focuses on the proof of Theorem 1.1. We first recall the classical poset fiber theorem for homotopy Cohen-Macaulay posets by Quillen.

**Theorem 3.1** [19, Corollary 9.7], [10, Theorem 5.1] Let $P$ and $Q$ be graded posets. Let further $f: P \to Q$ be a surjective rank-preserving poset map. Assume that for every $q \in Q$ the fiber $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay. If $Q$ is homotopy Cohen-Macaulay, then so is $P$.

We will need the following result which follows from Remark 2.6 and Corollary 3.2 in [10].

**Corollary 3.2** Let $P$ and $Q$ be graded posets of rank $n$. Let $f: P \to Q$ be a surjective rank-preserving poset map such that for all $q \in Q$ the order complex $\Delta(Q_{>q})$ is $(n - \mathrm{rank}(q) - 2)$-connected and for all non-minimal $q \in Q$ the inclusion map

$$ \Delta(f^{-1}(Q_{<q})) \hookrightarrow \Delta(f^{-1}(\langle q \rangle)) $$

is homotopic to a constant map which sends $\Delta(f^{-1}(Q_{<q}))$ to $c_q$ for some $c_q \in \Delta(f^{-1}(\langle q \rangle))$. Then $\Delta(P)$ is $(n-1)$-connected if and only if $Q$ is $(n-1)$-connected.
**Proof of Theorem 1.1:** It directly follows from Theorem 3.1 that the poset $P$ is homotopy Cohen-Macaulay and hence so is the interval $I = (u, v)$. Let $\tilde{I}$ denote the poset $I - \{x\}$ and let $k$ be its rank. We need to verify that all links of faces $F \in \Delta(\tilde{I})$ are $(\dim(\mathrm{link}_{\Delta(\tilde{I})}(F)) - 1)$-connected. The arguments we use are similar to those employed in the proof of [10, Theorem 5.1 (i)].

We first show that $\Delta(\tilde{I}) = \mathrm{link}_{\Delta(\tilde{I})}(\emptyset)$ is $(k-1)$-connected. For this aim, we use Corollary 3.2.

Let $\tilde{f} : \tilde{I} \to f(I) - \{q_0\}$ denote the restriction of $f$ to $\tilde{I}$. This map is well-defined, since $f^{-1}(q_0) = \{x\}$, and it is a surjective poset map, because $f$ is. Since $f$ is rank-preserving and since $\tilde{I}$ is graded by hypothesis, we deduce that $\tilde{f}$ is rank-preserving. We set $\tilde{J} = f(I) - \{q_0\}$ and by assumption we know that $\tilde{J}$ is homotopy Cohen-Macaulay. In the following, consider $q \in \tilde{J}$. Since $\Delta(\tilde{J}_{>q})$ is the link of a face of $\Delta(\tilde{J})$, we infer from the above that $\Delta(\tilde{J}_{>q})$ is $(\mathrm{rank}(\tilde{J}_{>q}) - 1) = (\mathrm{rank}(f(v)) - \mathrm{rank}(q) - 3)$-connected. This shows one of the conditions of Corollary 3.2 we need to verify. By assumption on $f$, the fiber $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay and therefore it is $(\mathrm{rank}(q) - 1)$-connected. As in the proof of Theorem 1.1 in [10], it follows that there exists a homotopy from the inclusion map $\Delta(f^{-1}(Q_{<q})) \hookrightarrow \Delta(f^{-1}(\langle q \rangle))$ to the constant map which sends $\Delta(f^{-1}(Q_{<q}))$ to $c_q \in \Delta(f^{-1}(\langle q \rangle))$. We can choose $c_q \in \Delta(\tilde{f}^{-1}(\langle q \rangle)) \subseteq \tilde{I}$. Then the above homotopy restricts to a homotopy from $\Delta(\tilde{f}^{-1}(\tilde{J}_{<q})) \hookrightarrow \Delta(\tilde{f}^{-1}(\langle q \rangle))$ to the constant map which sends $\Delta(\tilde{f}^{-1}(\tilde{J}_{<q}))$ to $c_q$. Thus, $\Delta(\tilde{f}^{-1}(\tilde{J}_{<q})) \hookrightarrow \Delta(\tilde{f}^{-1}(\langle q \rangle))$ is homotopic to a constant map. Finally, we can apply the Corollary aforementioned. Since, by homotopy Cohen-Macaulayness, $\tilde{J}$ is $(k-1)$-connected, it follows that $\tilde{I}$ is $(k-1)$-connected as well.

It remains to show that all links of proper faces $F \neq \emptyset$ of $\Delta(\tilde{I})$ are $(\dim(\mathrm{link}_{\Delta(\tilde{I})}(F)) - 1)$-connected. Since the join of an $s$-connected and an $r$-connected complex is $(r+s-2)$-connected, it suffices to check open intervals and principal upper and lower order ideals (see e.g., [11]).

Let $(a, b)$ be an open interval in $\tilde{I}$. Note that $(a, b)_P = (a, b)_I$. If $x \notin (a, b)_P$, then $(a, b)_I$ and $(a, b)_{\tilde{I}}$ coincide. Since $I$ is homotopy Cohen-Macaulay, it follows that $(a, b)_{\tilde{I}}$ is $(\mathrm{rank}(b) - \mathrm{rank}(a) - 3)$-connected. Now let $a < x < b$ and let $c = f(b)$, i.e., $b \in f^{-1}(c)$. From $b \neq v$, we infer that $b \in I$ and thus $b \in f^{-1}(c) \cap I$. Moreover, we have $c > q_0$ and by condition (ii) of the theorem, it follows that $[u, b)_P - \{x\}$ is homotopy Cohen-Macaulay. Since $(a, b)_{\tilde{I}} = (a, b)_P - \{x\}$ is the link of a face of $[u, b)_P - \{x\}$, we conclude that $(a, b)_{\tilde{I}}$ is $(\mathrm{rank}(b) - \mathrm{rank}(a) - 3)$-connected. The same reasoning shows that open principal lower order ideals $\tilde{I}_{<p}$ of $\tilde{I}$ are $(\mathrm{rank}(p) - \mathrm{rank}(u) - 3)$-connected.

Next, we show that for all $p \in \tilde{I}$ the open principal upper order ideal $\tilde{I}_{>p} = (p, v)_P - \{x\}$ is $(\mathrm{rank}(v) - \mathrm{rank}(p) - 3)$-connected. If $p \not< x$, then $(p, v)_P - \{x\} = (p, v)_P$, and the claim follows, because $P$ is homotopy Cohen-Macaulay. Let now $p < x$. We consider the restriction of $f$ to $P_{\ge p}$. To avoid confusion, let $f : P_{\ge p} \to Q_{\ge f(p)}$ denote this restriction. We show that the map $f$ is a surjective rank-preserving poset map, satisfying all assumptions of the theorem for the interval $(p, v)$ and the element $x \in (p, v)$. Since, due to $u < p$, we have $\mathrm{rank}([p, v]_P - \{x\}) < \mathrm{rank}([u, v]_P - \{x\})$, we can then deduce by induction on the rank of the considered interval that $(p, v)_P - \{x\} = \tilde{I}_{>p}$ is homotopy Cohen-Macaulay. In particular, we obtain that $\tilde{I}_{>p}$ is $(\mathrm{rank}(v) - \mathrm{rank}(p) - 3)$-connected. For the verification of the assumptions, first note that $Q_{\ge f(p)}$ is homotopy Cohen-Macaulay because $Q$ is. Clearly, $x \in (p, v)_P \subsetneq P_{\ge p}$. Since $\tilde{I}$ is graded by assumption, the same is true for $(p, v)_P - \{x\}$. Furthermore, $f$ is a rank-preserving poset map, thus so is $\tilde{f}$. To see that $\tilde{f}$ is surjective, let $q \in Q_{\ge f(p)}$. Since $f$ is rank-preserving and surjective and $f^{-1}(\langle q \rangle)$ is graded, all maximal elements of $f^{-1}(\langle q \rangle)$ are mapped to $q$ and one of these has to be greater
than $p$. Hence, $\bar{f}$ is surjective. For condition (i), note that for $q \in Q_{\ge f(p)}$ the fiber $\bar{f}^{-1}(\langle q \rangle)$ equals $f^{-1}(\langle q \rangle) \cap P_{\ge p}$. Thus, it is a closed principal upper order ideal of the homotopy Cohen-Macaulay poset $f^{-1}(\langle q \rangle)$ and as such homotopy Cohen-Macaulay.

It remains to verify condition (ii). Since $x > p$, we have $f(x) = q_0 \in Q_{\ge f(p)}$ and we obtain that $\bar{f}^{-1}(q_0) = \{x\}$. In addition, it holds that $\bar{f}((p, v)_P) - \{q_0\} = (f(I) - \{q_0\}) \cap (f(p), f(v))_Q$. Thus, $\bar{f}((p, v)_P) - \{q_0\}$ is an open principal upper order ideal of the homotopy Cohen-Macaulay poset $f(I) - \{q_0\}$ and as such homotopy Cohen-Macaulay.

Now let $q > q_0$ and let $\bar{p} \in \bar{f}^{-1}(q) \cap (p, v)_P$. The poset $[p, \bar{p}]_P - \{x\}$ is a closed interval of $[u, \bar{p}]_P - \{x\}$. Since by hypothesis the latter one is homotopy Cohen-Macaulay, so is $[p, \bar{p}]_P - \{x\}$. Finally, it follows by induction that $\tilde{I}_{>p} = (p, v)_P - \{x\}$ is homotopy Cohen-Macaulay. This finishes the first part of the proof. The statement concerning double homotopy Cohen-Macaulayness follows directly from the definition of this property and the first part of the theorem. $\square$

As a corollary of Theorem 1.1 one obtains the following poset fiber theorem for doubly homotopy Cohen-Macaulay posets, see [18] for the exact proof.

**Corollary 3.3** Let $P$ be a graded poset without a minimum and a maximum element and let $x \in P$. Assume that $P - \{x\}$ is graded and that $Q$ is a homotopy Cohen-Macaulay poset. Let further $f: P \to Q$ be a surjective rank-preserving poset map which satisfies the following conditions:

(i) For every $q \in Q$ the fiber $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay.

(ii) There exists $q_0 \in Q$ such that

* $f^{-1}(q_0) = \{x\}$ and $Q - \{q_0\}$ is homotopy Cohen-Macaulay, and

* for every $q > q_0$ and $p \in f^{-1}(q)$ the poset $\langle p \rangle - \{x\}$ is homotopy Cohen-Macaulay.

Then $P - \{x\}$ is homotopy Cohen-Macaulay as well. If for all $x \in P$ there exists a map satisfying the above conditions and if $\mathrm{rank}(P - \{x\}) = \mathrm{rank}(P)$, then $P$ is doubly homotopy Cohen-Macaulay.

It is rather straightforward to give a generalization of Corollary 3.3 to $k$-Cohen-Macaulay posets where $k \ge 2$ (see [18, Proposition 3.4] for the exact result).

# 4 Applications of Corollary 3.3 and Theorem 1.1

This section provides applications of Corollary 3.3 and Theorem 1.1 to $I_n$ and $\mathrm{NC}(S_n)$, respectively. We recall the notion of doubly homotopy Cohen-Macaulay posets.

**Definition 4.1** Let $P$ be a homotopy Cohen-Macaulay poset. Then, $P$ is called doubly homotopy Cohen-Macaulay if for every $x \in P$ the poset $P - \{x\}$ is homotopy Cohen-Macaulay of the same rank as $P$.

For the proofs of Theorems 1.2 and 1.3 we will need the following technical result.

**Theorem 4.2** Let $P$ be a poset of rank $n$ with a minimum element $\hat{0}_P$. Let $\tilde{P} = \bar{P}$ if $P$ is bounded, and let $\tilde{P} = P - \{\hat{0}_P\}$ if $P$ does not have a maximum. Assume that $\tilde{P}$ is doubly homotopy Cohen-Macaulay. Then, for every $x \in \tilde{P}$ the poset $(P \times \{\hat{0}, \tilde{1}\}) - \{(x, \hat{0})\}$ is homotopy Cohen-Macaulay of rank $n + 1$.
**Sketch of the proof:** Let $x \in \tilde{P}$. We write $(P \times \{\hat{0}, \hat{1}\}) - \{(x, \hat{0})\}$ in the following way:

$$ (P \times \{\hat{0}, \hat{1}\}) - \{(x, \hat{0})\} = ((P - \{x\}) \times \{\hat{0}, \hat{1}\}) \cup ((P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus \{(x, \hat{1})\} \oplus (P_{>x} \times \{\hat{1}\})). \quad (1) $$

The first part of the right-hand side of the above equation accounts for all chains in $(P \times \{\hat{0}, \hat{1}\}) - \{(x, \hat{0})\}$ not containing $(x, \hat{1})$. All chains in $(P \times \{\hat{0}, \hat{1}\}) - \{(x, \hat{0})\}$ passing through $(x, \hat{1})$, are captured by the second part of the right-hand side of Equation (1). Since homotopy Cohen-Macaulayness is preserved under taking direct products [11, Corollary 3.8] and ordinal sums [11, Corollary 3.4], it can be proved that the posets $(P - \{x\}) \times \{\hat{0}, \hat{1}\}$ and $(P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus \{(x, \hat{1})\} \oplus (P_{>x} \times \{\hat{1}\})$ are homotopy Cohen-Macaulay of rank $n + 1$. We now consider the intersection of those two posets. We have

$$ ((P - \{x\}) \times \{\hat{0}, \hat{1}\}) \cap ((P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus \{(x, \hat{1})\} \oplus (P_{>x} \times \{\hat{1}\})) = (P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus (P_{>x} \times \{\hat{1}\}). $$

We obtain $(P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus (P_{>x} \times \{\hat{1}\})$ from $(P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus \{(x, \hat{1})\} \oplus (P_{>x} \times \{\hat{1}\})$ by deleting the element $(x, \hat{1})$. From the fact that rank-selection preserves homotopy Cohen-Macaulayness (see e.g., [6]) it follows that $(P_{<x} \times \{\hat{0}, \hat{1}\}) \oplus (P_{>x} \times \{\hat{1}\})$ is homotopy Cohen-Macaulay of rank $n$. If one applies Lemma 4.9 from [24] to the order complex of $(P \times \{\hat{0}, \hat{1}\}) - \{(x, \hat{0})\}$ as well as to its links, one obtains that $(P \times \{\hat{0}, \hat{1}\}) - \{(x, \hat{0})\}$ is homotopy Cohen-Macaulay of rank $n + 1$. $\square$

## 4.1 Proof of Theorem 1.2

Doubly shellable posets are defined in a similar way as doubly homotopy Cohen-Macaulay posets and it was shown by Baclawski [4, Corollary 4.3] that geometric lattices have this property. Combining this with the facts that the Boolean algebra is such a lattice and that homotopy Cohen-Macaulayness is implied by shellability, immediately yields the following.

**Corollary 4.3** *The proper part of the Boolean algebra $B_n$ is doubly homotopy Cohen-Macaulay.*

In various places of the proof of Theorem 1.2 we will employ the notion of strongly constructible posets. We therefore recall the definition of this notion which was introduced and studied in [3].

**Definition 4.4** A graded poset $P$ of rank $n$ with a minimum element is strongly constructible if either

(i) $P$ is bounded and pure shellable, or

(ii) $P$ can be written as a union of two strongly constructible proper ideals $J_1, J_2$ of rank $n$ such that the intersection $J_1 \cap J_2$ is a strongly constructible poset of rank at least $n - 1$.

**Lemma 4.5** [3, Corollary 3.3, Proposition 3.6] Let $P$ be a strongly constructible poset. Then, $P$ is homotopy Cohen-Macaulay.

So as to show that the poset of injective words is doubly homotopy Cohen-Macaulay we will need the following simple lemma.

**Lemma 4.6** Let $P$ be a strongly constructible poset of rank $n$ and let $x \in P$ be a maximal element such that $P - \{x\}$ is graded of rank $n$. Then, the poset $P - \{x\}$ is strongly constructible of rank $n$.
**Proof:** Let $x$ be a maximal element of $P$ such that $P - \{x\}$ is graded of rank $n$. Then, $x$ cannot be the only maximal element of $P$. Since $P$ is strongly constructible and $-$ by the last argument $-$ not bounded, there are proper ideals of $P$, say $J_1$ and $J_2$, which are strongly constructible of rank $n$ and their intersection $J_1 \cap J_2$ is a strongly constructible ideal of rank at least $n-1$. Let $x \in J_1$ and $x \notin J_2$; the case $x \in J_2$ can be treated similarly. Using induction, we may assume that $J_1 = \langle x \rangle$. Since $P - \{x\}$ is graded of rank $n$, it follows that every element which is covered by $x$ is also covered by at least one maximal element of $J_2$. Thus, $J_1 - \{x\} \subseteq J_2$ and therefore $P - \{x\} = (J_1 - \{x\}) \cup J_2 = J_2$, which by assumption is strongly constructible of rank $n$. $\square$

**Proof of Theorem 1.2:** Throughout this proof, we use $\tilde{I}_n$ to denote $I_n - \{\emptyset\}$. In order to show that $\tilde{I}_n$ is doubly homotopy Cohen-Macaulay we proceed by induction on $n$. If $n=2$, then $\tilde{I}_2$ has two maximal elements (the words 12 and 21) and two elements (1 and 2) of rank 1. No matter which one of the elements 12, 21, 1 or 2 is removed from $\tilde{I}_2$ the poset obtained is homotopy Cohen-Macaulay of rank 1. Thus, $\tilde{I}_2$ is doubly homotopy Cohen-Macaulay. Now, assume that $n \ge 3$. Let $x \in \tilde{I}_n$ be a maximal element. Since $I_n$ is shellable, it is in particular strongly constructible. Lemma 4.6 implies that $I_n - \{x\}$ is strongly constructible and using Lemma 4.5 we deduce that $\tilde{I}_n - \{x\}$ is homotopy Cohen-Macaulay.

Consider $x \in \tilde{I}_n$ that is not a maximal element. For every $w \in \tilde{I}_n$ let $\pi(w)$ denote the word obtained from $w$ by deleting $n$. Note that $\pi(\tilde{I}_n) = I_{n-1}$, since $\pi(n) = \emptyset$. We define the map $f: \tilde{I}_n \to I_{n-1} \times \{\hat{0}, \hat{1}\} - \{(\hat{0}, \hat{0})\}$ by letting

$$f(w) = \begin{cases} (\pi(w), \hat{0}), & \text{if } n \not\le w, \\ (\pi(w), \hat{1}), & \text{if } n \le w \end{cases}$$

for $w \in \tilde{I}_n$. Our aim is to apply Corollary 3.3 to this map. By definition, $f$ is a rank-preserving map. We show that $f$ is also a poset map and surjective. Let $u, v \in \tilde{I}_n$ with $u \le v$. Suppose first that $n \not\le v$. Then we also have $n \not\le u$, thus $f(u) = (\pi(u), \hat{0}) = (u, \hat{0})$ and $f(v) = (\pi(v), \hat{0}) = (v, \hat{0})$. It follows that $f(u) \le f(v)$. Suppose now that $n \le v$. Then, $f(v) = (\pi(v), \hat{1})$ and $f(u)$ is either equal to $(\pi(u), \hat{0})$ or to $(\pi(u), \hat{1})$. Since $\pi(u) \le \pi(v)$ and $\hat{0} < \hat{1}$, in both cases it holds that $f(u) \le f(v)$. Altogether, this proves that $f$ is a poset map. Let $w \in \tilde{I}_{n-1}$. Then $f^{-1}((w, \hat{0})) = \{w\}$ and every word obtained from $w$ by inserting the letter $n$ into some position of $w$ lies in $f^{-1}((w, \hat{1}))$. Since $f^{-1}((\hat{0}, \hat{1})) = n$, we obtain that $f$ is surjective.

Next, we show that for $q \in I_{n-1} \times \{\hat{0}, \hat{1}\} - \{(\hat{0}, \hat{0})\}$ the fiber $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay. By a straightforward but rather tedious computation one can verify that for those $q$ it holds that $f^{-1}(\langle q \rangle) = \langle f^{-1}(q) \rangle_{\tilde{I}_n}$. So as to show that $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay, it thus suffices to show that $\langle f^{-1}(q) \rangle_{I_{n-1}} = \langle f^{-1}(q) \rangle_{I_n} - \{\emptyset\}$ has this property. If $q = (w, \hat{0})$ for some $w \in \tilde{I}_{n-1}$, then $\langle f^{-1}(q) \rangle_{\tilde{I}_n} = \langle w \rangle_{I_n} - \{\emptyset\}$. Since every interval in $I_n$ is shellable (see Section 2.2), we infer that $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay in this case. Now suppose that $q = (w, \hat{1})$ for $q \in I_{n-1}$. Without loss of generality, we may assume that $w = 123 \cdots k$, for some $k \le n-1$. Then, $\langle f^{-1}(q) \rangle = \bigcup_{i=0}^k \langle 12 \cdots i n i + 1 \cdots k \rangle_{\tilde{I}_n} = \bigcup_{i=0}^k \langle 12 \cdots i n i + 1 \cdots k \rangle_{I_n} - \{\emptyset\}$. For every $i \in \{0, 1, \dots, k\}$, the ideal $S_i = \langle 12 \cdots i n i + 1 \cdots k \rangle_{I_n}$ is shellable and therefore strongly constructible and we have $\text{rank}(S_i) = k+1$. We show by induction on $j$ that the union $\bigcup_{i=0}^j S_i$ is strongly constructible as well. For this, it suffices to show that $S_j \cap (\bigcup_{i=0}^{j-1} S_i)$ is strongly constructible of rank $k$. We have

$$S_j \cap \left( \bigcup_{i=0}^{j-1} S_i \right) = \langle 12 \cdots k, 12 \cdots j - 1 n j + 1 \cdots k \rangle_{I_n} = \langle 12 \cdots k \rangle_{I_n} \cup \langle 12 \cdots j - 1 n j + 1 \cdots k \rangle_{I_n}.$$
Both ideals, $\langle 12 \cdots k \rangle_{I_n}$ and $\langle 12 \cdots j - 1 nj + 1 \cdots k \rangle_{I_n}$, are strongly constructible of rank $k$ and their intersection is equal to $\langle 12 \cdots j - 1 j + 1 \cdots k \rangle_{I_n}$, which is a strongly constructible ideal of rank $k-1$. This completes the induction and in particular implies that $\bigcup_{i=0}^k S_i$ is strongly constructible and by Lemma 4.5 homotopy Cohen-Macaulay. Since $\emptyset$ is the minimum of $\langle f^{-1}(q) \rangle_{I_n} = \bigcup_{i=0}^k S_i$, we deduce that $f^{-1}(\langle q \rangle)$ is homotopy Cohen-Macaulay.

Let $x \in \tilde{I}_n$. It is easy to see that $\tilde{I}_n - \{x\}$ is graded of rank $n-1$. It remains to verify condition (ii) of Corollary 1.1. Without loss of generality, we may assume that $x = 12 \cdots k$ for some $1 \le k \le n-1$. Let $q_0 = (x, \hat{0})$. Clearly, $f(x) = q_0$ and $f^{-1}(q_0) = \{x\}$ by definition of $f$. By induction we may assume that $\tilde{I}_{n-1}$ is doubly homotopy Cohen-Macaulay and it now follows from Theorem 4.2 that $(I_{n-1} \times \{\hat{0}, \hat{1}\}) - \{q_0\}$ is homotopy Cohen-Macaulay. Since $(\emptyset, \hat{0})$ is the minimum of this poset, we conclude that $(I_{n-1} \times \{\hat{0}, \hat{1}\}) - \{(\emptyset, \hat{0})\}, q_0\}$ is homotopy Cohen-Macaulay. Let $q \in I_{n-1} \times \{\hat{0}, \hat{1}\} - \{(\emptyset, \hat{0})\}$ such that $q > q_0$ and let $p \in f^{-1}(q)$. We need to show that the ideal $\langle p \rangle_{\tilde{I}_n} - \{x\}$ is homotopy Cohen-Macaulay. We know from Section 2.2 that $\langle p \rangle_{I_n}$ is isomorphic to a Boolean algebra. Since $x < p$ (i.e., $x$ is not the maximal element of $\langle p \rangle_{I_n}$), we deduce from Corollary 4.3 that $\langle p \rangle_{I_n} - \{x\}$ is homotopy Cohen-Macaulay. Hence, so is $\langle p \rangle_{\tilde{I}_n} - \{x\}$. We can finally apply Corollary 3.3 which yields that $\tilde{I}_n - \{x\}$ is homotopy Cohen-Macaulay. $\square$

## 4.2 Proof of Theorem 1.3

It was shown by Athanasiadis, Brady and Watt [2, Theorem 1.1] that for each finite Coxeter group the lattice of non-crossing partitions is shellable and in particular homotopy Cohen-Macaulay. In this section we show that the proper part of the lattice of classical non-crossing partitions is indeed doubly homotopy Cohen-Macaulay.

**Proof of Theorem 1.3:** Let $u \in \text{NC}(S_n)$ for some $n$ be a permutation of rank $s$. We show by induction on $s$ that open intervals $(e, u)$ of any non-crossing partition lattice are doubly homotopy Cohen-Macaulay. Without loss of generality, we can assume that $u$ does not have a fixed point. For $s=2$ the result is easy to check. It follows from [2, Theorem 1.1] and [1, Proposition 2.6.11] that $(e, u)$ is shellable, hence homotopy Cohen-Macaulay. We need to show that for every $x \in (e, u)$ the poset $(e, u) - \{x\}$ is homotopy Cohen-Macaulay of rank $s-2$. Since, by Lemma 2.1, $\langle u \rangle$ is self-dual, it is enough to consider those $x$ of rank at most $\lfloor \frac{s}{2} \rfloor$. Note that such an $x$ has to have a fixed point. Without loss of generality, we can assume that $x(n) = n$. We consider the following map from [17]. For every $w \in \text{Abs}(S_n)$ let $\pi(w)$ be the permutation obtained from $w$ by deleting $n$ from its cycle decomposition. We define $g: \text{Abs}(S_n) \to \text{Abs}(S_{n-1}) \times \{\hat{0}, \hat{1}\}$ by letting

$$g(w) = \begin{cases} (\pi(w), \hat{0}), & \text{if } w(n) = n, \\ (\pi(w), \hat{1}), & \text{if } w(n) \neq n \end{cases}$$

for $w \in \text{Abs}(S_n)$. Our goal is to apply Theorem 1.1 to the map $g$ and the interval $(e, u)$. In [17] it is shown that $g$ is a surjective rank-preserving poset map whose fibers are homotopy Cohen-Macaulay. We note first that $(e, u) - \{x\}$ is graded. We consider the element $q_0 = (x, \hat{0}) \in g((e, u))$. By definition, $g^{-1}(q_0) = \{x\}$. Moreover, by $u(n) \neq n$, we know that the permutation $\pi(u)$ is of rank $s-1$ and by induction, the interval $(e, \pi(u))$ is doubly homotopy Cohen-Macaulay. It follows from Theorem 4.2 that the poset $[e, \pi(u)) \times \{\hat{0}, \hat{1}\} - \{q_0\}$ is homotopy Cohen-Macaulay. Since $(e, \hat{0})$ is the minimum of this poset, we conclude that $g((e, u)) - \{q_0\} = [e, \pi(u)) \times \{\hat{0}, \hat{1}\} - \{(e, \hat{0}), q_0\}$ is homotopy Cohen-Macaulay.
It remains to verify the second part of condition (ii) of Theorem 1.1. Let $q \in g((e, u))$ such that $q > q_0$ and let $p \in g^{-1}(q) \cap (e, u)$. We need to show that $[e, p] - \{x\}$ is homotopy Cohen-Macaulay. Since the rank of $p$ is at most $s-1$, the induction hypothesis implies that $(e, p)$ is doubly homotopy Cohen-Macaulay. In particular, $[e, p] - \{x\}$ is homotopy Cohen-Macaulay. Finally, we can apply Theorem 1.1, which yields that $(e, u) - \{x\}$ is homotopy Cohen-Macaulay. From $\mathrm{rank}((e, u) - \{x\}) = \mathrm{rank}((e, u))$ we deduce that $(e, u)$ is doubly homotopy Cohen-Macaulay. This finishes the proof since the proper part of any $\mathrm{NC}(S_n)$ is isomorphic to an interval in $\mathrm{NC}(S_{n+1})$ of the form $(e, u)$. □

We want to remark that double homotopy Cohen-Macaulayness of the non-crossing partition lattice $\mathrm{NC}(S_n)$ can also be concluded by combining Theorem 6.3 and Theorem 3.1 in [15] and [23], respectively. It seems natural to ask whether also the proper parts of non-crossing partition lattices of other type are doubly homotopy Cohen-Macaulay. This turns out to be true for type B (see [18] for the proof of this result). (Note that in this case double homotopy Cohen-Macaulayness does not follow from [15] and [23].) After the reduction to the removal of elements having a fixed point, the proof for type B is literally the same as for type A. However, the question remains open for non-crossing partition lattices of other types.

## Acknowledgments

We would like to thank Christos Athanasiadis for suggesting to study this problem. We are also grateful to Volkmar Welker and to two referees for helpful comments and valuable suggestions on an earlier version of this article.

## References

[1] D. Armstrong. Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Mem. Amer. Math. Soc. **209** (2009).

[2] C. A. Athanasiadis, T. Brady, and C. Watt. Shellability of noncrossing partition lattices. Proc. Amer. Math. Soc. **135** (2007), 939–949.

[3] C. A. Athanasiadis and M. Kallipoliti. The absolute order on the symmetric group, constructible partially ordered sets and Cohen-Macaulay complexes. J. Combin. Theory Series A **115** (2008), 1286–1295.

[4] K. Baclawski. Cohen-Macaulay ordered sets. J. Algebra **63** (1980), 226–258.

[5] D. Bessis. The dual braid monoid. Ann. Sci. Ecole Norm. Sup. **36** (2003), 647–683.

[6] A. Björner. Shellable and Cohen-Macaulay Partially Ordered Sets. Trans. AMS **260**, no 1 (1980), 159–183.

[7] A. Björner. *Topological methods*, in *Handbook of combinatorics* (R.L. Graham, M. Grötschel and L. Lovász, eds.). North Holland, Amsterdam, 1995, 1819–1872.

[8] A. Björner and M. Wachs. Shellable Nonpure Complexes And Posets. I. Trans. AMS **348**, no 4 (1996), 1299–1327.
[9] A. Björner and M. Wachs. On Lexicographically Shellable Posets. Trans. AMS **277**, no 1 (1983), 323–341.

[10] A. Björner, M. Wachs and V. Welker. Poset Fiber Theorems. Trans. AMS **357**, no 5 (1983), 1877–1899.

[11] A. Björner, M. Wachs and V. Welker. On sequentially Cohen-Macaulay complexes and posets. Israel J. Math. **169**, no 1 (2009), 295 – 316.

[12] T. Brady. A partial order on the symmetric group and new $K(\pi, 1)'$'s for the braid groups. Adv. Math. **161** (2001), 20–40.

[13] F. D. Farmer. Cellular homology for posets. Math. Japan **23** (1978/79), 607 – 613.

[14] P. Hanlon and P. Hersh. A Hodge Decomposition for the Complex of Injective Words. Pacific J. Math. **214** (2004), 109 – 125.

[15] P. Hersh. Chain decomposition and the flag $f$-vector. J. Combin. Theory Ser. A **103**, no 1 (2003), 27–52.

[16] J. Jonsson and V. Welker. Complexes of Injective Words and Their Commutation Classes. Pacific J. Math. **243**, no 2 (2009), 313 – 329.

[17] M. Kallipoliti. The absolute order on the hyperoctahedral group. J. Alg. Comb. (2010), to appear.

[18] M. Kallipoliti and M. Kubitzke. New poset fiber theorems and their applications to non-crossing partitions and injective words. arXiv:1101.5770. Preprint.

[19] D. Quillen. Homotopy properties of the poset of non-trivial $p$-subgroups of a group, Adv. Math. **28** (1978), 101–128.

[20] V. Reiner and P. Webb. The Combinatorics of the Bar Resolution in Group Cohomology. J. Pure Appl. Algebra **190** (2004), 291 – 327.

[21] R. P. Stanley. Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA (1986); second printing, Cambridge Studies in Advanced Mathematics **49**, Cambridge University Press, Cambridge (1997).

[22] M. Wachs, *Poset Topology: Tools and Applications*, in *Geometric Combinatorics* (E. Miller, V. Reiner and B. Sturmfels, eds.). IAS/Park City Mathematics Series **13**, 497–615, Amer. Math. Society, Providence, RI, 2007.

[23] V. Welker. On the Cohen-Macaulay connectivity of supersolvable lattices and the homotopy type of posets. European J. Combin. **16**, no 4 (1995), 415 – 426.

[24] V. Welker, G. M. Ziegler and R. T. Živaljević. Homotopy colimits – comparison lemmas for combinatorial applications. J. reine angew. Math. **509** (1999), 117 – 149.