# On the Topology of the Cambrian Semilattices (Extended Abstract)

Myrto Kallipoliti and Henri Mühle†

Fak. für Mathematik, Universität Wien, Garnisongasse 3, 1090 Vienna, Austria

**Abstract.** For an arbitrary Coxeter group $W$, David Speyer and Nathan Reading defined Cambrian semilattices $C_\gamma$ as certain sub-semilattices of the weak order on $W$. In this article, we define an edge-labeling using the realization of Cambrian semilattices in terms of $\gamma$-KH elements, and show that this is an EL-labeling for every closed interval of $C_\gamma$. In addition, we use our labeling to show that every finite open interval in a Cambrian semilattice is either contractible or spherical, and we characterize the spherical intervals, generalizing a result by Nathan Reading.

**Résumé.** Pour tout groupe de Coxeter $W$, David Speyer et Nathan Reading ont défini les demi-treillis Cambriens comme certains sous-demi-treillis de l'ordre faible sur $W$. Dans cet article, nous définissons un étiquetage des arêtes basé sur la réalisation des demi-treillis Cambriens en termes d'éléments $\gamma$-triables, et prouvons que c'est un étiquetage EL pour tout intervalle fermé de $C_\gamma$. Nous utilisons de plus cet étiquetage pour montrer que tout intervalle ouvert fini dans un demi-treillis Cambrien est soit contractible soit sphérique, et nous caractérisons les intervalles sphériques, généralisant ainsi un résultat de Nathan Reading.

**Keywords:** Coxeter Groups, Weak Order, Cambrian Semilattices, EL-Shellability

## 1 Introduction

In [6, Theorem 9.6] Anders Björner and Michelle Wachs showed that the Tamari lattice $T_n$, introduced in [17], can be regarded as the subposet of the weak-order lattice on the symmetric group $S_n$, consisting of 312-avoiding permutations. More precisely, there exists a lattice homomorphism $\sigma : S_n \to T_n$ such that $T_n$ is isomorphic to the subposet of the weak-order lattice on $S_n$ consisting of the bottom elements in the fibers of $\sigma$. In [13], the map $\sigma$ was realized as a map from $S_n$ to the triangulations of an $(n+2)$-gon, where the partial order on the latter is given by diagonal flips. It was shown that the fibers of $\sigma$ induce a congruence relation on the weak-order lattice on $S_n$, and that the Tamari lattice is isomorphic to the lattice quotient induced by this congruence. Moreover, it was observed that different embeddings of the $(n+2)$-gon in the plane yield different lattice quotients of the weak-order lattice on $S_n$. The realization of $S_n$ as the Coxeter group $A_{n-1}$ was then used to connect the embedding of the $(n+2)$-gon in the plane with a Coxeter element of $A_{n-1}$. This connection eventually led to the definition of Cambrian

<footnote>†Email: {myrto.kallipoliti,henri.muehle}@univie.ac.at. The authors were supported by the FWF research grant no. Z130-N13.</footnote>
lattices, which can analogously be defined for an arbitrary finite Coxeter group $W$ as lattice quotients of the weak-order lattice on $W$ with respect to certain lattice congruences induced by orientations of the Coxeter diagram of $W$, see [14].

In [15], Nathan Reading and David Speyer generalized the idea of Cambrian lattices to infinite Coxeter groups. Since there exists no longest element in an infinite Coxeter group, the weak order constitutes only a (meet)-semilattice. Using the realization of the Cambrian lattices in terms of Coxeter-sortable elements, which was first described in [14] and later extended in [15], the analogous construction as in the finite case yields a quotient semilattice of the weak-order semilattice, the so-called *Cambrian semilattice*.

This article is dedicated to the investigation of the topological properties of the order complex of the proper part of closed intervals in a Cambrian semilattice. One (order-theoretic) tool to investigate these properties is EL-shellability, which was introduced in [1], and further developed in [4, 5, 6]. The fact that a poset is EL-shellable implies a number of properties of the associated order complex: this order complex is Cohen-Macaulay, it is homotopy equivalent to a wedge of spheres and the dimensions of its homology groups can be computed from the labeling. The main results of the present article are the following.

**Theorem 1.1** Every closed interval in $C_\gamma$ is EL-shellable for every (possibly infinite) Coxeter group $W$ and every Coxeter element $\gamma \in W$.

We prove this result uniformly using the realization of $C_\gamma$ in terms of Coxeter-sortable elements, and thus our proof does not require $W$ to be finite or even crystallographic. For finite crystallographic Coxeter groups, Theorem 1.1 is implied by [9, Theorem 4.17]. Colin Ingalls and Hugh Thomas considered in [9] the category of finite dimensional representations of an orientation of the Coxeter diagram of a finite crystallographic Coxeter group $W$. However, their approach cannot be applied to non-crystallographic or to infinite Coxeter groups. Recently, Vincent Pilaud and Christian Stump gave a proof of Theorem 1.1 for finite Coxeter groups, by investigating increasing flip posets of certain subword complexes, see [11].

Finally, using the fact that every closed interval of $C_\gamma$ is EL-shellable, we are able to determine the homotopy type of the proper parts of these intervals by counting the number of falling chains with respect to our labeling. It turns out that every open interval is either contractible or spherical, i.e. homotopy equivalent to a sphere. We can further characterize which intervals of $C_\gamma$ are contractible and which are spherical, as our second main result shows. Recall that a closed interval $[x, y]$ in a lattice is called *nuclear* if $y$ is the join of atoms of $[x, y]$.

**Theorem 1.2** Let $W$ be a (possibly infinite) Coxeter group and let $\gamma \in W$ be a Coxeter element. Every finite open interval in the Cambrian semilattice $C_\gamma$ is either contractible or spherical. Furthermore, a finite open interval $(x, y)_\gamma$ is spherical if and only if the corresponding closed interval $[x, y]_\gamma$ is nuclear.

