# An introduction to diagram groups

Anthony Genevois

► To cite this version:

Anthony Genevois. An introduction to diagram groups. Journal of Combinatorial Algebra, 2023, 9 (1), pp.31-119. 10.4171/JCA/81. hal-05067117

HAL Id: hal-05067117

https://hal.science/hal-05067117v1

Submitted on 14 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# An introduction to diagram groups

Anthony Genevois

**Abstract.** To every semigroup presentation $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$ and every baseword $w \in \Sigma^+$ can be associated a *diagram group* $D(\mathcal{P}, w)$, defined as the fundamental group of the *Squier complex* $S(\mathcal{P}, w)$. Roughly speaking, $D(\mathcal{P}, w)$ encodes the lack of asphericity of $\mathcal{P}$. Examples of diagram groups include Thompson's group $F$, the wreath product $Z \bowtie Z$, the pure planar braid groups, and various right-angled Artin groups. This survey aims at summarising what is known about the family of diagram groups.

## 1. Introduction

Defined by J. Meakin and M. Sapir (unpublished), and first investigated by V. Kilibarda in her thesis [55], diagram groups have been mainly promoted by V. Guba and M. Sapir, in particular through their monograph [45]. Since then, many articles have been dedicated to the understanding of which groups can be described as (subgroups of) diagram groups and which properties can be deduced from such a description. Perspectives on the subject include computational problems, such as the word, conjugacy, and commutation problems [45, 47], finiteness properties [24], homology [49], orderability [50, 67], median geometry [24, 33, 34], Hilbertian geometry [2], and negatively curved geometry [32, 36].

In this survey, our goal is to organise in a coherent and essentially self-contained way what is known about the family of diagram groups.

In Section 2, we first present three different, but equivalent, descriptions of diagram groups: as a way to encode the lack of asphericity of a semigroup presentation (Section 2.1); as a two-dimensional analogue of free groups, where words are replaced with diagrams over semigroup presentations (Section 2.2); and finally as second fundamental groups of directed 2-complexes (Section 2.3). Next, we record explicit examples of diagram groups in Section 2.4, including Thompson's group $F$, its commutator subgroup $F'$, the wreath product $Z \bowtie Z$, the pure planar braid groups,

*Mathematics Subject Classification 2020:* 20F65 (primary); 05C25, 57M07 (secondary).

**Keywords:** Diagram groups, semigroup diagrams, Squier complexes, directed 2-complexes, Thompson groups, median graphs, CAT(0) cube complexes.
and various right-angled Artin groups. Most properties satisfied by diagram groups are listed in Section 2.5, sometimes accompanied with ideas of proofs.

In Section 3, we are mainly concerned with algorithmic and computational aspects of diagrams. In Section 3.1, we show how one can compute efficiently presentations of diagram groups. Sections 3.2 and 3.3 essentially deal with the combinatorics of semigroup diagrams, with a focus on the conjugacy problem in Section 3.2 and on centralisers in Section 3.3. In Section 3.4, we show how to determine efficiently whether an element of a diagram group belongs to the commutator subgroup. Finally, in Section 3.5, we exploit the point of view given by directed 2-complexes in order to adapt the well-known foldings of Stallings from free groups to diagram groups. This allows us to solve the membership problem for some specific subgroups.

In Section 4, we consider diagram groups from a more geometric perspective. After a crash course on median geometry in Section 4.1, we show in Section 4.2 that diagram groups naturally act on median graphs. This geometry allows us to extract some valuable information about diagram groups regarding finiteness properties, once combined with a combinatorial version of Morse theory (Section 4.3); Hilbert space compression (Section 4.4); and acylindrical hyperbolicity (Section 4.6). The structure of hyperplanes in the nonpositively curved cube complexes whose fundamental groups are the diagram groups is studied in Section 4.5, with applications to residual finiteness and subgroup separability. Finally, in Section 4.7, we introduce diagram products, a version of diagram groups with coefficients coming from a family of groups indexed by the alphabet of the underlying semigroup presentation. We show that these products naturally act on quasi-median graphs, and we exploit this geometry in order to extract some information on the structure of diagram products.

We conclude this survey by describing various possible generalisations of diagram groups; most of them are already available in the literature (Section 5) and by listing several open questions and problems that we find appealing (Section 6), with the hope that this could motivate future works on diagram groups.

## 2. A first taste

### 2.1. Diagram groups as lack of asphericity

Let $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$ be a semigroup presentation, i.e., an alphabet $\Sigma$ and a collection of relations $\mathcal{R}$ of the form $u = v$, where $u, v$ are positive and non-empty words written over $\Sigma$. In the sequel, we will always assume that $\mathcal{R}$ does not contain obvious redundancy; i.e., if $u = v$ is in $\mathcal{R}$, we will assume that $v = u$ is not in $\mathcal{R}$. In particular, $\mathcal{R}$ does not contain a relation of the form $u = u$. As an example, we can take

$$ \mathcal{P} = \langle a, b \mid ab = ba, a = a^2 \rangle. $$
The presentation $\mathcal{P}$ is said to be aspherical if, given two positive words $p, q \in \Sigma^+$ representing the same element in the semigroup, there is essentially a unique way to derive $q$ from $p$ by applying relations in $\mathcal{R}$. Depending on the meaning one gives to such a uniqueness, one may obtain distinct notions of asphericity. For instance, the words $abba$ and $bab$ represent the same element in the semigroup given by $\mathcal{P} = \langle a, b | ab = ba, a = a^2 \rangle$, a natural derivation being

$$abba \to baba \to baab \to bab.$$

However, such a derivation is far from being unique. For instance, instead of applying the relation $ab = ba$ to the first half of $abba$ and next to the second half, we can apply the relation to the second half of the word and next to the first half

$$abba \to abab \to baab \to bab.$$

Even worse, we can apply a relation and next undo what we have just did, e.g.,

$$abba \to bab \to baab \to bab \to bba \to bab.$$

However, we do not consider such variations as being essentially different from our initial derivations. In order to formalise this idea, we use some algebraic topology.

**Definition 2.1.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. The Squier square complex $S(\mathcal{P})$ is the complex whose vertices are the positive words written over $\Sigma$; whose edges $[a, u = v, b]$ connect two words $aub$ and $avb$ if one can be obtained from the other by applying a relation

$$u = v$$

from $\mathcal{R}$; and whose squares

$$[a, u = v, b, p = q, c]$$

bound the 4-cycles given by edges

$$[a, u = v, bpc], \quad [a, u = v, bqc], \quad [aub, p = q, c], \quad [avb, p = q, c].$$

Then, one says that our presentation $\mathcal{P}$ is aspherical if the fundamental group of each connected component of the correspond Squier square complex is trivial. Thus, the fundamental groups of the connected components of $S(\mathcal{P})$ encode the lack of asphericity of $\mathcal{P}$. These groups are our *diagram groups*.

**Definition 2.2.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. The *diagram group* $D(\mathcal{P}, w)$ is the fundamental group $\pi_1(S(\mathcal{P}), w)$ of the Squier square complex $S(\mathcal{P})$ based at $w$.
<figure><img src="image_2.png" /><figcaption>**Figure 1.** The complex $S(\mathcal{P}, ad)$ where $\mathcal{P} = \langle a, b, c, x, y \mid a = b, b = c, c = a, x = y \rangle$.</figcaption></figure>

This is the shortest definition one can get of diagram groups, and it already allows us to construct examples. For instance, the diagram group given by Figure 1 is a free group of rank two. However, Definition 2.2 does not explain why we are focusing on semigroup presentations instead of monoid or group presentations, and its formulation has nothing to do with *diagrams*, so the terminology we are using remains mysterious. These points will be clarified in the next section.

## 2.2. Diagrammatic representation

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. Given two positive words $w_1, w_2 \in \Sigma^+$ representing the same element in the semigroup given by $\mathcal{P}$ a derivation from $w_1$ to $w_2$, or equivalently a path in the Squier complex $S(\mathcal{P})$ from $w_1$ to $w_2$, can be encoded by a *diagram over* $\mathcal{P}$. For instance, if $\mathcal{P} = \langle a, b \mid ab = ba, a = a^2 \rangle$, then the derivation

$$abba \to baba \to baab \to bab \to abb$$

can be represented by the diagram

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

The diagram is constructed as follows. We start with a top path (oriented from left to right) labelled by our initial word $abba$. The first step $abba \to baba$ in our
derivation applies the relation $ab = ba$ to the first half of the word $abba$, so we glue a 2-cell to our path with a boundary which is the disjoint union of a top path $ab$ and a bottom path $ba$. Similarly, following the second step $baba \to baab$ in our derivation, we glue a 2-cell with a boundary which is the disjoint union of a top path $ba$ and a bottom path $ab$. So far, we have a diagram with two 2-cells, whose top path is labelled by $abba$, and whose bottom path is labelled by $baab$. Following the third step $baab \to bab$ of our derivation, we glue a 2-cell with a boundary which is the disjoint union of a top path labelled $aa$ and a bottom path labelled $a$. Finally, we glue a fourth 2-cell corresponding to the fourth step $bab \to abb$ from our derivation.

Formally, a diagram of a semigroup presentation $\mathcal{P} = (\Sigma|\mathcal{R})$ is a planar oriented graph $\Delta$ whose oriented edges are labelled by letters from $\Sigma$ such that

* $\Delta$ has a unique source and a unique sink;

* the boundary of every cell is a disjoint union of two oriented paths, referred to as the *top* and *bottom* paths of the cell;

* for every cell, if $u$ and $v$ denote the labels of its top and bottom paths, then $u = v$ or $v = u$ belongs to $\mathcal{R}$.

By definition, a diagram comes with a fixed embedding in the plane. Two diagrams only differing by an isotopy of the plane are considered as identical. In the sequel, orientations of edges in diagrams will be clear from our embeddings (from left to right) so they will not be specified.

Our diagrams are the analogues of the semigroups of van Kampen diagrams for groups. In particular, two positive words $w_1, w_2 \in \Sigma^+$ represent the same element of the semigroup given by $\mathcal{P}$ if and only if there exists a diagram $\Delta$ over $\mathcal{P}$ with

$$ \text{top}(\Delta) = w_1 \quad \text{and} \quad \text{bot}(\Delta) = w_2. $$

Thus, every path in the Squier complex $S(\mathcal{P})$ from some vertex $w_1$ to another vertex $w_2$ can be represented by a diagram over $\mathcal{P}$ whose top and bottom words, respectively, are $w_1$ and $w_2$. Notice that two paths can be represented by the same diagram. For instance, the diagram given above also represents the path

$$ abba \to abab \to baab \to baba \to abb. $$

Clearly, the paths represented by a given diagram $\Delta$ correspond to the different ways one has to construct $\Delta$ by gluing 2-cells successively. In our example, we can glue the top left cell first and next the top right cell, or we can glue the top right cell first and next the top left cell. These two possibilities correspond to the two paths we gave.

It is worth noticing that all the paths encoded by a diagram are pairwise homotopic. However, two homotopic paths may not be represented by the same diagram.
<figure><img src="image_4.png" /></figure>

In a square complex, two paths in the one-skeleton are homotopy equivalent if and only if one can be obtained from the other by a sequence of elementary moves, namely, flipping a square and adding or removing a backtrack (see Figure 2).

It is clear that flipping a square does not modify the diagram representing our path. However, adding or removing a backtrack does modify the diagram. This motivates the following definition.

**Definition 2.3.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $\Delta$ a diagram over $\mathcal{P}$. A dipole in $\Delta$ is the data of two cells $\pi_1, \pi_2 \subset \Delta$ such that $\mathrm{bot}(\pi_1) = \mathrm{top}(\pi_2)$ and such that $\pi_1, \pi_2$ correspond to a relation of $\mathcal{R}$ and its inverse. One *reduces* the dipole by identifying the paths $\mathrm{top}(\pi_1)$ and $\mathrm{bot}(\pi_2)$.

For instance, the blue diagram above contains a dipole, namely, the two right cells. Reducing the dipole provides the red diagram. It is worth noticing that the diagram associated to a path with a backtrack necessarily contains a dipole. However, the converse is not true, as shown by the blue diagram above.

<figure><img src="image_5.png" /><figcaption>**Figure 2.** Flipping a square and removing/adding a backtrack.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>**Figure 3.** Product of diagrams over $\mathcal{P} = \langle a, b \mid ab = ba, a = a^2 \rangle$.</figcaption></figure>

**Proposition 2.4.** Let $\mathcal{P}$ be a semigroup presentation. Two paths in the Squier complex $S(\mathcal{P})$ having the same endpoints are homotopy equivalent if and only if the diagrams over $\mathcal{P}$ representing them have the same reduction.

Here, the *reduction* of a diagram refers to the diagram obtained after reducing all the dipoles. A priori, the diagram thus obtained could differ depending on the order we are following when reducing the dipoles. It turns out not to be the case; see [45, Theorem 3.17]. Thus, the reduction of a diagram is well defined.

Proposition 2.4 immediately implies the following corollary.

**Corollary 2.5.** Let $\mathcal{P}$ be a semigroup presentation. The map that sends a path in $S(\mathcal{P})$ to its diagram over $\mathcal{P}$ induces an isomorphism from the fundamental groupoid of $S(\mathcal{P})$ to the diagram groupoid $D(\mathcal{P})$ whose elements are the diagrams over $\mathcal{P}$ up to dipole reduction and whose product sends any two diagrams $\Delta_1, \Delta_2$ with $\mathrm{bot}(\Delta_1), \mathrm{top}(\Delta_2)$ labelling by the same word to the diagram $\Delta_1 \circ \Delta_2$ obtained by gluing $\Delta_2$ below $\Delta_1$.

Here, we think as a groupoid as a set endowed with a product only partially defined but satisfying basically the same axioms as groups: the product, when it is defined, is associative; there are neutral elements (not unique); and every element admits a unique inverse. The example to keep in mind is the fundamental groupoid of a topological space: its elements are the oriented paths up to homotopy, and the product between two paths $\alpha, \beta$ is well defined when the terminal point of $\alpha$ coincides with the initial vertex point of $\beta$ in which case the product is just the concatenation of $\alpha$ and $\beta$. Neutral elements are single points and the inverse of an element is obtained by reversing the orientation. In $D(\mathcal{P})$, the neutral elements are the diagrams with no 2-cells and the inverse of a diagram is given by its mirror image (along a horizontal axis). See Figure 3.

As a particular case of Corollary 2.5, given a semigroup presentation $\mathcal{P} = \langle \Sigma \mid \mathcal{R} \rangle$ and a baseword $w \in \Sigma^+$, the diagram group $D(\mathcal{P}, w)$ can be described as the set of $(w, w)$-diagrams over $\mathcal{P}$ (i.e., the diagrams whose top and bottom paths are labelled by $w$) up to dipole reductions endowed with the concatenation product.
**2.3. Diagram groups as two-dimensional free groups**

There is an analogy between our previous description of diagram groups and the construction of free groups. Elements of free groups are words (which can be thought of as linear objects) up to reductions $xx^{-1} = 1$ (corresponding to dipole reductions), which we concatenate together (similarly to concatenations of diagrams). The analogy can be pushed further. In the same way that free groups can be described as fundamental groups of graphs, diagram groups can be described as *second fundamental groups of directed 2-complexes*. This point of view was developed in [49] and will be crucial in Section 3.5. However, since it will not be essentially used elsewhere and is rather technical, the present section can be skipped in a first reading.

**Definition 2.6.** A *directed 2-complex* is the data of a directed graph $\Gamma$, a set of 2-cells $F$, two maps top, bot sending each 2-cell to a directed path in $\Gamma$, and a map $\iota: F \to F$ such that

* for every $f \in F$, bot($f$) and top($f$) are non-empty and have common initial and terminal vertices;

* $\iota$ is a fixed-point free involution satisfying top($\iota(f)$) = bot($f$) and bot($\iota(f)$) = top($f$) for every $f \in F$.

For instance, given a semigroup presentation $\mathcal{P}$, a diagram $\Delta$ over $\mathcal{P}$ is naturally a directed 2-complex (drawn on the plane). If the top and bottom paths of $\Delta$ have the same label, then one can identify top($\Delta$) with bot($\Delta$) in order to obtain another directed 2-complex (drawn on the sphere).

Mimicking the construction of a cellular 2-complex from a group presentation, one can also associate a directed 2-complex $\mathcal{X}(\mathcal{P})$ to our semigroup presentation $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$. Namely, $\mathcal{X}(\mathcal{P})$ has a single vertex, one directed edge for each generator in $\Sigma$, and, for each relation $u = v$ in $\mathcal{R}$, we add two 2-cells whose top and bottom paths are, respectively, labelled by $u$, $v$ and $v$, $u$.

Now, our goal is to define a *second fundamental groupoid* of a directed 2-complex. Roughly speaking, it is given by homotopy classes of 2-paths (i.e., paths of paths) endowed with the usual concatenation.

**Definition 2.7.** Let $\mathcal{X}$ be a directed 2-complex. A *1-path* is a directed path in the underlying directed graph. An *elementary transformation* of a 1-path $\alpha$ is the replacement of a subsegment $\beta \subset \alpha$ which coincides with the bottom path of some 2-cell $\pi$ with top($\pi$). A *2-path* is a finite sequence of 1-paths such that each 1-path is obtained from the previous one by an elementary transformation.

One should think of an elementary transformation as *pushing* a 1-path $\alpha$ through a 2-cell having its bottom path in $\alpha$. Observe that, given a semigroup presentation $\mathcal{P}$, a 2-path in the directed 2-complex $\mathcal{X}(\mathcal{P})$ is naturally encoded by a diagram over $\mathcal{P}$.
**Definition 2.8.** Let $\mathcal{X}$ be a directed 2-complex. Two 2-paths are *elementary equivalent* if they are of the form

$$ \alpha_1, \dots, \alpha_r, \zeta\mathrm{bot}(\pi)\xi, \zeta\mathrm{top}(\pi)\xi, \zeta\mathrm{bot}(\pi)\xi, \beta_1, \dots, \beta_s, \\ \alpha_1, \dots, \alpha_r, \zeta\mathrm{bot}(\pi)\xi, \beta_1, \dots, \beta_s $$

for some 2-cell $\pi$, or

$$ \alpha_1, \dots, \alpha_r, \alpha\mathrm{bot}(\mu)\beta\mathrm{bot}(\nu)\gamma, \alpha\mathrm{top}(\mu)\beta\mathrm{bot}(\nu)\gamma, \alpha\mathrm{top}(\mu)\beta\mathrm{top}(\nu)\gamma, \beta_1, \beta_s \\ \alpha_1, \dots, \alpha_r, \alpha\mathrm{bot}(\mu)\beta\mathrm{bot}(\nu)\gamma, \alpha\mathrm{bot}(\mu)\beta\mathrm{top}(\nu)\gamma, \alpha\mathrm{top}(\mu)\beta\mathrm{top}(\nu)\gamma, \beta_1, \beta_s $$

for some 2-cells $\mu, \nu$. Two 2-paths are *homotopy equivalent* if one can pass from one to the other by a sequence of elementary equivalences.

In other words, the first elementary equivalence tells us that pushing a 1-path through a 2-cell and next through its inverse amounts to doing nothing. The second elementary equivalence tells us that, given two 2-cells $\pi_1, \pi_2$ having their bottom paths in our 1-path $\zeta$ and disjoint, pushing $\alpha$ through $\pi_1$ and next through $\pi_2$ amounts to pushing $\alpha$ through $\pi_2$ and next through $\pi_1$.

As previously mentioned, a 2-path in the directed 2-complex $\mathcal{X}(\mathcal{P})$ associated to a semigroup presentation $\mathcal{P}$ is naturally encoded by a diagram over $\mathcal{P}$. It should be clear from our definition that any two homotopy equivalent 2-paths are encoded by the same diagram modulo dipole reduction.

**Definition 2.9.** Let $\mathcal{X}$ be a directed 2-complex. The *second fundamental groupoid* $\Pi_2(\mathcal{X})$ of $\mathcal{X}$ is the set of 2-paths up to homotopy equivalence endowed with concatenation. Given a 1-path $\alpha$, the *fundamental group* $\pi_2(\mathcal{X}, \alpha)$ is the set of 2-paths starting and ending at $\alpha$ up to homotopy equivalence endowed with concatenation.

Observe that neutral elements of $\Pi_2(\mathcal{X})$ are 2-paths reduced to single 1-paths and that the inverse of a 2-path is the same 2-path but read in the reversed order.

Interestingly, second fundamental groups of directed 2-complexes define the same class of groups as diagram groups [49, Theorem 4.3].

**Theorem 2.10.** For every semigroup presentation $\mathcal{P}$, the map that sends a 2-path in $\mathcal{X}(\mathcal{P})$ to the diagram encoding it induces a groupoid isomorphism $\Pi_2(\mathcal{X}(\mathcal{P})) \to D(\mathcal{P})$. Conversely, every directed 2-complex $\mathcal{X}$ can be turned into the directed 2-complex associated to a semigroup presentation $\mathcal{P}$ such that $\Pi_2(\mathcal{X})$ and $D(\mathcal{P})$ are isomorphic.

The first assertion should be clear from what we already said. We refer to [49] for more information on the second assertion.
## 2.4. Examples of diagram groups

The simplest diagram group is given by the semigroup presentation

$$ \mathcal{P} = \langle a, b, c \mid a = b, b = c, c = a \rangle. $$

The connected component $S(\mathcal{P}, a)$ containing $a$ of the Squier complex $S(\mathcal{P})$ is just a 3-cycle with vertices $a, b, c$, so $D(\mathcal{P}, a)$ is infinite cyclic. From this example, it is possible to construct new diagram groups by combination.

**Proposition 2.11** ([55]). *Free products of diagram groups are diagram groups.*

*Proof.* Let $I$ be a set. For every $i \in I$, let $\mathcal{P}_i := \langle \Sigma_i | \mathcal{R}_i \rangle$ be a semigroup presentation and $w_i \in \Sigma_i^+$ a baseword. Without loss of generality, we assume that the alphabets $\Sigma_i$ are pairwise disjoint. Set

$$ \mathcal{Q} := \left\langle \{o\} \sqcup \sqcup_{i \in I} \Sigma_i \mid \sqcup_{i \in I} \mathcal{R}_i \sqcup \{o = w_i, i \in I\} \right\rangle. $$

Then, $D(\mathcal{Q}, o)$ is isomorphic to the free product $\ast_{i \in I} D(\mathcal{P}_i, w_i)$ because $S(\mathcal{Q}, o)$ coincides with the disjoint union of the $S(\mathcal{P}_i, w_i)$ together with the new vertex $o$ which is adjacent to all the $w_i$. ■

Thus, free groups are diagram groups. By applying the construction above, a group freely generated by a set $I$ can be represented as the diagram group given by the semigroup presentation

$$ \langle o, a_i, b_i, c_i (i \in I) \mid o = a_i, a_i = b_i, b_i = c_i, c_i = a_i (i \in I) \rangle $$

and the baseword $o$.

**Proposition 2.12** ([55]). *Direct sums of finitely many diagram groups are diagram groups.*

*Proof.* Fix an integer $n \ge 1$, and, for every $1 \le i \le n$, let $\mathcal{P}_i := \langle \Sigma_i | \mathcal{R}_i \rangle$ be a semigroup presentation and $w_i \in \Sigma_i^+$ a baseword. Without loss of generality, we assume that the alphabets $\Sigma_i$ are pairwise disjoint. Set

$$ \mathcal{Q} := \left\langle \sqcup_{i=1}^{n} \Sigma_i \mid \sqcup_{i=1}^{n} \mathcal{R}_i \right\rangle $$

and $w := w_1 \cdots w_n$. Then, $D(\mathcal{Q}, w)$ is isomorphic to $D(\mathcal{P}_1, w_1) \oplus \cdots \oplus D(\mathcal{P}_n, w_n)$ because $S(\mathcal{Q}, w)$ coincides with the (2-skeleton of the) product $S(\mathcal{P}_1, w_1) \times \cdots \times S(\mathcal{P}_n, w_n)$. ■
Thus, free abelian groups of finite ranks are diagram groups. By applying the construction above, if

$$ \mathcal{P} = \langle a, b, c \mid a = b, b = c, c = a \rangle, $$

then $D(\mathcal{P}, a^n)$ is free abelian of rank $n$.

Comparing Proposition 2.12 with Proposition 2.11, it is natural to ask whether direct sums of infinitely many diagram groups are still diagram groups. The construction used in Proposition 2.12 does not work anymore, but one can apply a trick.

**Proposition 2.13** ([47]). *Directs sums of countably many diagram groups are diagram groups.*

*Sketch of proof.* For every $i \ge 1$, let $\mathcal{P}_i := \langle \Sigma_i | \mathcal{R}_i \rangle$ be a semigroup presentation and $w_i \in \Sigma_i^+$ a baseword. Without loss of generality, we assume that the alphabets $\Sigma_i$ are pairwise disjoint. Following Proposition 2.12, what we would like to do is to consider the infinite word $w := w_1w_2\cdots$ and to apply derivations on the $w_i$ independently according to the $\mathcal{P}_i$, respectively. However, infinite words are not allowed. The trick is to introduce a new letter $x_0$ in the alphabet and to “hide” the infinite part of our $w$ inside $x_0$. More precisely, set

$$ \mathcal{Q} := \left\{ \{x_i, i \ge 0\} \sqcup \sqcup_{i \ge 1} \Sigma_i \mid \sqcup_{i \ge 1} \mathcal{R}_i \sqcup \{x_{i-1} = x_i w_i, i \ge 1\} \right\}. $$

The claim is that $D(\mathcal{Q}, x_0)$ is isomorphic to $\bigoplus_{i \ge 1} D(\mathcal{P}_i, w_i)$. For every $i \ge 1$, the derivations of the form

$$ x_0 \to x_1 w_1 \to \dots \to \underbrace{x_i w_i \cdots w_1}_{\text{derivation in } \mathcal{P}_i \text{ applied to } w_i} \to \dots \to x_i w_i \cdots w_1 \to \dots \to x_0 $$

correspond to the elements of the factor $D(\mathcal{P}_i, w_i)$ in our direct sum. ■