For finite Coxeter groups, Theorem 1.2 is implied by concatenating [12, Theorem 1.1] and [12, Propositions 5.6 and 5.7]. Nathan Reading's approach in the cited article was to investigate fan posets of central hyperplane arrangements. He then showed that for a finite Coxeter group $W$ the Cambrian lattices can be viewed as fan posets of a fan induced by certain regions of the Coxeter arrangement of $W$ which are determined by orientations of the Coxeter diagram of $W$. The tools Nathan Reading developed in [12] apply to a much larger class of fan posets, but cannot be applied directly to infinite Coxeter groups.

The proofs of Theorems 1.1 and 1.2 are obtained completely within the framework of Coxeter-sortable elements and thus have the advantage that they are uniform and direct.

This article is organized as follows. In Section 2, we recall the necessary order-theoretic concepts, as well as the definition of EL-shellability. Furthermore, we recall the definition of Coxeter groups, and the
construction of the Cambrian semilattices. In Section 3, we define a labeling of the Hasse diagram of a Cambrian semilattice and give a case-free proof that this labeling is indeed an EL-labeling for every closed interval of this semilattice, thus proving Theorem 1.1. In Section 4, we prove Theorem 1.2, by counting the falling maximal chains with respect to our labeling and by applying [5, Theorem 5.9] which relates the number of falling maximal chains in a poset to the homotopy type of the corresponding order complex. The characterization of the spherical intervals of $C_γ$ follows from Theorem 4.3.

The present article is an extended abstract of [10], and we have thus omitted most of the proofs and some illustrating examples. They can be found at the corresponding places in the original article.

# 2 Preliminaries

In this section, we recall the necessary definitions, which are used throughout the article. For further background on posets, we refer to [7] or to [16] where in addition some background on lattices and lattice congruences is provided. An introduction to poset topology can be found in either [2] or [18]. For more background on Coxeter groups, we refer to [3] and [8].

## 2.1 Posets and EL-Shellability

Let $(P, \le_P)$ be a finite partially ordered set (poset for short). We say that $P$ is *bounded* if it has a unique minimal and a unique maximal element, which we usually denote by $\hat{0}$ and $\hat{1}$, respectively. For $x, y \in P$, we say that $y$ covers $x$ (and write $x \le_P y$) if $x \le_P y$ and there is no $z \in P$ such that $x <_P z <_P y$. We denote the set of all covering relations of $P$ by $\mathcal{E}(P)$. For $x, y \in P$ with $x \le_P y$, we define the closed interval $[x, y]$ to be the set $\{z \in P \mid x \le_P z \le_P y\}$. Similarly, we define the open interval $(x, y) = \{z \in P \mid x <_P z <_P y\}$. A chain $c : x = p_0 \le_P p_1 \le_P \cdots \le_P p_s = y$ is called maximal if $(p_i, p_{i+1}) \in \mathcal{E}(P)$ for every $0 \le i \le s-1$. Let $(P, \le_P)$ be a bounded poset and let $c : \hat{0} = p_0 \le_P p_1 \le_P \cdots \le_P p_s = \hat{1}$ be a maximal chain of $P$. Given another poset $(\Lambda, \le_\Lambda)$, a map $\lambda : \mathcal{E}(P) \to \Lambda$ is called edge-labeling of $P$. We denote the sequence $(\lambda(p_0, p_1), \lambda(p_1, p_2), \dots, \lambda(p_{s-1}, p_s))$ of edge-labels of $c$ by $\lambda(c)$. The chain $c$ is called rising (respectively falling) if $\lambda(c)$ is a strictly increasing (respectively weakly decreasing) sequence. For two words $(p_1, p_2, \dots, p_s)$ and $(q_1, q_2, \dots, q_t)$ in the alphabet $\Lambda$, we write $(p_1, p_2, \dots, p_s) \le_\Lambda^*(q_1, q_2, \dots, q_t)$ if and only if either

$$ 
\begin{array}{ll}
p_i = q_i, & \text{for } 1 \le i \le s \text{ and } s \le t, \text{ or} \\
p_i <_\Lambda q_i, & \text{for the least } i \text{ such that } p_i \ne q_i.
\end{array}
$$

A maximal chain $c$ of $P$ is called *lexicographically first* among all maximal chains of $P$ if for every other maximal chain $c'$ of $P$ we have $\lambda(c) \le_\Lambda^* \lambda(c')$. An edge-labeling of $P$ is called *EL-labeling* if for every closed interval $[x, y]$ in $P$ there exists a unique rising maximal chain which is lexicographically first among all maximal chains in $[x, y]$. A bounded poset that admits an EL-labeling is called *EL-shellable*. Finally, we recall that the Möbius function $\mu$ of $P$ is the map $\mu : P \times P \to \mathbb{Z}$ defined recursively by

$$ \mu(x, y) = \begin{cases} 1, & x = y \\ -\sum_{x \le_P z <_P y} \mu(x, z), & x <_P y \\ 0, & \text{otherwise.} \end{cases} $$
A remarkable property of EL-shellable posets is that we can compute the value of the Möbius function for every closed interval of P from the labeling, as is stated in the following proposition$^{(i)}$.

**Proposition 2.1 ([5, Proposition 5.7])** Let $(P, \le_P)$ be an EL-shellable poset, and let $x, y \in P$ with $x \le_P y$. Then,

$$ \mu(x, y) = \text{number of even length falling maximal chains in } [x, y] $$

– number of odd length falling maximal chains in $[x, y]$.

## 2.2 Coxeter Groups and Weak Order

Let $W$ be a (possibly infinite) group, which is generated by the finite set $S = \{s_1, s_2, \dots, s_n\}$. Let $m = (m_{i,j})_{1 \le i,j \le n}$ be a symmetric $(n \times n)$-matrix, where the entries are either positive integers or the formal symbol $\infty$, and which satisfies $m_{i,i} = 1$ for all $1 \le i \le n$, and $m_{i,j} \ge 2$ otherwise. (We use the convention that $\infty$ is formally larger than any natural number.) We call $W$ a Coxeter group if it has the presentation