Thus, a free abelian group of countable rank is a diagram group. By applying the construction above, it can be represented as the diagram group given by the semigroup presentation

$$ \langle x, a, b, c \mid a = b, b = c, c = a, a^n x = a^{n+1} x (n \ge 0) \rangle $$

and the baseword $x$.

**Proposition 2.14** ([47]). *If $G$ is a diagram group, then so is $G \rtimes \mathbb{Z}$.*

Recall that the *wreath product* $A \rtimes B$ of two groups $A, B$ is the semidirect product

$$ \bigoplus_B A \rtimes B, $$
and that

$$ \Xi \cdot D_i \cdot \Xi^{-1} = D_{i+1} $$

for every index $i \in \mathbb{Z}$.

It is worth noticing that $D(\mathcal{Q}, ab)$ is isomorphic to $D(\mathcal{Q}, aswsb)$ because $ab$ and $aswsb$ belong to the same connected component of the Squier complex $S(\mathcal{P})$. Therefore, $D(\mathcal{Q}, ab)$ can also be taken as a description of $D(\mathcal{P}, w) \sim \mathbb{Z}$ as a diagram group. ■

Thus, the wreath product $\mathbb{Z} \ltimes \mathbb{Z}$ is a diagram group. By applying the construction above, it can be represented as the diagram group given by the semigroup presentation

$$ \langle a, b, p_1, p_2, p_3 \mid p_1 = p_2, p_2 = p_3, p_3 = p_1, a = ap_1, b = p_1b \rangle $$

and the baseword $ab$.

Let us mention two last group operations preserving diagram groups. First, given two groups $A$ and $B$, let $A \bullet B$ denote the group given by the (relative) presentation

$$ \langle A, B, t \mid [a, t^n bt^{-n}] = 1 \text{ for all } a \in A, b \in B, \text{ and } n \ge 0 \rangle. $$

As an alternative description [34, Example 4.29], $A \bullet B$ can be described as the subgroup $\langle A, B, yx \rangle$ in $(A * \mathbb{Z}) \times (B * \mathbb{Z})$, where $x$ (resp., $y$) denotes a generator of the left (resp., right) factor $\mathbb{Z}$. For instance, the group

$$ \mathbb{Z} \bullet \mathbb{Z} = \langle a, b, t \mid [a, t^n bt^{-n}] = 1, n \ge 0 \rangle $$

coincides with the kernel of the morphism $\mathbb{F}_2 \times \mathbb{F}_2 \to \mathbb{Z}$ that sends each generator to 1 (sometimes referred to as the Bestvina-Brady group of $\mathbb{F}_2 \times \mathbb{F}_2$).

**Proposition 2.15** ([45]). The •-product of two diagram groups is again a diagram group.

*Sketch of proof.* Let

$$ \mathcal{P}_1 = \langle \Sigma_1 | \mathcal{R}_1 \rangle \quad \text{and} \quad \mathcal{P}_2 = \langle \Sigma_2 | \mathcal{R}_2 \rangle $$

be two semigroup presentations. Without loss of generality, we assume that $\Sigma_1 \cap \Sigma_2 = \emptyset$. Fix two basewords $w_1 \in \Sigma_1^+$ and $w_2 \in \Sigma_2^+$. The claim is that, given the semigroup presentation

$$ \mathcal{Q} := \langle \Sigma_1 \cup \Sigma_2 \cup \{p\} \mid \mathcal{R}_1 \cup \mathcal{R}_2 \cup \{w_1 = w_1p, w_2 = pw_2\} \rangle, $$

the diagram group $D(\mathcal{Q}, w_1w_2)$ coincides with

$$ D(\mathcal{P}_1, w_1) \bullet D(\mathcal{P}_2, w_2). $$
More precisely, $D(\mathcal{Q}, w_1w_2)$ naturally contains copies $D_1$ and $D_2$ of $D(\mathcal{P}_1, w_1)$ and $D(\mathcal{P}_2, w_2)$, corresponding to applications of derivations in $\mathcal{P}_1$ and $\mathcal{P}_2$ to $w_1$ and $w_2$. Then, an isomorphism

$$D(\mathcal{P}_1, w_1) \bullet D(\mathcal{P}_2, w_2) \to D(\mathcal{Q}, w_1w_2)$$

is obtained by sending $D(\mathcal{P}_1, w_1)$ to $D_1$, $D(\mathcal{P}_2, w_2)$ to $D_2$, and the generator $t$ to the diagram $\Xi$ associated to the derivation

$$w_1 w_2 \xrightarrow{w_1=w_1 p} w_1 p w_2 \xrightarrow{p w_2=w_2} w_1 w_2. \quad \blacksquare$$

Thus, the group $\mathbb{Z} \bullet \mathbb{Z}$ previously mentioned is a diagram group, and, by applying the construction above, it can be described as the diagram group given by the semigroup presentation

$$\langle a_1, a_2, a_3, b_1, b_2, b_3, p \mid a_1 = a_2, a_2 = a_3, a_3 = a_1, a_1 = a_1 p, \\ b_1 = b_2, b_2 = b_3, b_3 = b_1, b_1 = p b_1 \rangle$$

and the baseword $a_1b_1$.

Next, given two groups $A$ and $B$, let $A \square B$ denote the group given by the (relative) presentation

$$\langle A, B, t \mid [a, b] = [a, tbt^{-1}] = 1 \text{ for all } a \in A, b \in B \rangle.$$

For instance,

$$\mathbb{Z} \square \mathbb{Z} = \langle a, b, t \mid [a, b] = [a, tbt^{-1}] = 1 \rangle.$$

**Proposition 2.16** ([31]). The $\square$-product of two diagram groups is again a diagram group.

*Proof.* Let $\mathcal{P}_1 = \langle \Sigma_1 | \mathcal{R}_1 \rangle$ and $\mathcal{P}_2 = \langle \Sigma_2 | \mathcal{R}_2 \rangle$ be two semigroup presentations. Without loss of generality, we assume that $\Sigma_1 \cap \Sigma_2 = \emptyset$. Fix two basewords $w_1 \in \Sigma_1^+$ and $w_2 \in \Sigma_2^+$. The claim is that, given the semigroup presentation

$$\mathcal{Q} := \langle \Sigma_1 \sqcup \Sigma_2 \sqcup \{x, y\} \mid \mathcal{R}_1 \sqcup \mathcal{R}_2 \sqcup \{w_1x = w_1y, xw_2 = yw_2\} \rangle,$$

the diagram group $D(\mathcal{Q}, w_1xw_2)$ coincides with

$$D(\mathcal{P}_1, w_1) \square D(\mathcal{P}_2, w_2).$$

The key observation is that the Squier complex $S(\mathcal{Q}, w_1xw_2)$ contains two natural copies (of the two-skeleton) of $S(\mathcal{P}_1, w_1) \times S(\mathcal{P}_2, w_2)$, which we denote by

$$S(\mathcal{P}_1, w_1) \times S(\mathcal{P}_2, w_2) \quad \text{and} \quad S(\mathcal{P}_1, w_1) y S(\mathcal{P}_2, w_2).$$
Observe that the two copies of $S(\mathcal{P}_1, w_1)$ span (the two-skeleton of) a product $S(\mathcal{P}_1, w_1) \times [0, 1]$; and similarly for $S(\mathcal{P}_2, w_2)$. Thus, we get a decomposition of $S(\mathcal{Q}, w_1xw_2)$ as a graph of spaces which implies that $D(\mathcal{Q}, w_1xw_2)$ decomposes as the fundamental group of graph of groups with two vertices, both labelled by $D(\mathcal{P}_1, w_1) \times D(\mathcal{P}_2, w_2)$, and two edges, respectively, identifying the two copies of $D(\mathcal{P}_1, w_1)$ and $D(\mathcal{P}_2, w_2)$. Hence, the relative presentation

$$ \langle A_1, B_1, A_2, B_2, t \mid [A_1, B_1] = [A_2, B_2] = 1, tB_1t^{-1} = B_2 \rangle, $$

where $A_1, A_2$ (resp., $B_1, B_2$) are two copies of $A$ (resp., of $B$), which can be simplified as the presentation given above for $A \square B$. ■

As an application, we can describe our group $Z \square Z$ as the diagram group given by the semigroup presentation

$$ \langle a_1, a_2, a_3, b_1, b_2, b_3, x, y \mid a_1 = a_2, a_2 = a_3, a_3 = a_1, a_1x = a_1y, \\ b_1 = b_2, b_2 = b_3, b_3 = b_1, xb_1 = yb_1 \rangle $$

and the baseword $a_1xb_1$.

Given an integer $n \ge 1$, the *planar braid group* $T_n$, also referred to as the *twin group* or the group of *flat braids*, is the fundamental group of

$$ \{(x_1, \dots, x_n) \in \mathbb{R}^n \mid \forall i, \#\{j \mid x_j = x_i\} \le 1\} / S_n; $$

i.e., the configuration space of $n$ (unordered) points moving in $\mathbb{R}$, where collisions between two points, but no more, is allowed. Elements of $T_n$ can be represented as *planar braids* subject to the following relations:

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

The planar braid group $T_n$ turns out to be naturally isomorphic to the right-angled Coxeter group

$$ \langle \tau_1, \dots, \tau_{n-1} \mid \tau_i^2 = 1 (1 \le i \le n-1), [\tau_i, \tau_j] = 1 (|i-j| \ge 2) \rangle. $$

The kernel of the natural morphism $T_n \to S_n$ is the *pure planar braid group* $P T_n$.
**Proposition 2.17** ([23, 36]). For every $n \ge 1$, the pure planar braid group $PT_n$ is isomorphic to $D(\mathcal{P}_n, x_1 \cdots x_n)$, where

$$ \mathcal{P}_n := \{x_1, \dots, x_n \mid x_i x_j = x_j x_i \quad (1 \le i < j \le n)\}. $$

The isomorphism between the diagram group $D(\mathcal{P}_n, x_1 \cdots x_n)$ and the planar braid group $PT_n$ is illustrated in the following diagram. It shows that every diagram over $\mathcal{P}_n$ with top path labelled $x_1 \cdots x_n$ is naturally dual to a planar braid. The correspondence is clearly compatible with the group structures.

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

It is worth noticing that diagram groups given by the same semigroup presentation $\mathcal{P}_n$ as in Proposition 2.17 but with different basewords lead to interesting variations. For instance, $D(\mathcal{P}_n, x_1^{r_1} \cdots x_n^{r_n})$ corresponds to the group of the pure planar braids with $r_1 + \cdots + r_n$ strands, coloured with $n$ colours such that there are $r_i$ strands coloured with the $i$th colour, such that no two strands with the same colour are allowed to cross.

Now, let us turn probably to the most famous example of diagram group, namely, Thompson's group $F$. There are many possible definitions of $F$. The shortest is the following: $F$ is the group of the increasing piecewise linear homeomorphisms $[0, 1] \to [0, 1]$ whose breakpoints of the derivative have dyadic coordinates and whose slopes are integer powers of 2. We refer to [15] for more information on Thompson's groups.

**Proposition 2.18** (Kilibarda–Guba [55]). The diagram group $D(\mathcal{P}, x)$, where

$$ \mathcal{P} := \langle x \mid x = x^2 \rangle, $$

is isomorphic to the Thompson group $F$.

The key observation is that a diagram $\Delta$ over $\mathcal{P}$ with no dipoles decomposes as the concatenation of two diagrams $\Delta^+ \cdot \Delta^-$ where the 2-cells of $\Delta^+$ (resp., $\Delta^-$) are labelled by the relation $x \to x^2$ (resp., $x^2 \to x$). The following figure illustrates how to associate an element of $F$ from an element of $D(\mathcal{P}, w)$ both in terms of pairs of trees and of piecewise linear homeomorphisms.
<figure><img src="image_9.png" /></figure>

In the right part of the figure, one should think of a 2-cell from the top part of the diagram as a map $[0, 1] \to [0, 2]$ defined by $x \mapsto 2x$ and of a 2-cell from the bottom part of the diagram as a map $[0, 2] \to [0, 1]$ defined by $x \mapsto x/2$. This is a particular case of the construction mentioned in Section 6 after Question 6.13.

Clearly, the arguments above generalise to every Thompson's group $F_n$ (defined from $n$-adic numbers instead of 2-adic numbers). Thus, the diagram groups $D(\mathcal{P}_n, x)$ given by

$$ \mathcal{P}_n := \langle x \mid x = x^n \rangle $$

is isomorphic to $F_n$ for every $n \ge 2$.

Interestingly, there turns out to exist (algebraically) simple diagram groups.

**Proposition 2.19** ([47]). *Given the semigroup presentation*

$$ \mathcal{P} := \langle x, a_i, b_i \ (i \ge 1) \mid x = x^2, a_i = a_{i+1}x, b_i = xb_{i+1} \ (i \ge 1) \rangle, $$

the diagram group $D(\mathcal{P}, a_1b_1)$ is isomorphic to the commutator subgroup $F'$ of Thompson's group $F$.

Recall that the elements in $F'$ coincide with the homeomorphisms $[0, 1] \to [0, 1]$ fixing pointwise neighbourhoods of 0 and 1. In terms of pairs of trees, the elements in $F'$ correspond to the pairs $(T_1, T_2)$ such that the leftmost leaves of $T_1$ and $T_2$ have the same *dyadic representations*, and same thing for the rightmost leaves of $T_1$ and $T_2$. Here, the dyadic representation of a vertex in a planar 2-regular rooted tree refers to the digits associated to it when we label the root by $\emptyset$, its left child by 0, its right child by 1, the left child of 0 by 00, the right child of 0 by 01, the left child of 1 by 10, etc. For instance, the leftmost leaves of the top and bottom trees in the figure below have 00 as dyadic representatives. However, the leftmost leaves of the top and bottom trees in the figure above have 0 and 00 as dyadic representatives; therefore, the element of $F$ represented does not belong to the commutator subgroup $F'$. (See also Example 3.26 below for an equivalent description of $F'$ in $F$.)

The figure below shows how to associate a pair of trees, and a fortiori an element of $F$, to every diagram with no dipole over the presentation given by Proposition 2.19. The key observation is that such a diagram corresponds to a derivation starting with
the moves

$$a_1 \to a_2 x \to a_3 x x \to \dots \to a_r x^{r-1} \quad \text{and} \quad b_1 \to x b_2 \to x x b_3 \to \dots \to x^{s-1} b_s$$

and ending with the moves

$$a_r x^{r-1} \to a_{r-1} x^{r-2} \to \dots a_1 \quad \text{and} \quad x^{s-1} b_s \to x^{s-2} b_{s-1} \to \dots \to b_1.$$

This is why the leftmost (resp., rightmost) leaves in the top and bottom trees have the same dyadic representation.

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

Let us end this section by mentioning a last interesting families of groups. Given a (simplicial) graph $\Gamma$, the right-angled Artin group $A(\Gamma)$, also referred to as partially commutative group, is given by the presentation

$$\langle u \in V(\Gamma) \mid [u, v] = 1, \{u, v\} \in E(\Gamma) \rangle,$$

where $V(\Gamma)$ and $E(\Gamma)$ denote the vertex- and edge-sets of $\Gamma$. Because diagram groups include $\mathbb{Z}$ and are stable under direct sums and free products, we already know that many right-angled Artin groups are diagram groups. However, not every right-angled Artin group is a diagram group, and the question of which right-angled Artin groups are diagram groups is still open; see Question 6.11.

An easily recognisable family of right-angled Artin groups that are diagram groups is the following. Recall that a graph $\Gamma$ is an interval graph if there exist an $n \ge 1$ and a collection $\mathcal{C}$ of intervals in $\{1, \dots, n\}$ such that $\mathcal{C}$ is the vertex-set of $\Gamma$ and such that two intervals are connected by an edge whenever they are disjoint.

**Proposition 2.20 ([33])**. If $\Gamma$ is a finite interval graph, then $A(\Gamma)$ is a diagram group.

More precisely, if our interval graph $\Gamma$ is given by a collection $\mathcal{C}$ of intervals in $\{1, \dots, n\}$, then the diagram group given by the baseword $x_1 \cdots x_n$ and the semigroup presentation

$$\langle x_1, \dots, x_n, a_I, b_I, c_I (I \in \mathcal{C}) \mid x_I = a_I, a_I = b_I, b_I = c_I (I \in \mathcal{C}) \rangle,$$
where $x_I$ is a shorthand for $x_{i_1}x_{i_2}\cdots x_{i_s}$ if $I = \{i_1 < i_2 < \cdots < i_s\}$, is naturally isomorphic to the right-angled Artin group $A(\Gamma)$.

Another source of examples can be found in [50]. As a particular case of interest.

**Proposition 2.21** ([50]). *Right-angled Artin groups over finite trees are diagram groups.*

In fact, one can prove something stronger. One can prove that, if $\Gamma$ is either a finite interval graph or a finite tree, then a graph product of diagram groups over $\Gamma$ is again a diagram group. Recall that, given a (simplicial) graph $\Gamma$ and a collection of groups $\mathcal{G} = \{G_u \mid u \in V(\Gamma)\}$ indexed by the vertices of $\Gamma$, the *graph product* $\Gamma\mathcal{G}$ is given by the (relative) presentation

$$ \langle G_u, u \in V(\Gamma) \mid [G_u, G_v] = 1, \{u, v\} \in E(\Gamma) \rangle, $$

where $[G_u, G_v] = 1$ is a shorthand for $[a, b] = 1$ for all $a \in G_u$ and $b \in G_v$. Notice that graph products of infinite cyclic groups coincide with right-angled Artin groups.

## 2.5. First properties of diagram groups

So far, we have described diagram groups from several perspectives in Sections 2.1, 2.2, and 2.3, and we have shown in Section 2.4 that there exist many interesting groups that turn out to be diagram groups. Now, the natural question is what can we learn from the fact that a given group can be described as a diagram group? In this section, our goal is to show that, despite the fact that the family of diagram groups is very broad, being a diagram groups turns out to be quite restrictive; or, in other words, it provides valuable information on the group. As a complement of the previous section, this will also allow us to give examples of groups that are not diagram groups.

For the statements below, we include ideas of proofs, following the arguments given in the original articles. However, as it will be explained in Section 4, some of these arguments based on the combinatorics of diagrams follow almost for free from the median geometry described in Section 4.2.

Let us first explain that diagram groups are torsion-free, which already prevents many groups from being diagram groups.

**Theorem 2.22** ([45,55]). *Diagram groups are torsion-free.*

Let $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$ be a semigroup presentation. A diagram $\Delta$ over $\mathcal{P}$ is *reduced* if it does not contain any dipole. Assuming that $\Delta$ is *spherical* (i.e., if its top and bottom paths have the same label), one says that $\Delta$ is *absolutely reduced* if $\Delta^n$ is reduced for every $n \ge 1$. A key property is that every reduced spherical diagram $\Delta$ decomposes (up to dipole reduction) as $\Psi \circ \Delta_0 \circ \Psi^{-1}$ for some absolutely reduced diagram $\Delta_0$ [45, Lemma 15.10]. We emphasise that $\Psi$ may not be spherical.
Consequently, given a baseword $w \in \Sigma^+$ and a reduced diagram $\Delta \in D(\mathcal{P}, w)$, we decompose $\Delta$ as $\Psi \circ \Delta_0 \circ \Psi^{-1}$ for some absolutely reduced diagram $\Delta_0$. Then, $\Delta^n$ is trivial in $D(\mathcal{P}, w)$ if and only if so is $\Delta_0^n$ in $D(\mathcal{P}, w_0)$, where $w_0$ denotes the word labelling the top and bottom paths of $\Delta_0$. But $\Delta_0$ is absolutely reduced, so $\Delta_0^n$ is trivial if and only if $\Delta_0$ is itself trivial, which amounts to saying that $\Delta$ is trivial. Thus, we have shown that the only torsion element in $D(\mathcal{P}, w)$ is the trivial element.

**Theorem 2.23** ([47]). In diagram groups, nilpotent and polycyclic subgroups are free abelian and undistorted when they are finitely generated.

We refer to Sections 3.3 and 4.2 for elements of proofs.

As a consequence of Theorem 2.23, there are no interesting examples of nilpotent or polycyclic diagram groups. For instance, the fundamental group of the Klein bottle or the Heisenberg groups are not diagram groups. Nevertheless, there are metabelian but not abelian diagram groups, such as $Z \approx Z$; as well as solvable diagram groups of arbitrary lengths, such as $((Z \approx Z) \approx Z) \cdots \approx Z$. The absence of distortion given by Theorem 2.23 also allows us to discard non-amenable groups from diagram groups, such as most Baumslag–Solitar groups.

**Theorem 2.24** ([32]). A diagram group with no $Z^2$ is locally free.

The proof of this proposition is fundamentally based on the median geometry that will be described in Section 4.2. The idea is as follows. Let $D(\mathcal{P}, w)$ be a diagram group with no $Z^2$ and let $M(\mathcal{P}, w)$ denote the median graph on which it acts naturally. Given a finitely generated subgroup $H \subseteq D(\mathcal{P}, w)$, we want to prove that $H$ is free. We can assume without loss of generality that $H$ is freely irreducible. The trick is to choose carefully some hyperplane $J$ in $M(\mathcal{P}, w)$ such that no two $H$-translates of $J$ are transverse and the $H$-stabiliser of $J$ is trivial. Thus, the orbit $H \cdot J$ induces an arboreal structure on $M(\mathcal{P}, w)$ and $H$ acts on the dual tree (non-trivially and) with trivial edge-stabilisers. This implies that $H$ splits over the trivial group, which amounts to saying that $H$ is either trivial or infinite cyclic, as desired. Of course, the difficulty is to choose the good hyperplane $J$, and this is where we use the assumption that there is not $Z^2$ in $D(\mathcal{P}, w)$.

It follows from Theorem 2.24 that free groups are the only hyperbolic groups that are diagram groups. In particular, surface groups are not diagram groups. Nevertheless, it is worth mentioning that surface groups are subgroups of diagram groups. Indeed, the complement graph $\overline{P_7}$ of the path $P_7$ of length seven (i.e., the graph whose vertices are the vertices of $P_7$ and whose edges connect two vertices whenever they are not adjacent in $P_7$) is an interval graph, so it follows from Proposition 2.20 that the right-angled Artin group $A(\overline{P_7})$ is a diagram group. This group contains $A(C_n)$ for every $n \ge 5$, where $C_n$ denotes the cycle of length $n$ [16, Corollary 4.4]; and a fortiori every surface group [16, Corollary 4.5]. (Here, by a surface group, we mean
the fundamental group of an orientable closed surface of genus $\ge 2$.) As a corollary, it follows that subgroups of diagram groups may not be diagram groups themselves.

**Theorem 2.25** ([50]). *Diagram groups are bi-orderable, hence locally indicable.*

Recall that a group $G$ is (bi-)orderable if there exists a total order $\le$ and $G$ such that, for all $a, b, c \in G$, if $a \le b$, then $ac \le bc$ (and $ca \le cb$). A group is locally indicable if all its finitely generated subgroups surject onto $Z$. Locally indicable groups are automatically orderable, but the converse does not hold. However, bi-orderable groups are locally indicable.

It has been first proved in [67] that diagram groups are orderable. (See also Corollary 4.47 below.) Both [67] and [50] use the same strategy: first, they construct a “universal” group containing all the diagram groups; and next they show this universal group is (bi-)orderable. The universal groups are however very different in the two articles. In [67], this is a braid group on infinitely many strands. In [50], this is a well-chosen diagram group which turns out to split as a semi-direct product between a right-angled Artin group and Thompson’s group $F$.

Observe that, as an immediate consequence of Theorem 2.25, no finitely generated diagram group can be simple. This contrasts with the fact that the commutator subgroup $F'$ of Thompson’s group $F$, which is simple but not finitely generated, is a diagram group (Proposition 2.19).

**Corollary 2.26** ([45]). *Every diagram group $G$ satisfies the unique extraction of roots property; i.e., for all $a, b \in G$ and $k \ge 1$, if $a^k = b^k$, then $a = b$.*

This a consequence of the orderability of $G$. Indeed, given some $a, b \in G$ satisfying

$$a^k = b^k \quad \text{for some } k \ge 1,$$

it is clear that $a < b$ implies that

$$a^k = a \cdots aa < a \cdots ab < a \cdots bb < \cdots < b \cdots bb = b^k,$$

which would contradict that $a^k = b^k$; and similarly for $b < a$. Therefore, we must have $a = b$, as desired. Nevertheless, it is possible and instructive to prove directly Corollary 2.26 thanks to the combinatorics of diagrams. See [45, Theorem 15.25] for more details.

Let us record a couple of nice consequences of the unique extraction of roots property. Given a diagram group $G$ and two elements $a, b \in G$,

* if $[a^m, b^n] = 1$ for some $m, n \neq 0$, then $[a, b] = 1$;

* if $a^m = b^n$ for some $m, n \neq 0$, then there exist $c \in G$ and $k, \ell \ge 0$ satisfying $km = \ell n$ such that $a = c^k$ and $b = c^\ell$.

See [45, Corollaries 15.27 and 15.28] for more details.
**Proposition 2.27** ([45]). Every element of a diagram group $G$ has only finitely many roots. More precisely, if $a, b \in G \setminus \{1\}$ satisfies

$$a = b^k \quad \text{for some } k \neq 0,$$

then $|k|$ does not exceed half the number of cells in a reduced diagram representing $a$.

We refer to Section 3.2 for a proof of the proposition.

We conclude this section with some information on homology groups of diagram groups. The main result in this direction is the following theorem.

**Theorem 2.28** ([49]). Homology groups over $\mathbb{Z}$ of diagram groups are free abelian.

Some elements from the proof of the theorem are given in Section 3.1. Interestingly, with some restrictions on the underlying semigroup presentations, further information can be extracted from the proof of the following theorem.

**Theorem 2.29** ([49]). Let $\mathcal{P}$ be a finite and complete presentation of a finite semigroup. A diagram group over $\mathcal{P}$ has a rational Poincaré series.

Recall that the Poincaré series of a group $G$ is the series

$$P_G(t) := \sum_{n \ge 0} r_n t^n,$$