$$ W = \langle S \mid (s_i s_j)^{m_{i,j}} = \varepsilon, \text{ for } 1 \le i, j \le n \rangle, $$

where $\varepsilon \in W$ denotes the identity. We interpret the case $m_{i,j} = \infty$ as stating that there is no relation between the generators $s_i$ and $s_j$, and we call the matrix $m$ the Coxeter matrix of $W$. The Coxeter diagram of $W$ is the graph $G = (V, E)$, with $V = S$ and $E = \{\{s_i, s_j\} \mid m_{i,j} \ge 3\}$. In addition, an edge $\{s_i, s_j\}$ of $G$ is labeled by the value $m_{i,j}$ if and only if $m_{i,j} \ge 4$.

Since $S$ is a generating set of $W$, we can write every element $w \in W$ as a product of the elements in $S$, and we call such a word a reduced word for $w$ if it has minimal length. More precisely, define the word length on $W$ (with respect to $S$) as

$$ \ell_S : W \to \mathbb{N}, \quad w \mapsto \min\{k \mid w = s_{i_1}s_{i_2}\cdots s_{i_k} \text{ and } s_{i_j} \in S \text{ for all } 1 \le j \le k\}. $$

If $\ell_S(w) = k$, then every product of $k$ generators which yields $w$ is a reduced word for $w$. Define the (right) weak order of $W$ by

$$ u \le_S v \quad \text{if and only if} \quad \ell_S(v) = \ell_S(u) + \ell_S(u^{-1}v). $$

The poset $(W, \le_S)$ is a graded meet-semilattice, the so-called weak-order semilattice of $W$, and $\ell_S$ is its rank function. Further, $(W, \le_S)$ is finitary meaning that every closed interval of $(W, \le_S)$ is finite. In the case where the group $W$ is finite, there exists a unique longest word $w_o$ of $W$, and $(W, \le_S)$ is a lattice.

## 2.3 Coxeter-Sortable Words

Let $\gamma = s_1s_2\cdots s_n \in W$ be a Coxeter element, and define the half-infinite word

$$ \gamma^{\infty} = s_1s_2\cdots s_n|s_1s_2\cdots s_n|\cdots. $$

The vertical bars in the representation of $\gamma^{\infty}$ are “dividers”, which have no influence on the structure of the word, but shall serve for a better readability. Clearly, every reduced word for $w \in W$ can be considered as a subword of $\gamma^{\infty}$. Among all reduced words for $w$, there is a unique reduced word, which is lexicographically first as a subword of $\gamma^{\infty}$. This reduced word is called the $\gamma$-sorting word of $w$.

<footnote>(i) Actually, Proposition 5.7 in [5] is stated for posets admitting a so-called CR-labeling. EL-shellable posets are a particular instance of this class of posets, and for the scope of this article it is sufficient to restrict our attention to these.</footnote>
**Example 2.2** Consider the Coxeter group $W = \mathfrak{S}_5$, generated by $S = \{s_1, s_2, s_3, s_4\}$, where $s_i$ corresponds to the transposition $(i, i+1)$ for all $i \in \{1, 2, 3, 4\}$ and let $\gamma = s_1s_2s_3s_4$. Clearly, $s_1$ and $s_4$ commute. Hence, $w_1 = s_1s_2|s_1s_4$ and $w_2 = s_1s_2s_4|s_1$ are reduced words for the same element $w \in W$. Considering $w_1$ and $w_2$ as subwords of $\gamma^\infty$, we find that $w_2$ is a lexicographically smaller subword of $\gamma^\infty$ than $w_1$ is. There are six other reduced words for $w$, namely

$$w_3 = s_1s_4|s_2|s_1,$$

$$w_4 = s_4|s_1s_2|s_1,$$

$$w_5 = s_4|s_2|s_1s_2,$$

$$w_6 = s_2s_4|s_1s_2,$$

$$w_7 = s_2|s_1s_4|s_2,$$

$$w_8 = s_2|s_1s_2s_4.$$

It is easy to see that among these $w_2$ is the lexicographically first subword of $\gamma^\infty$, and hence $w_2$ is the $\gamma$-sorting word of $w$.

In the following, we consider only $\gamma$-sorting words, and write

$$w = s_1^{\delta_{1,1}} s_2^{\delta_{1,2}} \dots s_n^{\delta_{1,n}} | s_1^{\delta_{2,1}} s_2^{\delta_{2,2}} \dots s_n^{\delta_{2,n}} | \dots | s_1^{\delta_{l,1}} s_2^{\delta_{l,2}} \dots s_n^{\delta_{l,n}}, \quad (1)$$

where $\delta_{i,j} \in \{0, 1\}$ for $1 \le i \le l$ and $1 \le j \le n$. For each $i \in \{1, 2, \dots, l\}$, we say that

$$b_i = \{s_j \mid \delta_{i,j} = 1\} \subseteq S$$

is the $i$-th block of $w$. We consider the blocks of $w$ sometimes as sets and sometimes as subwords of $\gamma$, depending on how much structure we need. We say that $w$ is $\gamma$-GRAVELING if and only if $b_1 \supseteq b_2 \supseteq \dots \supseteq b_l$. In the previous example, we have seen that $w_2 = s_1s_2s_4|s_1$ is a $\gamma$-sorting word in $W$ with $b_1 = \{s_1, s_2, s_4\}$ and $b_2 = \{s_1\}$. Since $b_2 \subseteq b_1$, we see that $w_2$ is indeed $\gamma$-GRAVELING.

By definition, the set of $\gamma$-GRAVELING words of $W$ does not depend on the choice of the reduced word for $\gamma$. Furthermore, the $\gamma$-GRAVELING words of $W$ are characterized by a recursive property which we will describe next. A generator $s \in S$ is called initial in $\gamma$ if it is the first letter in some reduced word for $\gamma$. For some subset $J \subseteq S$, we denote by $W_J$ the parabolic subgroup of $W$ generated by the set $J$, and for $s \in S$ we abbreviate $\langle s \rangle = S \setminus \{s\}$. For $w \in W$, and $J \subseteq S$, we denote by $w_J$ the restriction of $w$ to the parabolic subgroup $W_J$.

**Proposition 2.3 ([15, Proposition 2.29])** Let $W$ be a Coxeter group, $\gamma$ a Coxeter element and let $s$ be initial in $\gamma$. Then an element $w \in W$ is $\gamma$-GRAVELING if and only if

(i) $s \le_S w$ and $sw$ is $s\gamma s$-GRAVELING, or

(ii) $s \not\le_S w$ and $w$ is an $s\gamma$-GRAVELING word of $W_{\langle s \rangle}$.

## 2.4 Cambrian Semilattices

In [15, Section 7] the *Cambrian semilattice* $C_\gamma$ was defined as the sub-semilattice of the weak order on $W$ consisting of all $\gamma$-GRAVELING elements. That $C_\gamma$ is well-defined follows from [15, Theorem 7.1]. It turns out that $C_\gamma$ is not only a sub-semilattice of the weak order, but also a quotient semilattice. The key role in the proof of this property is played by the projection $\pi_\downarrow^\gamma$ which maps every word $w \in W$ to the unique largest $\gamma$-GRAVELING element below $w$. More precisely if $s$ is initial in $\gamma$, then define

$$\pi_\downarrow^\gamma(w) = \begin{cases} s\pi_\downarrow^{s\gamma s}(sw), & \text{if } s \le_S w \\ \pi_\downarrow^{s\gamma}(w_{\langle s \rangle}), & \text{if } s \not\le_S w, \end{cases} \quad (2)$$
and set $\pi_{\downarrow}^{\gamma}(\varepsilon) = \varepsilon$, see [15, Section 6].

Theorem 7.3 in [15] implies that $\pi_{\downarrow}^{\gamma}$ is a semilattice homomorphism from the weak-order semilattice on $W$ to $C_{\gamma}$, and $C_{\gamma}$ can be considered as the quotient semilattice of the weak order modulo the semilattice congruence $\theta_{\gamma}$ induced by the fibers of $\pi_{\downarrow}^{\gamma}$. This semilattice congruence is called *Cambrian congruence*. Since the lack of a maximal element is the only obstruction for the weak order to be a lattice, it follows immediately that the restriction of $\pi_{\downarrow}^{\gamma}$ (and hence $\theta_{\gamma}$) to closed intervals of the weak order yields a lattice homomorphism (and hence a lattice congruence).

In the remainder of this article, we switch frequently between the weak-order semilattice on $W$ and the Cambrian semilattice $C_{\gamma}$. In order to point out properly which semilattice we consider, we denote the order relation of the weak-order semilattice by $\leq_S$, and the order relation of $C_{\gamma}$ by $\leq_{\gamma}$. Analogously, we denote a closed (respectively open) interval in the weak-order semilattice by $[u, v]_S$ (respectively $(u, v)_S$), and a closed (respectively open) interval in $C_{\gamma}$ by $[u, v]_{\gamma}$ (respectively $(u, v)_{\gamma}$).

# 3 EL-Shellability of the Closed Intervals in $C_{\gamma}$

In this section, we define an edge-labeling of $C_{\gamma}$, discuss some of its properties and eventually prove Theorem 1.1.

## 3.1 The Labeling

Define for every $w \in W$ the set of positions of the $\gamma$-sorting word of $w$ as

$$ \alpha_{\gamma}(w) = \{(i-1) \cdot n + j \mid \delta_{i,j} = 1\} \subseteq \mathbb{N}, $$

where the $\delta_{i,j}$'s are the exponents from (1). We remark that the set of positions of $w$ depends not only on the choice of the Coxeter element $\gamma$, but also on the choice of the reduced word of $\gamma$.

**Example 3.1** Let $W = \mathfrak{S}_4$, $\gamma = s_1s_2s_3$ and consider $u = s_1s_2s_3|s_2$, and $v = s_2s_3|s_2|s_1$. Then, $\alpha_{\gamma}(u) = \{1, 2, 3, 5\}$, and $\alpha_{\gamma}(v) = \{2, 3, 5, 7\}$, where $u \in C_{\gamma}$, while $v \notin C_{\gamma}$.

It is not hard to see that an element $w \in W$ lies in $C_{\gamma}$ if and only if the following holds: if $i \in \alpha_{\gamma}(w)$ and $i > n$, then $i - n \in \alpha_{\gamma}(w)$. In the previous example, we see that $\alpha_{\gamma}(u)$ contains both 5 and 2, while $\alpha_{\gamma}(v)$ does not contain $7 - 3 = 4$.

**Lemma 3.2** Let $u, v \in W$ with $u \leq_S v$. Then $\alpha_{\gamma}(u)$ is a subset of $\alpha_{\gamma}(v)$.

Denote by $\mathcal{E}(C_{\gamma})$ the set of covering relations of $C_{\gamma}$, and define an edge-labeling of $C_{\gamma}$ by

$$ \lambda_{\gamma}: \mathcal{E}(C_{\gamma}) \to \mathbb{N}, \quad (u, v) \mapsto \min\{i \mid i \in \alpha_{\gamma}(v) \setminus \alpha_{\gamma}(u)\}. \quad (3) $$

Figure 1 shows the Hasse diagram of a Cambrian lattice $C_{\gamma}$ of the Coxeter group $A_3$, together with the labels defined by the map $\lambda_{\gamma}$.

## 3.2 Properties of the Labeling

We notice that the definition of $\lambda_{\gamma}$ depends on a specific reduced word for $\gamma$. The following lemma shows that the structural properties of $\lambda_{\gamma}$ are independent of the choice of reduced word for $\gamma$.