where $r_n$ denotes the rank of $H_n(G, \mathbb{Z})$ for every $n \ge 0$. Complete semigroup presentation will be defined in Section 3.1.

As a particular case of Theorem 2.28, abelianisations of diagram groups are free abelian (also proved in [45]; see Corollary 3.5 below). This contrasts with Pride's result from [60]: for every abelian group $A$ which is a finite or countably infinite direct product of cyclic groups, there exists a diagram group $G$ such that

$$[G, G]/[[G, G], G] \simeq A.$$

# 3. Algorithmic and computational properties

## 3.1. Computation of presentations and homology groups

In this section, we are concerned with the following problem: given a semigroup presentation $\mathcal{P} := (\Sigma|\mathcal{R})$ and a baseword $w \in \Sigma^+$, how can we compute efficiently a presentation for the diagram group $D(\mathcal{P}, w)$? Or equivalently, how can we compute efficiently a presentation for the fundamental group of the Squier square complex $S(\mathcal{P}, w)$? We describe here the solution proposed in [45, Chapter 9]. See also Section 4.5 for a decomposition of diagram groups as fundamental groups of graphs of groups.
The starting idea is simple. We want to fix, in our Squier square complex $S(\mathcal{P}, w)$, an orientation of the edges and a spanning tree $T(\mathcal{P}, w)$ so that

> (oriented edges in $S(\mathcal{P}, w)$ | edges in $T(\mathcal{P}, w)$ are trivial
> the boundary of a square is trivial)

defines a presentation of our diagram group $D(\mathcal{P}, w)$. As an illustration, consider the semigroup presentation

$$ \mathcal{P} := \langle a, b, c, x, y \mid a = b, x = y, c = ax, c = bx \rangle. $$

Draw the Squier complex $S(\mathcal{P}, c)$, orient the edges, and choose a spanning tree as illustrated in the diagram below. One gets the presentation

$$ \langle p, q, r, s, u, v \mid u = q = r = s = 1, qrsp = 1 \rangle $$

of the diagram group $D(\mathcal{P}, c)$, which can be simplified as $\langle v \mid \rangle$.

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

The difficulty is to find an automatic procedure constructing a spanning tree. This is why we restrict ourselves to *complete* semigroup presentations, which we define now.

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. Given two positive words $w_1, w_2 \in \Sigma^+$, we write $w_1 \to w_2$ if $w_2$ can be obtained from $w_1$ by applying a (an ordered) relation of $\mathcal{R}$, i.e., if we can write $w_1 = aub$ and $w_2 = avb$ for some $u = v$ in $\mathcal{R}$. We emphasise that, because $v = u$ does not belong to $\mathcal{R}$, $w_1 \to w_2$ does not necessarily imply $w_2 \to w_1$. We denote by $\stackrel{*}{\to}$ the reflexive-transitive closure of $\to$, i.e., given two words $u, v \in \Sigma^+$, we write $u \stackrel{*}{\to} v$ if there exist $w_1, \dots, w_n \in \Sigma^+$ satisfying $u \to w_1 \to \dots \to w_n \to v$. The presentation $\mathcal{P}$ is *complete* if the relation $\stackrel{*}{\to}$ is *confluent* (i.e., if $u \stackrel{*}{\to} a$ and $u \stackrel{*}{\to} b$, then there exists $v$ such that $a \stackrel{*}{\to} v$ and $a \stackrel{*}{\to} v$) and *terminating* (i.e., every sequence $w_1 \to w_2 \to \dots$ eventually terminates). For instance, the presentation $\langle x \mid x^2 = x \rangle$ is complete but not the presentation $\langle x \mid x = x^2 \rangle$ because $x \to x^2 \to x^3 \to \dots$ does not terminate.
From now on, we assume that our semigroup presentation $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ is complete. As a consequence, every positive word $w \in \Sigma^+$ has a unique reduced form, i.e., a positive word $\bar{w} \in \Sigma^+$ such that $w \xrightarrow{\star} \bar{w}$ and such that there is no $u \in \Sigma^+$ such that $\bar{w} \to u$. (Because $\xrightarrow{\star}$ is terminating, such a word exists; and because $\xrightarrow{\star}$ is confluent, such a word is unique.) However, a derivation from a word to its reduction may not be uniquely defined. What we want to do is to define a canonical way to reduce words and to define our spanning tree in the Squier square complex as the union of all the paths given by these reductions. These canonical reductions are defined by the elementary moves associated to the following edges in our Squier complex.

**Definition 3.1.** An oriented edge $(u, \ell \to r, v)$ in $S(\mathcal{P})$ is a *principal left edge* if the following conditions hold:

* each proper prefix of the word $u\ell$ is reduced;

* $\ell$ is the longest suffix of $u\ell$ which is the left side of a relation in $\mathcal{R}$;

* if there is a relation $\ell = r'$ in $\mathcal{R}$ with $r \neq r'$, then $r$ is smaller than $r'$ in the ShortLex order.

Here, we think of the letters in $\Sigma$ as totally ordered (say, following the left-right order when we write the presentation $\mathcal{P}$) so that positive words are naturally totally ordered by the corresponding ShortLex order, namely, given $w_1, w_2 \in \Sigma^+$, we write $w_1 \le w_2$ if $w_1$ is shorter than $w_2$ or if $w_1, w_2$ have the same length and $w_1$ is smaller than $w_2$ with respect to the lexicographic order given by our total order on $\Sigma$.

Let us illustrate with an example how to reduce a word by following the pattern given by the previous definition (which seems to be difficult to digest, but which turns out to quite natural when we understand how it works). So, let us consider the semigroup presentation

$$ \mathcal{P} := \langle a, b \mid a^3 = a, a^3 = a^2, ba^3 = a^3b \rangle, $$

which is complete. The word $aba^3ba^4$ is not reduced.

* Identify the smallest prefix of $aba^3ba^4$ that is not reduced. This is $aba^3$.

* Identify the longest suffix of $aba^3$ that can be modified by applying a relation. This is $ba^3$.

* Observe that

$$ ba^3 = a^3b $$

is the only relation having $ba^3$ as its left side, so this is the relation we have to apply.

Thus, the first step in our derivation from $aba^3ba^4$ to its reduction is $aba^3ba^4 \to a^4b^2a^4$. Our new word is again not reduced, so another step is necessary.
* Identify the smallest prefix of $a^4b^2a^4$ that is not reduced. This is $a^3$.

* Identify the longest suffix of $a^3$ that can be modified by applying a relation. This is $a^3$.

* We have two relations having $a^3$ as their left sides, namely, $a^3 = a$ and $a^3 = a^2$. Compare the right sides $a$ and $a^2$ with respect to the ShortLex order. Since $a$ is shorter than $a^2$, the relation we must apply is $a^3 = a$.

Thus, the second step in our derivation is $a^4b^2a^4 \to a^2b^2a^4$. Keeping applying the procedure, we eventually find

$$aba^3ba^4 \to a^4b^2a^4 \to a^2b^2a^4 \to a^2ba^3ba \to a^5b^2a \to a^3b^2a \to ab^2a,$$

which is the canonical reduction we are looking for.

The union of all the principal left edges given by Definition 3.1 defines a spanning forest in our Squier complex, as previously claimed [45, Lemma 9.4], which allows us to deduce the following statement.

**Theorem 3.2** ([45]). Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a complete semigroup presentation and $w \in \Sigma^+$ a baseword. The diagram group $D(\mathcal{P}, w)$ admits the following presentation. The generators are the triples $(u, \ell \to r, v)$, where $(\ell = r) \in \mathcal{R}$, $uv = w \mod \mathcal{P}$, $u$ is a reduced word, $v \in \Sigma^+$, $(u, \ell \to r, v)$ is not a principal left edge. The defining relations are all the relations of the form

$$(u, \ell \to r, vsw) = (u, \ell \to r, vtw)^{(\overline{uv}, s \to t, w)},$$

where $(s = t) \in \mathcal{R}$ and the edge $(\overline{uv}, s \to t, w)$ is not a principal left edge; or of the form

$$(u, \ell \to r, vsw) = (u, \ell \to r, vtw)$$

if $(\overline{uv}, s \to t, w)$ is a principal left edge.

Here, we use the notation $a^b = b^{-1}ab$. It is worth mentioning that the presentation given by Theorem 3.2 is in general not optimal since the second type of relations allows us to decrease the number of generators. It is possible to extract a presentation with a minimal number of generators (which turns out to coincide with the rank of the abelianisation) but at the cost of a more technical statement. We refer the interested reader to [45, Theorem 9.8].

An interesting consequence of Theorem 3.2 is that diagram groups over complete semigroup presentations are examples of *LOG groups*.

**Definition 3.3.** Let $\Gamma$ be a directed graph and $\lambda : E(\Gamma) \to V(\Gamma)$ a labelling map. The *LOG group* $\Gamma(\lambda)$ is given by the presentation

$$\langle V(\Gamma) | a = b^{\lambda(a,b)}, (a,b) \in E(\Gamma) \rangle.$$
LOG stands for Labelled Oriented Graph. It is worth noticing that not all diagram groups are LOG. Indeed, it is clear that every LOG group surjects onto $\mathbb{Z}$ (it suffices to send all the generators to 1), but we know from Proposition 2.19 that the commutator subgroup $F'$ of Thompson's group $F$ is a simple diagram group. Thus, $F'$ is a diagram group but not an LOG group. We also deduce that $F'$ cannot be described as a diagram group over a complete semigroup presentation, so we lost some generality when restricting ourselves to complete semigroup presentation. Nevertheless, as shown by Lemma 3.6 below, it turns out that every diagram group can be described (more or less explicitly) as a retract inside some diagram group over a complete semigroup presentation, so it is also possible to compute presentations of diagram groups over incomplete semigroup presentations thanks to the techniques developed in this section (see [45, Lemma 9.11] and the related discussion).

**Example 3.4.** Consider the semigroup presentation $\mathcal{P} = \langle x \mid x^2 = x \rangle$, which is complete. Notice that the principal left edges in $S(\mathcal{P}, x)$ are the edges of the form $(1, x^2 \to x, x^n)$, $n \ge 0$, where 1 refers to the empty word. A direct application of Theorem 3.2 shows that $D(\mathcal{P}, x)$, which is isomorphic to the Thompson group $F$ according to Proposition 2.18, admits a presentation whose generators are the triples $(x, x^2 \to x, x^n)$ for $n \ge 0$, and whose relations are

$$ (x, x^2 \to x, x^p x^2 x^q) = (x, x^2 \to x, x^p x^2 x^q)(x, x^2 \to x, x^q), \quad p, q \ge 0. $$

Setting $s_i := (x, x^2 \to x, x^i)$ for every $i \ge 0$, one gets the infinite presentation

$$ \langle s_0, s_1, \dots \mid s_{n+1} = s_n^{s_m}, n > m \ge 0 \rangle. $$

The presentation can be simplified as a finite presentation; see [45, Example 9.10] for details.

Let us mention a theoretical application of Theorem 3.2, namely, the following corollary.

**Corollary 3.5.** *Diagram groups have free abelianisations.*

**Lemma 3.6.** *Every diagram group is a retract of a diagram group over a complete semigroup presentation.*

Recall that, given a group $G$, a subgroup $H \le G$ is a retract if there exists a morphism $\rho: G \to H$ that restricts to the identity on $H$.

*Proof of Lemma 3.6.* Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. We fix a total order on $\Sigma$ with no infinite decreasing sequence and order the positive words in $\Sigma^+$ by using the corresponding ShortLex order. Up to replacing some $u = v$ in $\mathcal{R}$ with $v = u$, we assume that, for every $u = v$ in $\mathcal{R}$, $v$ is smaller than $u$ with respect to the
ShortLex order. Let $\mathcal{R}'$ denote the collection of all the relations $u = v$ such that $v$ is smaller than $u$ with respect to the ShortLex order and such that $u = v \mod \mathcal{P}$. Notice that $\mathcal{R} \subset \mathcal{R}'$.

Observe that $\mathcal{P}' := \langle \Sigma | \mathcal{R}' \rangle$ is complete. Indeed, the fact that our initial order on $\Sigma$ has no infinite decreasing sequence implies that the corresponding ShortLex order has no infinite decreasing sequence either. Moreover, for every $w \in \Sigma^+$, there exists a unique ShortLex-minimal word $\bar{w} \in \Sigma^+$ among all the positive words equal to $w$ mod $\mathcal{P}$; and, for all $u, v \in \Sigma^+$ satisfying $w \xrightarrow{*} u$ and $w \xrightarrow{*} v$, we have $u \to \bar{w}$ and $v \to \bar{w}$ by definition of $\mathcal{R}'$. Thus, $\mathcal{P}'$ is terminating and confluent.