**Lemma 3.3** Let $\gamma \in W$ be a Coxeter element, and let $u, v \in C_{\gamma}$ with $u \leq_{\gamma} v$. The number of maximal falling and rising chains in $[u, v]_{\gamma}$ does not depend on the choice of a reduced word for $\gamma$.
<figure><img src="image_1.png" /><figcaption>Fig. 1: An A_3-Cambrian lattice with the labeling as defined in (3).</figcaption></figure>

Whenever we use an initial letter $s$ of $\gamma$ in the remainder of this article, we consider $\lambda_{\gamma}$ with respect to a fixed reduced word for $\gamma$ which has $s$ as its first letter. The previous lemma implies that this can be done without loss of generality.

**Lemma 3.4** Let $C_{\gamma}$ be a Cambrian semilattice, and let $u, v \in C_{\gamma}$ such that $u \leq_{\gamma} v$. Let $i_0 = \min\{i \mid i \in \alpha_{\gamma}(v) \setminus \alpha_{\gamma}(u)\}$. Then the following hold.

(i) The label $i_0$ appears in every maximal chain of the interval $[u, v]_{\gamma}$.

(ii) The labels of a maximal chain in $[u, v]_{\gamma}$ are distinct.

The $\gamma$-sorted words of $W$ are defined recursively as described in Proposition 2.3. Thus we need to investigate how our labeling behaves with respect to this recursion.

**Lemma 3.5** Let $W$ be a Coxeter group and let $\gamma \in W$ be a Coxeter element. For $u, v \in C_{\gamma}$ with $u \leq_{\gamma} v$ and for $s \in S$ initial in $\gamma$, we have

$$ \lambda_{\gamma}(u, v) = \begin{cases} 1, & \text{if } s \not\leq_{S} u \text{ and } s \leq_{S} v, \\ \lambda_{s\gamma s}(su, sv) + 1, & \text{if } s \leq_{S} u, \\ \lambda_{s\gamma}(u_{\langle s \rangle}, v_{\langle s \rangle}) + k, & \text{if } s \not\leq_{S} v \text{ and the first position where } u \text{ and } v \\ & \text{differ is in their } k\text{-th block.} \end{cases} $$
### 3.3 Proof of Theorem 1.1

We will prove Theorem 1.1 by showing that the map $\lambda_\gamma$ defined in (3) is an EL-labeling for every closed interval in $C_\gamma$. In particular we show the following.

**Theorem 3.6** Let $u, v \in C_\gamma$ with $u \leq_\gamma v$. Then the map $\lambda_\gamma$ defined in (3) is an EL-labeling for $[u, v]_\gamma$.

We notice in view of Lemma 3.3 that the statement of Theorem 3.6 does not depend on a reduced word for $\gamma$, even though our labeling does. For the proof of Theorem 3.6, we need one more technical lemma. This lemma uses many of the deep results on Cambrian semilattices developed in [15], and requires the following alternative characterization of the (right) weak order on $W$. Let $T = \{wsw^{-1} | w \in W, s \in S\}$, and define for $w \in W$, the (left) inversion set of $w$ as $\text{inv}(w) = \{t \in T | \ell_S(tw) \leq \ell_S(w)\}$. It is the statement of [3, Proposition 3.1.3] that $u \leq_S v$ if and only if $\text{inv}(u) \subseteq \text{inv}(v)$. Moreover, for $w \in W$, we say that $t \in \text{inv}(w)$ is called a cover reflection of $w$ if there exists some $s \in S$ with $tw = ws$. We denote by $\text{cov}(w)$ the set of all cover reflections of $w$.

**Lemma 3.7** Let $u, v \in C_\gamma$ with $u \leq_\gamma v$ and let $s$ be initial in $\gamma$. If $s \not\leq_\gamma u$ and $s \leq_\gamma v$, then the join $s \vee_\gamma u$ covers $u$ in $C_\gamma$.

**Proof:** First of all, since $s \leq_\gamma v$ and $u \leq_\gamma v$, we conclude from [15, Theorem 7.1] that $s \vee_\gamma u$ exists, and set $z = s \vee_\gamma u$. By assumption, we have $u = \pi_\downarrow^{s\gamma}(u_{\langle s \rangle}) \in W_{\langle s \rangle}$, and Proposition 2.3 implies $u = u_{\langle s \rangle}$. We deduce then from [15, Lemma 2.23] that $\text{cov}(z) = \{s\} \cup \text{cov}(u)$. Therefore $s$ is a cover reflection of $z$, and it follows from [15, Proposition 5.4 (i)] that $z = s \vee_\gamma z_{\langle s \rangle}$, and [15, Proposition 5.4 (ii)] implies that $\text{cov}(z) = \{s\} \cup \text{cov}(z_{\langle s \rangle})$. Hence, $\text{cov}(u) = \text{cov}(z_{\langle s \rangle})$, and [15, Theorem 8.9 (iv)] implies $u = z_{\langle s \rangle}$. (The required fact that $z_{\langle s \rangle}$ is $\gamma$-PHA follows from [15, Propositions 3.13 and 6.10].)

On the other hand, it follows from the definition of a cover reflection that there exists an element $z' = sz \in W$ with $z' \leq_S z$, thus $z'_{\langle s \rangle} \leq_S z_{\langle s \rangle}$, see [15, Section 2.5]. Furthermore we have that $\text{inv}(z') = \text{inv}(z) \setminus \{s\}$, and since $\text{inv}(s) = \{s\}$, Proposition 3.1.3 in [3] implies $s \not\leq_S z'$. Hence, by definition of $\pi_\downarrow^\gamma$, see (2), we have $\pi_\downarrow^\gamma(z') = \pi_\downarrow^{s\gamma}(z'_{\langle s \rangle}) \in W_{\langle s \rangle}$, and $\pi_\downarrow^\gamma(z') \leq_\gamma z$. Since $\pi_\downarrow^{s\gamma}$ is order-preserving, see [15, Theorem 6.1], we conclude from $z'_{\langle s \rangle} \leq_S z_{\langle s \rangle}$ that $\pi_\downarrow^{s\gamma}(z'_{\langle s \rangle}) \leq_S \pi_\downarrow^{s\gamma}(z_{\langle s \rangle})$. Hence,

$$ \pi_\downarrow^\gamma(z') = \pi_\downarrow^{s\gamma}(z'_{\langle s \rangle}) \leq_S \pi_\downarrow^{s\gamma}(z_{\langle s \rangle}) = \pi_\downarrow^{s\gamma}(u) = \pi_\downarrow^{s\gamma}(u_{\langle s \rangle}) = \pi_\downarrow^\gamma(u) = u. $$

Since $\pi_\downarrow^\gamma(z') \leq_\gamma z$ and $u <_\gamma z$, the previous implies $u = \pi_\downarrow^\gamma(z')$ and thus $u \leq_\gamma z$. $\square$

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

**Proof of Theorem 3.6:** Let $[u, v]_\gamma$ be a closed interval of $C_\gamma$. Since the weak order on $W$ is finitary, it follows that $[u, v]_\gamma$ is a finite lattice. We show that there exists a unique maximal rising chain in $[u, v]_\gamma$ which is the lexicographically first among all maximal chains in this interval.

We proceed by induction on length and rank, using the recursive structure of $\gamma$-PHA words, see Proposition 2.3. We assume that $\ell_S(v) \geq 3$, and that $W$ is a Coxeter group of rank $\geq 2$, since the result is trivial otherwise. Say that $W$ is of rank $n$, and say that $\ell_S(v) = k$. Suppose that the induction hypothesis is true for all parabolic subgroups of $W$ of rank $< n$ and suppose that for every closed interval $[u', v']_\gamma$ of $C_\gamma$ with $\ell_S(v') < k$, there exists a unique rising maximal chain from $u'$ to $v'$ which is lexicographically first among all maximal chains in $[u', v']_\gamma$. We show that there is a unique rising maximal chain in the interval $[u, v]_\gamma$ which is lexicographically first among all maximal chains in $[u, v]_\gamma$. For $s$ initial in $\gamma$, we distinguish two cases: (1) $s \leq_\gamma v$ and (2) $s \not\leq_\gamma v$.
(1a) Suppose first that $s \leq_{\gamma} u$ as well. Then, $s$ is the first letter in the $\gamma$-sorting word of every element in $[u, v]_{\gamma}$. It follows from [15, Proposition 2.18] and Proposition 2.3 that the interval $[u, v]_{\gamma}$ is isomorphic to the interval $[su, sv]_{s\gamma s}$. Moreover, Lemma 3.5 implies that for a covering relation $x \prec_{\gamma} y$ in $[u, v]_{\gamma}$ we have $\lambda_{\gamma}(x, y) = \lambda_{s\gamma s}(sx, sy) + 1$. Say that $c' : su = sx_0 \prec_{s\gamma s} sx_1 \prec_{s\gamma s} \cdots \prec_{s\gamma s} sx_t = sv$ is the unique rising maximal chain in $[su, sv]_{s\gamma s}$. (This chain exists by induction, since $\ell_S(sv) < \ell_S(v)$.) Then, the chain $c : u = x_0 \prec_{\gamma} x_1 \prec_{\gamma} \cdots \prec_{\gamma} x_t = v$ is a maximal chain in $[u, v]_{\gamma}$ and clearly rising. With Lemma 3.5, we find that $c$ is the unique rising chain and every other maximal chain in $[u, v]_{\gamma}$ is lexicographically larger than $c$.

(1b) Suppose now that $s \not\leq_{\gamma} u$. Since $s \leq_{\gamma} v$ and $u \leq_{\gamma} v$ the join $u_1 = s \lor_{\gamma} u$ exists and lies in $[u, v]_{\gamma}$. Lemma 3.7 implies that $u \prec_{\gamma} u_1$. Consider the interval $[u_1, v]_{\gamma}$. Then $s \leq_{\gamma} u_1$ and analogously to (1a) we can find a unique maximal rising chain $c' : u_1 \prec_{\gamma} u_2 \prec_{\gamma} \cdots \prec_{\gamma} u_t = v$ in $[u_1, v]_{\gamma}$ which is lexicographically first. Moreover, $\min\{i \mid i \in \alpha_{\gamma}(v) \setminus \alpha_{\gamma}(u_1)\} > 1$, since $s \leq_{\gamma} u_1 \leq_{\gamma} v$. By definition of our labeling, the label 1 cannot appear as a label in any chain in the interval $[u_1, v]_{\gamma}$. On the other hand, it follows from Lemma 3.5 that $\lambda_{\gamma}(u, u_1) = 1$. Thus, the chain $c : u \prec_{\gamma} u_1 \prec_{\gamma} u_2 \prec_{\gamma} \cdots \prec_{\gamma} u_t = v$ is maximal and rising in $[u, v]_{\gamma}$. Suppose that there is another element $u'$ that covers $u$ in $[u, v]_{\gamma}$ such that $\lambda_{\gamma}(u, u') = 1$. Then, by definition of $\lambda_{\gamma}$, it follows that $s$ appears in the $\gamma$-sorting word of $u'$. In particular, since $s$ is initial in $\gamma$, we deduce that $s \leq_{\gamma} u'$. Therefore $u'$ is above both $s$ and $u$ in $C_{\gamma}$. By the uniqueness of joins and the definition of $u_1$ it follows that $u_1 = u'$. Thus $c$ is the lexicographically smallest maximal chain in $[u, v]_{\gamma}$. Finally, Lemma 3.4 implies that $c$ is the unique maximal rising chain.

(2) Since $s \not\leq_{\gamma} v$, it follows that no element of $[u, v]_{\gamma}$ contains the letter $s$ in its $\gamma$-sorting word. We consider the parabolic Coxeter group $W_{\langle s \rangle}$ (generated by $S \setminus \{s\}$) and the Coxeter element $s\gamma$. It follows from Proposition 2.3 that the interval $[u, v]_{\gamma}$ is isomorphic to the interval $[u_{\langle s \rangle}, v_{\langle s \rangle}]_{s\gamma}$ in $W_{\langle s \rangle}$. Since the rank of $W_{\langle s \rangle}$ is $n-1 < n$, by induction there exists a unique maximal rising chain $c' : u_{\langle s \rangle} = (x_0)_{\langle s \rangle} \prec_{s\gamma} (x_1)_{\langle s \rangle} \prec_{s\gamma} \cdots \prec_{s\gamma} (x_t)_{\langle s \rangle} = v_{\langle s \rangle}$ which is lexicographically first among all maximal chains in $[u_{\langle s \rangle}, v_{\langle s \rangle}]_{s\gamma}$. The result then follows with Lemma 3.5. $\square$

**Proof of Theorem 1.1:** This follows by definition from Theorem 3.6. $\square$

# 4 Applications

In [12], Nathan Reading investigated, among others, the topological properties of open intervals in so-called fan posets. A fan poset is a certain partial order defined on the maximal cones of a complete fan of regions of a real hyperplane arrangement. For a finite Coxeter group $W$ and a Cambrian congruence $\theta$, the Cambrian fan $F_{\theta}$ is the complete fan induced by certain cones in the Coxeter arrangement $A_W$ of $W$. More precisely, each such cone is a union of regions of $A_W$ which correspond to elements of $W$ lying in the same congruence class of $\theta$. It is the assertion of [12, Theorem 1.1], that a Cambrian lattice of $W$ is the fan poset associated to the corresponding Cambrian fan. The following theorem is a concatenation of [12, Theorem 1.1] and [12, Propositions 5.6 and 5.7]. In fact, Propositions 5.6 and 5.7 in [12] imply this result for a much larger class of fan posets.

**Theorem 4.1** Let $W$ be a finite Coxeter group and let $\gamma \in W$ be a Coxeter element. Every open interval in the Cambrian lattice $C_{\gamma}$ is either contractible or spherical.

It is well-known that the reduced Euler characteristics of the order complex of an open interval $(x, y)$ in a poset determines $\mu(x, y)$, see for instance [16, Proposition 3.8.6]. Hence, it follows immediately from
**Theorem 4.1** that for $\gamma$-sorted elements $x$ and $y$ in a finite Coxeter group $W$ satisfying $x \leq_{\gamma} y$, we have $|\mu(x, y)| \leq 1$, as was already remarked in [13, pp. 4-5]. In light of Proposition 2.1 and Theorem 3.6, we can extend this statement to compute the Möbius function of closed intervals in the Cambrian semilattice $C_{\gamma}$, by counting the falling maximal chains with respect to the labeling defined in (3).

**Theorem 4.2** Let $W$ be a (possibly infinite) Coxeter group and $\gamma \in W$ a Coxeter element. For $u, v \in C_{\gamma}$ with $u \leq_{\gamma} v$, we have $|\mu(u, v)| \leq 1$.

**Proof:** In view of Proposition 2.1 it is enough to show that the interval $[u, v]_{\gamma}$ has at most one maximal falling chain. We use similar arguments as in the proof of Theorem 3.6 and proceed by induction on length and rank. Again, for $s$ initial in $\gamma$, we distinguish the following two cases: $s \leq_{\gamma} v$ and $s \not\leq_{\gamma} v$. Here we discuss only the special case where $s \leq_{\gamma} v$ and $s \not\leq_{\gamma} u$. (The others follow by applying the same methods as in the proof of Theorem 3.6.) It follows from Lemma 3.4 that a maximal chain $u = c_0 \ll_{\gamma} c_1 \ll_{\gamma} \cdots \ll_{\gamma} c_{t-1} \ll c_t = v$ of $[u, v]_{\gamma}$ can be falling only if $\lambda_{\gamma}(c_{t-1}, v) = 1$. Hence, if there is no element $v_1 \in (u, v)_{\gamma}$, with $v_1 \ll v$ satisfying $\lambda_{\gamma}(v_1, v) = 1$, then the interval $[u, v]_{\gamma}$ has no maximal falling chain, which means that $\mu(u, v) = 0$. Otherwise, consider the interval $[u, v_1]_{\gamma}$. By the choice of $v_1$, it follows that every maximal falling chain in $[u, v_1]_{\gamma}$ can be extended to a maximal falling chain in the interval $[u, v]_{\gamma}$. Conversely, every maximal falling chain in $[u, v]_{\gamma}$ can be restricted to a maximal falling chain in $[u, v_1]_{\gamma}$. Therefore, since $\ell_{S}(v_1) < \ell_{S}(v)$, we deduce from the induction hypothesis that the interval $[u, v_1]_{\gamma}$ has at most one maximal falling chain. Thus $|\mu(u, v)| \leq 1$. $\square$

In addition Propositions 5.6 and 5.7 in [12] characterize the open intervals in a (finite) Cambrian lattice which are contractible, and those which are spherical in the following way: an interval $[u, v]_{\gamma}$ in $C_{\gamma}$ is called *nuclear* if the join of the upper covers of $u$ is precisely $v$. Nathan Reading showed that the nuclear intervals are precisely the spherical intervals. With the help of our labeling, we can generalize this characterization to infinite Coxeter groups.

**Theorem 4.3** Let $u, v \in C_{\gamma}$ with $u \leq_{\gamma} v$ and let $k$ denote the number of atoms of the interval $[u, v]_{\gamma}$. Then, $\mu(u, v) = (-1)^k$ if and only if $[u, v]_{\gamma}$ is nuclear.

For the proof of Theorem 4.3, we need the following lemma.

**Lemma 4.4** Let $u, v \in C_{\gamma}$ with $u \leq_{\gamma} v$, and let $s$ be initial in $\gamma$. Suppose further that $s \not\leq_{\gamma} u$, while $s \leq_{\gamma} v$. Then the following are equivalent:

1. The interval $[u, v]_{\gamma}$ is nuclear.

2. There exists an element $v' \in [u, v]_{\gamma}$ satisfying $s \not\leq_{\gamma} v'$, $v' \ll_{\gamma} v$, and the interval $[u, v']_{\gamma}$ is nuclear.

**Proof of Theorem 4.3:** In view of Proposition 2.1, we need to show that $[u, v]_{\gamma}$ has a falling chain if and only if $[u, v]_{\gamma}$ is nuclear. We use similar arguments as in the proof of Theorem 3.6 and proceed by induction on length and rank. For the inductive step we distinguish two cases: (1) $s \not\leq_{\gamma} v$ and (2) $s \leq_{\gamma} v$, where $s$ initial in $\gamma$. Here we discuss the special case where $s \not\leq_{\gamma} u$, while $s \leq_{\gamma} v$. If $[u, v]_{\gamma}$ is nuclear, the result follows by combining Lemmas 3.5,4.4, Theorem 4.2 and by applying induction on the rank of $W$. Conversely, suppose that there exists a maximal falling chain $c : u = x_0 \ll_{\gamma} x_1 \ll_{\gamma} \cdots \ll_{\gamma} x_t = v$ in $[u, v]_{\gamma}$, and let $A = \{w \in C_{\gamma} \mid w \ll_{\gamma} u$ and $w \leq_{\gamma} v\}$ denote the set of atoms of $[u, v]_{\gamma}$. It follows then that the chain $c' : u = x_0 \ll_{\gamma} x_1 \ll_{\gamma} \cdots \ll_{\gamma} x_{t-1}$ is falling, thus by induction we can conclude that
the interval $[u, x_{t-1}]_{\gamma}$ is nuclear. We deduce from Lemma 3.4 that $s \preceq_{\gamma} x_{t-1}$, and since $x_{t-1} \preceq_{\gamma} v$, it
follows from Lemma 4.4 that $[u, v]_{\gamma}$ is nuclear. This completes the proof of the theorem. $\square$

**Proof of Theorem 1.2:** It follows directly from Theorem 1.1, [5, Theorem 5.9] and Theorem 4.2. The characterization of the spherical intervals is an immediate consequence of Theorem 4.2. $\square$

We conclude this article with a short example of an infinite Coxeter group.

**Example 4.5** Consider the affine Coxeter group $\tilde{A}_2$, which is generated by the set $\{s_1, s_2, s_3\}$ satisfying
$(s_1s_2)^3 = (s_1s_3)^3 = (s_2s_3)^3 = \varepsilon$, as well as $s_1^2 = s_2^2 = s_3^2 = \varepsilon$. Consider the Coxeter element
$\gamma = s_1s_2s_3$. Figure 2 shows the sub-semilattice of the Cambrian semilattice $C_{\gamma}$ consisting of all $\gamma$-
sorted elements of $\tilde{A}_2$ of length $\le 7$. We encourage the reader to verify Theorem 3.6 and Theorem 4.2.

<figure><img src="image_3.png" /><figcaption>Fig. 2: The first seven ranks of an $\tilde{A}_2$-Cambrian semilattice, with the labeling as defined in (3).</figcaption></figure>

Acknowledgements

The authors would like to thank Nathan Reading for pointing out a weakness in a previous version of the
proof of Theorem 3.6 and for many helpful discussions on the topic.
References

[1] A. Björner. Shellable and Cohen-Macaulay Partially Ordered Sets. *Trans. Amer. Math. Soc.*, 260:159-183, 1980.

[2] A. Björner. Topological Methods. volume 2 of *Handbook of Combinatorics*, pages 1819–1872. MIT Press, Cambridge, MA, 1996.

[3] A. Björner and F. Brenti. *Combinatorics of Coxeter Groups*. Springer, New York, 2005.

[4] A. Björner and M. L. Wachs. On Lexicographically Shellable Posets. *Trans. Amer. Math. Soc.*, 277:323-341, 1983.

[5] A. Björner and M. L. Wachs. Shellable and Nonpure Complexes and Posets I. *Trans. Amer. Math. Soc.*, 348:1299-1327, 1996.

[6] A. Björner and M. L. Wachs. Shellable and Nonpure Complexes and Posets II. *Trans. Amer. Math. Soc.*, 349:3945-3975, 1997.

[7] B. A. Davey and H. A. Priestley. *Introduction to Lattices and Order*. Cambridge University Press, Cambridge, 2002.

[8] J. E. Humphreys. *Reflection Groups and Coxeter Groups*. Cambridge University Press, Cambridge, 1990.

[9] C. Ingalls and H. Thomas. Noncrossing Partitions and Representations of Quivers. *Composition Mathematica*, 145:1533-1562, 2009.

[10] M. Kallipoliti and H. Mühle. On the Topology of the Cambrian Semilattices. *arXiv:1206.6248*, 2012.

[11] V. Pilaud and C. Stump. EL-Labelings and Canonical Spanning Trees for Subword Complexes. *arXiv:1210.1435*, 2012.

[12] N. Reading. Lattice Congruences, Fans and Hopf Algebras. *J. Combin. Theory (Ser. A)*, 110:237-273, 2005.

[13] N. Reading. Cambrian Lattices. *Adv. Math.*, 205:313-353, 2006.

[14] N. Reading. Sortable Elements and Cambrian Lattices. *Alg. Universalis*, 56:411-437, 2007.

[15] N. Reading and D. E. Speyer. Sortable Elements in Infinite Coxeter Groups. *Trans. Amer. Math. Soc.*, 363:699-761, 2011.

[16] R. P. Stanley. *Enumerative Combinatorics, Vol. 1*. Cambridge University Press, Cambridge, 1997.

[17] D. Tamari. The Algebra of Bracketings and their Enumeration. *Nieuw Archief voor Wiskunde*, 10:131-146, 1962.

[18] M. L. Wachs. Poset Topology: Tools and Applications. In *Geometric Combinatorics*, volume 13 of *IAS/Park City Math. Ser.*, pages 497-615. American Mathematical Society, Providence, RI, 2007.