Fix a baseword $w \in \Sigma^+$. Because a (reduced) diagram over $\mathcal{P}$ is also a (reduced) diagram over $\mathcal{P}'$, there is an obvious injective morphism $D(\mathcal{P}, w) \to D(\mathcal{P}', w)$. From now on, we identify $D(\mathcal{P}, w)$ with its image in $D(\mathcal{P}', w)$. For every $u = v$ in $\mathcal{R}'$ but not in $\mathcal{R}$, we know that $u = v \mod \mathcal{P}$, so there must exist a diagram $\Delta(u, v)$ with its top path labelled $u$ and its bottom path labelled $v$. Define a map $D(\mathcal{P}', w) \to D(\mathcal{P}, w)$ by sending a diagram over $\mathcal{P}'$ to the diagram over $\mathcal{P}$ obtained by replacing each two-cell labelled by $u = v$ with $(u = v) \in \mathcal{R}$ (resp., with $(v = u) \in \mathcal{R}$) with a copy of $\Delta(u, v)$ (resp., $\Delta(u, v)^{-1}$). We can verify that this map is a well-defined morphism; see [45, Theorem 7.7] for more details. Moreover, this morphism is clearly the identity on $D(\mathcal{P}, w)$. $\blacksquare$

*Proof of Corollary 3.5.* We know that diagram groups over complete semigroup presentations are LOG groups, and clearly LOG groups have free abelianisations. Therefore, it follows from Lemma 3.6 that the following observation is sufficient to conclude the proof of our corollary.

**Fact 3.7.** Let $G$ be a group and $H \leq G$ a retract. The abelianisation of $H$ embeds into the abelianisation of $G$.

Let $\alpha : G \to G^{ab}$ denote the abelianisation map of $G$ and let $\rho : G \to H$ be a retraction. The restriction of $\alpha$ to $H$ yields a morphism $H \to G^{ab}$, which factors through $\varphi : H^{ab} \to G^{ab}$. Let $g \in H^{ab}$ be an element in the kernel of $\varphi$. Fix a pre-image $\tilde{g}$ of $g$ in $H$. By definition of $\varphi$, $\alpha(\tilde{g})$ is trivial. In other words, $\tilde{g}$ belongs to $[G, G]$. Hence

$$ \tilde{g} = \rho(\tilde{g}) \in [\rho(G), \rho(G)] = [H, H], $$

which implies that $g$ is trivial in $H^{ab}$. Thus, we have proved that $\varphi : H^{ab} \to G^{ab}$ is injective. $\blacksquare$

As already mentioned in Section 2.5, Corollary 3.5 can be generalised by showing that homology groups of diagram groups are free abelian. The strategy is similar in the spirit of the proof of Corollary 3.5. We refer to [49] for more details and only sketch the argument below (in the language of diagrams instead of directed 2-complexes).
<figure><img src="image_12.png" /><figcaption>**Figure 4.** A collapsible scheme. Collapsible cells in red, redundant cells in green, essential cells in blue.</figcaption></figure>

Given a semigroup presentation $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ and a baseword $w \in \Sigma^+$, we need a classifying space for the diagram group $D(\mathcal{P}, w)$. We already know that $D(\mathcal{P}, w)$ is the fundamental group of the Squier square complex $S(\mathcal{P}, w)$, but this complex is not contractible in general. However, by adding natural higher-dimensional cubes to it, it turns out to be contractible.

**Definition 3.8.** The Squier cube complex $S^+(\mathcal{P})$ is the cube complex whose vertices are the words in $\Sigma^+$; whose (oriented) edges can be written as $(a, u \to v, b)$, where $u = v$ or $v = u$ belongs to $\mathcal{R}$, connecting the vertices $aub$ and $avb$; and whose $n$-cubes similarly can be written as $(a_1, u_1 \to v_1, \dots, a_n, u_n \to v_n, a_{n+1})$, spanned by the set of vertices

$$ \{a_1 w_1 \cdots a_n w_n a_{n+1} \mid w_i = v_i \text{ or } u_i\}. $$

Given a word $w \in \Sigma^+$, we denote by $S^+(\mathcal{P}, w)$ the connected component of $S^+(\mathcal{P})$ containing the vertex $w$.

Observe that $S(\mathcal{P})$ coincides with the two-skeleton of $S^+(\mathcal{P})$, so our diagram group $D(\mathcal{P}, w)$ remains isomorphic to the fundamental group of $S^+(\mathcal{P}, w)$. Each connected component of the Squier cube complex is contractible. This can be proved directly [24, Theorem 3.10] or can be deduced from its nonpositive curvature described in Section 4.2. Anyway, the key point is that $S^+(\mathcal{P}, w)$ yields a classifying space for the corresponding diagram group $D(\mathcal{P}, w)$.

Next, observe that, given a group $G$, if $H \le G$ is a retract then the homology groups of $H$ are retracts of the homology groups of $G$, so it follows from Lemma 3.6 that we can focus on diagram groups over complete semigroup presentations. So, let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a complete semigroup presentation and fix a baseword $w \in \Sigma^+$. Similarly to what we did for $S(\mathcal{P}, w)$ above, we can use the completeness of $\mathcal{P}$ in order to extract from $S^+(\mathcal{P}, w)$ the essential part that encodes the homology.

Formally [49] defines a collapsible scheme on $S^+(\mathcal{P}, w)$ (see Figure 4); see [49, Section 9] for a precise statement. Roughly speaking, this is a partition of the cubes of $S^+(\mathcal{P}, w)$ into three categories: *contractible*, *redundant*, and *essential* cubes. Under reasonable assumptions, it is possible to successively collapse contractible cubes by pushing inside a codimension-one face that is redundant. At the end of the process,
one gets a homotopy equivalent cube complex $E(\mathcal{P}, w)$ containing only the initial
essential cubes.

Thanks to a well-chosen collapsible scheme, it is proved in [49] that $E(\mathcal{P}, w)$ is
as small as possible. More precisely, in each dimension $n$, the $n$th homology group
of $E(\mathcal{P}, w)$ (which is also the $n$th homology group of $D(\mathcal{P}, w)$ since $E(\mathcal{P}, w)$ and
$S^+(\mathcal{P}, w)$ are homotopy equivalent) is freely generated by the $n$-cubes.

**3.2. Word and conjugacy problems**

As already mentioned, every diagram over a semigroup presentation admits a unique
reduction (i.e., a diagram with no dipole). Therefore, in order to determine whether
a given diagram represents the neutral element in the corresponding diagram group,
it suffices to reduce its dipoles, in whatever order, and to look at if 2-cells survive at
the end of the process. If so, the diagram represents a non-trivial element; otherwise,
it represents the neutral element. Moreover, this word problem can be solved very
efficiently.

**Theorem 3.9** ([45]). Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. Fix finitely many $(w, w)$-diagrams $\Delta_1, \dots, \Delta_r$ over $\mathcal{P}$. There exists an algorithm that decides, given a product of $n$ diagrams $\Delta_i$, whether it represents the trivial element in $D(\mathcal{P}, w)$ with time complexity $O(n^2 \log^2 n)$.

In order to solve the conjugacy problem, we need to introduce some terminology.

**Definition 3.10.** Let $\mathcal{P}$ be a semigroup diagram. The sum $\Delta_1 + \Delta_2$ of two diagrams $\Delta_1, \Delta_2$ over $\mathcal{P}$ is the diagram obtained by identifying the sink-vertex of $\Delta_1$ with the source-vertex of $\Delta_2$. A diagram is *simple* if it does not decompose as the sum of two diagrams. Clearly, every diagram admits a unique decomposition as a sum of simple diagrams. A spherical diagram is *normal* if all the diagrams in its decomposition as a sum of simple diagrams are spherical.

**Definition 3.11.** Let $\mathcal{P}$ be a semigroup presentation and $\Delta$ a diagram. If $\Delta$ decomposes as the concatenation $\Delta_1 \circ \Delta_2$, then the diagram $\Delta_2 \circ \Delta_1$, when well defined, is a *cyclic shift* of $\Delta$.

We emphasise that $\Delta_1 \circ \Delta_2$ is a decomposition of $\Delta$ on the nose, not up to dipole reduction. As an illustration, given the two diagrams $\Delta$, $\Omega$ below, $\Omega$ is a cyclic shift of $\Delta$ (see Figure 5).

Indeed, $\Delta$ decomposes as $(A^{-1} + \varepsilon(x)) \circ (\varepsilon(x) + A)$, where $\varepsilon(x)$ denotes the $(x, x)$-diagram with no 2-cell and where $A$ denotes the $(x, x^2)$-diagram with a single 2-cell; and $\Omega = (\varepsilon(x) + A) \circ (A^{-1} + \varepsilon(x))$. Notice that the diagram $\Delta$ above is neither simple nor normal. However, its cyclic conjugate $\Omega$ is simple.
<figure><img src="image_13.png" /><figcaption>**Figure 5.** A diagram $\Delta$ over $\mathcal{P} := \langle x \mid x = x^2 \rangle$ and a cyclic shift $\Omega$.</figcaption></figure>

**Theorem 3.12** ([45]). Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. If the semigroup $\mathcal{P}$ has a solvable word problem, then the conjugacy problem in the diagram group $D(\mathcal{P}, w)$ is solvable.

It is worth noticing that a diagram group given by a semigroup presentation with unsolvable word problem may have an unsolvable conjugacy problem; see [45, Example 15.22]. Let us describe the main ingredients needed in order to solve the conjugacy problem in practice. The first step is to reduce the problem to simple absolutely reduced diagrams.

**Lemma 3.13** ([45, Lemma 15.14]). Let $\mathcal{P}$ be a semigroup presentation and $\Delta$ a spherical diagram over $\mathcal{P}$. There exist diagrams $\Phi, \Omega$ such that $\Delta = \Phi \circ \Omega \circ \Phi^{-1}$, up to dipole reduction, and with $\Omega$ normal and absolutely reduced. Moreover, $\Omega$ can be chosen with a number of 2-cells bounded above by the number of 2-cells of $\Delta$.

We emphasise that $\Omega$ must be a spherical diagram but its top and bottom paths may have distinct labels than the top and bottom paths of $\Delta$. Recall from Section 2.5 that a spherical diagram $\Delta$ is absolutely reduced if $\Delta^n$ is reduced for every $n \ge 1$.

**Lemma 3.14** ([45, Lemma 15.15]). Let $\mathcal{P}$ be a semigroup presentation and $\Delta, \Gamma$ two normal and absolutely reduced diagrams over $\mathcal{P}$. Decompose $\Delta$ (resp., $\Gamma$) as a sum $\Delta_1 + \cdots + \Delta_m$ (resp., $\Gamma_1 + \cdots + \Gamma_n$) of simple diagrams. For every $1 \le i \le m$ (resp., $1 \le j \le n$), let $x_i$ (resp., $y_j$) be the words labelling the top and bottom paths of $\Delta_i$ (resp., $\Gamma_j$). Assume that there exists some $\Theta$ such that

$$ \Delta = \Theta \circ \Gamma \circ \Theta^{-1}, $$

up to dipole reduction. Then, $m = n$ and $\Gamma$ decomposes as a sum $\Gamma_1 + \cdots + \Gamma_m$ where each $\Gamma_i$ is a $(y_i, x_i)$-diagram satisfying

$$ \Delta_i = \Theta_i \circ \Gamma_i \circ \Theta_i^{-1}, $$

up to dipole reduction.

Next, we can solve the conjugacy problem for simple absolutely reduced diagrams thanks to the next lemma. In its statement, we denote by $\text{Shift}(\Delta)$ the set of all the
<figure><img src="image_14.png" /><figcaption>**Figure 6.** Two $(x, x)$-diagrams over $\langle x, | x = x^2 \rangle$ that are not conjugate.</figcaption></figure>

diagrams that can be obtained from $\Delta$ by a sequence of cyclic shifts. (It is worth mentioning that a cyclic shift of a cyclic shift may not be a cyclic shift of the initial diagram.)

**Lemma 3.15.** Let $\mathcal{P}$ be a semigroup presentation. Two simple and absolutely reduced spherical diagrams $\Delta_1, \Delta_2$ are conjugate if and only if

$$ \mathrm{Shift}(\Delta_1) = \mathrm{Shift}(\Delta_2). $$

Putting everything together, the conjugacy problem is solved as follows. Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. We fix two $(w, w)$-diagrams $\Delta_1, \Delta_2$ over $\mathcal{P}$ and we would like to determine whether or not $\Delta_1$ and $\Delta_2$ are conjugate in $D(\mathcal{P}, w)$.

(1) For $i = 1, 2$, write $\Delta_i$ as $\Phi_i \circ \Omega_i \circ \Phi_i^{-1}$, where $\Omega_i$ is normal and absolutely reduced. (Which is possible according to Lemma 3.13, and can be done algorithmically.)

(2) Decompose $\Omega_i$ as a sum $\Omega_i^1 + \cdots + \Omega_i^{n_i}$ of simple diagrams.

(3) If $n_1 \neq n_2$, it follows from Lemma 3.14 that $\Delta_1$ and $\Delta_2$ are not conjugate.

(4) Otherwise, check whether $\mathrm{Shift}(\Omega_1^j) = \mathrm{Shift}(\Omega_2^j)$ for every $1 \le j \le n_1 = n_2$. (This can be done algorithmically according to [45, Lemma 15.21].)

(5) According to Lemma 3.15, $\Delta_1$ and $\Delta_2$ are conjugate if and only if all the equalities hold.

As a simple illustration, we can show that the two smallest reduced $(x, x)$-diagrams over $\mathcal{P} = \langle x | x = x^2 \rangle$ are not conjugate in $D(\mathcal{P}, x)$ (see Figure 6).
It is worth mentioning that the tools developed in order to solve the conjugacy problem turn out to be also useful to help proving some of the statements mentioned in Section 2.5. For instance, see Proposition 2.27.

**Proof of Proposition 2.27.** Let $\Delta$, $\Gamma$ be two spherical reduced diagrams satisfying $\Delta = \Gamma^k$ for some $k \ge 1$. We assume that $\Delta$ and $\Gamma$ contain at least one 2-cell. According to Lemma 3.13, we can write $\Delta$ as $\Phi\Delta_0\Phi^{-1}$ and $\Gamma$ as $\Psi\Gamma_0\Psi^{-1}$ for some normal absolutely reduced diagrams $\Delta_0$ and $\Gamma_0$. Moreover, we can choose $\Delta$ with a number of 2-cells bounded above by the number of 2-cells of $\Delta$. Let

$$ \Delta_0 = \Delta_0^1 + \dots + \Delta_0^m \quad \text{and} \quad \Gamma_0 = \Gamma_0^1 + \dots + \Gamma_0^n $$

be the decompositions of $\Delta_0$ and $\Gamma_0$ as sums of simple diagrams. We have

$$ \Delta_0^1 + \dots + \Delta_0^m = (\Phi^{-1}\Psi) \circ (\Gamma_0^1 + \dots + \Gamma_0^n)^k \circ (\Phi^{-1}\Psi)^{-1}. $$

As a consequence of Lemma 3.14, $n=m$ and $\Phi^{-1}\Phi$ decomposes as a sum $\Omega_1 + \dots + \Omega_n$ such that $\Delta_0^i = \Omega_i \circ (\Gamma_0^i)^k \circ \Omega_i^{-1}$ for every $1 \le i \le n$. Fix an index $1 \le i \le n$ such that $\Delta_0^i$ contains at least one 2-cell. We deduce from Lemma 3.15 that

$$ \mathrm{Shift}(\Delta_0^i) = \mathrm{Shift}((\Gamma_0^i)^k), $$

which implies that $\Delta_0^i$ and $(\Gamma_0^i)^k$ have the same number of 2-cells. Because the number of 2-cells of $(\Gamma_0^i)^k$ coincides with $k$ times the number of 2-cells of $\Gamma_0^i$, it follows that $k$ is at most half the number of 2-cells of $\Delta_0^i$, and a fortiori of $\Delta_0$ and finally of $\Delta$. ■

### 3.3. Commutation problem

Centralisers in diagram groups are rather well understood. More precisely, see the following theorem.

**Theorem 3.16 ([45]).** Let $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$ be a semigroup presentation, $w \in \Sigma^+$ a base-word, and $g \in D(\mathcal{P}, w)$ an element. One can represent $g$ as

$$ \Gamma \cdot (\Delta_1^{n_1} + \dots + \Delta_r^{n_r}) \cdot \Gamma^{-1}, $$

where $\Gamma$ is some $(w, u_1 \cdots u_r)$-diagram and where each $\Delta_i$ is a simple absolutely reduced $(u_i, u_i)$-diagram with $\langle\Delta_i\rangle$ either trivial or a maximal cyclic subgroup in $D(\mathcal{P}, u_i)$. Then, the centraliser of $g$ coincides with

$$ \{\Gamma \cdot (\Omega_1 + \dots + \Omega_r) \cdot \Gamma^{-1} \mid \Omega_1 \in C_1, \dots, \Omega_r \in C_r\}, $$

where $C_i := \langle\Delta_i\rangle$ if $\Delta_i$ is non-trivial and $C_i := D(\mathcal{P}, u_i)$ otherwise.
As a consequence, the centraliser of an element in a diagram group is always isomorphic to the product of a free abelian group of finite rank with finitely many diagram groups given by the same semigroup presentation but possibly different base-words.

**Example 3.17.** Let $\mathcal{P}$ be the semigroup presentation $\langle x \mid x = x^2 \rangle$ and $g \in D(\mathcal{P}, x)$ the element represented by the following diagram:

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

By applying Theorem 3.16, we deduce that the centraliser of $g$ in $D(\mathcal{P}, x)$ is

$$ \{\Gamma \cdot (\Phi + \Delta^n + \Psi) \cdot \Gamma^{-1} \mid \Phi, \Psi \in D(\mathcal{P}, x), n \in \mathbb{Z}\}. $$

In particular, the centraliser is isomorphic to $F \times \mathbb{Z} \times F$. Notice that, in $D(\mathcal{P}, x)$ and a fortiori in $F$, all the centralisers are isomorphic to $\mathbb{Z}^m \times F^n$ for some $m, n \ge 0$.

Theorem 3.16 has a lot of interesting applications. The rest of the section is essentially dedicated to them.

**Corollary 3.18 ([47]).** In diagram groups, abelian subgroups are free.

*Proof.* Let $H$ be an abelian subgroup in a diagram group $G$. Our goal is to show that $H$ is *residually infinite cyclic*; i.e., for every non-trivial $h \in H$, there exists a morphism $\varphi : H \to \mathbb{Z}$ satisfying $\varphi(h) \neq 0$. This implies that $H$ embeds into a direct product of (infinitely many) cyclic groups. Such a product being free abelian, the desired conclusion follows.

So, let $h \in H$ be a non-trivial element. Decompose $h$ as

$$ \Gamma \cdot (\Delta_1^{n_1} + \cdots + \Delta_r^{n_r}) \cdot \Gamma^{-1}, $$

where $\Gamma$ is some $(w, u_1 \cdots u_r)$-diagram and where each $\Delta_i$ is a simple absolutely reduced $(u_i, u_i)$-diagram with $\langle \Delta_i \rangle$ either trivial or a maximal cyclic subgroup in $D(\mathcal{P}, u_i)$. Because $h$ is non-trivial, at least one of the $\Delta_i$ is non-trivial, say, $\Delta_k$. According to Theorem 3.16, the centraliser $C_G(h)$ of $h$ is

$$ \{\Gamma \cdot (\Omega_1 + \cdots + \Omega_r) \cdot \Gamma^{-1} \mid \Omega_1 \in C_1, \dots, \Omega_r \in C_r\}, $$

where $C_i := \langle \Delta_i \rangle$ if $\Delta_i$ is non-trivial and $C_i := D(\mathcal{P}, u_i)$ otherwise. The restriction to $H$ of the morphism $\varphi : C_G(h) \to \langle \Delta_k \rangle$ defined by

$$ \Gamma \cdot (\Omega_1 + \cdots + \Omega_r) \cdot \Gamma^{-1} \mapsto \Omega_k $$

satisfies $\varphi(h) \neq 1$. This concludes the proof of our corollary.

■
We saw with Propositions 2.20 and 2.21 that many right-angled Artin groups are
diagram groups. As another application of Theorem 3.16, we can show that there are
also many right-angled Artin groups that are not diagram groups.

**Corollary 3.19 ([47]).** Let $\Gamma$ be a triangle-free graph. If $\Gamma$ contains an induced cycle of odd length $\ge 5$, then the right-angled Artin group $A(\Gamma)$ is not a diagram group<fnref n="1" />.

*Sketch of proof.* Given a triangle-free graph $\Gamma$ with an induced cycle of odd length $\ge 5$, assume for contradiction that $A(\Gamma)$ is a diagram group, say, $D(\mathcal{P}, w)$ for some semigroup presentation $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ and some baseword $w \in \Sigma^+$.

Any spherical diagram over $\mathcal{P}$ can be conjugate to a sum of spherical diagrams,
and the number of non-trivial components depends only on the element of $D(\mathcal{P}, w)$
we are looking at. Say that an element of $D(\mathcal{P}, w)$ is *monocomponent* if it has only
one such component. Given two monocomponent elements $g_1, g_2 \in D(\mathcal{P}, w)$, we
write $g_1 < g_2$ whenever there exist a $(w, xuyvz)$-diagram $\Gamma$ and simple absolutely
reduced $(u, u)$- and $(v, v)$-diagrams $\Psi_1$ and $\Psi_2$ such that

$$
g_1 = \Gamma \cdot (\varepsilon(x) + \Psi_1 + \varepsilon(yvz)) \cdot \Gamma^{-1} \quad \text{and} \quad g_2 = \Gamma \cdot (\varepsilon(xuy) + \Psi_2 + \varepsilon(z)) \cdot \Gamma^{-1}.
$$

It can be verified that < is transitive and antisymmetric, and that any two commuting
monocomponent elements that do not belong to the same cyclic subgroup are <-
comparable. See [47] for details.

Now, let $s_0, \dots, s_{2n} \in D(\mathcal{P}, w)$ denote the generators of $A(\Gamma)$ given by an induced cycle of odd length $\ge 5$. It follows from the description of centralisers in right-angled Artin groups [64] that the centraliser of each $s_i$ is $\langle s_{i-1}, s_i, s_{i+1} \rangle \simeq \mathbb{Z} \times \mathbb{F}_2$; in particular, its centre is infinite cyclic. We deduce from Theorem 3.16 that the $s_i$ are monocomponent.

Assume without loss of generality that $s_0 < s_1$. We cannot have $s_1 < s_2$ since otherwise this would imply that $s_0 < s_2$, which is impossible since $s_0$ and $s_2$ do not commute. Therefore, we have $s_2 < s_1$. Similarly, we cannot have $s_3 < s_2$ since otherwise we would have $s_3 < s_1$ and $s_3$ would commute with $s_1$. Hence, $s_2 < s_3$. Iterating the argument, we find that

$$
s_0 < s_1, s_1 < s_2, s_2 < s_3, \dots, s_{2n-1} < s_{2n}, s_{2n} < s_0.
$$

It follows that $s_{2n}$ commutes with $s_1$ since $s_{2n} < s_1$, a contradiction. $\blacksquare$

<footnote n="1">¹Reference [47, Theorem 30] only proves that a right-angled Artin group defined by a cycle of odd length $\ge 5$ is not a diagram group, but the proof can be repeated without any modification to deduce our corollary. In fact, our statement is not optimal either, [47, Theorem 30] proves that a diagram group does not contain elements $g_0, \dots, g_{2n}$ such that $g_i$ commutes with $g_{i+1}$ for every $i \in \mathbb{Z}_{2n+1}$, such that the centraliser of each $g_i$ has a cyclic centre, and such that $g_i$ and $g_{i+1}$ do not belong to the same cyclic subgroup for every $i \in \mathbb{Z}_{2n+1}$.</footnote>
An interesting consequence of Theorem 3.16 is that nilpotent subgroups in diagram groups must be abelian (and a fortiori free abelian according to Corollary 3.18). This assertion will follow from the next statement.

**Theorem 3.20 ([47]).** For subgroup in a diagram group, the centre and the commutator subgroup intersect trivially.

*Proof.* Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation, $w \in \Sigma^+$ a baseword, and $H$ a subgroup of $D(\mathcal{P}, w)$. Assume that the centre of $H$ contains a non-trivial element $h \in H$; otherwise, there is nothing to prove. Decompose $h$ as

$$ \Gamma \cdot (\Delta_1^{n_1} + \cdots + \Delta_r^{n_r}) \cdot \Gamma^{-1}, $$

where $\Gamma$ is some $(w, u_1 \cdots u_r)$-diagram and where each $\Delta_i$ is a simple absolutely reduced $(u_i, u_i)$-diagram with $\langle \Delta_i \rangle$ either trivial or a maximal cyclic subgroup in $D(\mathcal{P}, u_i)$. For any two $a, b \in H$, it follows from Theorem 3.16 that we can write

$$ a = \Gamma \cdot (A_1 + \cdots + A_r) \cdot \Gamma^{-1} \quad \text{and} \quad b = \Gamma \cdot (B_1 + \cdots + B_r) \cdot \Gamma^{-1}, $$

where, for each $1 \le i \le r$, $A_i$ and $B_i$ belong to $\langle \Delta_i \rangle$ if $\Delta_i$ is non-trivial and to $D(\mathcal{P}, u_i)$ otherwise. Then

$$ [a, b] = \Gamma \cdot ([A_1, B_1] + \cdots + [A_r, B_r]) \cdot \Gamma^{-1}. $$

Observe that, for every $1 \le i \le r$ such that $\Delta_i$ is non-trivial, $[A_i, B_i]$ must be trivial. Consequently, a product of commutators of elements in $H$ decomposes as

$$ \Gamma \cdot (C_1 + \cdots + C_r) \cdot \Gamma^{-1}, $$

where each $C_i$ is trivial if $\Delta_i$ is non-trivial. This implies that $h$ cannot be written as a product of commutators in $H$. $\blacksquare$

**Corollary 3.21 ([47]).** Nilpotent subgroups in diagram groups are abelian.

*Proof.* For every $k \ge 2$, a $k$-step nilpotent group always contains a 2-step nilpotent group. But being a 2-step nilpotent group precisely means that its commutator subgroup is non-trivial and contains in its centre. Thus, it follows from Theorem 3.20 that nilpotent subgroups in diagram groups are 1-step nilpotent, i.e., abelian. $\blacksquare$

It is worth noticing that, even though diagram groups do not contain interesting nilpotent groups, they may contain interesting solvable groups. For instance, we saw in Section 2.4 that the wreath product $Z \rtimes Z$, which is metabelian, is a diagram group; as well as the iterated wreath product (($Z \rtimes Z$) $\rtimes \cdots$) $\rtimes Z$. In fact, it is contained in many diagram groups. It is proved in [47] that a diagram group $D(\mathcal{P}, w)$ contains
a subgroup isomorphic to $\mathbb{Z} \subsetneq \mathbb{Z}$ if and only if there exist words $x, y, z$ such that $D(\mathcal{P}, z) \neq \{1\}$ and the equalities

$$w = xy, \quad x = xz, \quad y = zy$$

hold modulo $\mathcal{P}$. This includes, for instance, Thompson's group $F$.

We saw with Corollary 3.18 that abelian subgroups in diagram groups are necessarily free. In fact, we can be more precise and describe the structure of abelian subgroups in terms of diagrams.

**Theorem 3.22** ([47]). Let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. For all pairwise commuting elements $g_1, \dots, g_m \in D(\mathcal{P}, w)$, there exist a $(w, v_1 \cdots v_n)$-diagram $\Gamma$ and $(v_j, v_j)$-diagrams $\Delta_j$ such that

$$g_i = \Gamma \cdot (\Delta_1^{p_{i1}} + \cdots + \Delta_n^{p_{in}}) \cdot \Gamma^{-1} \quad \text{for some } p_{i1}, \dots, p_{in} \in \mathbb{Z}$$

for every $1 \le i \le m$. Moreover, the diagrams $\Delta_1, \dots, \Delta_n$ can be chosen either trivial or simple and absolutely reduced.

As a consequence, one can show that abelian subgroups in diagram groups are undistorted.

**Corollary 3.23** ([47]). In diagram groups, finitely generated abelian subgroups are undistorted.

*Proof.* Given a diagram group, let $A$ be a finitely generated abelian subgroup. Fix a finite generating set $\{g_1, \dots, g_m\}$ in $A$. According to Theorem 3.22, there exist a $(w, v_1 \cdots v_n)$-diagram $\Gamma$ and $(v_j, v_j)$-diagrams $\Delta_j$ such that

$$g_i = \Gamma \cdot (\Delta_1^{p_{i1}} + \cdots + \Delta_n^{p_{in}}) \cdot \Gamma^{-1} \quad \text{for some } p_{i1}, \dots, p_{in} \in \mathbb{Z}$$

for every $1 \le i \le m$. Moreover, we can choose the diagrams $\Delta_1, \dots, \Delta_n$ either trivial or simple and absolutely reduced. Let $A^+$ denote the abelian subgroup freely generated by

$$\{\Gamma \cdot (\varepsilon(u_1 \cdots u_{k-1}) + \Delta_k + \varepsilon(u_{k+1} \cdots u_n)) \cdot \Gamma^{-1} \mid 1 \le k \le n \text{ with } \Delta_k \text{ non-trivial}\}.$$

It suffices to show that $A^+$ is undistorted in our diagram group in order to conclude. So, let $H$ be a finitely generated subgroup containing $A^+$. On the one hand, if $|\cdot|$ denotes the word length of $A^+$ given by our free basis, then it is clear that

$$|a| - 2\#(\Gamma) \le \#(a) \le |a| \cdot \max\{\#(\Delta_i), 1 \le i \le n\} + 2\#(\Gamma)$$

for every $a \in A^+$. And, on the other hand, if we fix a generating set $\{s_1, \dots, s_r\}$ of $H$ and a shortest representative $m = m(s_1, \dots, s_r)$ of a given element $a \in A^+$, then

$$\#(a) = \#(m) \le \text{length}(m) \cdot \max\{\#(s_i), 1 \le i \le r\}.$$
Thus, the length in $\mathcal{H}$ of an element in $\mathcal{A}^+$ is bounded below by its length in $\mathcal{A}^+$. This
concludes the proof of our corollary. $\blacksquare$

**3.4. Membership problem for the commutator subgroup**

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. Our goal
in this section is to describe a natural morphism $\alpha : D(\mathcal{P}, w) \to \mathcal{A}(\mathcal{P})$ from our
diagram group $D(\mathcal{P}, w)$ to some free abelian group $\mathcal{A}(\mathcal{P})$ whose kernel coincides
with commutator subgroup of $D(\mathcal{P}, w)$. The motivation being to solve efficiently the
membership problem for the commutator subgroup of $D(\mathcal{P}, w)$ in terms of diagrams,
as soon as the word problem is solvable in $\mathcal{P}$.

So, let $\mathcal{A}(\mathcal{P})$ denote the free abelian group generated by $\mathcal{M} \times \mathcal{R} \times \mathcal{M}$, where $\mathcal{M}$ denotes the monoid given by $\mathcal{P}$. Given a diagram $\Delta$ over $\mathcal{P}$, we associate to each cell $\pi$ of $\Delta$ an element $\eta(\pi)$ of $\mathcal{M} \times \mathcal{R} \times \mathcal{M}$ as follows. The top and bottom paths of $\pi$ meet at two points: a source $\iota(\pi)$ and a sink $\tau(\pi)$. All the oriented paths in $\Delta$ from the source of $\Delta$ to $\iota(\pi)$ are labelled by positive words representing the same element in the monoid $\mathcal{M}$; let $\ell(\pi)$ denote this element. Similarly, all the oriented paths in $\Delta$ from $\tau(\pi)$ to the sink of $\Delta$ are labelled by positive words representing the same element in the monoid $\mathcal{M}$; let $r(\pi)$ denote this element. If $\pi$ is labelled by the relation $u = v$ with $(u = v) \in \mathcal{R}$ (resp., $(v = u) \in \mathcal{R}$), then we set $\eta(\pi) := (\ell(\pi), u = v, r(\pi))$ (resp., $-(\ell(\pi), v = u, r(\pi)))$. Finally, we define

$$
\alpha(\Delta) := \sum_{\pi \text{ cell of } \Delta} \eta(\pi) \in \mathcal{A}(\mathcal{P}).
$$

Let us consider an explicit example in order to illustrate our definition. Take the
presentation

$$
\mathcal{P} := \langle x, a_i, b_i (i \ge 1) \mid x = x^2, a_i = a_{i+1}x, b_i = xb_{i+1} (i \ge 1) \rangle
$$

from Proposition 2.19 and the following diagram $\Delta$:

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

First of all, observe that $a_i x^n = a_1$ and $x^n b_i = b_1 \mod \mathcal{P}$ for all $i, n \ge 1$. Indeed,
we have

$$
a_i x^n = a_{i+1} x^{n+1} = a_{i+1} x = a_i \mod \mathcal{P}
$$
for all $i, n \ge 1$, and

$$a_1 = a_2 x = a_2 = a_3 x = a_3 = \dots \mod \mathcal{P}.$$

We argue similarly for the equality mod $\mathcal{P}$ with $b_1$. This allows us to deduce that

$$\begin{align*}
\eta(\pi_5) &= -(1, a_1 = a_2 x, x b_1) = -(1, a_1 = a_2 x, b_1) = -\eta(\pi_1), \\
\eta(\pi_6) &= -(a_2 x, b_1 = x b_2, 1) = -(a_1, b_1 = x b_2, 1) = -\eta(\pi_2),
\end{align*}$$

and

$$\eta(\pi_4) = -(a_2 x, x = x^2, b_2) = -(a_2, x = x^2, b_1) = -\eta(\pi_3).$$

Therefore,

$$\alpha(\Delta) = \eta(\pi_1) + \dots + \eta(\pi_6) = 0.$$

Coming back to the general case, the main result of interest for us is the following.

**Proposition 3.24** ([45]). Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. The kernel of $\alpha : D(\mathcal{P}, w) \to \mathcal{A}(\mathcal{P})$ coincides with the commutator subgroup of $D(\mathcal{P}, w)$.

We emphasise that $\alpha$ is not surjective in general, so we cannot identify $\mathcal{A}(\mathcal{P})$ with the abelianisation of $D(\mathcal{P}, w)$. In fact, $\mathcal{A}(\mathcal{P})$ is usually much bigger than the abelianisation.

An idea to prove Proposition 3.24 is the following. If $\mathcal{P}$ is a complete semigroup presentation, then Theorem 3.2 provides a presentation of $D(\mathcal{P}, w)$. Given an element $\Delta$ in the kernel of $\alpha$, we write it as a product of generators from our presentation, say, $\Delta = \Phi_1 \cdots \Phi_n$. Using the fact that

$$0 = \alpha(\Delta) = \alpha(\Phi_1) + \dots + \alpha(\Phi_n),$$

we deduce that $\Delta$ can be written as a product of commutators. This argument shows that Proposition 3.24 holds for complete semigroup presentation. The general case is then deduced thanks to Lemma 3.6. See [45, Theorem 11.3] for a detailed proof.

**Example 3.25.** Thanks to Proposition 3.24, we deduce that the diagram $\Delta$ from our previous example belongs to the commutator subgroup of the corresponding diagram group. This is not surprising since the diagram group coincides with $F'$, a simple group. Nevertheless, it can easily verified thanks to Propositions 3.24 and 2.19 that $F'$ is perfect.

**Example 3.26.** Let $\mathcal{P} = \langle x | x = x^2 \rangle$ be the semigroup presentation naturally associated to Thompson's group $F$. Because $\mathcal{P}$ has a single relation and because the monoid defined by $\mathcal{P}$ contains exactly two elements, namely, 1 and $x$, let us say that the
abelian group $\mathcal{A}(\mathcal{P})$ is freely generated by $\{1, x\}^2$. Given a reduced diagram $\Delta$ over $\mathcal{P}$, observe that the top cell is sent to (1, 1) under $\eta$, that the bottom cell is sent to $-(1, 1)$ under $\eta$, and that no other cell is sent to $\pm(1, 1)$. We refer to a cell sent to $\pm(1, x)$ as left, to a cell sent to $\pm(x, 1)$ as right, and to a cell sent to $\pm(x, x)$ as internal. Remember that the cells of $\Delta$ labelled by $x = x^2$ (resp., $x^2 = x$) are called positive (resp., negative); this convention is compatible with the sign of the image of a cell under $\eta$. We have

$$ \alpha(\Delta) = \begin{array}{c} \text{\# of pos. left cells} \\ \text{\# of neg. left cells} \end{array} (1, x) + \begin{array}{c} \text{\# of pos. right cells} \\ \text{\# of neg. right cells} \end{array} (x, 1) + \begin{array}{c} \text{\# of pos. internal cells} \\ \text{\# of neg. internal cells} \end{array} (x, x). $$

Thus, $\Delta$ belongs to the commutator subgroup of $D(\mathcal{P}, w)$ if and only if $\Delta$ has the same number of positive and negative left cells and the same number of positive and negative right cells. (The number of positive and negative cells is the same; these two equalities automatically imply that $\Delta$ has the same number of positive and negative internal cells as well.)

### 3.5. Foldings and closed subgroups

The method of folding graphs [65] has been quite influential in the study of free groups and has been generalised in various directions. Interestingly, thinking of a diagram groups as second fundamental groups of directed 2-complexes, foldings appear naturally in a similar way. This allows us, in particular, to solve the membership problem for some subgroups.

First of all, let us recall how to solve the membership problem in free groups thanks to folding. In other words, given a free group $F$ and elements $g, h_1, \dots, h_n \in F$, we want to determine whether or not $g$ belongs to the subgroup $H := \langle h_1, \dots, h_n \rangle$. We fix a free basis $s_1, \dots, s_r$ of $F$ and we think of $F$ as the fundamental group of a bouquet $\Omega$ of $r$ circles, each oriented and labelled by a generator $s_i$. To $H$, we associate a bouquet $\Gamma_0$ of $n$ circles, each subdivided and labelled by a generator $h_i$. Observe that both $\Omega$ and $\Gamma_0$ have a distinguished vertex.

Now, we fold $\Gamma_0$. More precisely, if two edges of $\Gamma_0$ share an endpoint and have the same image in $\Omega$, then we identify it. After finitely many folds $\Gamma_0 \to \dots \to \Gamma_k$, one gets a graph $\Gamma_k$ with a locally injective map $\iota: \Gamma_k \to \Omega$ such that $H$ coincides with the image under $\iota$ of the fundamental group of $\Gamma_k$ in the fundamental group of $\Omega$. (The basepoints defining the fundamental groups being the distinguished vertices.) The key property is that an element of $F$ belongs to $H$ if and only if the reduced word $w$ representing it is accepted by $\Gamma_k$, i.e., there is a loop in $\Gamma_k$ based at the
<figure><img src="image_17.png" /><figcaption>**Figure 7.** Foldings for $\langle ab^{-1}a, abab^{-1}, a^2b^{-1} \rangle$ in $\langle a, b | \rangle$.</figcaption></figure>

distinguished vertex which is labelled by $w$. As an illustration, one deduces from Figure 7 that $ba^{-1}b^{-2}aba^{-2}$ belongs to $\langle ab^{-1}a, abab^{-1}, a^2b^{-1} \rangle$, but $ba^{-3}b^2$ does not.

This method for finite graphs can be naturally adapted to finite directed 2-complexes. This has been done by V. Guba and M. Sapir in the late 1990s (unpublished), but it first appeared in print in [43].

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. We think of the diagram group $D(\mathcal{P}, w)$ as the second fundamental group of the directed 2-complex $\mathcal{X}(\mathcal{P})$ based at the 1-path labelled by $w$. See Section 2.3 for the relevant definitions. We fix some spherical diagrams $\Delta, \Delta_1, \dots, \Delta_n \in D(\mathcal{P}, w)$, and we would like to know whether $\Delta$ belongs to the subgroup $H := \langle \Delta_1, \dots, \Delta_n \rangle$.

To $H$ we associate the directed 2-complex $X_0$ obtained by identifying all the top and bottom paths of the $\Delta_i$ to a single segment. Topologically, $X_0$ can be thought of as a bouquet of 2-spheres pairwise intersecting along a fixed segment. Observe that there is a natural morphism of directed 2-complexes $X_0 \to \mathcal{X}(\mathcal{P})$ and that both $\mathcal{X}(\mathcal{P})$ and $X_0$ have a distinguished 1-path. A *folding* refers to the following operation: if one sees two cells in $X_0$ sharing their top or bottom paths and having the same image in $\mathcal{X}(\mathcal{P})$, then we identify them. After finitely many folds $X_0 \to \dots \to X_k$, one gets a directed 2-complex $X_k$ with a locally injective morphism $X_k \to \mathcal{X}(\mathcal{P})$.

Define the closure $\mathrm{Cl}(H)$ of $H$ as the subgroup of $D(\mathcal{P}, w)$ given by the diagrams accepted by $X_k$, i.e., the image of the second fundamental group of $X_k$ based at its distinguished 1-path under the morphism $X_k \to \mathcal{X}(\mathcal{P})$. (It can be shown that the closure of a subgroup does not depend on a particular choice of generators.) By
construction, the closure of $H$ contains $H$, but, contrary to the case of free groups, it
can be bigger. One can say that the closure of a subgroup is itself a diagram group, but
subgroups of diagram groups may not be diagram groups themselves, so there must
exist subgroups properly contained in their closure. In fact, it is easy to construct
subgroups distinct from their closures. Indeed, if $\Delta$ is a diagram decomposing as a
sum of two spherical diagrams $\Delta_1 + \Delta_2$, then the closure of $\langle\Delta\rangle$ contains $\Delta_1 + \varepsilon(u_2)$
and $\varepsilon(u_1) + \Delta_2$, where each $\varepsilon(u_i)$ denotes the trivial diagram having the same label
as the top and bottom paths of $\Delta_i$. Indeed, when identifying the top and bottom paths
of $\Delta$, we do not get a topological sphere, but a pointed sum of two spheres due to
the cut-point separating $\Delta_1$ and $\Delta_2$ in $\Delta$. It is conjectured that this phenomenon
is essentially the only obstruction for a subgroup to coincide with its closure. See
[41, Conjecture 3.11] for a precise statement.

In conclusion, for every diagram group, there exists an algorithm that decides,
given spherical diagrams $\Delta$, $\Delta_1, \dots, \Delta_n$, whether or not $\Delta$ belongs to the closure
of the subgroup $\langle\Delta_1, \dots, \Delta_n\rangle$. In particular, the membership problem is solvable for
*closed subgroups* (i.e., subgroups that coincide with their closures).

# 4. Median geometry

## 4.1. Crash course on median geometry

In this preliminary section, we record some basic definitions and results related to median graphs that will be used in the next sections.

**Definition 4.1.** A connected graph $X$ is *median* if, for all vertices $x_1, x_2, x_3 \in X$, there exists a unique vertex $m \in X$ satisfying

$$d(x_i, x_j) = d(x_i, m) + d(m, x_j) \quad \text{for all } i \neq j.$$

We refer to this vertex $m$ as the *median point* of $x_1, x_2, x_3$.

Examples include of course simplicial trees, the median point of a triple of vertices corresponding to the centre of the tripod they delimit. A product of median graphs is still median, so the product of trees is also median graphs. This includes in particular (one-skeleta of) cubes of arbitrary dimensions (see Figure 8).

A fundamental idea is that the geometry of a median graph is essentially encoded in the combinatorics of its *hyperplanes*.

**Definition 4.2.** Let $X$ be a median graph. A (an *oriented*) *hyperplane* $J$ is an equivalence class of (oriented) edges with respect to the transitive closure of the relation that identifies two (oriented) edges when they are opposite sides of a 4-cycle.
<figure><img src="image_18.png" /><figcaption>**Figure 8.** Examples of median graphs and median points.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>**Figure 9.** Hyperplanes in a median graph and its cube-completion. The red hyperplane is transverse to the green and yellow hyperplanes. Green and yellow hyperplanes are tangent.</figcaption></figure>

• If $X \setminus J$ denotes the graph obtained from $X$ by removing all the edges of $J$, then a connected component of $X \setminus J$ is a *half-space*. Two subsets $A, B \subset X$ are *separated* by $J$ if they lie in distinct half-spaces delimited by $J$.

• Two hyperplanes $J_1$ and $J_2$ are *transverse* if there exist two intersecting edges $e_1 \subset J_1$ and $e_2 \subset J_2$ that span a 4-cycle.

• They are *tangent* if there exist two intersecting edges $e_1 \subset J_1$ and $e_2 \subset J_2$ that do not span a 4-cycle.

See Figure 9 for a few examples.

The previous claim is mainly motivated by the following statement.

**Theorem 4.3** ([62]). Let $X$ be a median graph. The following assertions hold:

• Every hyperplane $J$ separates $X$. More precisely, $X \setminus J$ has exactly two connected components, which turn out to be convex.

• A path in $X$ is a *geodesic* if and only if it crosses each hyperplane at most once.

• The distance between two vertices $x, y \in X$ coincides with the number of hyperplanes separating $x, y$.
In geometric group theory, median graphs are better known as CAT(0) *cube complexes*.

**Definition 4.4.** A cube complex is *nonpositively curved* if the links of its vertices are flag simplicial complexes.

Recall that the *link* of a vertex $x$ is the complex whose vertices are the (half)edges starting from $x$ and whose simplices are given by edges that span a cell. Typically, the link of a vertex should be thought of as a small ball around the vertex, endowed with the cellular structure induced by the whole complex. A complex is *flag* if, for all $n \ge 1$, any $n+1$ vertices span an $n$-simplex if and only if they are pairwise adjacent.

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

The terminology is justified by the fact that a cube complex, when endowed by the length metric extending the Euclidean metrics of its cubes, is *locally CAT(0)* exactly when it is nonpositively curved [44, 56]. As a consequence, a cube complex endowed with the same metric is CAT(0) if and only if it is simply connected and nonpositively curved. We refer to [9] for more information on CAT(0) geometry. It turns out that CAT(0) cube complexes and median graphs define essentially the same objects. More precisely, see the following theorem.

**Theorem 4.5** ([17, 40, 61]). *A graph is median if and only if its cube-completion is simply connected and nonpositively curved.*

Here, given a graph $X$, its *cube-completion* refers to the cube complex $X_\square$ obtained by filling with cubes all the subgraphs isomorphic to one-skeleta of cubes.

Usually, hyperplanes are thought of slightly differently in cube-completions of median graphs: they are thought of as unions of *midcubes*. See Figure 9. The terminology related to hyperplanes in median graphs can be easily adapted for this alternative point of view.

The following observation can be thought of as a consequence of the CAT(0)ness of the cube complexes under consideration, but it can also be proved directly thanks to the combinatorics of hyperplanes.

**Proposition 4.6.** *Cube-completions of median graphs are contractible.*

For more information on median graphs, or equivalently CAT(0) cube complexes, we refer to [30, 63].
## 4.2. Median geometry of diagram groups

In this section, we show that diagram groups act on median graphs. These median graphs can be described in several equivalent ways. For now, we give a direct and explicit definition and postpone more conceptual characterisations.

**Definition 4.7.** Let $\mathcal{P}$ be a semigroup presentation. Let $M(\mathcal{P})$ denote the graph whose vertices are the diagrams over $\mathcal{P}$ modulo dipole reduction and whose edges connect two diagrams whenever one can be obtained from another by right-concatenation by an *atomic diagram* (i.e., a diagram with a single 2-cell).

In other words, the vertices are given by reduced diagrams and one passes from a vertex to a neighbour by gluing below a 2-cell. In the sequel, vertices of $M(\mathcal{P})$ will be often thought of as reduced diagrams (see Figure 10 below).

One easily verifies that two diagrams belong to the same connected component of $M(\mathcal{P})$ if and only if their top paths have the same label. Given a word $w \in \Sigma^+$, we denote by $M(\mathcal{P}, w)$ the connected component of $M(\mathcal{P})$ containing the diagrams whose top paths are labelled by $w$.

Notice that the diagram group $D(\mathcal{P}, w)$ naturally acts on $M(\mathcal{P}, w)$ by left multiplication.

It is worth noticing that, since edges of $M(\mathcal{P})$ are labelled by atomic diagrams, the paths in $M(\mathcal{P})$ are naturally labelled by the diagrams obtained by concatenating the atomic diagrams given by the edges along the path. Whether such a diagram is reduced characterises the geodesics in $M(\mathcal{P})$. More precisely, see the following lemma.

**Lemma 4.8.** Let $\mathcal{P}$ be a semigroup presentation, $w \in \Sigma^+$ a baseword, and $\Phi, \Psi \in M(\mathcal{P}, w)$ two vertices. A path

$$ \Phi, \Phi \circ \Delta_1, \Phi \circ \Delta_1 \circ \Delta_2, \dots, \Phi \circ \Delta_1 \circ \dots \circ \Delta_n = \Psi $$

is a geodesic if and only if the diagram $\Delta_1 \circ \dots \circ \Delta_n$ is reduced. As a consequence, the distance between $\Phi$ and $\Psi$ in $M(\mathcal{P}, w)$ coincides with the number $\#(\Phi^{-1}\Psi)$ of 2-cells in the reduction of $\Phi^{-1}\Psi$.

<figure><img src="image_21.png" /><figcaption>**Figure 10.** A piece of $M(\mathcal{P}, x^3)$ for $\mathcal{P} = \langle x | x = x^2 \rangle$.</figcaption></figure>
*Proof.* It is clear that any path from $\Phi$ to $\Psi$ must have length at least $\#(\Phi^{-1}\Psi)$, and that there exists at least one such path of this length. So, the distance between $\Phi$ and $\Psi$ in $M(\mathcal{P}, w)$ coincides with $\#(\Phi^{-1}\Psi)$. Therefore, our path is a geodesic if and only if $\Delta_1 \circ \cdots \circ \Delta_n = \Phi^{-1}\Psi$ with $n = \#(\Phi^{-1}\Psi)$. The only possibility is that there is no dipole in $\Delta_1 \circ \cdots \circ \Delta_n$, which amounts to saying that $\Delta_1 \circ \cdots \circ \Delta_n$ is reduced. ■

The following theorem is the main result of this section.

**Theorem 4.9** ([24]). Let $\mathcal{P}$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. Then, $M(\mathcal{P}, w)$ is a median graph, locally of finite cubical dimension, on which $D(\mathcal{P}, w)$ acts freely. The action is cocompact if and only if $[w]_{\mathcal{P}}$ is finite.

Here, we use the notation

$$[w]_{\mathcal{P}} := \{m \in \Sigma^+ \mid m = w \mod \mathcal{P}\}.$$

We are going to give two proofs of Theorem 4.9. The first one verifies that every triple of vertices admits a unique median point thanks to the description of the geodesics provided by Lemma 4.8; and the second proof applies the characterisation of median graphs provided by Theorem 4.5.

*First proof of Theorem 4.9.* Let $\Delta_0, \Delta_1, \Delta_2$ be three reduced diagrams representing three vertices of $M(\mathcal{P}, w)$. Up to conjugating by $\Delta_0$, we can assume without loss of generality that $\Delta_0$ has no cell. (Notice that this operation may modify the baseword $w$.) Let $\Delta$ be the biggest common prefix of $\Delta_1$ and $\Delta_2$. (Given two diagrams $\Phi, \Psi$, one says that $\Phi$ is a prefix of $\Psi$ if $\Psi$ decomposes as a concatenation $\Phi \circ \Gamma$ for some diagram $\Gamma$.) The fact that $\Delta$ is a common prefix of $\Delta_1$ and $\Delta_2$ implies that $\Delta$ belongs to geodesics from $\Delta_0$ to $\Delta_1$ and from $\Delta_0$ to $\Delta_2$. And the maximality of this prefix assures that, if we decompose $\Delta_1$ (resp., $\Delta_2$) as $\Delta \circ \Gamma_1$ (resp., $\Delta \circ \Gamma_2$), then $\Gamma_1 \circ \Gamma_2^{-1}$ is reduced. This implies that $\Delta$ also belongs to a geodesic between $\Delta_1$ and $\Delta_2$. Thus, $\Delta$ provides a median point for $\Delta_0, \Delta_1, \Delta_2$.

If $\Xi$ is a median point of $\Delta_0, \Delta_1, \Delta_2$, then $\Xi$ must be a common prefix of $\Delta_1$ and $\Delta_2$, and consequently a prefix of $\Delta$. Decompose $\Delta$ as $\Xi \circ \Omega$. Because $\Xi$ belongs to a geodesic between $\Delta_1$ and $\Delta_2$, the concatenation $(\Omega \circ \Gamma_1)^{-1}(\Omega \circ \Gamma_2)$ must be reduced. In other words, $\Omega$ cannot have any cell, hence $\Xi = \Delta$. ■

*Second proof of Theorem 4.9.* According to Theorem 4.5, it suffices to show that the cube-completion $M_{\square}(\mathcal{P}, w)$ is simply connected and nonpositively curved.

We begin by describing the cubes in $M_{\square}(\mathcal{P}, w)$. A *thin diagram* is a sum of atomic diagrams (see Definition 3.10). Given a diagram $\Delta \in M(\mathcal{P}, w)$ and thin diagram $\Psi$ with top label equal to the bottom label of $\Delta$, the vertices $\{\Delta \circ \Psi_0 | \Psi_0 \text{ prefix of } \Psi\}$ span an $n$-cube if $\Psi$ has $n$ cells. One can show that all the cubes in $M_{\square}(\mathcal{P}, w)$ are of this form.
As a consequence, given a vertex $\Delta \in M_{\square}(\mathcal{P}, w)$, if $w$ denotes the bottom label of $\Delta$ then the link of $\Delta$ is isomorphic to the simplicial complex whose vertices are the subwords of $w$ which are part of a relation from $\mathcal{R}$ and whose simplices are given by pairwise disjoint subwords. Clearly, such a complex is flag, so $M_{\square}(\mathcal{P}, w)$ is nonpositively curved.

Now, let us show that every compact subcomplex in $M_{\square}(\mathcal{P}, w)$ is contractible. More precisely, given a finite set of vertices $S$, we claim that the subcomplex spanned by $\bar{S} := \{\Delta \mid \exists \Omega \in S, \Delta \text{ prefix of } \Omega\}$ is contractible. According to Lemma 4.8, $\bar{S}$ coincides with the union of all the geodesics from the trivial diagram to the vertices in $S$. Fix a reduced diagram $\Delta \in \bar{S}$ with a maximal number of cells (which amounts to saying that the distance from the trivial diagram to $\Delta$ is maximal). Decompose $\Delta$ as the concatenation $\Delta_0 \circ \Gamma$ where $\Gamma$ is a thin diagram containing all the cells of $\Delta$ whose bottom paths lie in the bottom path of $\Delta$. (In other words, $\Gamma$ is the maximal thin suffix of $\Delta$.) If $\Gamma$ has $n$ cells, let $\Delta_1, \dots, \Delta_n$ denote the diagrams obtained from $\Delta$ by removing a single cell from $\Gamma$. Then

$$ \bar{S} = \underbrace{S \setminus \{\Delta\} \cup \{\Delta_1, \dots, \Delta_n\}}_{=: R} \cup \underbrace{\{\Delta_0 \circ \Gamma_0 \mid \Gamma_0 \text{ prefix of } \Gamma\}}_{n\text{-cube}} $$

Thus, $\bar{S}$ deformation retracts onto $\bar{R}$. During the replacement, observe that the following quantity:

$$ \left( \substack{\text{maximal number of cells} \\ \text{of a diagram in } S} \quad \substack{\text{number of vertices with a} \\ \text{maximal number of cells}} \right), $$

ordered with respect to the lexicographic order, decreases. Therefore, the process has to stop after finitely many steps. Necessarily, the final step corresponds to the situation where our set of vertices is reduced to the trivial diagram. ■

Interestingly, the median geometry of diagram groups can replace the combinatorics of diagrams in some arguments. We record some of examples below.

*Second proof of Theorem 2.22.* Let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation and let $w \in \Sigma^+$ be a baseword. A finite-order isometry of a median graph has to stabilise (the one-skeleton of) a cube (for instance, combine [66, Lemma 2.1.3] with [5]). Because cube-stabilisers are vertex-stabilisers for the action of $D(\mathcal{P}, w)$ on $M(\mathcal{P}, w)$, the fact that $D(\mathcal{P}, w)$ acts freely on $M(\mathcal{P}, w)$ immediately implies that $D(\mathcal{P}, w)$ is torsion-free. ■

*Proof of a weak version of Theorem 2.23.* If a group acts properly on a median graph, then its finitely generated abelian subgroups are automatically undistorted [18, Corollary 6.B.5] and its polycyclic subgroups are automatically virtually abelian [18, Corollary 6.C.8]. ■
Second proof of Proposition 2.27. Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. Given an isometry of a median graph, if no power inverts a hyperplane (i.e., stabilises the hyperplane but swaps the two halfspaces it delimits), then it acts as a translation on a bi-infinite geodesic lines [52]. Because $D(\mathcal{P}, w)$ acts on $M(\mathcal{P}, w)$ with no inversion, it follows that a non-trivial element $g \in D(\mathcal{P}, w)$ does act as a translation on some bi-infinite geodesic. This amounts to saying that there exists a diagram $\Delta$ and a geodesic $[\Delta, g\Delta]$ from $\Delta$ to $g\Delta$ such that the concatenation

$$ \bigcup_{n \in \mathbb{Z}} b^n \cdot [\Delta, g\Delta] $$

is a geodesic. Observe that the translation length $\tau(g)$ of $g$ is

$$ d(\Delta, g\Delta) = \#(g). $$

Now, if $a, b \in D(\mathcal{P}, w) \setminus \{1\}$ and $k \neq 0$ are such that $a = b^k$, then

$$ \#(a) = \tau(a) = |k| \cdot \tau(b) = |k| \cdot \#(b), $$

which implies that

$$ |k| \leq \#(a)/2. \qquad \blacksquare $$

As already mentioned, there are several equivalent but more conceptual view on the median graph given by Definition 4.7. Below, we record three of them.

**Cayley graph of the diagram groupoid.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. Recall from Section 2.2 that the diagram groupoid $D(\mathcal{P})$ is defined as the set of diagrams over $\mathcal{P}$ up to dipole reduction endowed with the concatenation of diagrams. Because every diagram can be constructed by adding one 2-cell at a time, the atomic diagrams generate the groupoid $D(\mathcal{P})$. It follows directly from Definition 4.7 that $M(\mathcal{P})$ coincides with the Cayley graph of $D(\mathcal{P})$ with respect to the generating set given by the atomic diagrams, i.e., the graph whose vertices are the elements of $D(\mathcal{P})$ and whose edges connect one element to another if one can be obtained from the other by right-multiplying by a generator.

This observation is compatible with our analogy between diagram groups and free groups.

<table><thead><tr><td>Free groups</td><td>Diagram groups</td></tr></thead><tbody><tr><td>Letters</td><td>2-cells</td></tr><tr><td>Free generators</td><td>Atomic diagrams</td></tr><tr><td>Words</td><td>Semigroup diagrams</td></tr><tr><td>Cancellations</td><td>Dipole reductions</td></tr></tbody></table>
From this perspective, Cayley graphs of free groups with respect to free bases correspond to Cayley graphs of diagram groupoids with respect to atomic diagrams. Then, the arboreal geometry of free groups becomes the median geometry of diagram groups.

**Remark 4.10.** Pushing further this analogy, one could say that free groups have natural boundaries, which can be described both as infinite words and as geodesic rays in their trees; and ask whether there is a counterpart for diagram groups. It turns out to the case: one can define boundaries of diagram groups both as infinite semigroup diagrams and as geodesic rays in their median graphs. Such a boundary coincides with the usual boundary of median graphs: the *Roller boundary*. See [36, Proposition A.3] for more details.

**Universal cover of the Squier cube complex.** It turns out that (cube-completions of) our median graphs can be constructed directly from the Squier cube complexes (as defined by Definition 3.8). More precisely, see the following proposition.

**Proposition 4.11.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. The map that sends a semigroup diagram over $\mathcal{P}$ to the labels of its bottom path induces a universal cover $M_{\square}(\mathcal{P}) \to S^+(\mathcal{P})$.

The proposition is essentially immediate from the definitions of the spaces involved, it is clear that the map $M_{\square}(\mathcal{P}) \to S^+(\mathcal{P})$ induces isomorphisms between links of vertices, so it is a covering map, and we already saw that each connected component of $M_{\square}(\mathcal{P})$ is simply connected.

**From directed 2-complexes to cube complexes.** One can naturally associate to every directed 2-complex $\mathcal{X}$ a cube complex $\mathrm{Sq}(\mathcal{X})$, namely, the cube-completion of the graph whose vertices are 1-paths in $\mathcal{X}$ and whose edges connect two 1-paths whenever one can be obtained from the other by an elementary transformation. Observe that, if $\mathcal{P}$ is a semigroup presentation and if $\mathcal{X}(\mathcal{P})$ is the associated directed 2-complex, then $\mathrm{Sq}(\mathcal{X}(\mathcal{P}))$ coincides with the Squier cube complex $S^+(\mathcal{P})$. It turns out that the cube-completion $M_{\square}(\mathcal{P})$ can also be constructed from a directed 2-complex.

**Definition 4.12.** A *rooted 2-tree* is a directed 2-complex with a distinguished 1-path $\alpha$ which can be described as a union of directed 2-complexes $\mathcal{X}_0 \subset \mathcal{X}_1 \subset \cdots$ such that

* $\mathcal{X}_0$ coincides with the 1-path $\alpha$;

* for every $n \ge 0$, $\mathcal{X}_{n+1}$ is obtained from $\mathcal{X}_n$ by adding new 2-cells whose bottom paths are pairwise disjoint, except possibly at their endpoints; and such that, for each new cell, its top path lies in $\mathcal{X}_n$ but its bottom path must be a simple arc meeting $\mathcal{X}_n$ only at its endpoints.
Among directed 2-complexes, there is a natural notion of covers and every directed 2-complexes (with a distinguished 1-path) admits a (unique) universal cover. This cover is a rooted 2-tree and it is constructed as follows. Let $\mathcal{X}$ be a directed 2-complex with a distinguished 1-path $\alpha$.

* Let $\mathcal{X}_0$ denote the directed 2-complex reduced to a single 1-path, which we endow with a map $\phi_0 : \mathcal{X}_0 \to \mathcal{X}$ that sends isomorphically $\mathcal{X}_0$ to $\alpha$.

* Assume that $\mathcal{X}_n$ and $\phi_n : \mathcal{X}_n \to \mathcal{X}$ are constructed for some $n \ge 0$. If there exist a 1-path $\xi \subset \mathcal{X}_n$ and a 2-cell $\pi \subset \mathcal{X}$ such that the top path of $\pi$ is $\phi_n(\xi)$ and such that no 2-cell of $\mathcal{X}_n$ is sent to $\pi$ under $\phi_n$, then we constructed $\mathcal{X}_{n+1}$ by gluing a new 2-cell along $\xi$ and extend $\phi_n$ by sending this new cell to $\pi$.

Possibly after infinitely many steps, one gets a rooted 2-tree $\tilde{\mathcal{X}}$ and a (covering) map $\phi : \tilde{\mathcal{X}} \to \mathcal{X}$. We refer to [49] for more details.

**Proposition 4.13.** Let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation and $w \in \Sigma^+$ a base-word. Let $X(\mathcal{P})$ denote the directed 2-complex associated to $\mathcal{P}$ with $w$ as its distinguished 1-path. The cube complex $M_{\square}(\mathcal{P}, w)$ is naturally isomorphic to $\mathrm{Sq}(\tilde{\mathcal{X}}(\tilde{\mathcal{P}}))$.

A possible description of the universal cover $\tilde{\mathcal{X}}(\tilde{\mathcal{P}})$ is the following. Take all the reduced diagrams over $\mathcal{P}$ with top labels $w$ and glue them along their top paths $\tau$. Each time two diagrams $\Delta_1$ and $\Delta_2$ have a common prefix $\Delta$ (i.e., each time $\Delta_1$ and $\Delta_2$ decompose as concatenations $\Delta_1 = \Delta \circ \Gamma_1$ and $\Delta_2 = \Delta \circ \Gamma_2$), identify the two copies of $\Delta$. The directed 2-complex one gets is precisely $\tilde{\mathcal{X}}(\tilde{\mathcal{P}})$, with $\tau$ as its root. Observe that $\tau$ and any 1-path $\alpha$ in $\tilde{\mathcal{X}}(\tilde{\mathcal{P}})$ delimit a unique diagram $\Omega(\alpha) \subset \tilde{\mathcal{X}}(\tilde{\mathcal{P}})$. The map $\alpha \mapsto \Omega(\alpha)$ yields the isomorphism

$$ \mathrm{Sq}(\tilde{\mathcal{X}}(\tilde{\mathcal{P}})) \to M_{\square}(\mathcal{P}, w) $$

from the proposition.

## 4.3. Morse theory and finiteness properties

Recall that, given an $n \ge 0$, a group is of type $F_n$ if it admits a classifying space with only finitely many $k$-cells for $k \le n$. It is of type $F_\infty$ if is of type $F_n$ for every $n \ge 0$; or equivalently if it admits a classifying space with only finitely many cells in each dimension. A group is of type $F$ if it admits a classifying space with only finitely many cells. It is worth noticing that a group is of type $F_1$ (resp., of type $F_2$) if and only if it is finitely generated (resp., finitely presented).

Since universal covers of Squier cube complexes are contractible, as cube-completions of median graphs, one gets explicit classifying spaces for diagram groups, which allows us to deduce various finiteness properties. As an immediate application, we have the following proposition.
**Proposition 4.14.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a base-word. If only finitely many words in $\Sigma^+$ equal $w$ modulo $\mathcal{P}$, then the diagram group $D(\mathcal{P}, w)$ is of type F.

*Proof.* The Squier cube complex $S(\mathcal{P}, w)$ defines a classifying space of $D(\mathcal{P}, w)$ with only finitely many cells. ■

For instance, the proposition applies to all the diagram groups associated to the semigroup presentations

$$ \langle x_1, \dots, x_n \mid x_i x_j = x_j x_i \ (1 \le i < j \le n) \rangle, \quad n \ge 1, $$

including to the pure planar braid groups given by Proposition 2.17. It is worth noticing that not every diagram group satisfies good finiteness properties. For instance, the groups $\mathbb{Z} \subsetneq \mathbb{Z}$ and $\mathbb{Z} \cdot \mathbb{Z}$ given in Section 2.4 are finitely generated but not finitely presented. As a more elementary example, it is not difficult to see that the diagram group $D(\mathcal{P}, x)$, where

$$ \mathcal{P} = \langle x, a, b, c \mid x = xa, a = b, b = c, c = a \rangle, $$

is a free abelian group of infinite rank. Of course, this group is not finitely generated.

Even though the Squier cube complex contains infinitely many cells in each dimension, it is possible to deduce good finiteness properties of the corresponding diagram groups by extracting from the cube complex a compact core. A general result illustrating this assertion is the following.

**Theorem 4.15 ([24]).** *Diagram groups given by finite presentations of finite semigroups are of type $F_\infty$.*

Let us illustrate the proof in the particular case of the diagram group $D(\mathcal{P}, x)$ where $\mathcal{P} := \langle x \mid x = x^2 \rangle$. So, we want to show that $D(\mathcal{P}, x)$ is of type $F_\infty$ thanks to its action on the cube-completion $M_{\square}(\mathcal{P}, x)$ of $M(\mathcal{P}, x)$. We cannot deduce what we want to prove directly from $M_{\square}(\mathcal{P}, x)$ because there are infinitely many orbits of cells. The trick is to truncate the complex at some height.

More formally, given a polyhedral complex $X$, a map $f: X \to \mathbb{R}$ is a *Morse function* if the following conditions hold:

* $f$ is affine on each polyhedron;

* $f$ is never constant on a cell of positive dimension;

* $f(X^{(0)})$ is discrete in $\mathbb{R}$.

Typically, one should think of a Morse function as a height function.

In our cube complex $M_{\square}(\mathcal{P}, x)$, we have a natural Morse function at our disposal; it suffices to extend the map $M(\mathcal{P}, x) \to \mathbb{N}$ that sends a vertex represented
by an $(x, x^n)$-diagram to $n$. This Morse function $h : M \times (\mathcal{P}, x) \to \mathbb{R}_+$ is $D(\mathcal{P}, x)$-equivariant, so $D(\mathcal{P}, x)$ preserves the sublevels $h^{-1}([0, k])$, $k \ge 0$. Moreover, because $\mathcal{P}$ is a finite presentation, all these actions are cocompact. Thus, we would like to replace the Squier cube complex with the quotient under $D(\mathcal{P}, x)$ of a well-chosen sublevel. Unfortunately, there is no guarantee that such a sublevel is contractible, contrary to the Squier complex, so it is not clear in general that our new complex will be a classifying space.

This is where Morse theory enters the game, whose philosophy claims that understanding the topology of a polyhedron complex is equivalent to understanding the topology of the (sub)levels of a Morse function.

**Proposition 4.16** ([7]). Let $X$ be an $n$-connected polyhedron complex and $f : X \to \mathbb{R}$ a Morse function. Assume that there exists some $h_0 \in \mathbb{R}$ such that the descending link of every vertex of height $\ge h_0$ is $n$-connected. Then, $f^{-1}((-\infty, h_0])$ is $n$-connected.

Here, the *descending link* of a vertex refers to the subcomplex of the link given by the edges connecting our vertex to vertices of lower heights. The proposition can be easily understood for $n=1$. So, let $\gamma$ be a loop in our sublevel $f^{-1}((-\infty, h_0])$ and let us show that $\gamma$ is homotopically trivial in $f^{-1}((-\infty, h_0])$. Because $X$ is simply connected by assumption, there must be a disc $D^2 \to X$ bounded by $\gamma$. However, this disc $D$ may not lie in our sublevel. Nevertheless, pick a vertex $x$ of maximal height $\ge h_0$ on $D$. Because $x$ has maximal height and because Morse functions are not constant on cells of positive dimensions, we can draw on $D$ a small loop $\sigma$ around $x$ lying in the descending link $\text{link}_\downarrow(x)$ of $x$. Because $\text{link}_\downarrow(x)$ is simply connected by assumption, there is a small disc $D'$ in $\text{link}_\downarrow(x)$ bounded by $\sigma$. Replacing with $D'$ the subdisc of $D$ delimited by $\sigma$ allows us to push down $D$. By iterating the process, we eventually get a disc bounded by $\gamma$ inside $f^{-1}((-\infty, h_0])$, proving that $\gamma$ is homotopically trivial in $f^{-1}((-\infty, h_0])$. Thus, $f^{-1}((-\infty, h_0])$ is indeed simply connected.

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

Thus, in order to show that our diagram group $D(\mathcal{P}, x)$ is of type $F_n$ for every $n \ge 1$, it suffices to verify that descending links of vertices in $M \times (\mathcal{P}, x)$ get more and more connected when the height increases. This is usually the delicate point, we need to describe the descending links of vertices and to prove that they are highly connected.
Let $\Delta$ be an $(x, x^k)$-diagram representing a vertex $x$ of height $k$ in $M_{\square}(\mathcal{P}, x)$. In order to connect $x$ to a vertex of lower height, we need to glue on bot($\Delta$) a negative cell (i.e., a 2-cell labelled by the relation $x^2 = x$); and a collection of such gluings spans a simplex in the descending link of $x$ exactly when they are performed on pairwise disjoint subsegments of bot($\Delta$). Thus, the descending link of a vertex of height $k$ in $M_{\square}(\mathcal{P}, x)$ is isomorphic to the simplicial complex $\mathfrak{S}_k$

* whose vertices are the subintervals $[i, i+1] \subset [1, k]$, $i \in \mathbb{N}$;

* whose simplices are collections of pairwise disjoint subintervals.

One can naturally reconstruct $\mathfrak{S}_{k+3}$ from a cone over $\mathfrak{S}_{k+1}$ (whose apex corresponds to the vertex $[k+2, k+3]$ of $\mathfrak{S}_{k+3}$) by gluing a cone over $\mathfrak{S}_k \subset \mathfrak{S}_{k+1}$ (whose apex corresponds to the vertex $[k+1, k+2]$ of $\mathfrak{S}_{k+3}$). This observation allows us to prove by induction that $\mathfrak{S}_k$ is $n$-connected for every $k \ge 3(n+2)$.

Thus, given an $n \ge 0$, we know that $D(\mathcal{P}, x)$ acts freely, properly, and cocom-
pactly on the sublevel $\mathfrak{h}^{-1}([1, 3(n+2)])$ in $M_{\square}(\mathcal{P}, x)$, which is $n$-connected. We
conclude that $D(\mathcal{P}, x)$ is of type $F_n$, as desired. The argument easily generalises to
the semigroup presentation $\langle x \mid x = x^r \rangle$, $r \ge 2$. We leave the details as an exercise
for the interested reader.

We conclude this section by mentioning the consequence of Theorem **4.15**.

**Corollary 4.17.** Every diagram group over a finite semigroup presentation embeds into a diagram group of type $F_\infty$.

*Proof.* Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a finite semigroup presentation and $w \in \Sigma^+$ a baseword.
Set

$$
\mathcal{Q} := \langle \Sigma \cup \{x\} \mid \mathcal{R} \cup \{x = x^2, a = b (a, b \in \Sigma)\} \rangle.
$$

Every (reduced) diagram over $\mathcal{P}$ also defines a (reduced) diagram over $\mathcal{Q}$, so there is an obvious injective morphism $D(\mathcal{P}, w) \hookrightarrow D(\mathcal{Q}, w)$. Clearly, the semigroup defined by $\mathcal{Q}$ is finite, so Theorem 4.15 implies that $D(\mathcal{Q}, w)$ is of type $F_\infty$. $\blacksquare$

**4.4. Hilbert space compression**

Roughly speaking, the *Hilbert space compression* of a metric space is a number
between zero and one which quantifies the compatibility between the geometry of
the space with the geometry of Hilbert spaces. The smallest the compression is, the
highest the distortion of an embedding into a Hilbert space must be.

**Definition 4.18.** Let $f: X \to Y$ be a Lipschitz map between two metric spaces. The compression of $f$ is the least $\alpha > 0$ for which there exists a constant $C > 0$ such that

$$
C \cdot d(x, y)^{\alpha} \leq d(f(x), f(y)) \quad \text{for all } x, y \in X.
$$
The Hilbert space compression of $X$ is the least compression of a Lipschitz map from $X$ to a Hilbert space. By extension, the Hilbert space compression of a finitely generated group is the Hilbert space compression of its Cayley graphs (constructed from finite generating sets).

Interestingly, median graphs always admit good Lipschitz embeddings into Hilbert spaces with compression bounded below.

**Theorem 4.19** ([14,58]). *The Hilbert space compression of a median graph is always $\ge 1/2$. Moreover, it is equal to 1 when the cubical dimension is finite.*

Let us justify the first assertion. Given a median graph $X$, let $\mathcal{H}$ denote the Hilbert space given by the $\ell^2$-summable maps $\{\text{hyperplanes of } X\} \to \mathbb{R}$ endowed with the $\ell^2$-norm. For every hyperplane $J$ in $X$, we denote by $\delta_J$ the map that sends $J$ to 1 and all the other hyperplanes to 0. Given a basepoint $o \in X$, we claim that the map $\Phi: X \to \mathcal{H}$ defined by

$$x \mapsto \sum_{J \text{ separates } o \text{ and } x} \delta_J$$

induces a Lipschitz embedding with compression $\ge 1/2$. Indeed, for all vertices $x, y \in X$, if we denote by $m$ the median point of $\{x, y, o\}$ and by $\mathcal{W}(\cdot|\cdot)$ the set of the hyperplanes separating two given vertices, we have

$$\begin{aligned} \Phi(x) - \Phi(y) &= \sum_{J \in \mathcal{W}(o|m)} \delta_J + \sum_{J \in \mathcal{W}(m|x)} \delta_J - \sum_{J \in \mathcal{W}(o|m)} \delta_J - \sum_{J \in \mathcal{W}(m|y)} \delta_J \\ &= \sum_{J \in \mathcal{W}(m|x)} \delta_J - \sum_{J \in \mathcal{W}(m|y)} \delta_J, \end{aligned}$$

hence

$$\|\Phi(x) - \Phi(y)\|_2^2 = \#\mathcal{W}(m|x) + \#\mathcal{W}(m|y) = \#\mathcal{W}(x|y) = d(x, y).$$

This concludes the proof of our claim.

As an immediate consequence of Theorem 4.19, it follows that the Hilbert space compression of a finitely generated diagram group $D(\mathcal{P}, w)$ is $\ge 1/2$ if its orbits in the median graph $M(\mathcal{P}, w)$ are quasi-isometrically embedded; and is even equal to 1 if, in addition, the cubical dimension of $M(\mathcal{P}, w)$ is finite. For instance, we have the following proposition.

**Proposition 4.20.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a base-word. If only finitely many words in $\Sigma^+$ are equal to $w$ modulo $\mathcal{P}$, then the Hilbert space compression of $D(\mathcal{P}, w)$ is equal to 1.

*Proof.* Our assumptions imply $D(\mathcal{P}, w)$ acts on $M(\mathcal{P}, w)$ properly and cocompactly. Therefore, the Hilbert space compression of $D(\mathcal{P}, w)$ coincides with the Hilbert space compression of $M(\mathcal{P}, w)$, which is equal to 1 according to Theorem 4.19. ■
As a consequence of the description of the graph metric of $M(\mathcal{P}, w)$ given in Section 4.2, it is clear that the orbits of a finitely generated diagram group $D(\mathcal{P}, w)$ are quasi-isometrically embedded if and only if the following property is satisfied.

**Definition 4.21.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. The diagram group $D(\mathcal{P}, w)$ satisfies the *Burillo property* if it is finitely generated and if every word-metric given by a finite generating set is bi-Lipschitz equivalent to the *diagram metric* $\#(\cdot)$, i.e., the map that sends each element of $D(\mathcal{P}, w)$ to the number of 2-cells in a reduced diagram representing it.

Thus, we deduce the following statement.

**Proposition 4.22 ([2]).** A diagram group satisfying the *Burillo property* has Hilbert space compression $\ge 1/2$.

Examples of diagram groups satisfying the *Burillo property* include the pure planar braid groups and various right-angled Artin groups (according to Proposition 4.20), Thompson's group $F$ [13], the wreath product $Z \bowtie Z$ [2], and $Z \circled{\bullet} Z$ [33]. (All these examples are thought of as diagram groups by taking the semigroup presentations given in Section 2.4.) So far, no example of a finitely generated diagram group that does not satisfy the *Burillo property* appears in the literature.

**Proposition 4.22** only gives lower bounds on Hilbert space compression. Computing the exact value of the Hilbert space compression may be subtle and goes beyond the scope of this survey. Nevertheless, let us mention that Thompson's group $F$ has Hilbert space compression 1/2 [2] and that the wreath product $Z \bowtie Z$ has Hilbert space compression 2/3 (see [4]).

The proof of Proposition 4.22 given in [2] does not use median geometry, but it turns out to be the exact translation of the argument presented above through the correspondence between median graphs and rooted 2-trees described in Section 4.2. Let us describe the argument as presented in [2].

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. We glue together all the reduced diagrams over $\mathcal{P}$ with top label $w$ along their top paths $\tau$; and, for any two diagrams $\Delta_1, \Delta_2$, if $\Delta$ is a common prefix of $\Delta_1, \Delta_2$, then we identify the two copies of $\Delta$ in $\Delta_1$ and $\Delta_2$. Let $T(\mathcal{P}, w)$ denote the resulting object. Let $\mathcal{H}$ denote the Hilbert space given by the formal sums of 2-cells in $T(\mathcal{P}, w)$ endowed with the $\ell^2$-norm. For every $g \in D(\mathcal{P}, w)$, there is a unique copy of a reduced diagram representing $g$ having $\tau$ as its top path. Let $\Xi(g)$ denote the formal sum of the 2-cells contained in this copy. Then

$$ \|\Xi(g) - \Xi(h)\|_2^2 = \#(g^{-1}h) \quad \text{for all } g, h \in D(\mathcal{P}, w). $$

Thus, if $D(\mathcal{P}, w)$ satisfies the *Burillo property*, then $g \mapsto \Xi(g)$ defines a Lipschitz map $D(\mathcal{P}, w) \to \mathcal{H}$ with compression 1/2.
An explicit bijection between the 2-cells in $T(\mathcal{P}, w)$ and the hyperplanes in $M(\mathcal{P}, w)$ can be described as follows. A diagram $\Delta$ over $\mathcal{P}$ is *minimal* if it contains a single 2-cell having its bottom path in the bottom path of $\Delta$. If $\Delta^-$ denotes the diagram obtained from $\Delta$ by removing this 2-cell, then $[\Delta, \Delta^-]$ defines an edge in $M(\mathcal{P})$, and we denote by $J(\Delta)$ the hyperplane containing this edge. It turns out that the map $\Delta \mapsto J(\Delta)$ induces a bijection from the reduced minimal diagrams over $\mathcal{P}$ to the hyperplanes in $M(\mathcal{P})$ [32, Proposition 2]. For every 2-cell $\pi$ in $T(\mathcal{P}, w)$, let $\Delta(\pi)$ denote the smallest diagram in $T(\mathcal{P}, w)$ containing $\pi$ and having $\tau$ as its top path. The minimality assures that $\Delta(\pi)$ is minimal, and the map $\pi \mapsto J(\Delta(\pi))$ yields the desired bijection from the 2-cells of $T(\mathcal{P}, w)$ to the hyperplanes of $M(\mathcal{P}, w)$.

**Remark 4.23.** In this section, we have focused on Hilbert space compressions of groups, but one can define the *equivariant Hilbert space compression* of a finitely generated group $G$ as the least compression of a Lipschitz map from $G$ (endowed with the word length given by a finite generating set) to a Hilbert space on which $G$ acts by affine isometries. Everything that has been said about Hilbert space compressions in this section also holds for equivariant compressions.

**4.5. Hyperplanes in Squier's cube complex**

In this section, we focus on the combinatorics of hyperplanes in Squier cube complexes. In particular, this will allow us to prove that some diagram groups are linear over $\mathbb{Z}$, have finite asymptotic dimension, or satisfy some Tits alternative depending on their underlying semigroup presentations. We begin by recalling some terminology and results from [53].

**Definition 4.24.** Let $X$ be a nonpositively curved cube complex.

* A hyperplane is *one-sided* if its two orientations coincide. Otherwise, it is *two-sided*.

* A hyperplane $J$ *self-intersects* if there exist a vertex $o \in X$ and two neighbours $a, b \in X$ such that the edges $[o, a]$, $[o, b]$ span a square and are both transverse to $J$.

* A hyperplane $J$ *self-osculates* if there exist a vertex $o \in X$ and two neighbours $a, b \in X$ such that the edges $[o, a]$, $[o, b]$ do not span a square and are both transverse to $J$.

* Two hyperplanes *inter-osculate* if they are both transverse and tangent.

The cube complex $X$ is *conspicial$^2$* if all its hyperplanes are two-sided and if it does not contain self-intersections, self-osculations, nor inter-osculations.

<footnote n="2">²This property is called *A-special* in [53], shortened as *special* in the recent literature. In order to minimise conflicts with the everyday language, we propose to use the Latin word *conspicial* which is close to *special* both semantically and phonetically.</footnote>
Let us motivate this definition. Given a nonpositively curved cube complex $X$, let $\Delta X$ denote its crossing graph, i.e., the graph whose vertices are the hyperplanes of $X$ and whose edges connect two hyperplanes whenever they are transverse. Fix a basepoint $o \in X$. Also, we assume that the hyperplanes of $X$ are two-sided and fix an orientation on the hyperplanes of $X$. A loop in $X^{(1)}$ based at $o$ can be thought of as a sequence of oriented edges, to which we can associate a formal word written over $\{\text{hyperplanes of } X\}^{\pm 1}$ (an oriented edge $e$ being sent to the hyperplane it crosses or its inverse depending on whether the orientations of $e$ and the hyperplane agree). This correspondence induces a well-defined morphism

$$ \mathfrak{A}_X : \pi_1(X, o) \to A(\Delta X) $$

to the right-angled Artin group $A(\Delta X)$. (See Section 2.4 for a definition of right-angled Artin groups.) In full generality, we do not know anything about the morphism $\mathfrak{A}_X$. It may be even trivial. However, it turns out to be injective as soon as $X$ is conspicial [53, Theorem 4.2]. Thus, fundamental groups of conspicial cube complexes inherit all the properties satisfied by right-angled Artin groups and are stable under taking subgroups. This includes, for instance,

* being linear over $\mathbb{Z}$ (and, as a consequence, being residually finite);

* satisfying a strong Tits alternative, namely, every subgroup either is free abelian or contains a non-abelian free subgroup.

If moreover the conspicial cube complex is compact, then its fundamental group is nicely embedded into the corresponding right-angled Artin groups: it defines a *convex-cocompact* subgroup. This allows us to strengthen the residual finiteness previously mentioned and to deduce that convex-cocompact subgroups in our fundamental group are *separable* [53, Corollary 7.9].

A natural question to ask now is: when are Squier cube complexes conspicial?

**Proposition 4.25** ([33]). Let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. The Squier cube complex $S^+(\mathcal{P}, w)$ is conspicial if and only if the following conditions are satisfied:

* there are no words $a, b, p \in \Sigma^+$ such that $w = ab, a = ap, \text{ and } b = pb$ modulo $\mathcal{P}$ with $[p]_{\mathcal{P}} \neq \{p\}$;

* there are no words $a, u, v, w, b, p, q, \xi \in \Sigma^+$ such that $w = auvwb, au = au(v\xi), \text{ and } wb = (\xi v)wb$ modulo $\mathcal{P}$ with $uv = p, vw = q$ in $\mathcal{R}$.

Here, $[p]_{\mathcal{P}}$ denotes the set of all the words in $\Sigma^+$ equal to $p$ modulo $\mathcal{P}$. It is worth noticing that, if the condition from the first item fails, then

$$ \{ap^n b \mid n \ge 0\} \subset [w]_{\mathcal{P}}; $$
and, if the condition from the second item fails, then

$$ \{au(v\xi)^m v(\xi v)^n wb \mid n, m \ge 0\} \subset [w]_P. $$

Consequently, if we know that $[w]_P$ is finite, then it follows immediately from the proposition that our Squier cube complex is conspicial.

**Corollary 4.26.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a base-word. If $[w]_P$ is finite, then $S^+(\mathcal{P}, w)$ is conspicial.

Corollary 4.26 applies to the right-angled Artin groups and pure planar braid groups from Section 2.4. It does not apply to the group $\mathbb{Z} \bullet \mathbb{Z}$, but Proposition 4.25 holds anyway. It is worth mentioning that not all diagram groups can be described as fundamental groups of conspicial cube complexes. Thompson's group $F$ is such an example since it is not even residually finite.

In Corollary 4.26, the Squier cube complex is conspicial but also compact. Therefore, this allows us to deduce that convex-cocompact subgroups in the corresponding diagram group are separable. (Recall that, given a group $G$, a subgroup $H$ is separable if, for every non-trivial $h \in H$, $G$ has a finite-index subgroup not containing $h$.) One instance of this assertion is given by the following corollary.

**Corollary 4.27 ([33]).** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword with $[w]_P$ finite. Fix a $(w, x_1u_1 \cdots x_nu_nx_{n+1})$-diagram $\Delta$. The morphism

$$ \left\{ \begin{array}{l} D(\mathcal{P}, u_1) \times \cdots \times D(\mathcal{P}, u_n) \quad \to D(\mathcal{P}, w) \\ (\Gamma_1, \ldots, \Gamma_n) \quad \mapsto \Delta \cdot (\Gamma_1 + \cdots + \Gamma_n) \cdot \Delta^{-1} \end{array} \right. $$

is injective and its image is a separable subgroup of $D(\mathcal{P}, w)$.

Let us describe explicitly the morphism $\mathfrak{X}$ above in the specific case of our Squier cube complexes. So, we fix a semigroup presentation $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ and a base-word $w \in \Sigma^+$. The oriented edges of $S^+(\mathcal{P}, w)$ can be written as $(a, u \to v, b)$ when they connect $aub$ to $avb$; we denote by $[a, u \to v, b]$ the corresponding (oriented) hyperplane. It can be shown that two oriented hyperplanes $[a, u \to v, b]$ and $[c, p \to q, d]$

* coincide if and only if $a = c, b = d$ modulo $\mathcal{P}$ and $u = p, v = q$ in $\Sigma^+$ [33, Lemma 3.1];

* are transverse if and only if there exists some $y \in \Sigma^+$ such that either $c = auy$ and $b = ypd$ modulo $\mathcal{P}$ or $d = yub$ and $a = cpy$ modulo $\mathcal{P}$ [33, Lemma 3.2].

Let $A(\mathcal{P}, w)$ be the right-angled Artin group given by the crossing graph of $S^+(\mathcal{P}, w)$. The generators of $A(\mathcal{P}, w)$ are the oriented hyperplanes $[a, u \to v, b]$ where $u = v$ belongs to $\mathcal{R}$. The map that sends each oriented edge $(a, u \to v, b)$ to the element
<figure><img src="image_23.png" /><figcaption>Figure 11. Generators of $\mathbb{Z} \cdot \mathbb{Z}$.</figcaption></figure>

$[a, u \to v, b]$ if $u = v$ belongs to $\mathcal{R}$ and to the element $[a, v \to u, b]^{-1}$ if $v = u$ belongs to $\mathcal{R}$ induces a morphism

$$ \mathcal{A}(\mathcal{P}, w) : D(\mathcal{P}, w) \to A(\mathcal{P}, w). $$

It is injective as soon as the conditions of Proposition 4.25 are satisfied. This happens for instance when $[w]_{\mathcal{P}}$ is finite.

**Example 4.28.** Let us consider the following semigroup presentation:

$$ \mathcal{P} := \langle a_1, a_2, a_3, b_1, b_2, b_3, p \mid a_1 = a_2, a_2 = a_3, a_3 = a_1, a_1 = a_1 p, \\ b_1 = b_2, b_2 = b_3, b_3 = b_1, b_1 = pb_1 \rangle. $$

The diagram group $D(\mathcal{P}, a_1 b_1)$ is the group $\mathbb{Z} \cdot \mathbb{Z}$ described in Section 2.4. According to Proposition 4.25, the Squier cube complex $S^+(\mathcal{P}, a_1 b_1)$ is conspicial, so our morphism $\mathcal{A}(\mathcal{P}, w_1 b_1) \to A(\mathcal{P}, a_1 b_1)$ is injective.

Using our previous description of hyperplanes, we find that $S^+(\mathcal{P}, a_1 b_1)$ has eight hyperplanes

$$ \begin{align*} A_i &:= [1, a_i \to a_{i+1}, b_1], & B_i &:= [a_1, b_i \to b_{i+1}, 1], \\ C &:= [1, a_1 \to a_1 p, b_1], & D &:= [a_1, b_1 \to pb_1, 1]. \end{align*} $$

Moreover, we find that the crossing graph of $S^+(\mathcal{P}, a_1 b_1)$ is a complete bipartite graph $K_{4,4}$, where each vertex of $\{A_1, A_2, A_3, C\}$ is connected by an edge to each vertex of $\{B_1, B_2, B_3, D\}$. In particular,

$$ A(\mathcal{P}, a_1 b_1) \simeq \mathbb{F}_4 \times \mathbb{F}_4. $$

Then, by using Theorem 3.2 or Proposition 4.30 below, we find that $\mathbb{Z} \cdot \mathbb{Z}$ is generated by the three diagrams shown in Figure 11.

For instance, the first diagram corresponds to the loop of edges

$$ (1, a_1 \to a_2, b_1), \quad (1, a_2 \to a_3, b_1), \quad (1, a_3 \to a_1, b_1). $$
which implies that our morphism $\mathfrak{A} = \mathfrak{A}(\mathcal{P}, a_1b_1)$ sends $\Delta_1$ to $A_1A_2A_3$. Similarly, we find that

$$ \mathfrak{A}(\Delta_2) = B_1B_2B_3 \quad \text{and} \quad \mathfrak{A}(\Delta_3) = CD^{-1}. $$

We conclude that the subgroup $\langle A_1A_2A_3, B_1B_2B_3, CD^{-1} \rangle$ of

$$ \mathbb{F}_4 \times \mathbb{F}_4 = \langle A_1, A_2, A_3, C \mid \rangle \times \langle B_1, B_2, B_3, D \mid \rangle $$

is isomorphic to $\mathbb{Z} \bullet \mathbb{Z}$. The embedding can be simplified to an embedding into $\mathbb{F}_2 \times \mathbb{F}_2$; we refer to [33, Example 3.17] for more details.

From a more geometric perspective, it is possible to use the structure of hyperplanes in the Squier cube complexes in order to construct quasi-isometric embeddings from diagram groups into product of trees. More precisely, see the following proposition.

**Proposition 4.29.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a base-word. If $D(\mathcal{P}, w)$ satisfies the Burillo property and if $S^+(\mathcal{P}, w)$ has finite dimension $d$, then $D(\mathcal{P}, w)$ quasi-isometrically embeds into a product of $d$ trees. As a consequence, $D(\mathcal{P}, w)$ has finite asymptotic dimension $\le d$ and its Hilbert space compression is 1.

The last assertion of the proposition follows from the first part but also from [51, 68]. One easily observes that $S^+(\mathcal{P}, w)$ has dimension $\le d$ if and only if $d$ is the smallest integer $k$ for which there exist $u_1, \dots, u_k \in \Sigma^+$ such that $w = u_1 \cdots u_k$ modulo $\mathcal{P}$ and such that $[u_i]_\mathcal{P} \ne \{u_i\}$ for every $1 \le i \le k$. For instance, $S^+(\mathcal{P}, w)$ is automatically finite-dimensional when $[w]_\mathcal{P}$ is finite.

**Proof of Proposition 4.29.** First of all, we need to introduce some notation and vocabulary.

Let $J_1$ and $J_2$ be two hyperplanes in $S^+(\mathcal{P}, w)$. If they meet inside a square $(a, u \to v, b, p \to q, c)$ with $[a, u \to v, bpc] = J_1$ and $[aub, p \to q, c] = J_2$, then we write $J_1 \prec J_2$. This relation allows us to define the *rank* of a hyperplane $J$ in $S^+(\mathcal{P}, w)$ as

$$ \mathrm{rank}(J) := \max\{n \ge 0 \mid \text{there exist } J_1, \dots, J_n \text{ with } J_1 \prec \dots \prec J_n \prec J\}. $$

Because any two $\prec$-related hyperplanes must be transverse, the *rank* of a hyperplane lies between 0 and $d-1$. By extension, we define the *rank* of a hyperplane in the median graph $M(\mathcal{P}, w)$ as the *rank* of its image by the covering map $M \square(\mathcal{P}, w) \to S^+(\mathcal{P}, w)$.

Thus, we get a colouring of the hyperplanes of $M(\mathcal{P}, w)$ with $d$ colours given by the *rank* such that any two hyperplanes of the same colour cannot be transverse. This
implies that $M(\mathcal{P}, w)$ embeds isometrically into a product of $d$ trees (endowed with the $\ell^1$-metric), which allows us to conclude since $D(\mathcal{P}, w)$ embeds isometrically into $M(\mathcal{P}, w)$ as a consequence of the Burillo property.

Let us describe how $M(\mathcal{P}, w)$ can be embedded into a product of $d$ trees. For every $0 \le i \le d-1$, let $T_i$ denote the graph whose vertices are the connected components of the graph obtained by cutting $M(\mathcal{P}, w)$ along all the hyperplanes of rank $i$ and whose edges connect two components whenever they are separated by a single hyperplane of rank $i$; because no two hyperplanes of rank $i$ are transverse, $T_i$ is a tree; moreover, there is a natural projection $M(\mathcal{P}, w) \to T_i$ sending a vertex to the connected component it belongs to, and the distance in $T_i$ between the projections of two vertices $x, y \in M(\mathcal{P}, w)$ coincides with the number of hyperplanes of rank $i$ separating $x$ and $y$. Thus, the product of these projections yields a map $M(\mathcal{P}, w) \to T_0 \times \cdots \times T_{d-1}$ such that the distance between the images of two vertices $x, y \in M(\mathcal{P}, w)$ coincides with the sum over $i$ of the number of hyperplanes of rank $i$ separating $x$ and $y$, i.e., the total number of hyperplanes separating $x$ and $y$, which is exactly the distance between $x$ and $y$ in $M(\mathcal{P}, w)$. ■

We conclude this section by explaining how one can use hyperplanes in order to decompose Squier cube complexes as graphs of spaces and to compute presentations of diagram groups. Before stating our decomposition theorem, we need to introduce some vocabulary.

So, let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. A hyperplane $J = [a, u \to v, b]$ in $S^+(\mathcal{P}, w)$ is left if $D(\mathcal{P}, a) = \{1\}$ but $D(\mathcal{P}, au) \ne \{1\}$. If so, let $p_J, s_J \in \Sigma^+$ be two words and $\ell_J \in \Sigma$ a letter satisfying

$$u = p_J \ell_J s_J \quad \text{in } \Sigma^+, \quad D(\mathcal{P}, ap_J) = \{1\}$$

and

$$D(\mathcal{P}, ap_J \ell_J) \ne \{1\}.$$

Notice that $p_J$ is just the maximal prefix of $u$ satisfying $D(\mathcal{P}, ap_J) = \{1\}$ so that $p_J, s_J, \ell_J$ are uniquely determined. We define similarly $v = q_J m_J r_J$, where $q_J, r_J \in \Sigma^+$ and $m_J \in \Sigma$, so that

$$D(\mathcal{P}, q_J) = \{1\} \quad \text{and} \quad D(\mathcal{P}, q_J m_J) \ne \{1\}.$$

**Proposition 4.30.** Let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. Let $\mathfrak{J}$ denote the set of left hyperplanes of $S^+(\mathcal{P}, w)$ and let $\mathfrak{G}(\mathcal{P}, w)$ be the graph of spaces defined by the following:

* the set of vertex-spaces is

$$\{S^+(\mathcal{P}, ap_J) \ell_J S^+(\mathcal{P}, s_J b), S^+(\mathcal{P}, aq_J) m_J S^+(\mathcal{P}, r_J b) \mid J = [a, u \to v, b] \in \mathfrak{J}\};$$
* to each left hyperplane $[a, u \to v, b] \in \mathcal{J}$ is associated the edge-space $S^+(\mathcal{P}, a) \times S^+(\mathcal{P}, b)$;

* the edge-maps are the canonical maps

$$S^+(\mathcal{P}, a) \times S^+(\mathcal{P}, b) \to S^+(\mathcal{P}, a)uS^+(\mathcal{P}, b)$$

and

$$S^+(\mathcal{P}, a) \times S^+(\mathcal{P}, b) \to S^+(\mathcal{P}, a)vS^+(\mathcal{P}, b).$$

Then, $\mathcal{G}(\mathcal{P}, w)$ defines a decomposition of $S^+(\mathcal{P}, w)$ as a graph of spaces.

As an illustration of the proposition, let us compute a presentation of some diagram groups.

**Example 4.31.** Let

$$\mathcal{P} = \langle a_1, a_2, a_3, b_1, b_2, b_3, p \mid a_1 = a_2, a_2 = a_3, a_3 = a_1, a_1 = a_1 p, \\ b_1 = b_2, b_2 = b_3, b_3 = b_1, b_1 = pb_1 \rangle.$$

Then, $S^+(\mathcal{P}, a_1 b_1)$ contains four left hyperplanes

$$[1, a_1 \to a_2, b_1], \ [1, a_2 \to a_3, b_1], \ [1, a_3 \to a_1, b_1], \ [1, a_1 \to a_1 p, b_1].$$

Thus, the vertex-spaces of our graph of spaces will be

$$a_1 S(\mathcal{P}, b_1), \ a_2 S(\mathcal{P}, b_1), \ a_3 S(\mathcal{P}, b_1).$$

The graph of spaces given by Proposition 4.30 is then

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

The maps associated to the loop are induced by $w_0 \mapsto a_1 w_0$ and $w_0 \mapsto a_1 p w_0$. On the other hand, the Squier complex $S(\mathcal{P}, b_1)$ is easy to draw

<figure><img src="image_25.png" /></figure>
In particular, its fundamental group is isomorphic to $F_\infty = \langle x_1, x_2, \dots \mid \rangle$.

Thus, $D(\mathcal{P}, a_1b_1)$ may be decomposed as the graph of groups illustrated as follows, where the maps associated to the three edges on the left are identities, and where the two maps associated to the loop are the identity and the morphism induced by $x_i \mapsto x_{i+1}$:

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

Finally, this graph of groups may be simplified into the graph of groups illustrated as follows, where the maps associated to the left loop are identities and where the two maps associated to the right loop are the identity and the morphism induced by $x_i \mapsto x_{i+1}$:

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

Thus, we deduce the following presentation of our diagram group $D(\mathcal{P}, a_1b_1)$:

$$ \langle x_1, x_2, \dots, t, h \mid tx_i t^{-1} = x_i, hx_i h^{-1} = x_{i+1} \ (i \ge 1) \rangle. $$

Noticing that $x_{i+1} = h^i x_1 h^{-i}$ for every $i \ge 1$, we can simplify the presentation as

$$ \mathbb{Z} \cdot \mathbb{Z} = \langle a, t, h \mid [a, a^{h^i}] = 1 \ (i \ge 0) \rangle, $$

which is the presentation given in Section 2.4.

## 4.6. Acylindrical hyperbolicity

A powerful method to study groups, coming from the geometric group theory, is to look for behaviours of negative curvature. We saw with Theorem 2.24 that there is
essentially no hyperbolicity in diagram groups, and it can be expected that a similar phenomenon occurs for relative hyperbolicity (see Conjecture 6.15). Nevertheless, *acylindrical hyperbolicity* is sufficiently weak to encompass interesting examples of diagram groups and sufficiently restrictive to provide valuable information.

Formally, a group $G$ is *acylindrically hyperbolic* if it admits an action on some (Gromov-)hyperbolic space $X$ which is both *non-elementary* (i.e., with an infinite limit set) and *acylindrical* (i.e., for every $d \ge 0$, there exist $L, N \ge 0$ such that $\#\{g \in G \mid d(x, gx), d(y, gy) \le d\} \le N$ for all $x, y \in X$ satisfying $d(x, y) \ge L$). Acylindrical hyperbolicity can be thought of as a weak phenomenon of negative curvature, but which nevertheless provides strong restrictions on the structure of the group under consideration. For instance, consider the following statements:

* Acylindrically hyperbolic groups admit many quotients. This is a consequence of small cancellation [20] and Dehn fillings [54]. For instance, every acylindrically hyperbolic group $G$ is *SQ-universal* (i.e., every countable group embeds into a quotient of $G$).

* Acylindrically hyperbolic groups contain many free subgroups. This can also be seen as a consequence of small cancellation [20] since the normal subgroups produced are free. But we can also justify this assertion by using the Property $P_{\text{naive}}$ [1] or the fact that random subgroups are free [57].

* Acylindrically hyperbolic groups admit many quasimorphisms [8]. In particular, this implies that the second bounded cohomology group has uncountable dimension.

* An acylindrically hyperbolic group $G$ does not contain an infinite abelian subgroup $H$ that is *s-normal* (i.e., $H \cap gHg^{-1}$ is infinite for every $g \in G$) [59]. In particular, centres of acylindrically hyperbolic groups are finite.

* An acylindrically hyperbolic group does not decompose as the direct sum of two infinite groups [59].

Diagram groups may or may not be acylindrically hyperbolic. Obvious examples of acylindrically hyperbolic diagram groups are non-abelian free groups. More interesting examples will be given in this section. On the other hand, free abelian groups, Thompson's group $F$, and the wreath product $Z \rtimes Z$ are not acylindrically hyperbolic (since they do not contain any non-abelian free subgroup). Is it possible to recognise whether or not a given diagram group is acylindrically hyperbolic?

Even though the median graphs constructed in Section 4.2 are usually not hyperbolic, it turns out that there exist efficient methods that allow us to deduce that a group is acylindrically hyperbolic thanks to an action on a median graph; see [35] and references therein. One of these methods is to look for specific isometries that behave like isometries in hyperbolic spaces. More precisely, see the following statements.
<figure><img src="image_28.png" /><figcaption>**Figure 12.** Diagrams $g$ and $g^\infty$ from Example 4.34.</figcaption></figure>

**Definition 4.32.** Let $X$ be a metric space. An isometry $g \in \operatorname{Isom}(X)$ is *contracting* if there exists a basepoint $o \in X$ such that the map $n \mapsto g^n \cdot o$ induces a quasi-isometric embedding $\mathbb{Z} \to X$; and if there exists some $D \ge 0$ such that the nearest-point projection on $\langle g \rangle \cdot o$ of every ball disjoint from $\langle g \rangle \cdot o$ has diameter at most $D$.

It turns out that a group acting properly on a metric space with at least one contracting isometry must be either virtually infinite cyclic or acylindrically hyperbolic. Therefore, a natural problem is to determine when an element of a diagram group induces a contracting isometry on the corresponding median graph.

**Theorem 4.33 ([36]).** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation, $w \in \Sigma^+$ a base-word, and $g \in D(\mathcal{P}, w)$ a non-trivial absolutely reduced element. Then, $g$ is a contracting isometry of $M(\mathcal{P}, w)$ if and only if the following conditions are satisfied:

* $g^\infty$ does not contain any infinite proper prefix (i.e., $g^\infty$ does not decompose as a concatenation $\Phi \circ \Psi$ with $\Phi$ infinite and $\Psi$ non-trivial);

* if $\Delta$ is a reduced diagram with $g^\infty$ as a prefix, then $\Delta$ differs from $g^\infty$ by only finitely many 2-cells.

Roughly speaking, an infinite diagram refers to the object $\Delta_1 \circ \Delta_2 \circ \dots$ obtained by concatenating infinitely many finite diagrams $\Delta_1, \Delta_2, \dots$ over a given semigroup presentation. In particular, $g^\infty$ denotes the infinite diagram obtained by concatenating infinitely many copies of the diagram $g$. We refer to [36] for a more formal description.

**Example 4.34.** Let $\mathcal{P} = \langle a, b, p \mid a = ap, b = pb \rangle$ and let $g \in D(\mathcal{P}, ab)$ be the spherical diagram illustrated in Figure 12.

Then, $g^\infty$ clearly contains a proper infinite prefix. Therefore, $g$ is not a contracting isometry of $M(\mathcal{P}, ab)$.
<figure><img src="image_29.png" /><figcaption>**Figure 13.** Diagrams $g$ and $g^\infty$ from Example 4.35.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>**Figure 14.** The diagram $g$ and its associated infinite diagram $g^\infty$ from Example 4.36.</figcaption></figure>

**Example 4.35.** Let $\mathcal{P} = \langle a, b, c \mid a = b, b = c, c = a \rangle$ and let $g \in D(\mathcal{P}, a^2)$ be the spherical diagram illustrated in Figure 13.

Then, $g^\infty$ is a prefix of the diagram $\Delta$ given by Figure 13, but $\Delta$ contains infinitely many 2-cells not in $g^\infty$. Therefore, $g$ is not a contracting isometry of $M(\mathcal{P}, a^2)$.

**Example 4.36.** Let $\mathcal{P} = \langle a, b, c, d \mid ab = ac, cd = bd \rangle$ and let $g \in D(\mathcal{P}, ab)$ be the spherical diagram illustrated in Figure 14. Then, the infinite diagram $g^\infty$ is given by Figure 14.

We can notice that $g^\infty$ does not contain a proper infinite prefix and that any diagram containing $g^\infty$ as a prefix is necessarily equal to $g^\infty$. Therefore, $g$ yields a contracting isometry of $M(\mathcal{P}, ab)$. One easily verifies that $D(\mathcal{P}, ab)$ is not infinite cyclic, so $D(\mathcal{P}, ab)$ is acylindrically hyperbolic.

Theorem 4.33 may be considered as unsatisfying because infinite diagrams cannot be drawn. For diagrams with only a few cells, the previous examples show that the
theorem can be applied fairly easily, but for bigger diagrams it gets more delicate. For instance, consider the semigroup presentation

$$ \langle a_1, a_2, a_3, b_1, b_2, b_3, p \mid a_1 = a_2, a_2 = a_3, a_3 = a_1, a_1 = a_1 p, \\ b_1 = b_2, b_2 = b_3, b_3 = b_1, b_1 = p b_1 \rangle $$

corresponding to the diagram group $Z \bullet Z$, and let $g$ be the element given by the following spherical diagram:

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

Then, it can be verified that $g$ is a contracting isometry of $M(\mathcal{P}, a_1b_1)$, proving that $Z \bullet Z$ is acylindrically hyperbolic. (In fact, it can be proved that $A \bullet B$ is always acylindrically hyperbolic when the groups $A$ and $B$ are both non-trivial; see [36, Example 5.44] for more details.) However, applying Theorem 4.33 becomes painful. We refer to [36, Proposition 5.39] for an efficient method that allows us to verify the conditions given by Theorem 4.33 more easily.

Theorem 4.33 only provides a sufficient condition to be acylindrically hyperbolic. In fact, the diagram group may be acylindrically hyperbolic but with no contracting isometries in the associated median graph. However, when the action on the median graph is cocompact, the criterion turns out to provide a necessary and sufficient condition.

**Theorem 4.37.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword with $[w]_{\mathcal{P}}$ finite. There exist words $u_0, u_1, \dots, u_m \in \Sigma^+$ and a $(w, u_0u_1 \cdots u_m)$-diagram $\Gamma$ such that

$$ D(\mathcal{P}, w) = \Gamma \cdot (D(\mathcal{P}, u_0) \times D(\mathcal{P}, u_1) \times \cdots \times D(\mathcal{P}, u_m)) \cdot \Gamma^{-1}, $$

where each $D(\mathcal{P}, u_i)$ is trivial, infinite cyclic, or acylindrically hyperbolic.

We already mentioned that acylindrically hyperbolic groups do not split as product of infinite groups. Theorem 4.37 shows that this is essentially the only obstruction for a cocompact diagram group to be acylindrically hyperbolic.
## 4.7. Diagram products and quasi-median geometry

Diagram products, first introduced in [47], can be thought of as *diagram groups with coefficients*, where the coefficients come from some collection of groups (the factors of the product). Below, we follow the definition given in [31].

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups indexed by the letters of our alphabet $\Sigma$. A *diagram over* $(\mathcal{P}, \mathcal{G})$ is a diagram $\Delta$ over $\mathcal{P}$ such that each edge of $\Delta$ labelled by a letter $s \in \Sigma$ is also labelled by an element of $G_s$. In other words, the edges of a diagram are labelled by $\{(s, g) \mid s \in \Sigma, g \in G_s\}$. Most of the vocabulary introduced in Section 2.2 extends naturally to such diagrams. Let us record the two major differences.

* In a diagram $\Delta$ over $(\mathcal{P}, \mathcal{G})$, a *dipole* refers to two cells $\pi_1, \pi_2$ satisfying

$$ \mathrm{bot}(\pi_1) = \mathrm{top}(\pi_2) $$

and labelled as follows: the top path of $\pi_1$ is labelled by $(u_1, g_1) \cdots (u_m, g_m)$, its bottom path is labelled by $(v_1, 1) \cdots (v_n, 1)$, and the bottom path of $\pi_2$ is labelled by $(u_1, h_1) \cdots (u_m, h_m)$ where $u_1 \cdots u_m = v_1 \cdots v_n$ or its inverse belongs to $\mathcal{R}$. One *reduces* the dipole by removing $\pi_1, \pi_2$, identifying $\mathrm{top}(\pi_1)$ with $\mathrm{bot}(\pi_2)$, and labelling this path by $(u_1, g_1 h_1) \cdots (u_m, g_m h_m)$.

* Let $\Delta_1, \Delta_2$ be two diagrams over $(\mathcal{P}, \mathcal{G})$. If $\mathrm{bot}(\Delta_1)$ is labelled by $(u_1, g_1) \cdots (u_m, g_m)$ and $\mathrm{top}(\Delta_2)$ by $(u_1, h_1) \cdots (u_m, h_m)$, the *concatenation* $\Delta_1 \circ \Delta_2$ of $\Delta_1$ and $\Delta_2$ is the diagram obtained by identifying $\mathrm{bot}(\Delta_1)$ with $\mathrm{top}(\Delta_2)$ and by labelling this common path by $(u_1, g_1 h_1) \cdots (u_m, g_m h_m)$.

**Definition 4.38.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation, $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups, and $w \in \Sigma^+$ a baseword. The *diagram product* $D(\mathcal{P}, \mathcal{G}, w)$ is the group whose elements are the diagrams over $(\mathcal{P}, \mathcal{G})$ modulo dipole reductions and whose product is given by the concatenation.

As an illustration, consider the semigroup presentation $\mathcal{P} = \langle a, b, c \mid ab=ba, ac=ca, bc=cb \rangle$ and the factors $\mathcal{G} = \{G_a = G_b = G_c = \mathbb{Z}\}$. Here is a product of two diagrams over $(\mathcal{P}, \mathcal{G})$:

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

We emphasise that the rightmost diagram is reduced; even though there is a dipole in the diagram over $\mathcal{P}$ obtained by removing the labels coming from the factors, the
fact that these labels are not all trivial along the path between the two right 2-cells
implies that they do not define a dipole in our diagram over ($\mathcal{P}$, $\mathcal{G}$).

In the same way that diagram groups can be described both in terms of diagrams
and as fundamental groups of Squier complexes, it is also possible to describe diagram
products as fundamental groups of specific complexes, which we describe now.

**Definition 4.39.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups indexed by $\Sigma$. The Squier complex $S(\mathcal{P}, \mathcal{G})$ is the square complex whose vertex-set is $\Sigma^+$ with

* an edge $(a, u \to v, b)$ between the words $aub$ and $avb$ whenever $(u = v) \in \mathcal{R}$,

* a loop $b(g)$ based at $w = \ell_1 \cdots \ell_n \in \Sigma^+$ for every $g \in G(w) := G_{\ell_1} \times \cdots \times G_{\ell_n}$,

* a square delimited by the four vertices $aubpc$, $avbpc$, $aubqc$, and $avbqc$ whenever $(u = v)$, $(p = q) \in \mathcal{R}$,

* a triangle delimited by the three loops based at $w$ labelled by $g, h, gh \in G(w)$,

* a cylinder between the loops labelled by $g \in G(a) \times G(b) \le G(aub)$ and $h \in G(a) \times G(b) \le G(avb)$ following the edge $(a, u \to v, b)$, where $(u = v) \in \mathcal{R}$.

The reader familiar with complexes of groups should recognise the topological
realisation of a simple complex of groups with the Squier square complex $S(\mathcal{P})$ as
the underlying complex; we refer to [9, Chapter II.12] for more information on simple
complexes of groups. In [47], diagram products are defined as fundamental groups of
such complexes. This point of view is equivalent to the definition presented here.

**Proposition 4.40 ([31]).** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation, $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups, and $w \in \Sigma^+$ a baseword. The diagram product $D(\mathcal{P}, \mathcal{G}, w)$ is naturally isomorphic to the fundamental group of $S(\mathcal{P}, \mathcal{G})$ based at $w$.

The proof of Proposition 4.40 is basically the same as the proof of Corollary 2.5.
It can be shown that a diagram product of diagram groups yields a diagram group.
More precisely, see the following theorem.

**Theorem 4.41 ([47]).** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. For every $s \in \Sigma$, fix a semigroup presentation $\mathcal{P}_s = \langle \Sigma_s \mid \mathcal{R}_s \rangle$ and a baseword $w_s \in \Sigma^+$. Assume that the alphabets $\Sigma$, $\Sigma_s$ ($s \in \Sigma$) are pairwise disjoint. The diagram product $D(\mathcal{P}, \mathcal{G}, w)$, where $\mathcal{G} := \{D(\mathcal{P}_s, w_s) \mid s \in \Sigma\}$, is isomorphic to the diagram group given by the semigroup presentation

$$ \left\langle \Sigma \sqcup \{x_s \mid s \in \Sigma\} \sqcup \bigsqcup_{s \in \Sigma} \Sigma_s \mid \bigsqcup_{s \in \Sigma} \mathcal{R}_s \sqcup \mathcal{R} \sqcup \{s = x_s w_s x_s, s \in \Sigma\} \right\rangle $$

and the baseword $w$.
It is worth noticing that some of the examples given in Section 2.4 arise in this way.

Because diagram groups admit a natural median geometry, it is reasonable to expect diagram products to admit a median geometry relative to their factors. This idea is formalised in [31] through *quasi-median geometry*. (Compare with Remark 4.48 below.)

**Definition 4.42.** Let $X$ be a connected graph. Given three vertices $x_1, x_2, x_3 \in X$, a median triangle is the data of three vertices $y_1, y_2, y_3 \in X$ such that

$$d(x_i, x_j) = d(x_i, y_i) + d(y_i, y_j) + d(y_j, x_j) \quad \forall i \neq j.$$

Its size is $d(y_1, y_2) + d(y_2, y_3) + d(y_3, y_1)$. The graph $X$ is *quasi-median* if any three vertices admit a unique median triangle of minimal size and if the gated hull of any such median triangle is a product of complete graphs.

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

Recall that, given a graph $X$, a subgraph $Y \subset X$ is *gated* if, for every $x \in X$, there exists some $z \in Y$ (referred to as the *gate* or *projection*) that belongs to at least one geodesic from $x$ to $y$ for every $y \in Y$. Notice that, when there existing, the gate is unique and it minimises the distance to $x$ from $Y$. Gatedness should be thought of as a strong convexity.

In the same way that median graphs can be described as one-skeleta of non-positively curved cellular complexes, namely, CAT(0) cube complexes, quasi-median graphs can be described as one-skeleta of CAT(0) prism complexes (where a *prism* refers to a product of simplices) [31].

**Definition 4.43.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation and $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups. Let $\text{QM}(\mathcal{P}, \mathcal{G})$ denote the graph whose vertices are the diagrams over $(\mathcal{P}, \mathcal{G})$ modulo dipole reductions and whose edges connect two diagrams if one can be obtained from the other by right-multiplying by a *unitary diagram* (i.e., a diagram that either contains a single cell and all of whose edges have trivial second coordinates in their labels, or has no cell and a single edge with a non-trivial second coordinate in its label).
<figure><img src="image_34.png" /><figcaption>**Figure 15.** A piece of QM($\mathcal{P}$, $\mathcal{G}$, ab) for $\mathcal{P} = \langle a, b, c \mid a = c, b = c \rangle$ and $G_a = G_b = G_c = \mathbb{Z}$.</figcaption></figure>

One easily sees that two diagrams belong to the same connected component of QM($\mathcal{P}$, $\mathcal{G}$) if and only if the labels in $\Sigma^+$ (i.e., when the second coordinates are forgotten) of their top paths are identical. Given a baseword $w \in \Sigma^+$, we denote by QM($\mathcal{P}$, $\mathcal{G}$, w) the connected component containing the diagrams whose top paths are labelled by w in $\Sigma^+$. The diagram product $D(\mathcal{P}$, $\mathcal{G}$, w) naturally acts on QM($\mathcal{P}$, $\mathcal{G}$, w) by left-multiplication (see Figure 15).

**Theorem 4.44 ([31]).** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation, $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups, and $w \in \Sigma^+$ a baseword. Then, QM($\mathcal{P}$, $\mathcal{G}$, w) is a quasi-median graph on which the diagram product $D(\mathcal{P}$, $\mathcal{G}$, w) acts freely. The action is cocompact if and only if $[w]_{\mathcal{P}}$ is finite and all the groups in $\mathcal{G}$ are finite.

The combination of the combinatorics of diagrams and the quasi-median geometry allows us to deduce a lot of information about diagram products. For instance, consider the following statements.

* A finitely generated diagram product has a solvable word problem if so do its factor.

* A diagram product is torsion-free if and only if so are its factors.

* Distorted elements in a diagram product belong to products of factors.

* A diagram product of groups acting nicely on median graphs acts nicely on median graphs [31, Theorems 10.36–10.38].

* The Hilbert space compression of a diagram product is bounded below by the compressions of its factors [31, Theorem 10.39].
It is worth noticing that every diagram product $D(\mathcal{P}, \mathcal{G}, w)$ surjects onto its underlying diagram group $D(\mathcal{P}, w)$ via the map that “forgets” the labels coming from the factors. Conversely, it is clear that $D(\mathcal{P}, w)$ embeds into $D(\mathcal{P}, \mathcal{G}, w)$; it corresponds to the diagrams all of whose edges have labels with trivial second coordinates (referred to as diagrams over $\mathcal{P}$ for simplicity). Therefore, diagram products split as semidirect products. More precisely, see the following theorem.

**Theorem 4.45** ([31]). Let $\mathcal{P} = (\Sigma|\mathcal{R})$ be a semigroup presentation, $\mathcal{G} = \{G_s | s \in \Sigma\}$ a collection of groups, and $w \in \Sigma^+$ a baseword. The diagram product decomposes as

$$D(\mathcal{P}, \mathcal{G}, w) = A(\mathcal{P}, \mathcal{G}, w) \times D(\mathcal{P}, w),$$

where $A(\mathcal{P}, \mathcal{G}, w)$ is a graph product whose vertex-groups are isomorphic to groups in $\mathcal{G}$.

We refer to [31, Theorem 10.58] for an even more precise statement. Recall that, given a graph $\Gamma$ and a collection of groups $\mathcal{G} = \{G_u | u \in V(\Gamma)\}$ indexed by the vertices of $\Gamma$, the *graph product* $\Gamma\mathcal{G}$ is

$$\langle G_u, u \in V(\Gamma) | [G_u, G_v] = 1, \{u, v\} \in E(\Gamma) \rangle,$$

where $[G_u, G_v] = 1$ is a shorthand for $[a, b] = 1$ for all $a \in G_u$ and $b \in G_b$. Usually, graph products are described as an interpolation between free products (when $\Gamma$ has no edge) and direct sums (when $\Gamma$ is a complete graph).

The strategy to prove the theorem is the following. Let $Y$ denote the subgraph of $M(\mathcal{P}, \mathcal{G}, w)$ given by the diagrams over $\mathcal{P}$. Its stabiliser under the action of $D(\mathcal{P}, \mathcal{G}, w)$ coincides with $D(\mathcal{P}, w)$. Also, let $\mathcal{J}$ denote the collection of all the hyperplanes in $M(\mathcal{P}, \mathcal{G}, w)$ tangent to $Y$. In a quasi-median graph, a hyperplane is a class of parallel *cliques* (i.e., maximal complete subgraphs) instead of parallel edges in the case of median graphs. To each hyperplane corresponds a *rotative-stabiliser*, i.e., the subgroup of its stabiliser that stabilises each of the cliques it contains. Thanks to a ping-pong lemma, it can be shown that the subgroup generated by the rotative-stabilisers of all the hyperplanes in $\mathcal{J}$ decomposes as the graph product of the rotative-stabilisers over the crossing graph of $\mathcal{J}$ (i.e., the graph whose vertex-set is $\mathcal{J}$ and whose edges connect two hyperplanes whenever they are transverse). This is our graph product $A(\mathcal{P}, \mathcal{G}, w)$. One easily verifies that $D(\mathcal{P}, w)$ normalises and intersects trivially $A(\mathcal{P}, \mathcal{G}, w)$. The proof is complete once it is shown that $A(\mathcal{P}, \mathcal{G}, w)$ and $D(\mathcal{P}, w)$ generate the diagram product.

As an application of Theorem 4.45, it is possible to prove the following theorem, initially obtained in [50] by using different methods.

**Theorem 4.46.** Every diagram group $G$ satisfies a short exact sequence

$$1 \to R \to G \to S \to 1,$$
where $R$ is a subgroup of a right-angled Artin group and where $S$ is a subgroup of Thompson's group $F$.

The strategy is as follows. Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be an arbitrary semigroup presentation and $w \in \Sigma^+$ a baseword. The goal is to prove that $D(\mathcal{P}, w)$ embeds into the diagram product $D(\mathcal{Q}, \mathcal{G}, x)$ where $\mathcal{Q} = \langle x \mid x = x^2 \rangle$ and where $G_x$ is the free group $\mathbb{F}$ formally generated by the relations in $\mathcal{R}$. The desired conclusion will follow since $D(\mathcal{Q}, \mathcal{G}, x)$ splits as a semidirect product of a right-angled Artin group with Thompson group's $F$ as a consequence of Theorem 4.45.

In order to construct such an embedding, we fix, for every $n \ge 1$, a well-chosen $(x^n, x)$-diagram $\Gamma_n$ over $\mathcal{Q}$. Then, we transform a diagram $\Delta$ over $\mathcal{P}$ into a diagram over $(\mathcal{Q}, \mathcal{G})$ by replacing each cell of $\Delta$ labelled by a relation $u = v$ with the diagram $\Gamma_n \circ \varepsilon(f) \circ \Gamma_m^{-1}$, where $n$ is the length of $u$, $m$ the length of $v$, and $\varepsilon(f)$ the diagram reduced to a single edge labelled by $(x, f)$ with $f$ the (inverse of the) generator of $\mathbb{F}$ corresponding to $u = v$.

Since right-angled Artin groups and Thompson's group $F$ are locally indicable, and since locally indicable groups are automatically orderable, Theorem 4.46 immediately implies the following corollary.

**Corollary 4.47.** *Diagram groups are locally indicable, hence orderable.*

**Remark 4.48.** It is worth noticing that one can make a diagram product $D(\mathcal{P}, \mathcal{G}, w)$ act on a median graph instead of a quasi-median graph. Given a diagram $\Delta$ and a (possibly empty) collection of edges $\varepsilon$ in the bottom path of $\Delta$, let $\Delta(\varepsilon)$ denote the set of the diagrams obtained from $\Delta$ by modifying the second coordinates in the labels of the edges in $\varepsilon$. Observe that $\Delta(\varepsilon)$ defines a coset in the groupoid of the diagrams over $(\mathcal{P}, \mathcal{G})$. Let $M(\mathcal{P}, \mathcal{G})$ denote the graph whose vertices are the cosets $\Delta(\varepsilon)$ and whose edges connect two cosets $\Phi(\zeta)$ and $\Psi(\xi)$ either if $\Psi = \Phi$ and the symmetric difference between $\zeta, \xi$ has cardinality one or if $\Psi$ is obtained from $\Phi$ by gluing a 2-cell below $\Phi$ along a path disjoint from $\zeta$ and $\xi$ is the image of $\zeta$ after the process. Then, the diagram product $D(\mathcal{P}, \mathcal{G}, w)$ acts on a connected component $M(\mathcal{P}, \mathcal{G}, w)$ of $M(\mathcal{P}, \mathcal{G})$ with stabilisers isomorphic to products of factors. In fact, $M(\mathcal{P}, \mathcal{G})$ and $QM(\mathcal{P}, \mathcal{G})$ are basically subdivisions of a common space, but in practice it turns out to be easier and more natural to work with the quasi-median graph.

# 5. Generalisations

## 5.1. Planar, annular, and symmetric diagram groups

Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation. Given a diagram over $\mathcal{P}$, one can construct a *dual picture* made of *transistors* which are connected by *wires* labelled by $\Sigma$. See Figure 16. Roughly speaking, a transistor is a black box with top and bottom
<figure><img src="image_35.png" /><figcaption>**Figure 16.** A diagram over $\langle a, b \mid a = a^2, b = b^2, ab = ba \rangle$ and its dual picture.</figcaption></figure>

wires such that, if $u \in \Sigma^+$ (resp., $v \in \Sigma^+$) is the word obtained by reading from left to right the labels of its top (resp., bottom) wires, then $u = v$ or $v = u$ belongs to $\mathcal{R}$.

All the terminology introduced in Section 2 for diagrams can be easily adapted to pictures. For instance, a dipole in a picture refers to two transistors $\tau_1, \tau_2$ labelled by $u = v$ and $v = u$ for some relation in $\mathcal{R}$ such that bottom wires of $\tau_1$ and the top wires of $\tau_2$ coincide. One reduces the dipole by removing the two transistors and connecting the top wires of $\tau_1$ with the bottom wires of $\tau_2$.

This alternative point of view allows us to generalise diagram groups in several natural directions. Our initial diagram groups, now referred to as *planar diagram groups*, have their elements represented by pictures whose wires do not cross and are monotonic in the vertical direction. A similar definition on annuli yields *annular diagram groups*. And allowing wires to cross in an arbitrary way yields *symmetric*<fnref n="3" /> *diagram groups*. We do not give precise definitions and refer to [25] for more details. See Figures 17 and 18 for examples of products of annular and symmetric pictures.

Thus, given a semigroup presentation $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ and a baseword $w \in \Sigma^+$, we have three nested groups

$$D_p(\mathcal{P}, w) \subset D_a(\mathcal{P}, w) \subset D_s(\mathcal{P}, w)$$

given by the corresponding planar, annular, and symmetric diagram groups. As shown below, for $\mathcal{P} = \langle x \mid x = x^2 \rangle$ and $w = x$, one recovers the three classical Thompson groups $F \subset T \subset V$.

<footnote n="3">³In [45], these groups are referred to as *braided diagram groups*, even though the wires are not braided but just permuted. We suggest to replace *braided* with *symmetric*, and to keep the initial terminology for the groups considered in Section 5.2.</footnote>
<figure><img src="image_36.png" /><figcaption>**Figure 17.** A product of annular pictures over $\langle a, b \mid a = a^2, ab = ba \rangle$.</figcaption></figure>

Annular and symmetric diagram groups are sketched in [45] and further investigated in [25]. Compared to (planar) diagram groups, much less is known about these groups. Nevertheless, let us record what can be extracted from the existing literature.

**Word problem.** Similarly to diagrams, every planar, annular, or symmetric picture admits a unique *reduced representative*, i.e., reducing the dipoles, whatever the order we follow, always yields the same picture. See [25]. As a consequence, we have the following proposition.

**Proposition 5.1.** *Planar, annular, and symmetric diagram groups have solvable word problems.*

Indeed, given a picture representing an element of the group, it suffices to reduce its dipoles. Once we get a reduced picture, we know that our element is trivial if and only if the picture is reduced to a collection of vertical wires.

**Median geometry.** The construction described in Section 4.2 generalises to annular and symmetric diagram groups [25]. Given a semigroup presentation $\mathcal{P}$, we can construct a median graph $M_s(\mathcal{P})$ as follows. The vertices are the symmetric pictures over $\mathcal{P}$ modulo dipole reduction and right-multiplication by a *symmetric picture* (i.e., a picture with no transistor). And the edges connect the classes of two pictures when one can be obtained from the other by adding a transistor at its bottom. The graph $M_s(\mathcal{P})$ turns out to be median, and the symmetric diagram group $D_s(\mathcal{P}, w)$, given a base-word $w$, naturally acts by left-multiplication on the connected component $M_s(\mathcal{P}, w)$ containing the picture with only vertical wires labelled by the word $w$. Restricting to annular pictures, one gets similarly a median graph $M_a(\mathcal{P}, w)$ on which the annular diagram group $D_a(\mathcal{P}, w)$ acts. Consequently, Theorem 4.9 generalises as follows.

**Theorem 5.2 ([25]).** *Annular and symmetric diagram groups act properly on median graphs locally of finite cubical dimension.*
<figure><img src="image_37.png" /><figcaption>**Figure 18.** A product of symmetric pictures over $\langle a, b | a = a^2, b = b^2, ab = ba \rangle$.</figcaption></figure>

Contrary to planar diagram groups, annular and symmetric diagram groups are usually not torsion-free, since it is possible to permute the wires. More precisely, given an annular (resp., a symmetric) diagram group $D_a(\mathcal{P}, w)$ (resp., $D_s(\mathcal{P}, w)$) and a picture $\Delta$ with top label $w$, the subgroup given by the pictures

$$ \Delta \cdot \left( \substack{\text{permutation of the} \\ \text{bottom wires of } \Delta} \right) \cdot \Delta^{-1} $$

is always finite (but possibly trivial). We refer to such a subgroup as a *permutation subgroup*. In annular diagram groups, permutation subgroups are always cyclic. It turns out that permutation subgroups are sufficient to understand finite subgroups, and more generally finitely generated torsion subgroups.

**Corollary 5.3.** In an annular or symmetric diagram group, every finitely generated torsion subgroup is contained in a permutation subgroup.

*Proof.* Because the median graph on which our diagram group acts is locally of finite cubical dimension, every finitely generated torsion subgroup must fix a vertex [39, Theorem 4.23]. But it follows from the construction of the median graph that vertex-stabilisers are permutation subgroups. ■

It is worth noticing, in view of Corollary 5.3, that annular and symmetric diagram groups may contain infinite torsion subgroups. For instance, the Houghton groups described below contain the group of finitely supported permutations of an infinite set.
We can also deduce from Theorem 5.2 analogues of Theorem 2.23 and Proposition 2.27.

**Corollary 5.4.** In annular and symmetric diagram groups, polycyclic subgroups are virtually abelian and undistorted.

*Proof.* If a group acts properly on a median graph, then its finitely generated abelian subgroups are automatically undistorted [18, Corollary 6.B.5] and its polycyclic subgroups are automatically virtually abelian [18, Corollary 6.C.8]. ■

**Corollary 5.5.** In annular and symmetric diagram groups, an infinite-order element cannot be an arbitrarily large power.

*Proof.* If $g$ is an infinite-order element in our annular or symmetric diagram group, it follows from [52] that it acts as a translation on some bi-infinite geodesic line. Let $\|g\|$ denote the length of this translation. If the equality $a = b^k$ holds in our group, where $a, b$ are elements of infinite order, then

$$ \|a\| = \|b^k\| = |k| \cdot \|b\| \ge |k|, $$

since translation length are integers. Thus, $|k|$ cannot be arbitrarily large. ■

As a consequence, annular and symmetric diagram groups cannot contain $\mathbb{Q}$. This contrasts with, for instance, the lift $\bar{T}$ of Thompson's group $T$ in Homeo($\mathbb{R}$) [6].

**Finiteness properties.** Even though annular and symmetric diagram groups do not act freely on their median graphs, the properness of the actions still allows us to deduce that some diagram groups satisfy good finiteness properties. The easiest case is when the actions are cocompact, providing an analogue of Proposition 4.14.

**Proposition 5.6.** Let $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$ be a semigroup presentation and $w \in \Sigma^+$ a base-word. If $[w]_{\mathcal{P}}$ is finite, then the annular and symmetric diagram groups $D_a(\mathcal{P}, w)$ and $D_s(\mathcal{P}, w)$ are of type $F_\infty$.

A more interesting result, an analogue of Theorem 4.15 which is proved using the same strategy based on Morse theory, is the following theorem.

**Theorem 5.7 ([26]).** Let $\mathcal{P} = \langle\Sigma|\mathcal{R}\rangle$ be a semigroup presentation and $w \in \Sigma^+$ a baseword. If the oriented graph $\Gamma_a(\mathcal{P})$ (resp., $\Gamma_s(\mathcal{P})$) does not contain an infinite oriented ray and contains only finitely many sink vertices, then $D_a(\mathcal{P}, w)$ (resp., $D_s(\mathcal{P}, w)$) is of type $F_\infty$.

Here, $\Gamma_a(\mathcal{P})$ (resp., $\Gamma_s(\mathcal{P})$) is the oriented graph whose vertices are the words in $\Sigma^+$ modulo cyclic permutation (resp., modulo permutation) and whose oriented edges connect a given word $aub$ to a word $avb$ whenever $u = v$ belongs to $\mathcal{R}$.
**Diagram products.** Let $\mathcal{P} = \langle \Sigma | \mathcal{R} \rangle$ be a semigroup presentation, $\mathcal{G} = \{G_s \mid s \in \Sigma\}$ a collection of groups indexed by $\Sigma$, and $w \in \Sigma^+$ a baseword. By labelling the wires of annular and symmetric pictures with elements from groups in $\mathcal{G}$, one can naturally extend the definitions from Section 4.7 in order to define annular and symmetric diagram products. This is done in [34], where the quasi-median geometry is also extended. This allows us to prove an analogue of Theorem 4.45 and to prove a statement similar to Theorem 4.46, namely, the following theorem.

**Theorem 5.8 ([34]).** Every annular (resp., symmetric) diagram group satisfies a short exact sequence

$$1 \to R \to G \to S \to 1,$$

where R is a subgroup of a right-angled Artin group and S is a subgroup of Thompson's group T (resp., V).

For instance, this implies that every simple annular (resp., symmetric) diagram group embeds into Thompson's group T (resp., V). This excludes in particular the higher-dimensional Thompson groups $nV$ for $n \ge 2$ [10].

**Examples.** Let $\mathcal{P} = \langle x \mid x = x^2 \rangle$. A reduced annular (resp., symmetric) $(x, x)$-picture over $\mathcal{P}$ can always be written as the concatenation of a *positive picture* (i.e., all of whose transistors are labelled by $x = x^2$), followed by a *cyclic permutation* (resp., a permutation) of the wires, and finally by a *negative picture* (i.e., all of whose transistors are labelled by $x^2 = x$). Such a structure immediately yields a triple $(T_1, \sigma, T_2)$ where $T_1, T_2$ are two finite rooted 2-regular trees with the same number of leaves, say $n$, and where $\sigma$ is a cyclic permutation (resp., a permutation) of $n$ elements. This correspondence induces an isomorphism from the annular diagram group $D_a(\mathcal{P}, x)$ to Thompson's group T (resp., from the symmetric diagram group $D_s(\mathcal{P}, x)$ to Thompson's group V). We refer to [15] for more information about the representations of elements of T and V as pairs of trees.

These examples can be found in [45]. Other interesting examples can be found in [27], namely, the Houghton groups $H_n$ and the symmetrisation $QV$ of Thompson's group V.

Given an $n \ge 1$, let $R_n$ denote the union of $n$ disjoint infinite rays; we also denote by $R_n^{(0)}$ its vertex-set. The *Houghton group* $H_n$ is the group of the bijections $R_n^{(0)} \to R_n^{(0)}$ that preserve the ends of the graph $R_n$ and that preserve adjacency and non-adjacency for all but finitely many pairs of vertices. In other words, an element of $H_n$ acts by translations outside a finite set of $R_n$ and it permutes the vertices of this set in an arbitrary way. Since, on each infinite ray, an element of $H_n$ acts as a translation, we have $n$ morphisms $H_n \to \mathbb{Z}$ giving the corresponding translation lengths (positive if the vertices are translated towards infinity, negative otherwise). In order to get a bijection $R_n^{(0)} \to R_n^{(0)}$, the sum of these translation lengths must be zero. Thus, one
deduces a short exact sequence

$$1 \to S_{\infty} \to H_n \to \mathbb{Z}^{n-1} \to 1,$$

where $S_{\infty}$ is identified with the finitely supported permutations of $R_n^{(0)}$.

The definition of $QV$ has a similar flavor. Let $\mathcal{T}$ denote the rooted 2-regular tree with a fixed embedding in the plane (so each vertex has two children: a left and a right). We also denote by $\mathcal{T}^{(0)}$ its vertex-set. Then, $QV$ is the group of the bijections $\mathcal{T}^{(0)} \to \mathcal{T}^{(0)}$ that preserves adjacency, non-adjacency, and left-right order on the children with only finitely many exceptions. Notice that $QV$ has a well-defined action on the boundary of $\mathcal{T}$, which is a Cantor set. This action turns out to coincide with the usual definition of Thompson's group $V$ as a group of homeomorphisms of the Cantor set. Hence, one deduces a short exact sequence

$$1 \to S_{\infty} \to QV \to V \to 1,$$

where $S_{\infty}$ is identified with the finitely supported permutations of $\mathcal{T}^{(0)}$.

**Proposition 5.9 ([27]).** For every $n \ge 2$, the Houghton group $H_n$ is isomorphic to the symmetric diagram group $D_s(\mathcal{P}_n, r)$, where

$$\mathcal{P}_n := \langle a, x_1, \dots, x_n \mid x_1 = x_1 a, \dots, x_n = x_n a \rangle.$$

The group $QV$ is isomorphic to the symmetric diagram group $D_s(Q, x)$, where $Q := \langle a, x \mid x = xax \rangle$.

Figure 19 illustrates how to describe the second Houghton group as a symmetric diagram group. The philosophy is the same for the other Houghton groups and for $QV$. See [27, Examples 4.3 and 4.4] for more details. Notice that, by the same argument, one can show that the groups $QV_{n,r}$, which are defined by replacing our previous rooted tree $\mathcal{T}$ with a forest of $r$ rooted $n$-regular trees, are also symmetric diagram groups.

## 5.2. Braided-like diagram groups

In addition to planar, annular, and symmetric diagram groups, it would be natural to define *braided diagram groups*, where wires in pictures are thought of as strands in braids. This variation has not been defined properly in the literature yet. Nevertheless, the following results can be reasonably expected:

* The braided diagram group $D_b(\mathcal{P}, x)$, where $\mathcal{P} = \langle x \mid x = x^2 \rangle$, coincides with the braided Thompson group $brV$ [11, 22].

* A braided diagram group acts on a median graph with vertex-stabilisers isomorphic to finitely generated braid groups. As a consequence, it is torsion-free.
<figure><img src="image_38.png" /><figcaption>Figure 19. $D_s((a, x_1, x_2 | x_1 = x_1a, x_2 = ax_2), x_1x_2)$ isomorphic to $H_2$.</figcaption></figure>

* Polycyclic subgroups in braided diagram groups are virtually abelian and undis-
torted.

* Every braided diagram group $G$ satisfies a short exact sequence

$$1 \to R \to G \to S \to 1,$$

where $R$ is a subgroup of a right-angled Artin group and where $S$ is a subgroup of $brV$.

It would interesting to know whether braided diagram groups are bi-orderable. In other words, is it possible to combine the bi-orderability of braid groups and (planar) diagram groups in order to deduce the bi-orderability of braided diagram groups?

In this direction, we can imagine as many diagram-like groups as there are braided-like groups. This could include *virtual diagram groups*, in reference to virtual braid groups; *loop diagram groups*, in reference with loop braid groups; *cactus diagram groups*, in reference to the cactus groups; etc. The variations are virtually endless.

In another direction, it is possible to treat wires differently according to the letters labelling it. There are at least two such examples available in the literature.

The first example is [3], dedicated to the symmetrisation $QF$ (resp., $QT$) of Thompson's group $F$ (resp., $T$). The group $QF$ (resp., $QT$) is naturally a subgroup of $QV$, which is isomorphic to the symmetric diagram group $D_s(\mathcal{P}, x)$ where $\mathcal{P} = \langle a, x \mid x = axa \rangle$, and its elements can be described as the pictures where the wires labelled $a$ behave like in a planar (resp., annular) picture. This point of view allows the authors to show that the groups $QF, QT, QV$ are of type $F_\infty$.

As another example, we can mention the *Chambord groups* introduced in [37]. Formally, they are defined thanks to specific diagrams with both strands (which are braided) and wires (which are cyclically permuted). This formalism allows the authors