#  $C^{*}$-algebras associated to directed graphs of groups, and models of
Kirchberg algebras

Victor Wu  Victor Wu, School of Mathematics and Statistics
The University of Sydney<EMAIL_ADDRESS>
###### Abstract.

We introduce $C^{*}$-algebras associated to directed graphs of groups. In
particular, we associate a combinatorial $C^{*}$-algebra to each row-finite
directed graph of groups with no sources, and show that this $C^{*}$-algebra
is Morita equivalent to the crossed product coming from the corresponding
group action on the boundary of a directed tree. Finally, we show that these
$C^{*}$-algebras (and their Morita equivalent crossed products) contain the
class of stable UCT Kirchberg algebras.

##  1\. Introduction

Universal $C^{*}$-algebras for generators and relations encoding an underlying
combinatorial object have long been studied because of their tractable nature,
and their ability to prove rich sources of examples. The study of these
$C^{*}$-algebras, commonly referred to as combinatorial $C^{*}$-algebras,
began with the work of Cuntz and Krieger, who in [8] associated a
$C^{*}$-algebra to a finite $\\{0,1\\}$-matrix. These algebras developed into
directed graph $C^{*}$-algebras, which in turn have branched out into various
generalisations, including $C^{*}$-algebras of higher rank graphs [18] and
left cancellative small categories [33] (see also [27] for an overview).

One abundant class of combinatorial objects are graphs of groups, which were
introduced by Serre in [31] and further studied by Bass in [4]. Roughly
speaking, these are (undirected) graphs where each vertex and edge has an
associated group, and each edge group embeds into its adjacent vertex groups.
The key idea of what is known as Bass–Serre theory is that graphs of groups
“encode” group actions on trees: given a group acting on a tree (with a mild
assumption), we can construct a graph of groups from the quotient graph and
the stabiliser subgroups at the vertices and edges; and from this graph of
groups we can construct a group, called the fundamental group, and an action
of this group on a tree, called the Bass–Serre tree, which is isomorphic to
the original action. We provide a more detailed review of Bass–Serre theory in
Section 2, which also contains other background definitions and theory
necessary for the rest of the paper.

Graphs of groups were first studied in a $C^{*}$-algebraic setting in [22],
which considered finite graphs of finite groups; these were then generalised
to countable graphs of countable groups (with some regularity assumptions) in
[6]. The authors of [6] also proved a ‘$C^{*}$-algebraic Bass–Serre theorem’,
which states that their graph of groups $C^{*}$-algebra is stably isomorphic
to the crossed product coming from the action of the fundamental group on the
boundary of the Bass–Serre tree.

In this paper, we consider what we call directed graphs of groups: these are
simply graphs of groups where the graph additionally carries an orientation.
While these objects are not so interesting from a geometric group theory
perspective (as the orientation data does not fundamentally change anything in
the theory), they have found interest in other fields: for example, it was
shown in [20] that directed graph of groups are in a one-to-one correspondence
with skeletal cancellative Levi categories.

Our motivation for studying directed graphs of groups comes from the
observation that Bass–Serre theory implies that directed graphs of groups are
in a one-to-one correspondence with group actions on directed trees: we can
simply ‘lift’ the orientation of a directed graph of groups to the Bass–Serre
tree. These actions fit into the framework studied in [7], which provides
structural theorems and $K$-theoretic formulae for crossed products coming
from such actions.

In Section 3 we develop the theory of directed graphs of groups that we will
use in the rest of the paper. As part of this, we give an alternate approach
to associating a category (which we will call the word category) to a directed
graph of groups; this category matches the one from [20], but the construction
is more direct and is more natural for our purposes.

Inspired by the relations in [6], we associate a $C^{*}$-algebra to each
directed graph of groups in Section 4, where we also show that this algebra is
isomorphic to the $C^{*}$-algebra of the word category of the directed graph
of groups. These directed graph of groups $C^{*}$-algebras generalise directed
graph $C^{*}$-algebras (in that for a directed graph of groups where all
groups are trivial, the $C^{*}$-algebra of the directed graph of groups is
isomorphic to that of the underlying directed graph), and many properties of
directed graph $C^{*}$-algebras generalise to this broader class of
$C^{*}$-algebras as well.

One such property is that these $C^{*}$-algebras are Morita equivalent to
certain crossed products by commutative $C^{*}$-algebras. For a directed graph
$E$, it was shown in [17] that its $C^{*}$-algebra $C^{*}(E)$ is Morita
equivalent to the crossed product $C_{0}(\partial T)\rtimes G$, where $T$ is
the universal covering tree of $E$ and $G$ is the fundamental group of $E$,
which acts naturally on $T$. For a directed graph of groups $\mathcal{G}_{+}$,
we have the following generalisation (this can also be viewed as a
‘$C^{*}$-algebraic directed Bass–Serre theorem’, in line with [6]).

######  Theorem A (Theorem 5.1).

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite (connected)
directed graph of groups with no sources, and choose a base vertex
$x\in\Gamma^{0}$. Write $\pi_{1}(\mathcal{G},x)$ for the fundamental group of
$\mathcal{G}$ based at $x$, and write $X_{\mathcal{G}_{+},x}$ for the directed
Bass–Serre tree based at $x$. Then $C^{*}(\mathcal{G}_{+})$ is Morita
equivalent to $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$.

Section 5 is dedicated to the proof of this theorem, which has two steps:
first we find a tractable groupoid model for $C^{*}(\mathcal{G}_{+})$ with
some help from the general results in [23] concerning groupoid models for the
$C^{*}$-algebras of categories; then we show that this groupoid is equivalent
to the transformation groupoid $\pi_{1}(\mathcal{G},x)\ltimes\partial
X_{\mathcal{G}_{+},x}$, whose $C^{*}$-algebra is the crossed product in the
theorem statement.

Since Morita equivalence preserves $K$-theory and many structural properties
of $C^{*}$-algebras such as simplicity and nuclearity, we can use the results
of [7] to study these properties for directed graph of groups
$C^{*}$-algebras. In Section 6, the final section of this paper, we study
these properties for the special case of directed graphs of infinite cyclic
groups (that is, directed graphs of groups where all vertex and edge groups
are infinite cyclic); these are simple enough to study while also providing a
rich class of examples of $C^{*}$-algebras.

As a demonstration of this, we turn to the study of Kirchberg algebras
(simple, separable, nuclear and purely infinite $C^{*}$-algebras). By the
celebrated Kirchberg–Phillips theorem ([16, 26]), stable Kirchberg algebras
satisfying the Universal Coefficient Theorem (UCT) are classified completely
by their $K$-theory, making this an interesting class of $C^{*}$-algebras to
study. This classification result has led to the development of concrete
models for Kirchberg algebras, such as Spielberg’s hybrid graph algebras [32]
and Katsura’s topological graph algebras [14], which have in turn led to a
deeper understanding of Kirchberg algebras (see for example [15]).

In this paper, we find sufficient conditions on a directed graph of infinite
cyclic groups for its $C^{*}$-algebra to be a UCT Kirchberg algebra, and we
also provide a formula for the $K$-theory of these algebras. Using these
results, we are able to prove the following theorem, which provides two
additional models of Kirchberg algebras.

######  Theorem B (Theorem 6.2).

Let $A$ be a stable UCT Kirchberg algebra. There exists a countable, row-
finite directed graph of infinite cyclic groups
$\mathcal{G}_{+}=(\Gamma_{+},G)$ with no sources, such that $A\cong
C^{*}(\mathcal{G}_{+})\cong C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G}_{+},x)$ for any
$x\in\Gamma^{0}$.

Notably, we show how to construct any stable UCT Kirchberg algebra as a
crossed product $C^{*}$-algebra. Crossed product $C^{*}$-algebras,
particularly those arising from a group action on a commutative
$C^{*}$-algebra, are a fundamental class of examples of $C^{*}$-algebras, and
have been greatly studied from the perspective of determining conditions under
which they are Kirchberg algebras ([2, 11, 13, 19]). It is known that all
stable UCT Kirchberg algebras are crossed products by $A\mathbb{T}$-algebras
[30], but the construction is not concrete. Theorem B is, to the best of our
knowledge, the first concrete construction of (stable) UCT Kirchberg algebras
as crossed products. We hope that this might help develop our understanding of
Kirchberg algebras, as well as promote further research into the modelling of
classifiable $C^{*}$-algebras by crossed products.

Acknowledgements. The author would like to thank his PhD supervisor Nathan
Brownlowe for helpful conversations and comments during the preparation of
this paper. The author was supported by an Australian Government Research
Training Program Stipend Scholarship.

##  2\. Background

In this section we collect the background material required for the paper. We
recall definitions about graphs and trees in Section 2.1, left cancellative
small categories and their $C^{*}$-algebras in Section 2.2, and groupoids of
dynamical origin in Section 2.3. Finally in Section 2.4 we recount some of the
theory of (undirected) graphs of groups.

###  2.1. Graphs and trees

We start by defining the notions of graph that we will use throughout this
paper.

######  Definition 2.1.

A directed graph $E=(E^{0},E^{1},r,s)$ consists of countable sets of vertices
$E^{0}$ and edges $E^{1}$, along with range and source maps $r,s\colon
E^{1}\to E^{0}$. We say that $E$ is row-finite if $r^{-1}(v)$ is finite for
all $v\in E^{0}$ (that is, each vertex receives finitely many edges), and $E$
has no sources if $r^{-1}(v)\neq\emptyset$ for all $v\in E^{0}$.

######  Definition 2.2.

An undirected graph (or simply a graph) $\Gamma=(\Gamma^{0},\Gamma^{1},r,s)$
is a directed graph equipped with an “edge reversal” map
$e\mapsto\overline{e}$ on $\Gamma^{1}$ such that for all $e\in\Gamma^{1}$, we
have

$\overline{e}\neq e,\quad\overline{\overline{e}}=e,\quad\text{and}\quad
s(e)=r(\overline{e}).$

An orientation of $\Gamma$ is a subset $\Gamma_{+}^{1}$ of $\Gamma^{1}$
containing exactly one element of $\\{e,\overline{e}\\}$ for each
$e\in\Gamma^{1}$.

If $\Gamma_{+}^{1}$ is an orientation of the graph $\Gamma$, then we can
consider the directed graph $\Gamma_{+}=(\Gamma^{0},\Gamma_{+}^{1},r,s)$,
where the range and source maps are inherited from $\Gamma$. The original
graph $\Gamma$ can be recovered from $\Gamma_{+}$ by including a “reversal”
${\overline{e}}$ for each $e\in\Gamma_{+}^{1}$; we call $\Gamma$ the
underlying undirected graph of $\Gamma_{+}$.

A path (of length $n$) in a directed graph $E$ is a sequence of edges
$e_{1}e_{2}\dots e_{n}$ in $E^{1}$ satisfying $s(e_{i})=r(e_{i+1})$ for $1\leq
i\leq n-1$ (in the case that $n=0$, then a path is just a single vertex $v\in
E^{0}$). We note that we are using the “Australian” convention for path
notation, to be consistent with [6] and [7]. For a path
$\lambda=e_{1}e_{2}\dots e_{n}$ in $E$, we write $\lvert\lambda\rvert=n$ for
the length of $\lambda$. We write $E^{n}$ for the set of paths in $E$ of
length $n$, and we write $vE^{n}$ for the subset of $E^{n}$ consisting of
paths with range $v\in E^{0}$. We write $E^{*}$ for the set of all paths in
$E$.

For (undirected) graphs, we have the additional notion of a reduced path,
which is a path $e_{1}e_{2}\dots e_{n}$ such that
$e_{i+1}\neq{\overline{e}}_{i}$ for $1\leq i<n$ (that is, there is no “back-
tracking” in the path). An undirected graph is connected if there is a
(reduced) path between any two vertices, and a directed graph is connected if
its underlying undirected graph is connected. All directed and undirected
graphs in this paper will be connected unless specified otherwise.

A tree is a graph such that there is a unique reduced path from any vertex to
any other vertex. A directed tree is a directed graph whose underlying
undirected graph is a tree.

We will be considering the following natural topological spaces arising from
directed graphs and trees:

  1. (1)

Let $E$ be a directed graph. We write $E^{\infty}$ for the space of infinite
paths in $E$ (that is, infinite sequences of edges $e_{1}e_{2}\dots$ in
$E^{1}$ with $s(e_{i})=r(e_{i+1})$ for all $i\geq 1$) with topology generated
by finite unions, intersections and set differences of subsets of the form
$\lambda E^{\infty}$, $\lambda\in E^{*}$.

  2. (2)

Let $T$ be a directed tree. We can define an equivalence relation on the set
of infinite paths in $T$ as follows. We say that two infinite paths
$e_{1}e_{2}\dots$ and $f_{1}f_{2}\dots$ in $T$ are shift-tail equivalent if
there exist positive integers $N,M$ such that $e_{N+i}=f_{M+i}$ for all $i\geq
0$. The boundary $\partial T$ of $T$ is the space of shift-tail equivalence
classes of infinite paths in $T$, with topology generated by finite unions,
intersections and set differences of subsets of the form
$Z(v):=\\{[\lambda]:\lambda\in vT^{\infty}\\}$, $v\in T^{0}$.

###  2.2. Left cancellative small categories and their $C^{*}$-algebras

We now recall definitions relating to left cancellative small categories and
their $C^{*}$-algebras.

######  Definition 2.3.

A small category $\Lambda$ is left cancellative if
$\alpha\beta=\alpha\gamma\implies\beta=\gamma$ for all
$\alpha,\beta,\gamma\in\Lambda$ with $s(\alpha)=r(\beta)=r(\gamma)$. We will
refer to left cancellative small categories as LCSCs for short.

For any $\alpha\in\Lambda$, we will write $\alpha\Lambda$ to denote the set of
morphisms in $\Lambda$ of the form $\alpha\lambda$, $\lambda\in\Lambda$.

######  Definition 2.4.

An LCSC $\Lambda$ is finitely aligned if for every $\alpha,\beta\in\Lambda$
there is a finite set $F\subseteq\Lambda$ such that
$\alpha\Lambda\cap\beta\Lambda=\bigcup_{\gamma\in F}\gamma\Lambda$. If $F$ can
always be chosen to have at most one element (that is, for every
$\alpha,\beta\in\Lambda$ either $\alpha\Lambda\cap\beta\Lambda=\emptyset$, or
there is $\gamma\in\Lambda$ such that
$\alpha\Lambda\cap\beta\Lambda=\gamma\Lambda$), then $\Lambda$ is singly
aligned.

######  Definition 2.5.

Let $\Lambda$ be a LCSC. Define a relation $\leq$ on $\Lambda$ by
$\alpha\leq\beta$ if $\beta\in\alpha\Lambda$ (this relation is reflexive and
transitive but not necessarily antisymmetric, so it is not a partial order in
general). A common extension of $\alpha,\beta\in\Lambda$ is an element
$\gamma\in\Lambda$ such that $\alpha,\beta\leq\gamma$, and a common extension
$\gamma$ of $\alpha,\beta$ is minimal if there is no common extension $\delta$
of $\alpha$ and $\beta$ such that $\delta\leq\gamma$ and
$\gamma\not\leq\delta$. Write $\alpha\vee\beta$ for the set of minimal common
extensions of $\alpha$ and $\beta$.

######  Definition 2.6.

Let $\Lambda$ be a LCSC, and let $C\subseteq\Lambda$. A subset $E\subseteq C$
is exhaustive if for every $\alpha\in C$, there exists $\beta\in E$ such that
$\alpha\Lambda\cap\beta\Lambda\neq\emptyset$.

In [33], Spielberg defined the Cuntz–Krieger algebra for a LCSC. In the
finitely aligned case, we have the following presentation by generators and
relations, which we use here as an alternate definition:

######  Definition 2.7 ([33, Theorem 10.15(i)]).

Let $\Lambda$ be a finitely aligned LCSC. A Cuntz–Krieger $\Lambda$-family is
a collection $\\{S_{\lambda}:\lambda\in\Lambda\\}$ satisfying

  1. (S1)

$S_{\lambda}^{*}S_{\lambda}=S_{s(\lambda)}$;

  2. (S2)

$S_{\lambda}S_{\mu}=S_{\lambda\mu}$ if $s(\lambda)=r(\mu)$;

  3. (S3)

$S_{\lambda}S_{\lambda}^{*}S_{\mu}S_{\mu}^{*}=\bigvee_{\nu\in\lambda\vee\mu}S_{\nu}S_{\nu}^{*}$;

  4. (S4)

$S_{v}=\bigvee_{\lambda\in F}S_{\lambda}S_{\lambda}^{*}$ if $F\subseteq
v\Lambda$ is a finite exhaustive set.

The Cuntz–Krieger algebra $\mathcal{O}(\Lambda)$ of $\Lambda$ is the universal
$C^{*}$-algebra generated by a Cuntz–Krieger $\Lambda$-family.

######  Remark 2.8.

Relations (S1) and (S2) imply that for each object $v\in\Lambda^{0}$ (which we
identify with the identity morphism $1_{v}\in\Lambda$), the element
$S_{v}=S_{1_{v}}$ is a projection (take $\lambda=\mu=1_{v}$ in the relations).
Thus (S1) implies that each $S_{\lambda}$, $\lambda\in\Lambda$ is a partial
isometry.

###  2.3. Groupoids of dynamical origin

Here we recall the definitions of groupoid and inverse semigroup actions on
spaces, and of groupoids that encode these actions. We refer the reader to the
book [24] for a more in-depth discussion of these objects.

######  Definition 2.9.

A groupoid $\mathscr{G}$ is a small category with inverses: that is, it has a
set of units $\mathscr{G}^{(0)}$ and morphisms $\mathscr{G}$ such that:

  1. (1)

each morphism $g\in\mathscr{G}$ has a range $r(g)\in\mathscr{G}^{(0)}$ and a
source $s(g)\in\mathscr{G}^{(0)}$;

  2. (2)

there is a partially defined composition on $\mathscr{G}$, where a pair of
morphisms $(g,h)\in\mathscr{G}\times\mathscr{G}$ is composable if and only if
$s(g)=r(h)$;

  3. (3)

each unit $x\in\mathscr{G}^{(0)}$ has a corresponding identity morphism
$x\in\mathscr{G}$ (to which it will be identified) satisfying $xg=g$ for all
$g\in\mathscr{G}$ with range $x$, and $gx=g$ for all $g\in\mathscr{G}$ with
source $x$; and

  4. (4)

each morphism $g\in\mathscr{G}$ has a (unique) inverse $g^{-1}\in\mathscr{G}$
satisfying $gg^{-1}=r(g)$ and $g^{-1}g=s(g)$.

A topological groupoid is a groupoid which additionally carries a topology
such that composition and inversion are continuous. All topological groupoids
we consider will be Hausdorff étale, meaning that they have a Hausdorff
topology and the range map $r:\mathscr{G}\to\mathscr{G}$ is a local
homeomorphism.

If $x$ and $y$ are units in $\mathscr{G}^{(0)}$, we will write $x\mathscr{G}$
to denote the set of morphisms in $\mathscr{G}$ with range $x$, and
$x\mathscr{G}y$ to denote the set of morphisms in $\mathscr{G}$ with range $x$
and source $y$. If $U\subseteq\mathscr{G}^{(0)}$ is a subset of the unit space
of $\mathscr{G}$, we write $\mathscr{G}|_{U}$ for the restriction of
$\mathscr{G}$ to $U$, which is the subgroupoid of $\mathscr{G}$ consisting of
morphisms whose range and source are both in $U$.

######  Definition 2.10.

An inverse semigroup is a semigroup $\SS$ such that for each element $s\in\SS$
there is a unique element $s^{*}\in\SS$ such that $ss^{*}s=s$ and
$s^{*}ss^{*}=s^{*}$. A zero element of $\SS$ is an element $0\in S$ such that
$s0=0s=0$ for all $s\in\SS$.

Both groupoids and inverse semigroups act on topological spaces by partial
homeomorphisms, which we now define.

######  Definition 2.11.

Let $X$ be a locally compact Hausdorff space. A partial homeomorphism
$\varphi$ of $X$ is a homeomorphism from a subspace $D(\varphi)$ of $X$ (the
domain of $\varphi$) to another subspace $R(\varphi)$ of $X$ (the range of
$\varphi$). For two partial homeomorphisms $\varphi,\psi$ of $X$, the
composition $\varphi\circ\psi$ is the partial homeomorphism with domain
$\psi^{-1}(R(\psi)\cap D(\varphi))$ and range $\varphi(R(\psi)\cap
D(\varphi))$ satisfying $(\varphi\circ\psi)(x)=\varphi(\psi(x))$ for $x\in
D(\varphi\circ\psi)$.

######  Definition 2.12 (Actions).

Let $X$ be a locally compact Hausdorff space.

  1. (1)

An action of a groupoid $\mathscr{G}$ on $X$ consists of a surjective anchor
map $\tau\colon X\to\mathscr{G}^{(0)}$, and a collection of partial
homeomorphisms $\\{\varphi_{g}:g\in\mathscr{G}\\}$ of $X$ such that

    1. (i)

for all $g\in\mathscr{G}$, we have $D(\varphi_{g})=\tau^{-1}(s(g))$ and
$R(\varphi_{g})=\tau^{-1}(r(g))$;

    2. (ii)

for all $g\in\mathscr{G}$, we have $\varphi_{g^{-1}}=\varphi_{g}^{-1}$; and

    3. (iii)

for all $g,h\in\mathscr{G}$ with $s(g)=r(h)$, we have
$\varphi_{gh}=\varphi_{g}\circ\varphi_{h}$.

We will often write $g\cdot x$ instead of $\varphi_{g}(x)$, for
$g\in\mathscr{G}$ and $x\in X$.

  2. (2)

An action of an inverse semigroup $\SS$ on $X$ is a collection of partial
homeomorphisms $\\{\varphi_{s}:s\in\SS\\}$ of $X$ such that for all
$s,t\in\SS$, we have that $\varphi_{s^{*}}=\varphi_{s}^{-1}$ and
$\varphi_{st}=\varphi_{s}\circ\varphi_{t}$. As with groupoid actions, we will
often write $s\cdot x$ instead of $\varphi_{s}(x)$, for $s\in\SS$ and $x\in
X$.

######  Definition 2.13 (Groupoids associated to actions).

Let $X$ be a locally compact Hausdorff space.

  1. (1)

Suppose that the groupoid $\mathscr{G}$ acts on $X$. The transformation
groupoid of the action $\mathscr{G}\curvearrowright X$ is the set
$\mathscr{G}\ltimes X:=\\{(g,x):g\in\mathscr{G},\ x\in X,\ \tau(x)=s(g)\\}$,
where for $(g,x)\in\mathscr{G}\ltimes X$:

    1. (i)

$r(g,x)=x$ and $s(g,x)=g\cdot x$;

    2. (ii)

if $(h,y)\in\mathscr{G}$ satisfies $y=g\cdot x$, then $(h,y)(g,x)=(hg,x)$; and

    3. (iii)

$(g,x)^{-1}=(g^{-1},g\cdot x)$.

The topology of $\mathscr{G}\ltimes X$ is the subspace topology induced by the
product topology on $\mathscr{G}\times X$ (where $\mathscr{G}$ has the
discrete topology).

  2. (2)

Suppose that the inverse semigroup $\SS$ acts on $X$. Write
$S*X=\\{(s,x):s\in\SS,\ x\in D_{s^{*}s}\\}$ and define an equivalence relation
on $S*X$ by $(s,x)\sim(t,y)$ if and only if $x=y$ and there is an idempotent
$e\in\SS$ such that $x\in D_{e}$ and $se=te$. The groupoid of germs of the
action $\SS\curvearrowright X$ is the set $\SS\ltimes X=S*X/\sim$ with
composition given by $[s,x][t,y]=[st,y]$ if $x=t\cdot y$, and with inverse
given by $[s,x]^{-1}=[s^{*},s\cdot x]$. The topology of $\SS\ltimes X$ is
generated by open sets of the form $[s,U]:=\\{[s,x]:x\in U\\}$ where
$U\subseteq D_{s^{*}s}\subseteq X$ is an open set.

To any Hausdorff étale groupoid $\mathscr{G}$ one can associate a
$C^{*}$-algebra $C^{*}(\mathscr{G})$; we refer the reader to [28] for details.
Here we just note that for an action of a group $G$ on a locally compact
Hausdorff space $X$, the $C^{*}$-algebra $C^{*}(G\ltimes X)$ of the associated
transformation groupoid is isomorphic to the full crossed product
$C_{0}(X)\rtimes G$ for the induced action of $G$ on $C_{0}(X)$.

###  2.4. Graphs of groups

In this subsection we briefly recall the theory of (undirected) graphs of
groups. For a more detailed account, we refer the reader to [6].

######  Definition 2.14.

A graph of groups $\mathcal{G}=(\Gamma,G)$ is a graph $\Gamma$ along with:

  1. (1)

a vertex group $G_{v}$ for each $v\in\Gamma^{0}$;

  2. (2)

an edge group $G_{e}$ for each $e\in\Gamma^{1}$, such that
$G_{e}=G_{\overline{e}}$ for all $e\in\Gamma^{1}$; and

  3. (3)

a monomorphism $\alpha_{e}\colon G_{e}\to G_{r(e)}$ for each $e\in\Gamma^{1}$.

Graphs of groups naturally arise as “quotient objects” of group actions on
trees: if a group $G$ acts on a tree $T$ without inversions (that is, there
are no $g\in G$, $e\in T^{1}$ with $g\cdot e=\overline{e}$), the action
induces a graph of groups as follows. We let $\Gamma=G\backslash T$ be the
quotient graph of $T$ under the action of $G$: that is, the graph whose
vertices and edges are the vertex and edge orbits of $T$ respectively, and the
range and source maps are induced from those of $T$. For each $v\in\Gamma^{0}$
we pick a lift $v^{\prime}\in T^{0}$, and define the vertex group $G_{v}$ to
be the stabiliser subgroup of $G$ at $v^{\prime}\in T^{0}$; similarly for each
$e\in\Gamma^{1}$ we pick a lift $e^{\prime}\in T^{1}$, and define the edge
group $G_{e}$ to be the stabiliser subgroup of $G$ at $e^{\prime}\in T^{1}$.
Finally, for each $e\in\Gamma^{1}$ we define the monomorphism $\alpha_{e}$ as
follows. Write $v=r(e)$. Then $v^{\prime}$ is in the same vertex orbit as
$r(e^{\prime})$, so there is some $g\in G$ such that $g\cdot
r(e^{\prime})=v^{\prime}$. Now, each $h\in G_{e}$ fixes $e^{\prime}$ and thus
also fixes $r(e^{\prime})$; then $ghg^{-1}$ fixes $v^{\prime}$, so
$ghg^{-1}\in G_{v}=G_{r(e)}$. Hence we can define $\alpha_{e}\colon G_{e}\to
G_{r(e)}$ by $h\mapsto ghg^{-1}$.

In fact, from any graph of groups $\mathcal{G}$, one can construct a group
action on a tree whose induced graph of groups is isomorphic to $\mathcal{G}$
(in the sense that there is an isomorphism of graphs, and there are
isomorphisms of corresponding vertex and edge groups which preserve the
monomorphisms); this is part of what is known as the Fundamental Theorem of
Bass–Serre theory, which we quote as Theorem 2.21. Before we can state this
theorem, we recount some more theory concerning graphs of groups. We start by
discussing what is called the fundamental groupoid of $\mathcal{G}$, a notion
introduced in [12].

######  Definition 2.15.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups. The fundamental groupoid
$F(\mathcal{G})$ of $\mathcal{G}$ is the groupoid defined by the following
presentation. The vertex set of $F(\mathcal{G})$ is $\Gamma^{0}$; the
morphisms of $F(\mathcal{G})$ are generated by
$\Gamma^{1}\sqcup\bigsqcup_{v\in\Gamma^{0}}G_{v}$, where the range and source
of $e\in\Gamma^{1}$ in $F(\mathcal{G})$ are as they are in $\Gamma$, and for
any $v\in\Gamma^{0}$ and $g\in G_{v}$ we have $r(g)=s(g)=v$; and the relations
consist of the relations in each vertex group $G_{v}$, along with

  1. (i)

$\overline{e}=e^{-1}$ for all $e\in\Gamma^{1}$; and

  2. (ii)

$\alpha_{e}(g)e=e\alpha_{\overline{e}}(g)$ for all $e\in\Gamma^{1}$ and $g\in
G_{e}$.

Elements of the fundamental groupoid can be represented by
$\mathcal{G}$-words, which we will now define.

######  Definition 2.16.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups. A $\mathcal{G}$-word (of
length $n$) is a sequence of the form $g_{1}e_{1}g_{2}e_{2}\dots
g_{n}e_{n}g_{n+1}$, where $e_{1}\dots e_{n}$ is a path in $\Gamma$, $g_{i}\in
G_{r(e_{i})}$ for $i=1,\dots,n$, and $g_{n+1}\in G_{s(e_{n})}$ (in the case
where $n=0$, the $\mathcal{G}$-word is just an element $g_{1}$ of some vertex
group $G_{v}$). We set the range and source of a $\mathcal{G}$-word to be
$r(e_{1})$ and $s(e_{n})$ respectively (in the case where $n=0$, we set the
range and source to be the vertex whose group the element $g_{1}$ belongs to).

We will often identify a $\mathcal{G}$-word with its image in
$F(\mathcal{G})$. However, note that multiple $\mathcal{G}$-words can
represent the same element of $F(\mathcal{G})$. In order to find a unique
representative for each element of $F(\mathcal{G})$, we need the concept of a
normalised word.

######  Definition 2.17.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups. A set of transversals for
$\mathcal{G}$ is a set $\Sigma=\\{\Sigma_{e}:e\in\Gamma^{1}\\}$, where each
$\Sigma_{e}$ is a transversal of $G_{r(e)}/\alpha_{e}(G_{e})$ which includes
the identity element $1_{r(e)}\in G_{r(e)}$. A $\mathcal{G}$-word
$g_{1}e_{1}\dots g_{n}e_{n}g_{n+1}$ is called $\Sigma$-normalised if
$g_{i}\in\Sigma_{e_{i}}$ for $i=1,\dots,n$, and the $\mathcal{G}$-word does
not have any subsequence of the form $\overline{e}1_{r(e)}e$.

######  Proposition 2.18 ([12, Theorem]).

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups, and let $\Sigma$ be a set
of transversals for $\mathcal{G}$. Each element of $F(\mathcal{G})$ is
represented by a unique $\Sigma$-normalised word.

The fundamental groupoid $F(\mathcal{G})$ acts naturally on the following
graph [6, Section 2.4].

######  Definition 2.19.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups. Define the graph
$W_{\mathcal{G}}$ as follows. The vertex set of $W_{\mathcal{G}}$ is

$W_{\mathcal{G}}^{0}=\bigsqcup_{v,w\in\Gamma^{0}}vF(\mathcal{G})w/G_{w}=\\{\gamma
G_{w}:v,w\in\Gamma^{1},\ \gamma\in vF(\mathcal{G})w\\};$

and for $\gamma\in vF(\mathcal{G})w$ and $\gamma^{\prime}\in
v^{\prime}F(\mathcal{G})w^{\prime}$, there is an edge in $W_{\mathcal{G}}$
from $\gamma^{\prime}G_{w^{\prime}}$ to $\gamma G_{w}$ if and only if
$v=v^{\prime}$ and $\gamma^{-1}\gamma^{\prime}\in G_{v}eG_{w}$ for some $e\in
v\Gamma^{1}w$.

We note that $W_{\mathcal{G}}$ is not connected in general. Each connected
component of $W_{\mathcal{G}}$ consists of the vertices
$\bigsqcup_{w\in\Gamma^{0}}xF(\mathcal{G})w/G_{w}$ for some unique, fixed
$x\in\Gamma^{0}$; by [4, Theorem 1.17], each of these components are trees, so
$W_{\mathcal{G}}$ is a forest.

The fundamental groupoid $F(\mathcal{G})$ acts on $W_{\mathcal{G}}$ in the
following way. Let $v,w\in\Gamma^{0}$ and take $\gamma^{\prime}\in
vF(\mathcal{G})w$. An element $\gamma\in F(\mathcal{G})$ acts on
$\gamma^{\prime}G_{w}\in W_{\mathcal{G}}^{0}$ if and only if $v=s(\gamma)$, in
which case we have
$\gamma\cdot\gamma^{\prime}G_{w}=\gamma\gamma^{\prime}G_{w}$. Since
$W_{\mathcal{G}}$ is a forest, the action on the vertices induces an action on
the graph, and one can check that this action is without inversions.

We can now define the group action on a tree induced by a graph of groups.

######  Definition 2.20.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups, and let $x\in\Gamma^{0}$.
The fundamental group of $\mathcal{G}$ based at $x$, which we denote by
$\pi_{1}(\mathcal{G},x)$, is the isotropy group of $F(\mathcal{G})$ at $x$.
The Bass–Serre tree of $\mathcal{G}$ based at $x$, which we denote by
$X_{\mathcal{G},x}$, is the connected component in $W_{\mathcal{G}}$ of the
vertex $G_{x}$ (equivalently, it is the restriction of $W_{\mathcal{G}}$ to
the vertices $\bigsqcup_{w\in\Gamma^{0}}xF(\mathcal{G})w/G_{w}$).

The action of $F(\mathcal{G})$ on $W_{\mathcal{G}}$ restricts to an action of
the group $\pi_{1}(\mathcal{G},x)$ on the tree $X_{\mathcal{G},x}$. The
significance of this action comes from the Fundamental Theorem of Bass–Serre
theory, which we now state.

######  Theorem 2.21.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups, and let $x\in\Gamma^{0}$.
The induced graph of groups for the action of $\pi_{1}(\mathcal{G},x)$ on
$X_{\mathcal{G},x}$ is isomorphic to $\mathcal{G}$. Conversely, if
$\mathcal{G}$ is induced from an action (without inversions) of a group $G$ on
the tree $T$, then there is an isomorphism of groups
$\pi_{1}(\mathcal{G},x)\cong G$ and an equivariant isomorphism of trees
$X_{\mathcal{G},x}\cong T$.

######  Remark 2.22.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups, and let $x\in\Gamma^{0}$.
For any vertex $v\in\Gamma^{0}$, the lifts of $v$ in the Bass–Serre tree
$X_{\mathcal{G},x}$ are precisely the vertices

$xF(\mathcal{G})v/G_{v}=\\{\gamma G_{v}:\gamma\in xF(\mathcal{G})v\\}.$

For any edge $e\in\Gamma^{1}$, the lifts of $e$ in $X_{\mathcal{G},x}$ are the
edges with range $\gamma G_{r(e)}$ for some $\gamma\in xF(\mathcal{G})r(e)$
and with source $\gamma geG_{s(e)}$ for some $g\in G_{r(e)}$.

##  3\. Directed graphs of groups

In this section, we introduce and develop some theory for directed graph of
groups. We start by defining directed graphs of groups in Section 3.1, as well
as explaining how they relate to group actions on directed trees. In Section
3.2, we study a canonical (left cancellative small) category associated to a
directed graph of groups, which we call its word category. Finally, in Section
3.3 we study an action, canonically associated to a directed graph of groups,
of a groupoid on a directed forest.

###  3.1. Directed graphs of groups

We start by defining directed graphs of groups, and then briefly discuss a
‘directed version’ of Bass–Serre theory.

######  Definition 3.1.

A directed graph of groups $\mathcal{G}_{+}=(\Gamma_{+},G)$ is a graph of
groups $\mathcal{G}=(\Gamma,G)$ where the graph $\Gamma$ additionally carries
an orientation $\Gamma_{+}^{1}$. We call $\mathcal{G}$ the underlying graph of
groups of $\mathcal{G}_{+}$.

######  Remark 3.2.

We note that directed graphs of groups have also been studied in [20], where
they were called ‘graphs of groups with a given orientation’.

Just as graphs of groups are induced from group actions on trees, directed
graphs of groups are induced from group actions on directed trees. Indeed, if
a group $G$ acts on a directed tree $T_{+}$, then it acts on the underlying
undirected tree $T$ without inversion; this induces a graph of groups
$\mathcal{G}=(\Gamma,G)$, and we can give $\Gamma$ the orientation induced by
the orientation on $T$, yielding a directed graph of groups
$\mathcal{G}_{+}=(\Gamma_{+},G)$. Moreover, we can recover the action
$G\curvearrowright T_{+}$ from $\mathcal{G}_{+}$, like in the undirected case:
the acting group is still the fundamental group $\pi_{1}(\mathcal{G},x)$, and
the directed tree is the Bass–Serre tree $X_{\mathcal{G},x}$ with a suitable
orientation, which we now describe.

######  Definition 3.3.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups, and choose
a base vertex $x\in\Gamma^{0}$. The directed Bass–Serre tree
$X_{\mathcal{G}_{+},x}$ of $\mathcal{G}_{+}$ based at $x$ is the directed tree
with $X_{\mathcal{G},x}$ as the underlying undirected tree, and where an edge
from $\gamma^{\prime}G_{w}$ to $\gamma G_{v}$ is in the orientation if and
only if $\gamma^{-1}\gamma^{\prime}\in G_{v}eG_{w}$ for some $e\in
v\Gamma_{+}^{1}w$.

We now state and prove the directed analogue of the fundamental theorem of
Bass–Serre theory (Theorem 2.21).

######  Theorem 3.4.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups, and choose
a base vertex $x\in\Gamma^{0}$. The induced directed graph of groups for the
action of $\pi_{1}(\mathcal{G},x)$ on $X_{\mathcal{G}_{+},x}$ is isomorphic to
$\mathcal{G}_{+}$. Conversely, if $\mathcal{G}_{+}$ is induced from an action
of a group $G$ on a directed tree $T_{+}$, then there is an isomorphism of
groups $\pi_{1}(\mathcal{G},x)\cong G$ and an equivariant isomorphism of
directed trees $X_{\mathcal{G}_{+},x}\cong T_{+}$.

###### Proof.

In light of Theorem 2.21, all that we need to check is that the orientation of
the quotient graph $\pi_{1}(\mathcal{G},x)\backslash X_{\mathcal{G}_{+},x}$
matches the orientation of $\Gamma_{+}$. Take $e\in\Gamma_{+}^{1}$, and take
some lift of $e$ in $X_{\mathcal{G},x}$ (by Remark 2.22, the lift goes from
$\gamma geG_{s(e)}$ to $\gamma G_{r(e)}$ for some $\gamma\in
xF(\mathcal{G})r(e)$ and $g\in G_{r(e)}$). Remark 2.22 also gives that $\gamma
G_{r(e)}$ is a lift of the vertex $r(e)$ and $\gamma geG_{s(e)}$ is a lift of
the vertex $s(e)$. Since $\gamma^{-1}(\gamma ge)=ge1_{s(e)}\in
G_{r(e)}eG_{s(e)}$, there is an edge in the orientation of
$X_{\mathcal{G}_{+},x}$ from $\gamma geG_{s(e)}$ to $\gamma G_{r(e)}$, which
matches the direction of $e$ in $\Gamma_{+}^{1}$. This proves the theorem. ∎

We end this subsection with some examples.

######  Examples 3.5.

  1. (1)

Consider the following directed graph of groups (where $1$ denotes the trivial
group, and the monomorphisms are the trivial inclusions).

$v$$\mathbb{Z}_{2}$$w$$\mathbb{Z}_{3}$$e$$1$

We have transversals $\Sigma_{e}=\mathbb{Z}_{2}=\\{1,a\\}$ and
$\Sigma_{\overline{e}}=\mathbb{Z}_{3}=\\{1,b,b^{2}\\}$, and
$\mathcal{G}$-words have edge sequence alternating between $e$ and
$\overline{e}$. The fundamental group $\pi_{1}(\mathcal{G},v)$ is the free
product $\mathbb{Z}_{2}*\mathbb{Z}_{3}$ with generators $a$ and
$eb{\overline{e}}$ of order 2 and 3 respectively, and the directed Bass–Serre
tree is the following.

$\mathbb{Z}_{2}$$1e\mathbb{Z}_{3}$$ae\mathbb{Z}_{3}$$1eb\overline{e}\mathbb{Z}_{2}$$1eb^{2}\overline{e}\mathbb{Z}_{2}$$1eb\overline{e}ae\mathbb{Z}_{3}$$1eb^{2}\overline{e}ae\mathbb{Z}_{3}$$1eb\overline{e}aeb^{2}\overline{e}\mathbb{Z}_{2}$

$\cdots$

$1eb\overline{e}aeb\overline{e}\mathbb{Z}_{2}$$\cdots$$1eb^{2}\overline{e}aeb\overline{e}\mathbb{Z}_{2}$

$\cdots$

$1eb^{2}\overline{e}aeb^{2}\overline{e}\mathbb{Z}_{2}$$\cdots$$aeb\overline{e}\mathbb{Z}_{2}$$aeb^{2}\overline{e}\mathbb{Z}_{2}$$aeb\overline{e}ae\mathbb{Z}_{3}$$aeb^{2}\overline{e}ae\mathbb{Z}_{3}$$aeb\overline{e}aeb^{2}\overline{e}\mathbb{Z}_{2}$

$\cdots$

$aeb\overline{e}aeb\overline{e}\mathbb{Z}_{2}$$\cdots$$aeb^{2}\overline{e}aeb\overline{e}\mathbb{Z}_{2}$

$\cdots$

$aeb^{2}\overline{e}aeb^{2}\overline{e}\mathbb{Z}_{2}$$\cdots$

The fundamental group acts on the tree as follows: the copy of
$\mathbb{Z}_{2}$ in $\pi_{1}(\mathcal{G},v)$ acts by flipping about the vertex
$\mathbb{Z}_{2}$, and the copy of $\mathbb{Z}_{3}$ acts by rotating about the
vertex $1e\mathbb{Z}_{3}$. The solid vertices in the tree are the lifts of the
vertex $v$ from the directed graph of groups, and the unfilled vertices are
the lifts of the vertex $w$.

  2. (2)

Consider the following directed graph of groups.

$v$$\mathbb{Z}$$e$$\mathbb{Z}$$\times 2$$\times 1$

Here, the $\times 2$ and $\times 1$ represent the monomorphisms $\alpha_{e}$
and $\alpha_{\overline{e}}$ respectively, which are defined by
$\alpha_{e}(1)=2$ and $\alpha_{\overline{e}}(1)=1$. We have transversals
$\Sigma_{e}=\\{0,1\\}$ and $\Sigma_{\overline{e}}=\\{0\\}$. The fundamental
group $\pi_{1}(\mathcal{G},v)$ turns out to be the Baumslag–Solitar group
$BS(1,2)=\langle a,b:ab=b^{2}a\rangle$, with $a$ corresponding to the element
$e\in\pi_{1}(\mathcal{G},v)$ and $b$ corresponding to the generator of the
vertex group $\mathbb{Z}$. The directed Bass–Serre tree is the following.

$0{\overline{e}}\mathbb{Z}$$\cdots$$\mathbb{Z}$$0{\overline{e}}1e\mathbb{Z}$$0e\mathbb{Z}$$1e\mathbb{Z}$$0{\overline{e}}1e0e\mathbb{Z}$$0{\overline{e}}1e1e\mathbb{Z}$$0e0e\mathbb{Z}$$\cdots$$0e1e\mathbb{Z}$$\cdots$$1e0e\mathbb{Z}$$\cdots$$1e1e\mathbb{Z}$$\cdots$$0{\overline{e}}1e0e0e\mathbb{Z}$$\cdots$$0{\overline{e}}1e0e1e\mathbb{Z}$$\cdots$$0{\overline{e}}1e1e0e\mathbb{Z}$$\cdots$$0{\overline{e}}1e1e1e\mathbb{Z}$$\cdots$

The fundamental group acts on the tree as follows: the element
$a\in\pi_{1}(\mathcal{G},v)$ “shifts” the tree along the topmost infinite path
in the figure above: it sends $0{\overline{e}}\mathbb{Z}$ to $\mathbb{Z}$,
$\mathbb{Z}$ to $0e\mathbb{Z}$, $0e\mathbb{Z}$ to $0e0e\mathbb{Z}$, and so on.
The element $b\in\pi_{1}(\mathcal{G},v)$ fixes the vertex $\mathbb{Z}$ but
swaps the edges it receives; more generally it fixes each “level” of the tree
(that is, each set of vertices vertically in line with each other), but
permutes the vertices within each level.

###  3.2. Word category

In this subsection we introduce and study the word category of a directed
graph of groups, which generalises the notion of the path category of a
directed graph. The results in this subsection will be useful in Sections 4
and 5.

######  Definition 3.6.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups. A
$\mathcal{G}_{+}$-word is a $\mathcal{G}$-word where all edges in the word
belong to $\Gamma_{+}^{1}$. A $\mathcal{G}_{+}$-word maps naturally into the
fundamental groupoid $F(\mathcal{G})$ of the underlying graph of groups. The
word category of $\mathcal{G}_{+}$, which we will denote by
$\Lambda_{\mathcal{G}_{+}}$, is the subcategory of $F(\mathcal{G})$ consisting
of the images of $\mathcal{G}_{+}$-words.

Note that the word category is indeed a category since the concatenation of
two $\mathcal{G}_{+}$-words is again a $\mathcal{G}_{+}$-word. Moreover, since
$\Lambda_{\mathcal{G}_{+}}$ is a subcategory of a groupoid, it must be left
cancellative.

######  Remark 3.7.

This construction of a category from a directed graph of groups yields the
same result as the construction in [20]. Thus, [20, Theorem 4.17] tells us
that we can recover the directed graph of groups $\mathcal{G}_{+}$ from its
word category $\Lambda_{\mathcal{G}_{+}}$ (up to isomorphism).

Recall from Section 2.4 that elements of the fundamental groupoid
$F(\mathcal{G})$ of a graph of groups $\mathcal{G}$ can be uniquely
represented by $\Sigma$-normalised $\mathcal{G}$-words. For a directed graph
of groups $\mathcal{G}_{+}$, we can likewise define the notion of a
$\Sigma$-normalised $\mathcal{G}_{+}$-word, and we show that these uniquely
represent elements of the word category $\Lambda_{\mathcal{G}_{+}}$.

######  Definition 3.8.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups. A set of
transversals for $\mathcal{G}_{+}$ is a set
$\Sigma=\\{\Sigma_{e}:e\in\Gamma_{+}^{1}\\}$, where each $\Sigma_{e}$ is a
transversal of $G_{r(e)}/\alpha_{e}(G_{e})$ which includes the identity
element $1_{r(e)}\in G_{r(e)}$. A $\mathcal{G}_{+}$-word
$g_{1}e_{1}g_{2}e_{2}\ldots g_{n}e_{n}g_{n+1}$ is $\Sigma$-normalised if
$g_{i}\in\Sigma_{e_{i}}$ for all $1\leq i\leq n$.

######  Remark 3.9.

Suppose that $\Sigma$ is a set of transversals for a directed graph of groups
$\mathcal{G}_{+}=(\Gamma_{+},G)$. We can always extend $\Sigma$ to a set of
transversals for the underlying graph of groups $\mathcal{G}$ by simply
including transversals $\Sigma_{e}$ for each edge
$e\in\Gamma^{1}\setminus\Gamma_{+}^{1}$.

######  Proposition 3.10.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups, and let
$\Sigma$ be a set of transversals for $\mathcal{G}_{+}$. Every element of
$\Lambda_{\mathcal{G}_{+}}$ is uniquely represented by a $\Sigma$-normalised
$\mathcal{G}_{+}$-word.

###### Proof.

Extend $\Sigma$ to a set of transversals for $\mathcal{G}$. By Proposition
2.18, every element of $\Lambda_{\mathcal{G}_{+}}\subseteq F(\mathcal{G})$ is
uniquely represented by a $\Sigma$-normalised $\mathcal{G}$-word. But any such
$\mathcal{G}$-word must only contain edges in orientation $\Gamma_{+}^{1}$
(along with group elements), and so the $\mathcal{G}$-word is a
($\Sigma$-normalised) $\mathcal{G}_{+}$-word. ∎

Using Proposition 3.10, we now relate the word category
$\Lambda_{\mathcal{G}_{+}}$ to a certain directed graph. We show that this
graph encodes the order structure of $\Lambda_{\mathcal{G}_{+}}$ (Proposition
3.12), and then we derive some useful consequences.

######  Notation 3.11.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups, and let
$\Sigma$ be a set of transversals for $\mathcal{G}_{+}$. Write $E_{\Sigma}$
for the directed graph defined by

$E_{\Sigma}^{0}=\Gamma^{0},\quad E_{\Sigma}^{1}=\\{he:e\in\Gamma_{+}^{1},\
h\in\Sigma_{e}\\},\quad r(he)=r(e),\quad s(he)=s(e).$

(The directed graph $E_{\Sigma}$ is essentially just the directed graph
$\Gamma_{+}$ with its edges replicated a number of times depending on the size
of the respective transversal $\Sigma_{e}$.)

Write $q_{\Sigma}\colon\Lambda_{\mathcal{G}_{+}}\to E_{\Sigma}^{*}$ for the
map which sends (the image in $\Lambda_{\mathcal{G}_{+}}$ of) a
$\Sigma$-normalised $\mathcal{G}_{+}$-word $h_{1}e_{1}h_{2}e_{2}\dots
h_{n}e_{n}g_{n+1}$ to the path $h_{1}e_{1}h_{2}e_{2}\dots h_{n}e_{n}$ in
$E_{\Sigma}$ (in the case where $n=0$, we define $q_{\Sigma}(g_{1})$ to be the
vertex $v$ for which $g_{1}\in G_{v}$). We will often drop the subscript
‘$\Sigma$’ in the notation and write only ‘$q$’ for this map when $\Sigma$ is
understood.

Note that the path space $E_{\Sigma}^{*}$ can be viewed as a left cancellative
small category with unit space $E_{\Sigma}^{0}=\Gamma^{0}$. The relation
$\leq$ on $E_{\Sigma}^{*}$ as in Definition 2.5 is in this case a partial
order.

######  Proposition 3.12.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups, and let
$\Sigma$ be a set of transversals for $\mathcal{G}_{+}$. For any
$\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$, we have $\lambda\leq\mu$ in
$\Lambda_{\mathcal{G}_{+}}$ if and only if $q(\lambda)\leq q(\mu)$ in
$E_{\Sigma}^{*}$.

###### Proof.

Fix $\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$, and write
$\lambda=h_{1}e_{1}h_{2}e_{2}\dots h_{n}e_{n}g_{n+1}$ in $\Sigma$-normalised
form. First suppose that $\lambda\leq\mu$, so $\lambda\nu=\mu$ for some
$\nu\in\Lambda_{\mathcal{G}_{+}}$. Write
$\nu=g^{\prime}_{1}f_{1}g^{\prime}_{2}f_{2}\dots
g^{\prime}_{m}f_{m}g^{\prime}_{m+1}$, and let
$g_{n+1}\nu=h^{\prime}_{1}f_{1}h^{\prime}_{2}f_{2}\dots
h^{\prime}_{m}f_{m}g^{\prime\prime}_{m+1}$ be $\Sigma$-normalised. Then

$\mu=\lambda\nu=h_{1}e_{1}h_{2}e_{2}\dots
h_{n}e_{n}h^{\prime}_{1}f_{1}h^{\prime}_{2}f_{2}\dots
h^{\prime}_{m}f_{m}g^{\prime\prime}_{m+1}$

is in $\Sigma$-normalised form, so

$q(\lambda)=h_{1}e_{1}h_{2}e_{2}\dots h_{n}e_{n}\leq h_{1}e_{1}h_{2}e_{2}\dots
h_{n}e_{n}h^{\prime}_{1}f_{1}h^{\prime}_{2}f_{2}\dots
h^{\prime}_{m}f_{m}=q(\mu),$

as required.

For the other direction, suppose that $q(\lambda)\leq q(\mu)$, so $\mu$ has
$\Sigma$-normalised form

$h_{1}e_{1}h_{2}e_{2}\dots
h_{n}e_{n}h^{\prime}_{1}f_{1}h^{\prime}_{2}f_{2}\dots
h^{\prime}_{m}f_{m}g^{\prime\prime}_{m+1}.$

So $\mu=\lambda(g_{n+1}^{-1}h^{\prime}_{1}f_{1}h^{\prime}_{2}f_{2}\dots
h^{\prime}_{m}f_{m}g^{\prime\prime}_{m+1})$, showing that $\lambda\leq\mu$, as
required. ∎

######  Corollary 3.13.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups. For any
$\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$, if $\lambda$ and $\mu$ have a
common extension, then either $\lambda\leq\mu$ or $\mu\leq\lambda$.

###### Proof.

Suppose that $\lambda$ and $\mu$ have a common extension $\nu$, so
$\lambda,\mu\leq\nu$. Then by Proposition 3.12, we have that
$q(\lambda),q(\mu)\leq q(\nu)$ in $E_{\Sigma}^{*}$; that is, both $q(\lambda)$
and $q(\mu)$ are initial subpaths of $q(\nu)$. But this can only be true if
either $q(\lambda)$ is an initial subpath of $q(\mu)$ or vice versa. Then
Proposition 3.12 implies the claim. ∎

######  Corollary 3.14.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups. The
category $\Lambda_{\mathcal{G}_{+}}$ is singly aligned.

###### Proof.

Suppose that $\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$ are such that
$\lambda\Lambda_{\mathcal{G}_{+}}\cap\mu\Lambda_{\mathcal{G}_{+}}\neq\emptyset$.
Then $\lambda$ and $\mu$ have a common extension, and so by Corollary 3.13 we
can assume without loss of generality that $\lambda\leq\mu$. This implies that
$\mu\Lambda_{\mathcal{G}_{+}}\subseteq\lambda\Lambda_{\mathcal{G}_{+}}$ and
therefore that
$\lambda\Lambda_{\mathcal{G}_{+}}\cap\mu\Lambda_{\mathcal{G}_{+}}=\mu\Lambda_{\mathcal{G}_{+}}$.
This proves the claim. ∎

###  3.3. The directed forest $W_{\mathcal{G}_{+}}$

In this subsection we consider a directed version of the forest
$W_{\mathcal{G}}$ from Definition 2.19, and we study the action of the
fundamental groupoid $F(\mathcal{G})$ on the boundary of this directed forest.
This will be useful for Section 5, where we work with the transformation
groupoid $F(\mathcal{G})\ltimes\partial W_{\mathcal{G}_{+}}$. We start by
assigning an orientation to $W_{\mathcal{G}}$.

######  Definition 3.15.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups. Write
$W_{\mathcal{G}_{+}}$ for the directed forest with $W_{\mathcal{G}}$ as its
underlying graph, and where an edge from $\gamma^{\prime}G_{w}$ to $\gamma
G_{w}$ is in the orientation if and only if $\gamma^{-1}\gamma^{\prime}\in
G_{v}eG_{w}$ for some $e\in v\Gamma_{+}^{1}w$.

Note that for any $x\in\Gamma^{0}$, the connected component of the vertex
$G_{x}$ in $W_{\mathcal{G}_{+}}$ is exactly the directed Bass–Serre tree of
$\mathcal{G}_{+}$ based at $x$.

We are interested in studying the boundary $\partial W_{\mathcal{G}_{+}}$ of
$W_{\mathcal{G}_{+}}$, and for this it is useful to consider infinite
$\mathcal{G}$-words.

######  Definition 3.16.

Let $\mathcal{G}=(\Gamma,G)$ be a graph of groups, and let $\Sigma$ be a set
of transversals for $\mathcal{G}$. An infinite $\mathcal{G}$-word is a
sequence of the form $g_{1}e_{1}g_{2}e_{2}\dots$, where $e_{1}e_{2}\dots$ is
an infinite path in $\Gamma$, and $g_{i}\in G_{r(e_{i})}$ for each $i\geq 1$.
An infinite $\mathcal{G}$-word is $\Sigma$-normalised if
$g_{i}\in\Sigma_{e_{i}}$ for all $i\geq 1$, and there is no subsequence of the
form $\overline{e}1_{r(e)}e$. The range of an infinite $\mathcal{G}$-word is
$r(e_{1})$.

The boundary $\partial X_{\mathcal{G},x}$ of the Bass–Serre tree based at
$x\in\Gamma^{0}$ can be identified with the set of $\Sigma$-normalised
infinite $\mathcal{G}$-words with range $x$ (see [6, Section 2.3.1]), so the
boundary $\partial W_{\mathcal{G}}$ can be identified with the set of all
$\Sigma$-normalised infinite $\mathcal{G}$-words. The action of
$F(\mathcal{G})$ on $\partial W_{\mathcal{G}}$ induced from the action on
$W_{\mathcal{G}}$ is as follows. Take $\gamma\in F(\mathcal{G})$ and
$\xi\in\partial W_{\mathcal{G}}$ with $r(\xi)=s(\gamma)$. Then $\gamma$ is
represented by some $\mathcal{G}$-word and $\xi$ is represented by some
infinite $\mathcal{G}$-word, so the concatenation $\gamma\xi$ is also an
infinite $\mathcal{G}$-word. By a (possibly infinite) number of applications
of the relations in $F(\mathcal{G})$, we can turn $\gamma\xi$ into a
$\Sigma$-normalised infinite $\mathcal{G}$-word, which we call
$\gamma\cdot\xi$. It can be verified that this defines an action of
$F(\mathcal{G})$ on $\partial W_{\mathcal{G}}$; we refer to [6, Section 2] for
more detail.

In this paper we are interested in the action of $F(\mathcal{G})$ on the
boundary $\partial W_{\mathcal{G}_{+}}$ of the directed forest
$W_{\mathcal{G}_{+}}$. This boundary can be identified with the set of
eventually directed $\Sigma$-normalised infinite $\mathcal{G}$-words, in the
following sense.

######  Definition 3.17.

Let $\mathcal{G}=(\Gamma_{+},G)$ be a directed graph of groups, and let
$\Sigma$ be a set of transversals for $\mathcal{G}$. A $\Sigma$-normalised
infinite $\mathcal{G}$-word $g_{1}e_{1}g_{2}e_{2}\dots$ is eventually directed
if there is some $N\in\mathbb{N}$ such that $e_{i}\in\Gamma_{+}^{1}$ for all
$i\geq N$. Equivalently, an eventually directed infinite $\mathcal{G}$-word
has the form $\gamma\alpha$ for some $\gamma\in F(\mathcal{G})$ and some
infinite $\mathcal{G}_{+}$-word $\alpha$ (that is, $\alpha$ is an infinite
$\mathcal{G}$-word with all edges belonging to the orientation
$\Gamma_{+}^{1}$).

The basic open sets of $\partial W_{\mathcal{G}_{+}}$ have the form

$Z(\gamma G_{s(\gamma)})=\\{\gamma\alpha:\alpha\ \text{an infinite
$\mathcal{G}_{+}$-word},\ r(\alpha)=s(\gamma)\\}$

for a fixed $\gamma\in F(\mathcal{G})$. Note that if we consider $\partial
W_{\mathcal{G}_{+}}$ to be a subset of $\partial W_{\mathcal{G}}$, then it is
invariant under the action of $F(\mathcal{G})$, since the concatenation
$\gamma\xi$ of a $\mathcal{G}$-word $\gamma$ and an eventually directed
$\Sigma$-normalised infinite $\mathcal{G}$-word $\xi$ will also be eventually
directed. Moreover, the action of $\gamma$ takes a basic open set
$Z(\gamma^{\prime}G_{s(\gamma^{\prime})})$, $\gamma^{\prime}\in
s(\gamma)F(\mathcal{G})$ to the basic open set
$Z(\gamma\gamma^{\prime}G_{s(\gamma^{\prime})})$ Thus $F(\mathcal{G})$ acts on
the space $\partial W_{\mathcal{G}_{+}}$ by homeomorphisms.

We now focus on the subspace of $\partial W_{\mathcal{G}_{+}}$ corresponding
to ($\Sigma$-normalised) infinite $\mathcal{G}_{+}$-words. These words have
the form $h_{1}e_{1}h_{2}e_{2}\dots$, where for each $i\leq 1$ we have
$e_{i}\in\Gamma_{+}^{1}$ and $h_{i}\in\Sigma_{e_{i}}$. But sequences of this
form also describe infinite paths in $E_{\Sigma}^{\infty}$, and so we can
identify $E_{\Sigma}^{\infty}$ with a subset of $\partial
W_{\mathcal{G}_{+}}$. Moreover, the topology of $E_{\Sigma}^{\infty}$ matches
the topology coming from $\partial W_{\mathcal{G}_{+}}$, since the basic open
set $\alpha E_{\Sigma}^{\infty}\subseteq E_{\Sigma}^{\infty}$ corresponds to
the basic open set $Z(\alpha 1_{s(\alpha)}G_{s(\alpha)})\subseteq\partial
W_{\mathcal{G}_{+}}$; thus we can consider $E_{\Sigma}^{\infty}$ to be a
subspace of $\partial W_{\mathcal{G}_{+}}$. We end this section with the
following result which characterises the groupoid elements $\gamma\in
F(\mathcal{G})$ which send a fixed element of
$E_{\Sigma}^{\infty}\subseteq\partial W_{\mathcal{G}_{+}}$ to another element
of $E_{\Sigma}^{\infty}$.

######  Proposition 3.18.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of groups, and let
$\Sigma$ be a set of transversals for $\mathcal{G}_{+}$. Let $\alpha\in
E_{\Sigma}^{\infty}$ be an infinite path, considered as an element of
$\partial W_{\mathcal{G}}$, and let $\gamma\in F(\mathcal{G})$. Then
$\gamma\cdot\alpha$ is an element of $E_{\Sigma}^{\infty}\subseteq\partial
W_{\mathcal{G}}$ if and only if $\gamma$ has the form $\lambda\mu^{-1}$ for
some $\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$, where $q(\mu)\leq\alpha$.

###### Proof.

First suppose that $\gamma=\lambda\mu^{-1}$ for some
$\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$ with $q(\mu)\leq\alpha$. Let
$g_{\mu}\in G_{s(\mu)}$ be such that $\mu=q(\mu)g_{\mu}$, and let $\beta\in
E_{\Sigma}^{\infty}$ be such that $\alpha=q(\mu)\beta$. Then $\gamma=\lambda
g_{\mu}^{-1}q(\mu)^{-1}$, and so $\gamma\cdot\alpha=\lambda g_{\mu}^{-1}\beta$
is an infinite $\mathcal{G}_{+}$-word, and therefore (its $\Sigma$-normalised
version) corresponds to some infinite path in $E_{\Sigma}$. This proves the
backwards direction.

For the forwards direction, extend $\Sigma$ to a set of transversals for
$\mathcal{G}$, and write $\gamma=g_{1}e_{1}\dots g_{n}e_{n}g_{n+1}$ in
$\Sigma$-normalised form. If each $e_{i}\in\Gamma_{+}^{1}$, $i=1,\dots,n$,
then $\gamma\in\Lambda_{\mathcal{G}_{+}}$ and there is nothing to prove, so
assume that $e_{i}\notin\Gamma_{+}^{1}$ for some $i$. Write
$\alpha=h_{1}f_{1}h_{2}f_{2}\dots$. Since $\gamma\cdot\alpha=g_{1}e_{1}\dots
g_{n}e_{n}g_{n+1}h_{1}f_{1}h_{2}f_{2}\dots$ is directed, the path $e_{i}$ must
be “canceled out” by the relation $\overline{e}1_{r(e)}e=1_{s(e)}$ in
$F(\mathcal{G})$. But since $\gamma$ is already $\Sigma$-normalised, the only
possible cancellation that can occur is the sourcemost edge of $\gamma$ with
the rangemost edge of $\alpha$; that is, we need $e_{n}g_{n+1}h_{1}f_{1}$ to
have the form $\overline{f_{1}}1_{r(f_{1})}f_{1}$. This forces
$g_{n+1}=h_{1}^{-1}$ and $e_{n}=\overline{f_{1}}$. Write
$\gamma^{\prime}=g_{1}e_{1}\dots g_{n-1}e_{n-1}g_{n}$ and
$\alpha^{\prime}=h_{2}f_{2}h_{3}f_{3}\dots$, so
$\gamma^{\prime}\cdot\alpha^{\prime}=\gamma\cdot\alpha$. If each
$e_{i}\in\Gamma_{+}^{1}$, $i=1,\dots,n-1$, then we have that
$\gamma^{\prime}\in\Lambda_{\mathcal{G}_{+}}$ and
$\gamma=\gamma^{\prime}(h_{1}f_{1}1_{s(f_{1})})^{-1}$, so we are done. If not,
then we repeat the argument with $\gamma^{\prime}$ and $\alpha^{\prime}$. As
$\gamma$ is a finite $\mathcal{G}$-word, this process will eventually
terminate, at which point we will have that for some $k\leq n$, the word
$\gamma^{\prime\prime}=g_{1}e_{1}\dots g_{k}e_{k}g_{k+1}$ belongs to
$\Lambda_{\mathcal{G}_{+}}$, and $\gamma=\gamma^{\prime\prime}(h_{1}f_{1}\dots
h_{n-k}f_{n-k}1_{s(f_{n-k})})^{-1}$. Since $q(h_{1}f_{1}\dots
h_{n-k}f_{n-k}1_{s(f_{n-k})})=h_{1}f_{1}\dots h_{n-k}f_{n-k}\leq\alpha$, we
have proven the claim. ∎

##  4\. Directed graph of groups $C^{*}$-algebras

We now associate a universal $C^{*}$-algebra to a directed graph of groups,
where the generators and relations of the $C^{*}$-algebra are encoded by the
directed graph of groups. Then, we show that this $C^{*}$-algebra is
isomorphic to the Cuntz–Krieger algebra of the word category of the directed
graph of groups.

######  Definition 4.1.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources, and let $\Sigma$ be a set of transversals for
$\mathcal{G}_{+}$. A $(\mathcal{G}_{+},\Sigma)$-family is a collection of
partial isometries $S_{e}$ for each $e\in\Gamma^{1}_{+}$ and representations
$g\mapsto U_{v,g}$ of $G_{v}$ by partial unitaries for each $v\in\Gamma^{0}$
satisfying the relations:

  1. (1)

$U_{v,1}U_{w,1}=0$ for each $v,w\in\Gamma^{0}$ with $v\neq w$;

  2. (2)

$U_{r(e),\alpha_{e}(g)}S_{e}=S_{e}U_{s(e),\alpha_{\overline{e}}(g)}$ for each
$e\in\Gamma^{1}_{+}$ and $g\in G_{e}$;

  3. (3)

$U_{s(e),1}=S_{e}^{*}S_{e}$ for each $e\in\Gamma^{1}_{+}$; and

  4. (4)

$U_{v,1}=\sum_{e\in
v\Gamma^{1}_{+},h\in\Sigma_{e}}U_{v,h}S_{e}S_{e}^{*}U_{v,h}^{*}$ for each
$v\in\Gamma^{0}$.

We write $C^{*}(\mathcal{G}_{+})$ for the universal $C^{*}$-algebra generated
by a $(\mathcal{G}_{+},\Sigma)$-family, and we call it the directed graph of
groups $C^{*}$-algebra of $\mathcal{G}_{+}$. We write
$\\{s_{e}:e\in\Gamma_{+}^{1}\\}\cup\\{u_{v,g}:v\in\Gamma^{0},\ g\in G_{v}\\}$
for the $(\mathcal{G}_{+},\Sigma)$-family generating $C^{*}(\mathcal{G}_{+})$.

A priori, the $C^{*}$-algebra $C^{*}(\mathcal{G}_{+})$ depends on the choice
of the set of transversals $\Sigma$. However, it follows from Theorem 4.2
below that $C^{*}(\mathcal{G}_{+})$ is in fact independent (up to isomorphism)
of $\Sigma$, which justifies the omission of $\Sigma$ in the notation.

######  Theorem 4.2.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources, and let $\Sigma$ be a set of transversals for
$\mathcal{G}_{+}$. Let $\\{t_{\lambda}:\lambda\in\Lambda_{\mathcal{G}_{+}}\\}$
be the Cuntz–Krieger $\Lambda_{\mathcal{G}_{+}}$-family generating
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$. The map

$\displaystyle\Phi\colon C^{*}(\mathcal{G}_{+})$
$\displaystyle\to\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$ $\displaystyle s_{e}$
$\displaystyle\mapsto t_{1_{r(e)}e}$ $\displaystyle u_{v,g}$
$\displaystyle\mapsto t_{g}$

is an isomorphism of $C^{*}$-algebras.

To prove this, we use the universal property of $C^{*}(\mathcal{G})$ and
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$ to find maps $\Phi\colon
C^{*}(\mathcal{G})\to\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$ and
$\Psi\colon\mathcal{O}(\Lambda_{\mathcal{G}_{+}})\to C^{*}(\mathcal{G})$, and
then we show that the maps $\Phi$ and $\Psi$ are mutual inverses. We first
prove some intermediary results, and then tie everything together in a proof
of the theorem at the end of this section.

######  Lemma 4.3.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources, and let
$\\{S_{\lambda}:\lambda\in\Lambda_{\mathcal{G}_{+}}\\}$ be a family satisfying
(S4). For any $v\in\Gamma^{0}$ and $g\in G_{v}$, we have that
$S_{g}S_{g}^{*}=S_{v}$.

###### Proof.

Fix $v\in\Gamma^{0}$ and $g\in G_{v}$. The singleton set $\\{g\\}\subseteq
v\Lambda$ is finite exhaustive, since for any $\lambda\in v\Lambda$ we have
$g\leq g(g^{-1}\lambda)=\lambda$. Thus (S4) gives that $S_{v}=S_{g}S_{g}^{*}$,
as required. ∎

######  Proposition 4.4.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources. A family
$\\{S_{\lambda}:\lambda\in\Lambda_{\mathcal{G}_{+}}\\}$ satisfying (S1), (S2)
and (S4) satisfies (S3) if and only if it satisfies the relation

  1. (S3’)

$S_{\lambda}S_{\lambda}^{*}S_{\mu}S_{\mu}^{*}=\begin{cases}S_{\mu}S_{\mu}^{*}&\text{if}\
\lambda\leq\mu,\\\ S_{\lambda}S_{\lambda}^{*}&\text{if}\ \mu\leq\lambda,\\\
0&\text{otherwise}.\end{cases}$

###### Proof.

We show that

$\bigvee_{\nu\in\lambda\vee\mu}S_{\nu}S_{\nu}^{*}=\begin{cases}S_{\mu}S_{\mu}^{*}&\text{if}\
\lambda\leq\mu,\\\ S_{\lambda}S_{\lambda}^{*}&\text{if}\ \mu\leq\lambda,\\\
0&\text{otherwise}.\end{cases}$

Fix $\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$. By Corollary 3.13, we have that
$\lambda\vee\mu\neq\emptyset$ if and only if $\lambda\leq\mu$ or
$\mu\leq\lambda$. In the case that $\lambda\leq\mu$, we have that
$\lambda\vee\mu$ is the set of $\mathcal{G}_{+}$-words $\nu$ such that
$\mu\leq\nu$ and $\nu\leq\mu$, which by Proposition 3.12 is the set
$q^{-1}(\mu)=\\{\mu g:g\in G_{s(\mu)}\\}$. Now, (S2) and Lemma 4.3 together
give that

$S_{\mu g}S_{\mu
g}^{*}=S_{\mu}S_{g}S_{g}^{*}S_{\mu}^{*}=S_{\mu}S_{s(\mu)}S_{\mu}^{*}=S_{\mu}S_{\mu}^{*}$

for all $g\in G_{s(\mu)}$. So in this case

$\bigvee_{\nu\in\lambda\vee\mu}S_{\nu}S_{\nu}^{*}=\bigvee_{g\in
G_{s(\mu)}}S_{\mu g}S_{\mu g}^{*}=\bigvee_{g\in
G_{s(\mu)}}S_{\mu}S_{\mu}^{*}=S_{\mu}S_{\mu}^{*}$

as required. A similar argument in the case where $\mu\leq\lambda$ shows that

$\bigvee_{\nu\in\lambda\vee\mu}S_{\nu}S_{\nu}^{*}=\bigvee_{g\in
G_{s(\lambda)}}S_{\lambda g}S_{\lambda g}^{*}=\bigvee_{g\in
G_{s(\lambda)}}S_{\lambda}S_{\lambda}^{*}=S_{\lambda}S_{\lambda}^{*}.$

Finally, if neither $\lambda\leq\mu$ nor $\mu\leq\lambda$, then
$\lambda\vee\mu=\emptyset$ and so
$\bigvee_{\nu\in\lambda\vee\mu}S_{\nu}S_{\nu}^{*}=0$ as required. ∎

######  Proposition 4.5.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources, and let $\Sigma$ be a set of transversals for
$\mathcal{G}_{+}$. Let $\\{t_{\lambda}:\lambda\in\Lambda_{\mathcal{G}_{+}}\\}$
be the Cuntz–Krieger $\Lambda_{\mathcal{G}_{+}}$-family generating
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$. For each $e\in\Gamma_{+}^{1}$, let
$S_{e}=t_{e}$; and for each $v\in\Gamma^{0}$ and $g\in G_{v}$, let
$U_{v,g}=t_{g}$. Then
$\\{S_{e}:e\in\Gamma_{+}^{1}\\}\cup\\{U_{v,g}:v\in\Gamma^{0},\ g\in G_{v}\\}$
is a $(\mathcal{G}_{+},\Sigma)$-family in
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$.

###### Proof.

Remark 2.8 tells us that $\\{S_{e}:e\in\Gamma_{+}^{1}\\}$ is a family of
partial isometries. Now fix $v\in\Gamma^{0}$. Each $U_{v,g}=t_{g}$, $g\in
G_{v}$ is a partial isometry since $t_{g}^{*}t_{g}^{*}=t_{v}=t_{g}t_{g}^{*}$
by (S1) and Lemma 4.3. Moreover, for any $g_{1},g_{2}\in G_{v}$ we have
$t_{g_{1}}t_{g_{2}}=t_{g_{1}g_{2}}$ by (S2), so $G_{v}\ni g\mapsto U_{v,g}$ is
a representation by partial unitaries.

Now we show that the $S_{e}$’s and $U_{v,g}$’s satisfy the relations in
Definition 4.1. For any $v,w\in\Gamma^{0}$ with $v\neq w$, (S3’) gives that
$t_{v}t_{w}=t_{v}t_{v}^{*}t_{w}t_{w}^{*}=0$, so relation (1) is satisfied. For
any $e\in\Gamma_{+}^{1}$ and $g\in G_{e}$, we have
$t_{\alpha_{e}(g)}t_{e}=t_{\alpha_{e}(g)e}=t_{e\alpha_{\overline{e}}(g)}=t_{e}t_{\alpha_{\overline{e}}(g)}$
using (S2) and the relation $\alpha_{e}(g)e=e\alpha_{\overline{e}}(g)$ in the
word category, so relation (2) is satisfied. Relation (3) follows immediately
from (S1).

Finally, for relation (4), we first claim that for any $v\in\Gamma^{0}$, the
set $\\{he:e\in v\Gamma_{+}^{1},\ h\in\Sigma_{e}\\}$ is an exhaustive subset
of $v\Lambda_{\mathcal{G}_{+}}$. To see this, take $\lambda\in
v\Lambda_{\mathcal{G}_{+}}$. If $\lambda=g_{1}$ for some $g_{1}\in G_{v}$,
then $\lambda=g_{1}\leq g_{1}(g_{1}^{-1}he)=he$ for any $e\in v\Gamma_{+}^{1}$
and $h\in\Sigma_{e}$; otherwise if $\lambda=h_{1}e_{1}\dots h_{n}e_{n}g_{n+1}$
in reduced form, then $h_{1}e_{1}\leq\lambda$. In either case, $\lambda$ is
comparable with some element in $\\{he:e\in v\Gamma_{+}^{1},\
h\in\Sigma_{e}\\}$, showing that it is exhaustive. Then (S4) gives that

$t_{v}=\bigvee_{e\in v\Gamma_{+}^{1},\ h\in\Sigma_{e}}t_{he}t_{he}^{*}.$

But (S3’) implies that the $t_{he}t_{he}^{*}$’s are pairwise orthogonal, and
so we get that

$t_{v}=\sum_{e\in v\Gamma_{+}^{1},\ h\in\Sigma_{e}}t_{he}t_{he}^{*}=\sum_{e\in
v\Gamma_{+}^{1},\ h\in\Sigma_{e}}t_{h}t_{e}t_{e}^{*}t_{h}^{*},$

which is relation (4). This proves that
$\\{S_{e}:e\in\Gamma_{+}^{1}\\}\cup\\{U_{v,g}:v\in\Gamma^{0},\ g\in G_{v}\\}$
is a $(\mathcal{G}_{+},\Sigma)$-family in
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$, as claimed. ∎

######  Proposition 4.6.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources, and let $\Sigma$ be a set of transversals for
$\mathcal{G}_{+}$. For each $\lambda=g_{1}e_{1}g_{2}e_{2}\dots
g_{n}e_{n}g_{n+1}$ in $\Lambda_{\mathcal{G}_{+}}$, define

$S_{\lambda}=u_{r(e_{1}),g_{1}}s_{e_{1}}u_{r(e_{2}),g_{2}}s_{e_{2}}\dots
u_{r(e_{n}),g_{n}}s_{e_{n}}u_{s(e_{n}),g_{n+1}}.$

Then $\\{S_{\lambda}:\lambda\in\Lambda_{\mathcal{G}_{+}}\\}$ is a
Cuntz–Krieger $\Lambda_{\mathcal{G}_{+}}$-family in $C^{*}(\mathcal{G}_{+})$.

###### Proof.

First note that the $S_{\lambda}$’s are well-defined, since if the
$\mathcal{G}_{+}$-words $g_{1}e_{1}g_{2}e_{2}\dots g_{n}e_{n}g_{n+1}$ and
$h_{1}e_{1}h_{2}e_{2}\dots h_{n}e_{n}h_{n+1}$ are two presentations of the
same element $\lambda\in\Lambda_{\mathcal{G}_{+}}\subseteq F(\mathcal{G})$,
then they are related via a finite number of applications of the relation
$\alpha_{e}(g)e=e\alpha_{\overline{e}}(g)$ which is implemented by relation
(2) of Definition 4.1.

To see that (S1) holds, take $\lambda=g_{1}e_{1}g_{2}e_{2}\dots
g_{n}e_{n}g_{n+1}$. Note that we have

$u_{r(e_{i}),g_{i}}^{*}u_{r(e_{i}),g_{i}}=u_{r(e_{i}),1}=s_{e_{i}}^{*}s_{e_{i}}$

for $i=1,\dots,n$, and also
$u_{s(e_{n}),g_{n+1}}^{*}u_{s(e_{n}),g_{n+1}}=u_{s(e),1}$. Applying these
relations iteratively to $S_{\lambda}^{*}S_{\lambda}$ gives that
$S_{\lambda}^{*}S_{\lambda}=u_{s(e_{n}),1}=t_{s(\lambda)}=S_{s(\lambda)}$, as
required.

(S2) holds by definition of the $S_{\lambda}$’s. For (S3), Proposition 4.4
means that it is enough to show that (S3’) holds. Take
$\lambda,\mu\in\Lambda_{\mathcal{G}_{+}}$. We have four cases. If
$\lambda\leq\mu$, then there exists $\nu\in\Lambda_{\mathcal{G}_{+}}$ with
$\mu=\lambda\nu$. So

$S_{\lambda}S_{\lambda}^{*}S_{\mu}S_{\mu}^{*}=S_{\lambda}S_{\lambda}^{*}S_{\lambda}S_{\nu}S_{\nu}^{*}S_{\lambda}^{*}=S_{\lambda}S_{\nu}S_{\nu}^{*}S_{\lambda}^{*}=S_{\mu}S_{\mu}^{*}.$

Similarly if $\mu\leq\lambda$, then there exists
$\nu\in\Lambda_{\mathcal{G}_{+}}$ with $\lambda=\mu\nu$. So

$S_{\lambda}S_{\lambda}^{*}S_{\mu}S_{\mu}^{*}=S_{\mu}S_{\nu}S_{\nu}^{*}S_{\mu}^{*}S_{\mu}S_{\mu}^{*}=S_{\mu}S_{\nu}S_{\nu}^{*}S_{\mu}^{*}=S_{\lambda}S_{\lambda}^{*}.$

If $r(\lambda)\neq r(\mu)$, then $\lambda$ and $\mu$ are not comparable, and
relation (1) gives that

$S_{\lambda}S_{\lambda}^{*}S_{\mu}S_{\mu}^{*}=S_{\lambda}S_{\lambda}^{*}u_{r(\lambda),1_{r(\lambda)}}u_{r(\mu),1_{r(\mu)}}S_{\mu}S_{\mu}^{*}=0.$

Finally we come to the case where $\lambda$ and $\mu$ have the same range but
are not comparable. Write $\nu$ for the maximal common initial subpath of
$\lambda$ and $\mu$. Then

$\lambda=\nu(h_{1}e_{1})\lambda^{\prime}\quad\text{and}\quad\mu=\nu(h_{2}e_{2})\mu^{\prime}$

for some
$h_{1}e_{1},\lambda^{\prime},h_{2}e_{2},\mu^{\prime}\in\Lambda_{\mathcal{G}_{+}}$
with $h_{1}e_{1}\neq h_{2}e_{2}$. So

$S_{\lambda}^{*}S_{\mu}=S_{\lambda^{\prime}}^{*}S_{h_{1}e_{1}}^{*}S_{\nu}^{*}S_{\nu}S_{h_{2}e_{2}}S_{\mu^{\prime}}=S_{\lambda^{\prime}}^{*}S_{h_{1}e_{1}}^{*}S_{h_{2}e_{2}}S_{\mu^{\prime}}=0$

since $S_{h_{1}e_{1}}$ and $S_{h_{2}e_{2}}$ have orthogonal range projections
due to relation (4).

For (S4), fix $v\in\Gamma^{0}$ and a finite exhaustive set $F\subseteq
v\Lambda_{\mathcal{G}_{+}}$. First note that relation (4) says that
$u_{w,1}=\sum_{he\in wE_{\Sigma}^{1}}S_{he}u_{s(e),1}S_{he}^{*}$ for all
$w\in\Gamma^{0}$, and applying this inductively gives that
$u_{v,1}=\sum_{\alpha\in E_{\Sigma}^{n}}S_{\alpha}S_{\alpha}^{*}$ for all
$n\in\mathbb{N}$. Now, for any $\lambda\in F$, setting $n=\lvert\lambda\rvert$
(that is, the number of edges in the $\mathcal{G}_{+}$-word $\lambda$) shows
that $S_{\lambda}S_{\lambda}^{*}=S_{q(\lambda)}S_{q(\lambda)}^{*}\leq
u_{v,1}$, so $\bigvee_{\lambda\in F}S_{\lambda}S_{\lambda}^{*}\leq u_{v,1}$.

It remains to prove that $u_{v,1}\leq\bigvee_{\lambda\in
F}S_{\lambda}S_{\lambda}^{*}$. Let $n=\max_{\lambda\in F}\lvert
q(\lambda)\rvert$. Since $F$ is exhaustive, for each $\alpha\in
E_{\Sigma}^{n}$ there is some $\lambda_{\alpha}\in F$ such that $\alpha
1_{s(\alpha)}$ and $\lambda_{\alpha}$ have a common extension. But Corollary
3.13 and the choice of length of $\alpha$ force $\lambda_{\alpha}\leq\alpha
1_{s(\alpha)}$. This implies that $S_{\alpha 1_{s(\alpha)}}S_{\alpha
1_{s(\alpha)}}^{*}\leq
S_{\lambda_{\alpha}}S_{\lambda_{\alpha}}^{*}\leq\bigvee_{\lambda\in
F}S_{\lambda}S_{\lambda}^{*}$ for all $\alpha\in E_{\Sigma}^{n}$, and so

$u_{v,1}=\sum_{\alpha\in
E_{\Sigma}^{n}}S_{\alpha}S_{\alpha}^{*}=\bigvee_{\alpha\in
E_{\Sigma}^{n}}S_{\alpha 1_{s(\alpha)}}S_{\alpha
1_{s(\alpha)}}^{*}\leq\bigvee_{\lambda\in F}S_{\lambda}S_{\lambda}^{*},$

as required. ∎

We now put everything together to prove Theorem 4.2.

###### Proof of Theorem 4.2.

Proposition 4.5 along with the universal property of $C^{*}(\mathcal{G}_{+})$
show that the map $\Phi$ in the statement of the theorem is a well-defined
$*$-homomorphism. Proposition 4.6 along with the universal property of
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$ give a $*$-homomorphism
$\Psi\colon\mathcal{O}(\Lambda_{\mathcal{G}_{+}})\to C^{*}(\mathcal{G}_{+})$
satisfying $\Psi(t_{e})=s_{e}$ for $e\in\Gamma_{+}^{1}$ and
$\Psi(t_{g})=u_{v,g}$ for $v\in\Gamma^{0}$ and $g\in G_{v}$. So
$\Psi\circ\Phi$ is the identity map on $C^{*}(\mathcal{G}_{+})$, which means
that $\Phi$ is injective. To see that $\Phi$ is surjective, note that any
$\lambda\in\Lambda_{\mathcal{G}_{+}}$ is a finite composition of elements of
the form $e\in\Gamma_{+}^{1}$ and $g\in G_{v}$, $v\in\Gamma^{0}$. So the
elements $t_{e}=\Phi(s_{e})$ and $t_{g}=\Phi(u_{v,g})$ generate
$\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$, meaning that $\Phi$ is surjective.
Hence $\Phi$ is a $C^{*}$-isomorphism, as claimed. ∎

##  5\. A $C^{*}$-algebraic ‘directed’ Bass–Serre theorem

This section is dedicated to proving the following result, which can be seen
as the directed version of [6, Theorem 4.1], described in that paper as a
$C^{*}$-algebraic Bass–Serre theorem. This result also generalises [17,
Corollary 4.14], which gives the result in the setting of directed graph
algebras.

######  Theorem 5.1.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of groups with no sources, and choose a base vertex $x\in\Gamma^{0}$. Then
$C^{*}(\mathcal{G}_{+})$ is Morita equivalent to $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$.

To prove this result, we first describe a groupoid model for
$C^{*}(\mathcal{G}_{+})$ in Section 5.1, and then in Section 5.2 we show that
the underlying groupoid is equivalent in a suitable sense to the
transformation groupoid $\pi_{1}(\mathcal{G},x)\ltimes\partial
X_{\mathcal{G}_{+},x}$.

###  5.1. Groupoid model for $C^{*}(\mathcal{G}_{+})$

Ortega and Pardo [23] give a groupoid model for the Cuntz–Krieger algebra of a
countable, finitely aligned LCSC using the language of inverse semigroup
actions. In this subsection we analyse the model as it applies to our context,
and provide a tractable version of the model in Theorem 5.9. We begin with a
general discussion of the groupoid model from [23].

Let $\Lambda$ be a countable, finitely aligned LCSC. We can associate a
semigroup $\SS_{\Lambda}$ to $\Lambda$ in the following way.

######  Definition 5.2 ([23, Section 2]).

Let $\Lambda$ be a LCSC. For each $\lambda\in\Lambda$, we define maps

$\tau^{\lambda}\colon
s(\lambda)\Lambda\to\lambda\Lambda;\quad\mu\mapsto\lambda\mu,\qquad\text{and}\qquad\sigma^{\lambda}\colon\lambda\Lambda\to
s(\lambda)\Lambda;\quad\lambda\mu\mapsto\mu.$

We write $\SS_{\Lambda}$ for the semigroup generated by
$\\{\tau^{\lambda},\sigma^{\lambda}:\lambda\in\Lambda\\}$ under composition,
where a composition is deemed to equal $0$ if it has empty domain.

The semigroup $\SS_{\Lambda}$ is an inverse semigroup, called the left inverse
hull of $\Lambda$. Theorem 4.16 of [23] states that the Cuntz–Krieger algebra
of $\Lambda$ is isomorphic to the $C^{*}$-algebra of what is called the tight
groupoid of $\SS_{\Lambda}$. This groupoid is topologically isomorphic to the
groupoid of germs of the action of $\SS_{\Lambda}$ on a certain space
$\Lambda_{tight}$ [23, Lemma 4.9], so $\mathcal{O}(\Lambda)\cong
C^{*}(\SS_{\Lambda}\ltimes\Lambda_{tight})$.

We will now describe the space $\Lambda_{tight}$ and the action of
$\SS_{\Lambda}$ on $\Lambda_{tight}$.

######  Definition 5.3 ([23, Section 3]).

Let $\Lambda$ be a finitely aligned LCSC. A non-empty subset
$H\subseteq\Lambda$ is:

  1. (1)

hereditary if for any $\lambda\in H$ and $\mu\in\Lambda$ such that
$\mu\leq\lambda$, we have that $\mu\in H$;

  2. (2)

(upwards) directed if for any $\lambda,\mu\in H$, there exists some $\nu\in H$
such that $\lambda,\mu\leq\nu$; and

  3. (3)

tight if for any $\lambda\in H$,
$\\{\mu_{1},\dots,\mu_{n}\\}\subseteq\Lambda\setminus H$, and finite
exhaustive set $Z$ of
$\lambda\Lambda\setminus\bigcup_{i=1}^{n}\mu_{i}\Lambda$, we have that $Z\cap
H\neq\emptyset$.

Write $\Lambda^{*}$ for the collection of hereditary directed subsets of
$\Lambda$, and write $\Lambda_{tight}$ for the collection of tight hereditary
directed subsets of $\Lambda$.

We can turn $\Lambda^{*}$ and $\Lambda_{tight}$ into topological spaces as
follows. For finite sets $X,Y\subseteq\Lambda$, define

$\mathcal{M}^{X,Y}=\\{H\in\Lambda^{*}:X\subseteq H\ \text{and}\ Y\cap
H=\emptyset\\}.$

We can endow $\Lambda^{*}$ with a topology generated by open sets
$\\{\mathcal{M}^{X,Y}:X,Y\subseteq\Lambda\ \text{finite}\\}$, and we give
$\Lambda_{tight}$ the subspace topology.

The semigroup $\SS_{\Lambda}$ acts on $\Lambda^{*}$ as follows. The domain and
range of a generating element $\tau^{\lambda}\sigma^{\mu}\in\SS_{\Lambda}$
(where $\lambda,\mu\in\Lambda$ with $s(\lambda)=s(\mu)$) are
$\\{H\in\Lambda^{*}:\mu\in H\\}$ and $\\{H\in\Lambda^{*}:\lambda\in H\\}$
respectively, and $\tau^{\lambda}\sigma^{\mu}$ acts according to the formula

$\tau^{\lambda}\sigma^{\mu}\cdot
H=\\{\xi\in\Lambda:\xi\leq\tau^{\lambda}\sigma^{\mu}(\nu)\ \text{for some}\
\nu\in H\ \text{such that}\ \mu\leq\nu\\}$

for $H$ in the domain of $\tau^{\lambda}\sigma^{\mu}$. This action restricts
to an action on $\Lambda_{tight}$ [23, Corollary 4.7], whose groupoid of germs
has $C^{*}$-algebra isomorphic to $\mathcal{O}(\Lambda)$.

We now consider these results in the setting where the category $\Lambda$ is
the word category of a directed graph of groups. To avoid cluttered notation,
we will write $\SS_{\mathcal{G}_{+}}$ instead of
$\SS_{\Lambda_{\mathcal{G}_{+}}}$ to denote the left inverse hull of the word
category of a directed graph of groups $\mathcal{G}_{+}$. The following
proposition describes the structure of $\SS_{\mathcal{G}_{+}}$.

######  Proposition 5.4.

Let $\mathcal{G}_{+}$ be a directed graph of groups. We have that

$\SS_{\mathcal{G}_{+}}=\\{\tau^{\lambda}\sigma^{\mu}:\lambda,\mu\in\Lambda_{\mathcal{G}_{+}},\
s(\lambda)=s(\mu)\\}\cup\\{0\\}.$

Moreover, for any two nonzero elements
$\tau^{\lambda}\sigma^{\mu},\tau^{\nu}\sigma^{\xi}\in\SS_{\mathcal{G}_{+}}$,
we have

  1. (1)

$\tau^{\lambda}\sigma^{\mu}=\tau^{\nu}\sigma^{\xi}$ if and only if there is
$g\in G_{s(\lambda)}$ such that $\nu=\lambda g$ and $\xi=\mu g$; and

  2. (2)

$\tau^{\lambda}\sigma^{\mu}\tau^{\nu}\sigma^{\xi}=\begin{cases}\tau^{\lambda}\sigma^{\xi\eta}&\text{if}\
\mu=\nu\eta\ \text{for some}\ \eta\in\Lambda_{\mathcal{G}_{+}};\\\
\tau^{\lambda\eta}\sigma^{\xi}&\text{if}\ \nu=\mu\eta\ \text{for some}\
\eta\in\Lambda_{\mathcal{G}_{+}};\\\ 0&\text{otherwise.}\end{cases}$

###### Proof.

Since $\Lambda_{\mathcal{G}_{+}}$ is singly aligned (Corollary 3.14), [9,
Theorem 3.2] gives that

$\SS_{\mathcal{G}_{+}}=\\{\tau^{\lambda}\sigma^{\mu}:\lambda,\mu\in\Lambda_{\mathcal{G}_{+}},\
s(\lambda)=s(\mu)\\}\cup\\{0\\},$

and that multiplication is described by

$\tau^{\lambda}\sigma^{\mu}\tau^{\nu}\sigma^{\xi}=\begin{cases}\tau^{\lambda\sigma^{\mu}(\gamma)}\sigma^{\xi\sigma^{\nu}(\gamma)}&\text{if}\
\mu\Lambda_{\mathcal{G}_{+}}\cap\nu\Lambda_{\mathcal{G}_{+}}=\gamma\Lambda_{\mathcal{G}_{+}};\\\
0&\text{otherwise.}\end{cases}$

(Note that in [9], the semigroup $\SS_{\mathcal{G}_{+}}$ is denoted as
$ZM(\Lambda_{\mathcal{G}_{+}})$.) Now, the condition that
$\mu\Lambda_{\mathcal{G}_{+}}\cap\nu\Lambda_{\mathcal{G}_{+}}$ is non-empty is
equivalent to $\mu$ and $\nu$ having a common extension, which by Corollary
3.13 is in turn equivalent to $\mu$ and $\nu$ being comparable. In this case,
we can consider two (overlapping) subcases: $\nu\leq\mu$ or $\mu\leq\nu$.

If $\nu\leq\mu$, then $\mu=\nu\eta$ for some
$\eta\in\Lambda_{\mathcal{G}_{+}}$, and we can take $\gamma$ to be $\mu$. Then
$\sigma^{\mu}(\gamma)$ is just $s(\mu)$ and $\sigma^{\nu}(\gamma)=\eta$, so we
get that
$\tau^{\lambda\sigma^{\mu}(\gamma)}\sigma^{\xi\sigma^{\nu}(\gamma)}=\tau^{\lambda}\sigma^{\xi\eta}$.
If instead $\mu\leq\nu$, then $\nu=\mu\eta$ for some
$\eta\in\Lambda_{\mathcal{G}_{+}}$, and we can take $\gamma$ to be $\nu$. Then
$\sigma^{\nu}(\gamma)$ is just $s(\nu)$ and $\sigma^{\mu}(\gamma)=\eta$, so we
get that
$\tau^{\lambda\sigma^{\mu}(\gamma)}\sigma^{\xi\sigma^{\nu}(\gamma)}=\tau^{\lambda\eta}\sigma^{\xi}$.
This proves (2).

Finally, (1) follows from [9, Proposition 3.3], since invertible elements in
$\Lambda_{\mathcal{G}_{+}}$ at the object $s(\lambda)$ are exactly elements of
the vertex group $G_{s(\lambda)}$. ∎

######  Remark 5.5.

If all groups in $\mathcal{G}_{+}$ are trivial, then $\SS_{\mathcal{G}_{+}}$
is the graph inverse semigroup of $\Gamma_{+}$ as defined in [25].

We now turn to the space $(\Lambda_{\mathcal{G}_{+}})_{tight}$ of tight
hereditary directed subsets of $\Lambda_{\mathcal{G}_{+}}$. The aim of the
next series of results is to prove that $(\Lambda_{\mathcal{G}_{+}})_{tight}$
is isomorphic to the infinite path space $E_{\Sigma}^{\infty}$ of
$E_{\Sigma}$, for any set of transversals $\Sigma$. We prove this in several
steps: first we show that $(\Lambda_{\mathcal{G}_{+}})_{tight}$ is in
bijection with $(E_{\Sigma}^{*})_{tight}$ (Proposition 5.6); next we show that
$(E_{\Sigma}^{*})_{tight}$ is in turn in bijection with $E_{\Sigma}^{\infty}$
(Proposition 5.7); and finally we show that the bijection between
$(\Lambda_{\mathcal{G}_{+}})_{tight}$ and $E_{\Sigma}^{\infty}$ is a
homeomorphism (Proposition 5.8).

######  Proposition 5.6.

Let $\mathcal{G}_{+}$ be a directed graph of groups, and let $\Sigma$ be a set
of transversals for $\mathcal{G}_{+}$. The map
$q\colon\Lambda_{\mathcal{G}_{+}}\to E_{\Sigma}^{*}$ induces a bijection
$(\Lambda_{\mathcal{G}_{+}})_{tight}\to(E_{\Sigma}^{*})_{tight}$, whose
inverse is given by taking pre-images under $q$.

###### Proof.

First note that for any hereditary subset
$H\subseteq\Lambda_{\mathcal{G}_{+}}$, if $\lambda\in H$ then, by Proposition
3.12, $H$ also contains all $\mu\in\Lambda_{\mathcal{G}_{+}}$ for which
$q(\mu)=q(\lambda)$; thus $H=q^{-1}(q(H))$. Moreover, $q(H)$ is hereditary,
since for any $\alpha\in E_{\Sigma}^{*}$ and $\mu\in H$ such that $\alpha\leq
q(\mu)$, Proposition 3.12 gives that $\alpha\leq\mu$ in
$\Lambda_{\mathcal{G}_{+}}$ and thus that $\alpha\in H$ since $H$ is
hereditary; so we have $\alpha=q(\alpha)\in q(H)$ as required. Likewise, if
$K\subseteq E_{\Sigma}^{*}$ is hereditary, then its pre-image
$q^{-1}(K)\subseteq\Lambda_{\mathcal{G}_{+}}$ is also hereditary. So $q$
induces a bijection between the hereditary subsets of
$\Lambda_{\mathcal{G}_{+}}$ and $E_{\Sigma}^{*}$, with the inverse given by
taking pre-images under $q$. Now, Proposition 3.12 also implies that a subset
$H\subseteq\Lambda_{\mathcal{G}_{+}}$ is directed if and only if its image
$q(H)\subseteq E_{\Sigma}^{*}$ is directed, so $q$ in fact induces a bijection
between $\Lambda_{\mathcal{G}_{+}}^{*}$ and $(E_{\Sigma}^{*})^{*}$.

We now show that this bijection restricts to a bijection on the level of tight
hereditary directed subsets. First suppose that
$H\subseteq\Lambda_{\mathcal{G}_{+}}$ is a tight hereditary directed subset;
we show that $q(H)\subseteq E_{\Sigma}^{*}$ is tight. Take $\alpha\in q(H)$
and $\beta_{1},\dots,\beta_{n}\in E_{\Sigma}^{*}\setminus q(H)$, and let
$Z\subseteq\alpha
E_{\Sigma}^{*}\setminus\bigcup_{i=1}^{n}\beta_{i}E_{\Sigma}^{*}$ be finite
exhaustive. Since $H=q^{-1}(q(H))$, if we consider
$\alpha,\beta_{1},\dots,\beta_{n}$ as elements of $\Lambda_{\mathcal{G}_{+}}$,
then $\alpha\in H$ and
$\beta_{1},\dots,\beta_{n}\in\Lambda_{\mathcal{G}_{+}}\setminus H$. If we also
identify $Z$ with its image in $\Lambda_{\mathcal{G}_{+}}$, then
$Z\subseteq\alpha\Lambda_{\mathcal{G}_{+}}\setminus\bigcup_{i=1}^{n}\beta_{i}\Lambda_{\mathcal{G}_{+}}$
is also finite exhaustive: for any
$\lambda\in\alpha\Lambda_{\mathcal{G}_{+}}\setminus\bigcup_{i=1}^{n}\beta_{i}\Lambda_{\mathcal{G}_{+}}$,
we have $q(\lambda)\in\alpha
E_{\Sigma}^{*}\setminus\bigcup_{i=1}^{n}\beta_{i}E_{\Sigma}^{*}$, so since $Z$
is exhaustive there is some $z\in Z$ such that $q(\lambda)E_{\Sigma}^{*}\cap
zE_{\Sigma}^{*}\neq\emptyset$; but then Proposition 3.12 implies that
$\lambda\Lambda_{\mathcal{G}_{+}}\cup z\Lambda_{\mathcal{G}_{+}}\neq\emptyset$
also. Then, since $H$ is tight, we have $Z\cap H\neq\emptyset$, and so $Z\cap
q(H)\neq\emptyset$ in $E_{\Sigma}^{*}$. Hence $q(H)$ is tight. A similar
argument shows that if $K\subseteq E_{\Sigma}^{*}$ is a tight hereditary
directed subset, then its pre-image
$q^{-1}(K)\subseteq\Lambda_{\mathcal{G}_{+}}$ is also tight. Hence $q$ induces
a bijection $(\Lambda_{\mathcal{G}_{+}})_{tight}\to(E_{\Sigma}^{*})_{tight}$,
as claimed. ∎

######  Proposition 5.7.

Let $\mathcal{G}_{+}$ be a countable, row-finite directed graph of groups with
no sources, and let $\Sigma$ be a set of transversals for $\mathcal{G}_{+}$.
For each infinite path $\alpha\in E_{\Sigma}^{\infty}$, define a subset
$\Delta_{\alpha}\subseteq E_{\Sigma}^{*}$ by $\Delta_{\alpha}:=\\{\beta\in
E_{\Sigma}^{*}:\beta\leq\alpha\\}$. Write $\Delta$ for the map sending
$\alpha$ to $\Delta_{\alpha}$. Then $\Delta$ is a bijection
$E_{\Sigma}^{\infty}\to(E_{\Sigma}^{*})_{tight}$.

###### Proof.

It is easy to check that each $\Delta_{\alpha}$, $\alpha\in
E_{\Sigma}^{\infty}$ is hereditary and directed. To see that it is tight, fix
paths $\beta\in\Delta_{\alpha}$ and $\gamma_{1},\dots,\gamma_{n}\in
E_{\Sigma}^{*}\setminus\Delta_{\alpha}$, and fix a finite exhaustive subset
$Z\subseteq\beta
E_{\Sigma}^{*}\setminus\bigcup_{i=1}^{n}\gamma_{i}E_{\Sigma}^{*}$; we will
show that $Z\cap\Delta_{\alpha}\neq\emptyset$. Take
$\beta^{\prime}\in\Delta_{\alpha}$ such that $\beta\leq\beta^{\prime}$ and
$\lvert\beta^{\prime}\rvert>\max_{z\in Z}\lvert z\rvert$. Note that
$\gamma_{i}\not\leq\beta^{\prime}$ for $i=1,\dots,n$ (otherwise, since
$\Delta_{\alpha}$ is hereditary we would have $\gamma_{i}\in\Delta_{\alpha}$,
contradicting the choice of $\gamma_{i}$), so $\beta^{\prime}\in\beta
E_{\Sigma}^{*}\setminus\bigcup_{i=1}^{n}\gamma_{i}E_{\Sigma}^{*}$. Then, since
$Z$ is exhaustive, there is some $z\in Z$ which has a common extension with
$\beta^{\prime}$. This implies that either $z\leq\beta^{\prime}$ or
$\beta^{\prime}\leq z$. But the latter is impossible, since we chose
$\beta^{\prime}$ to be longer than any path in $Z$; so we must have
$z\leq\beta^{\prime}$. Finally, since $\Delta_{\alpha}$ is hereditary, we get
that $z\in\Delta_{\alpha}$, which implies that
$Z\cap\Delta_{\alpha}\neq\emptyset$, as required. Hence each
$\Delta_{\alpha}$, $\alpha\in E_{\Sigma}^{\infty}$ is tight, and so $\Delta$
is a map $E_{\Sigma}^{\infty}\to(E_{\Sigma}^{*})_{tight}$.

Since every infinite path in $E_{\Sigma}$ is uniquely determined by the set of
its initial subpaths, we get that $\Delta$ is injective. Now, the discussion
in [23, Example 3.31] (where our $\Delta_{\alpha}$ is denoted as $E_{\alpha}$)
shows that every tight hereditary directed subset of $E_{\Sigma}^{*}$ is equal
to $\Delta_{\alpha}$ for some $\alpha\in E_{\Sigma}^{\infty}$ (note that since
$\mathcal{G}_{+}$ is row-finite and has no sources, the same is true for
$E_{\Sigma}$, and so $E_{\Sigma}$ has no singular vertices), so $\Delta$ is
also surjective. Thus $\Delta\colon
E_{\Sigma}^{\infty}\to(E_{\Sigma}^{*})_{tight}$ is a bijection, as claimed. ∎

######  Proposition 5.8.

Let $\Delta\colon E_{\Sigma}^{\infty}\to(E_{\Sigma}^{*})_{tight}$ be as in
Proposition 5.7. The map $q^{-1}\circ\Delta\colon
E_{\Sigma}^{\infty}\to(\Lambda_{\mathcal{G}_{+}})_{tight}$ is a homeomorphism.

###### Proof.

Propositions 5.6 and 5.7 together give that $q^{-1}\circ\Delta$ is a
bijection, so it remains to prove that it is continuous and open. Recall that
the codomain $(\Lambda_{\mathcal{G}_{+}})_{tight}$ has basic open sets of the
form

$\mathcal{M}^{X,Y}=\\{H\in(\Lambda_{\mathcal{G}_{+}})_{tight}:X\subseteq H\
\text{and}\ Y\cap H=\emptyset\\},\quad X,Y\subseteq\Lambda_{\mathcal{G}_{+}}\
\text{finite}.$

Fix finite sets $X,Y\subseteq\Lambda_{\mathcal{G}_{+}}$. For an infinite path
$\alpha\in E_{\Sigma}^{\infty}$, the condition $X\subseteq
q^{-1}(\Delta_{\alpha})$ means that $q(\lambda)\leq\alpha$ for all $\lambda\in
X$, and similarly the condition $Y\cap q^{-1}(\Delta_{\alpha})=\emptyset$
means that $q(\mu)\not\leq\alpha$ for all $\mu\in Y$. So

$\displaystyle\Delta^{-1}(q(\mathcal{M}^{X,Y}))$ $\displaystyle=\\{\alpha\in
E_{\Sigma}^{\infty}:q(\lambda)\leq\alpha\ \text{for all}\ \lambda\in X,\
\text{and}\ q(\mu)\not\leq\alpha\ \text{for all}\ \mu\in Y\\}$
$\displaystyle=\left(\bigcap_{\lambda\in
X}q(\lambda)E_{\Sigma}^{\infty}\right)\setminus\left(\bigcup_{\mu\in
Y}q(\mu)E_{\Sigma}^{\infty}\right),$

which is a basic open set in $E_{\Sigma}^{\infty}$, and moreover, all basic
open sets in $E_{\Sigma}^{\infty}$ have this form. This implies that
$q^{-1}\circ\Delta$ is continuous and open, and hence is a homeomorphism. ∎

We are now ready to prove the main result of this subsection, which gives a
more tangible groupoid model for a directed graph of groups $C^{*}$-algebra.

######  Theorem 5.9.

Let $\mathcal{G}_{+}$ be a countable, row-finite directed graph of groups with
no sources, and let $\Sigma$ be a set of transversals for $\mathcal{G}_{+}$.
Then $C^{*}(\mathcal{G}_{+})\cong C^{*}(\SS_{\mathcal{G}_{+}}\ltimes
E_{\Sigma}^{\infty})$, where $\SS_{\mathcal{G}_{+}}\ltimes
E_{\Sigma}^{\infty}$ is the groupoid of germs for the action of
$\SS_{\mathcal{G}_{+}}$ on $E_{\Sigma}^{\infty}$ given by

$\tau^{\lambda}\sigma^{\mu}\cdot\alpha=\lambda\mu^{-1}\cdot\alpha,\quad\text{for}\
\alpha\ \text{such that}\ q(\mu)\leq\alpha,$

where in the right hand side the action of $\lambda\mu^{-1}\in F(\mathcal{G})$
on $\alpha\in E_{\Sigma}^{\infty}$ is as in Proposition 3.18.

###### Proof.

From Theorem 4.2 we know that
$C^{*}(\mathcal{G}_{+})\cong\mathcal{O}(\Lambda_{\mathcal{G}_{+}})$, and [23,
Section 4.4] gives that $\mathcal{O}(\Lambda_{\mathcal{G}_{+}})\cong
C^{*}(\SS_{\mathcal{G}_{+}}\ltimes(\Lambda_{\mathcal{G}_{+}})_{tight})$.
Proposition 5.8 says that the map $q^{-1}\circ\Delta\colon
E_{\Sigma}^{\infty}\to(\Lambda_{\mathcal{G}_{+}})_{tight}$ is a homeomorphism,
and so it remains to show that the induced action of $\SS_{\mathcal{G}_{+}}$
on $E_{\Sigma}^{\infty}$ has the formula given in the theorem statement (this
would also imply that the formula defines a legitimate action).

Recall that the action of $\SS_{\mathcal{G}_{+}}$ on
$(\Lambda_{\mathcal{G}_{+}})_{tight}$ is given by

$\tau^{\lambda}\sigma^{\mu}\cdot
H=\\{\xi\in\Lambda_{\mathcal{G}_{+}}:\xi\leq\tau^{\lambda}\sigma^{\mu}(\nu)\
\text{for some}\ \nu\in H\ \text{such that}\ \mu\leq\nu\\}$

for $H\in(\Lambda_{\mathcal{G}_{+}})_{tight}$ such that $\mu\in H$. Pulling
back through the homeomorphism $q^{-1}\circ\Delta$, we get that for $\alpha\in
E_{\Sigma}^{\infty}$ such that $q(\mu)\leq\alpha$,

$\displaystyle\tau^{\lambda}\sigma^{\mu}\cdot q^{-1}(\Delta_{\alpha})$
$\displaystyle=\\{\xi\in\Lambda_{\mathcal{G}_{+}}:\xi\leq\tau^{\lambda}\sigma^{\mu}(\nu)\
\text{for some}\ \nu\in q^{-1}(\Delta_{\alpha})\ \text{such that}\
\mu\leq\nu\\}$
$\displaystyle=\\{\xi\in\Lambda_{\mathcal{G}_{+}}:\xi\leq\tau^{\lambda}\sigma^{\mu}(\nu)\
\text{for some}\ \nu\in\Lambda_{\mathcal{G}_{+}}\ \text{such that}\ q(\mu)\leq
q(\nu)\leq\alpha\\}.$

But note that the condition that $\xi\leq\tau^{\lambda}\sigma^{\mu}(\nu)$ for
some $\nu\in\Lambda_{\mathcal{G}_{+}}$ with $q(\mu)\leq q(\nu)\leq\alpha$ is
equivalent to the condition that $q(\xi)\leq\lambda\mu^{-1}\cdot\alpha$, so
$\tau^{\lambda}\sigma^{\mu}\cdot
q^{-1}(\Delta_{\alpha})=q^{-1}(\Delta_{\lambda\mu^{-1}\cdot\alpha})$. Thus the
action of $\SS_{\mathcal{G}_{+}}$ on $E_{\Sigma}^{\infty}$ induced from the
action on $(\Lambda_{\mathcal{G}_{+}})_{tight}$ is given by
$\tau^{\lambda}\sigma^{\mu}\cdot\alpha=\lambda\mu^{-1}\cdot\alpha$, as
claimed. ∎

To finish this subsection, we study the groupoid of germs
$\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$ from Theorem 5.9. Recall
that the groupoid $\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$ consists
of equivalence classes of elements in
$\SS_{\mathcal{G}_{+}}*E_{\Sigma}^{\infty}=\\{(\tau^{\lambda}\sigma^{\mu},\alpha)\in\SS_{\mathcal{G}_{+}}\times
E_{\Sigma}^{\infty}:s(\lambda)=s(\mu)\ \text{and}\ q(\mu)\leq\alpha\\}$. We
now give a concrete description of the equivalence in our context.

######  Proposition 5.10.

Let
$(\tau^{\lambda}\sigma^{\mu},\alpha),(\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}},\beta)\in\SS_{\mathcal{G}_{+}}*E_{\Sigma}^{\infty}$.
The germs $[\tau^{\lambda}\sigma^{\mu},\alpha]$ and
$[\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}},\beta]$ are the same if and
only if $\alpha=\beta$ and (assuming without loss of generality that
$\mu\leq\mu^{\prime}$) there exists $\eta\in\Lambda_{\mathcal{G}_{+}}$ such
that $\lambda^{\prime}=\lambda\eta$ and $\mu^{\prime}=\mu\eta$.

###### Proof.

By definition, we have that the germs $[\tau^{\lambda}\sigma^{\mu},\alpha]$
and $[\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}},\beta]$ are the same if and
only if $\alpha=\beta$ and there is an idempotent $e\in\SS_{\mathcal{G}_{+}}$
such that $\alpha\in D_{e}$ and
$\tau^{\lambda}\sigma^{\mu}e=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}e$.
Note that $e$ must be non-zero, since otherwise $D_{e}$ would be empty. Now,
[9, Proposition 3.5(1)] gives that the non-zero idempotents of
$\SS_{\mathcal{G}_{+}}$ are exactly elements of the form
$\tau^{\xi}\sigma^{\xi}$ for some $\xi\in\Lambda_{\mathcal{G}_{+}}$, and we
have that $\alpha\in D_{\tau^{\xi}\sigma^{\xi}}$ if and only if
$q(\xi)\leq\alpha$. So the germs $[\tau^{\lambda}\sigma^{\mu},\alpha]$ and
$[\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}},\beta]$ are the same if and
only if $\alpha=\beta$ and there is $\xi\in\Lambda_{\mathcal{G}_{+}}$ such
that $q(\xi)\leq\alpha$ and
$\tau^{\lambda}\sigma^{\mu}\tau^{\xi}\sigma^{\xi}=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}\tau^{\xi}\sigma^{\xi}$.

First suppose that there is $\eta\in\Lambda_{\mathcal{G}_{+}}$ such that
$\lambda^{\prime}=\lambda\eta$ and $\mu^{\prime}=\mu\eta$. Then Proposition
5.4 gives that
$\tau^{\lambda}\sigma^{\mu}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}$,
so we can take $\xi=\mu^{\prime}$ to see that the germs
$[\tau^{\lambda}\sigma^{\mu},\alpha]$ and
$[\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}},\beta]$ are the same.

Now suppose that the germs $[\tau^{\lambda}\sigma^{\mu},\alpha]$ and
$[\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}},\beta]$ are the same. Note that
since $\alpha=\beta$, we must have both $q(\mu)\leq\alpha$ and
$q(\mu^{\prime})\leq\alpha$. This forces $q(\mu)$ and $q(\mu^{\prime})$ to be
comparable, since they are both initial subpaths of $\alpha$. Assume without
loss of generality that $q(\mu)\leq q(\mu^{\prime})$; then Proposition 3.12
gives that $\mu\leq\mu^{\prime}$, so there is some
$\eta\in\Lambda_{\mathcal{G}_{+}}$ such that $\mu^{\prime}=\mu\eta$.

It is left to show that $\lambda^{\prime}=\lambda\eta$. Let
$\xi\in\Lambda_{\mathcal{G}_{+}}$ be such that $q(\xi)\leq\alpha$ and
$\tau^{\lambda}\sigma^{\mu}\tau^{\xi}\sigma^{\xi}=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}\tau^{\xi}\sigma^{\xi}$.
Since $q(\xi)$, $q(\mu)$ and $q(\mu^{\prime})$ are all subpaths of $\alpha$,
we have that $q(\xi)$ is comparable with both $q(\mu)$ and $q(\mu^{\prime})$.
Hence by Proposition 3.12 we have that $\xi$ is comparable with both $\mu$ and
$\mu^{\prime}$.

We now reduce to the case where $(\mu\leq)\ \mu^{\prime}\leq\xi$. Indeed,
suppose that $\xi\leq\mu^{\prime}$, so $\mu^{\prime}=\xi\nu$ for some
$\nu\in\Lambda_{\mathcal{G}_{+}}$. Then $\sigma^{\xi}(\mu^{\prime})=\nu$, and
$\tau^{\xi}\sigma^{\xi}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}=\tau^{\xi\nu}\sigma^{\mu^{\prime}}=\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}$.
This means that

$\displaystyle\tau^{\lambda}\sigma^{\mu}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}$
$\displaystyle=\tau^{\lambda}\sigma^{\mu}\tau^{\xi}\sigma^{\xi}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}$
$\displaystyle=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}\tau^{\xi}\sigma^{\xi}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}$
$\displaystyle=\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}.$

We also have that $\alpha\in D_{\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}}$, so
$\tau^{\mu^{\prime}}\sigma^{\mu^{\prime}}$ is also an idempotent in
$\SS_{\mathcal{G}_{+}}$ with the required properties. Hence we can replace
$\xi$ with $\mu^{\prime}$, so that now $\mu^{\prime}\leq\xi$.

Finally we prove the statement in the case that $(\mu\leq)\
\mu^{\prime}\leq\xi$. Let $\nu,\nu^{\prime}\in\Lambda_{\mathcal{G}_{+}}$ be
such that $\xi=\mu\nu=\mu^{\prime}\nu^{\prime}$. Then
$\tau^{\lambda}\sigma^{\mu}\tau^{\xi}\sigma^{\xi}=\tau^{\lambda\nu}\sigma^{\xi}$,
and
$\tau^{\lambda^{\prime}}\sigma^{\mu^{\prime}}\tau^{\xi}\sigma^{\xi}=\tau^{\lambda^{\prime}\nu^{\prime}}\sigma^{\xi}$.
So the assumption on $\xi$ implies that
$\tau^{\lambda\nu}\sigma^{\xi}=\tau^{\lambda^{\prime}\nu^{\prime}}\sigma^{\xi}$,
and then [9, Proposition 3.3] gives that
$\lambda\nu=\lambda^{\prime}\nu^{\prime}$. Now,
$\mu\nu=\xi=\mu^{\prime}\nu^{\prime}=\mu\eta\nu^{\prime}$, so by
cancellativity of $\Lambda_{\mathcal{G}_{+}}$ we have that
$\nu=\eta\nu^{\prime}$. So
$\lambda^{\prime}\nu^{\prime}=\lambda\nu=\lambda\eta\nu^{\prime}$, and using
cancellativity again gives that $\lambda^{\prime}=\lambda\eta$, as required. ∎

###  5.2. Groupoid equivalence

We now use the groupoid model for $C^{*}(\mathcal{G}_{+})$ obtained in Theorem
5.9 to prove Theorem 5.1, that $C^{*}(\mathcal{G}_{+})$ is Morita equivalent
to the crossed product $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$. Our strategy is to show
that the underlying groupoids of the two $C^{*}$-algebras in question, namely
the groupoid of germs $\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$ and
the transformation groupoid $\pi_{1}(\mathcal{G},x)\ltimes\partial
X_{\mathcal{G}_{+},x}$, are equivalent in a suitable sense so that we have a
Morita equivalence on the level of $C^{*}$-algebras.

We begin with a discussion of groupoid equivalence. In [29], Renault
introduced the notion of groupoid equivalence: roughly speaking, two Hausdorff
étale groupoids $\mathscr{G}$ and $\mathscr{H}$ are equivalent if they act in
a compatible way on some space. For us, the important property is that
equivalent groupoids have Morita equivalent $C^{*}$-algebras ([21, Theorem
2.8]).

Rather than working with this notion of groupoid equivalence directly, we will
consider the notion of weak Kakutani equivalence for groupoids, which was
studied in [10]. Recall that a subset $X$ of the unit space of a groupoid
$\mathscr{G}$ is called full if it meets the orbit of every unit in
$\mathscr{G}$. Two Hausdorff étale groupoids are called weakly Kakutani
equivalent if there are full open subsets $U\subseteq\mathscr{G}^{(0)}$ and
$V\subseteq\mathscr{H}^{(0)}$ such that
$\mathscr{G}|_{U}\cong\mathscr{H}|_{V}$ [10, Definition 3.8]. Weak Kakutani
equivalence implies equivalence in the sense of Renault [10, Proposition
3.10].

We combine these concepts in the following key lemma, which we will use to
prove Theorem 5.1.

######  Lemma 5.11.

Let $\mathscr{G}$ be a Hausdorff étale groupoid, and suppose that
$U,V\subseteq\mathscr{G}^{(0)}$ are full open subsets. Then
$C^{*}(\mathscr{G}|_{U})$ and $C^{*}(\mathscr{G}|_{V})$ are Morita equivalent
$C^{*}$-algebras.

###### Proof.

Note that $\mathscr{G}|_{U}$ is weakly Kakutani equivalent to $\mathscr{G}$
(take $U$ to be the full open subset for both groupoids), and similarly
$\mathscr{G}|_{V}$ is also weakly Kakutani equialent to $\mathscr{G}$. Then
[10, Proposition 3.10] implies that $\mathscr{G}|_{U}$ and $\mathscr{G}|_{V}$
are both equivalent to $\mathscr{G}$ in the sense of Renault. Since
equivalence in the sense of Renault is an equivalence relation (see e.g. [21,
p. 6]), we get that $\mathscr{G}|_{U}$ and $\mathscr{G}|_{V}$ are equivalent,
and hence their $C^{*}$-algebras are Morita equivalent by [21, Theorem 2.8]. ∎

######  Proposition 5.12.

Let $\mathcal{G}_{+}$ be a countable, row-finite directed graph of groups with
no sources, and let $\Sigma$ be a set of transversals for $\mathcal{G}_{+}$.
The groupoid of germs $\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$ is
topologically isomorphic to the groupoid $(F(\mathcal{G})\ltimes\partial
W_{\mathcal{G}_{+}})|_{E_{\Sigma}^{\infty}}$.

###### Proof.

Propositions 5.10 and 3.18 together mean that we can define a map

$\Theta\colon\SS_{\mathcal{G}_{+}}\ltimes
E_{\Sigma}^{\infty}\to(F(\mathcal{G})\ltimes\partial
W_{\mathcal{G}_{+}})|_{E_{\Sigma}^{\infty}},\quad[\tau^{\lambda}\sigma^{\mu},\alpha]\mapsto(\lambda\mu^{-1},\alpha),$

and Theorem 5.9 implies that $\Theta$ is a groupoid homomorphism. We claim
that $\Theta$ is a topological groupoid isomorphism.

Proposition 3.18 gives that $\Theta$ is surjective. For injectivity, suppose
that $[\tau^{\lambda}\sigma^{\mu},\alpha]$ and
$[\tau^{\nu}\sigma^{\xi},\beta]$ are two germs in
$\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$ such that
$\Theta([\tau^{\lambda}\sigma^{\mu},\alpha])=\Theta([\tau^{\nu}\sigma^{\xi},\beta])$.
So $(\lambda\mu^{-1},\alpha)=(\nu\xi^{-1},\beta)$, which means that
$\alpha=\beta$ and $\lambda\mu^{-1}=\nu\xi^{-1}$. Now, since $\alpha$ is in
the domain of both $\tau^{\lambda}\sigma^{\mu}$ and $\tau^{\nu}\sigma^{\xi}$,
we must have that $q(\mu)$ and $q(\xi)$ are both initial subpaths of $\alpha$
and therefore must be comparable. Without loss of generality, suppose that
$q(\mu)\leq q(\xi)$. Then Proposition 3.12 gives that $\mu\leq\xi$, so there
is some $\eta\in\Lambda_{\mathcal{G}_{+}}$ such that $\xi=\mu\eta$. Then
$\lambda\mu^{-1}=\nu(\mu\eta)^{-1}=\nu\eta^{-1}\mu^{-1}$ in $F(\mathcal{G})$,
so $\lambda=\nu\eta^{-1}$ and thus $\nu=\lambda\eta$. Then Proposition 5.10
gives that
$[\tau^{\lambda}\sigma^{\mu},\alpha]=[\tau^{\nu}\sigma^{\xi},\beta]$, proving
that $\Theta$ is injective.

Finally we show that $\Theta$ is a homeomorphism. Take a basic open set
$[\tau^{\lambda}\sigma^{\mu},U]\subseteq\SS_{\mathcal{G}_{+}}\ltimes
E_{\Sigma}^{\infty}$, where $U\subseteq q(\mu)E_{\Sigma}^{\infty}$ is open.
The image of this set under $\Theta$ is $(\lambda\mu^{-1},U)$, which is open
in $(F(\mathcal{G})\ltimes\partial
W_{\mathcal{G}_{+}})|_{E_{\Sigma}^{\infty}}$. Similarly, the inverse image of
the basic open set $(\lambda\mu^{-1},U)\subseteq(F(\mathcal{G})\ltimes\partial
W_{\mathcal{G}_{+}})|_{E_{\Sigma}^{\infty}}$ is
$[\tau^{\lambda}\sigma^{\mu},U]$, which is open in
$\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$. Thus $\Theta$ induces a
bijection between basic open sets, and is therefore a homeomorphism. This
proves that the groupoids $\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty}$
and $(F(\mathcal{G})\ltimes\partial
W_{\mathcal{G}_{+}})|_{E_{\Sigma}^{\infty}}$ are topologically isomorphic. ∎

We are now ready to prove Theorem 5.1.

###### Proof of Theorem 5.1.

Let $\Sigma$ be a set of transversals for $\mathcal{G}_{+}$. Proposition 5.12
says that the groupoid of germs $\SS_{\mathcal{G}_{+}}\ltimes
E_{\Sigma}^{\infty}$ is topologically isomorphic to the groupoid
$(F(\mathcal{G})\ltimes\partial W_{\mathcal{G}_{+}})|_{E_{\Sigma}^{\infty}}$,
and by definition we have that the transformation groupoid
$\pi_{1}(\mathcal{G},x)\ltimes\partial X_{\mathcal{G}_{+},x}$ is the groupoid
$(F(\mathcal{G})\ltimes\partial W_{\mathcal{G}_{+}})|_{\partial
X_{\mathcal{G}_{+},x}}$. We claim that both $E_{\Sigma}^{\infty}$ and
$\partial X_{\mathcal{G}_{+},x}$ are full open subsets of the unit space of
$F(\mathcal{G})\ltimes\partial W_{\mathcal{G}_{+}}$.

First we consider $E_{\Sigma}^{\infty}$. This set is open as
$E_{\Sigma}^{\infty}=\bigsqcup_{v\in\Gamma^{0}}Z(G_{v})$. To see that it is
full, take any $\gamma\in\partial W_{\mathcal{G}_{+}}$, viewed as an
eventually directed infinite $\mathcal{G}$-word. Write
$\gamma=\gamma^{\prime}\alpha$, where $\alpha$ is an infinite
$\mathcal{G}_{+}$-word (which we can view as an element of
$E_{\Sigma}^{\infty}$, as in Section 3.3). Then $\gamma$ is in the same orbit
as $\alpha\in E_{\Sigma}^{\infty}$, showing that $E_{\Sigma}^{\infty}$ is
full.

Now consider $\partial X_{\mathcal{G}_{+},x}$. This set is open as $\partial
X_{\mathcal{G}_{+},x}=\bigcup_{\gamma\in x\mathcal{G}^{*}}Z(\gamma
G_{s(\gamma)})$. To see that it is full, again take any $\gamma\in\partial
W_{\mathcal{G}_{+}}$, viewed as an eventually directed infinite
$\mathcal{G}$-word. Write $v$ for the range of $\gamma$, and let
$\gamma_{v}\in xF(\mathcal{G})v$. Then $\gamma_{v}\gamma$ is an eventually
directed infinite $\mathcal{G}$-word with range $x$, and so can be viewed as
an element of $\partial X_{\mathcal{G}_{+},x}$. This shows that $\partial
X_{\mathcal{G}_{+},x}$ is full.

Hence we can apply Lemma 5.11, which together with Proposition 5.12 gives that
$C^{*}(\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty})$ is Morita equivalent
to $C^{*}(\pi_{1}(\mathcal{G},x)\ltimes\partial X_{\mathcal{G}_{+},x})$. The
theorem follows, since $C^{*}(\mathcal{G}_{+})\cong
C^{*}(\SS_{\mathcal{G}_{+}}\ltimes E_{\Sigma}^{\infty})$ by Theorem 5.9, and
$C_{0}(\partial X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)\cong
C^{*}(\pi_{1}(\mathcal{G},x)\ltimes\partial X_{\mathcal{G}_{+},x})$. ∎

######  Remark 5.13.

We can in fact say a little more about the relationship between
$C^{*}(\mathcal{G}_{+})$ and $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$, under the assumptions of
Theorem 5.1. Both $C^{*}$-algebras are separable since they have countable
generating sets, and two separable $C^{*}$-algebras are Morita equivalent if
and only if they are stably isomorphic [5]. Thus we have that
$C^{*}(\mathcal{G}_{+})$ is stably isomorphic to $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$.

##  6\. A construction of all stable UCT Kirchberg algebras

In this final section we aim to show that the class of directed graph of
groups $C^{*}$-algebras includes all stable UCT Kirchberg algebras (recall
that a Kirchberg algebra is a $C^{*}$-algebra that is simple, separable,
purely infinite, and nuclear). These algebras are the subject of the
celebrated Kirchberg–Phillips classification theorem [16, 26], part of which
we state below.

######  Theorem 6.1 (Kirchberg–Phillips classification theorem).

Suppose that $A$ and $B$ are both stable UCT Kirchberg algebras. Then $A\cong
B$ if and only if $K_{*}(A)\cong K_{*}(B)$.

One of the benefits of such a classification result is that it allows us
realise these abstractly defined $C^{*}$-algebras via a concrete construction,
as has been done in [32] and [14]. Our main result of this section, which we
state below, adds to this list of constructions; notably, our result gives the
first concrete construction of Kirchberg algebras as crossed product
$C^{*}$-algebras.

######  Theorem 6.2.

Let $A$ be a stable UCT Kirchberg algebra. There exists a countable, row-
finite directed graph of infinite cyclic groups
$\mathcal{G}_{+}=(\Gamma_{+},G)$ with no sources, such that $A\cong
C^{*}(\mathcal{G}_{+})\cong C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G}_{+},x)$ for any
$x\in\Gamma^{0}$.

In order to show this, we use Theorem 5.1 along with the results in [7], which
provides both a $K$-theory formula for crossed products coming from group
actions on directed tree boundaries as well as criteria for such a crossed
product to be a UCT Kirchberg algebra. We then transfer these results to our
context of directed graph of groups $C^{*}$-algebras using the observation
that the class of UCT Kirchberg algebras is closed under stable isomorphism
(see [30]).

###  6.1. $C^{*}$-algebras of directed graphs of infinite cyclic groups

In this subsection, we investigate the $C^{*}$-algebras of directed graphs of
groups where all vertex and edge groups are infinite cyclic (we will call
these directed graphs of infinite cyclic groups). In particular, we give a
formula for the $K$-theory of these $C^{*}$-algebras (Proposition 6.5), as
well as sufficient conditions for the $C^{*}$-algebra to be a UCT Kirchberg
algebra (Proposition 6.6).

We start with some notation.

######  Notation 6.3.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a directed graph of infinite cyclic
groups. We fix generators $1_{v}\in G_{v}$ and $1_{e}\in G_{e}$ for each
vertex $v\in\Gamma^{0}$ and each edge $e\in\Gamma_{+}^{1}$ so that for each
edge $e\in\Gamma_{+}^{1}$, the map $\alpha_{e}\colon G_{e}\to G_{r(e)}$ is
given by multiplication by some positive integer
$n_{e}\in\mathbb{N}\setminus\\{0\\}$ (this is always possible to arrange); and
the map $\alpha_{\overline{e}}\colon G_{e}\to G_{s(e)}$ will be given by
multiplication by some non-zero integer $m_{e}\in\mathbb{Z}\setminus\\{0\\}$.

######  Remark 6.4.

By Theorem 3.4, we have that the vertex stabilisers of the action
$\pi_{1}(\mathcal{G},x)\curvearrowright X_{\mathcal{G}_{+},x}$ are infinite
cyclic, and that the quotient directed graph of the action is isomorphic to
$\Gamma_{+}$. Moreover, for each $e\in\Gamma_{+}^{1}$, the integers $n_{e}$
and $m_{e}$ from Notation 6.3 are exactly the integers $\omega_{e}$ and
$\omega_{\overline{e}}$ of [7, Notation 4.18] respectively.

We can now give a formula for the $K$-theory of $C^{*}(\mathcal{G}_{+})$ for a
directed graph of infinite cyclic groups $\mathcal{G}_{+}$.

######  Proposition 6.5.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of infinite cyclic groups with no sources. Let
$N,M\colon\mathbb{Z}[\Gamma^{0}]\to\mathbb{Z}[\Gamma^{0}]$ be the
$\mathbb{Z}$-module homomorphisms given by

$N(v)=\sum_{e\in v\Gamma^{1}_{+}}n_{e}s(e)\qquad\text{and}\qquad
M(v)=\sum_{e\in v\Gamma^{1}_{+}}m_{e}s(e)\qquad\text{for}\ v\in\Gamma^{0}.$

Then

$\displaystyle K_{0}(C^{*}(\mathcal{G}_{+}))$
$\displaystyle\cong\operatorname{coker}(1-N)\oplus\ker(1-M),\quad\text{and}$
$\displaystyle K_{1}(C^{*}(\mathcal{G}_{+}))$
$\displaystyle\cong\operatorname{coker}(1-M)\oplus\ker(1-N).$

###### Proof.

We know from Theorem 5.1 that $C^{*}(\mathcal{G}_{+})$ is Morita equivalent to
the crossed product $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$. Since $K$-theory is
invariant under Morita equivalence, it is enough to show the corresponding
isomorphisms for the $K$-theory of the crossed product. To do this, we apply
[7, Theorem 4.19]. The tree $X_{\mathcal{G}_{+},x}$ is row-finite and has no
sources since $\Gamma_{+}$ has those properties, and it is a finitely aligned
multitree in the sense of [7] since it is a tree. The group
$\pi_{1}(\mathcal{G},x)$ is countable since $\mathcal{G}_{+}$ is countable,
and it acts amenably on $\partial X_{\mathcal{G}_{+},x}$ by [7, Proposition
6.11] (as per Remark 6.4, all vertex stabilisers of the action are infinite
cyclic, and hence amenable). So the assumptions of [7, Theorem 4.19] are
satisfied, and we get that

$\displaystyle K_{0}(C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes_{r}\pi_{1}(\mathcal{G},x))$
$\displaystyle\cong\operatorname{coker}(1-A_{0})\oplus\ker(1-A_{1}),\quad\text{and}$
$\displaystyle K_{1}(C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes_{r}\pi_{1}(\mathcal{G},x))$
$\displaystyle\cong\operatorname{coker}(1-A_{1})\oplus\ker(1-A_{0}),$

where $A_{0}$ and $A_{1}$ are the $\mathbb{Z}$-module homomorphisms
$\mathbb{Z}[\Gamma^{0}]\to\mathbb{Z}[\Gamma^{0}]$ defined by

$A_{0}(v)=\sum_{e\in v\Gamma_{+}^{1}}\lvert\omega_{e}\rvert
s(e)\quad\text{and}\quad A_{1}(v)=\sum_{e\in
v\Gamma_{+}^{1}}\operatorname{sgn}(\omega_{e})\omega_{\overline{e}}s(e)$

for $v\in\Gamma^{0}$. But by Remark 6.4, we have that $\omega_{e}=n_{e}$ and
$\omega_{\overline{e}}=m_{e}$ for all $e\in\Gamma_{+}^{1}$, and recall that
each $n_{e}$ was chosen to be positive. Thus the maps $A_{0}$ and $A_{1}$ are
exactly the maps $N$ and $M$ from the proposition statement, respectively.
Finally, we note that the reduced crossed product $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes_{r}\pi_{1}(\mathcal{G},x)$ is the same as the
full crossed product $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$ since the action of
$\pi_{1}(\mathcal{G},x)$ on $\partial X_{\mathcal{G}_{+},x}$ is amenable. This
concludes the proof. ∎

Next, we give sufficient conditions for $C^{*}(\mathcal{G}_{+})$ to be a UCT
Kirchberg algebra. In the following, for $q\in\mathbb{Q}^{\times}$ we denote
by $\langle q\rangle$ the smallest positive integer that can appear as a
denominator when expressing $q$ as a fraction.

######  Proposition 6.6.

Let $\mathcal{G}_{+}=(\Gamma_{+},G)$ be a countable, row-finite directed graph
of infinite cyclic groups with no sources. Suppose that:

  1. (1)

the directed graph $\Gamma_{+}$ is cofinal;

  2. (2)

there is a loop $\eta=\eta_{1}\eta_{2}\dots\eta_{m}$ in $\Gamma_{+}$ such that
either $\eta$ has an entrance, or $n_{\eta_{i}}\geq 2$ for some $1\leq i\leq
m$; and

  3. (3)

there is some infinite path $\alpha=e_{1}e_{2}\ldots\in\Gamma_{+}^{\infty}$
such that

$\limsup_{k\to\infty}\left\langle\frac{m_{e_{1}}\dots
m_{e_{k-1}}}{n_{e_{1}}\dots n_{e_{k}}}\right\rangle=\infty.$

Then $C^{*}(\mathcal{G}_{+})$ is a UCT Kirchberg algebra.

###### Proof.

Since the class of UCT Kirchberg algebras is closed under stable isomorphism,
Remark 5.13 means that it is enough to show that the crossed product
$C_{0}(\partial X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$ is a UCT
Kirchberg algebra.

Separability is automatic, since $\pi_{1}(\mathcal{G},x)$ is countable. Note
that the action $\pi_{1}(\mathcal{G},x)\curvearrowright\partial
X_{\mathcal{G}_{+},x}$ is amenable by [7, Proposition 6.11], so the crossed
product is nuclear [1] and satisfies the UCT (see [34]). So it remains to show
that the crossed product is simple and purely infinite.

By [3, p.124], the crossed product will be simple if the action
$\pi_{1}(\mathcal{G},x)\curvearrowright\partial X_{\mathcal{G}_{+},x}$ is
minimal and topologically free (we already know the action to be amenable);
and in this case the crossed product will be purely infinite if the action is
locally contractive [19, Theorem 9] (where local contractivity is called being
a local boundary action). By Remark 6.4, conditions (1) and (3) of the
proposition are exactly the conditions in [7, Propositions 6.1, 6.6] which are
equivalent to the action $\pi_{1}(\mathcal{G},x)\curvearrowright\partial
X_{\mathcal{G}_{+},x}$ being minimal and topologically free, respectively.

Finally, we need to show that the action
$\pi_{1}(\mathcal{G},x)\curvearrowright\partial X_{\mathcal{G}_{+},x}$ is
locally contractive. Take the loop $\eta$ from condition (2). Since
$n_{e}=[G_{r(e)}:\alpha(G_{e})]$ for any $e\in\Gamma_{+}^{1}$, we get that
$\eta$ satisfies condition (i) of [7, Proposition 6.2]; moreover, the
confinality of $\Gamma_{+}$ means that there is a path from $r(\eta)$ to any
vertex $v\in\Gamma^{0}$ (consider the infinite path $\eta\eta\dots$), so
condition (ii) is also satisfied. Hence [7, Proposition 6.2] gives that
$\pi_{1}(\mathcal{G},x)\curvearrowright\partial X_{\mathcal{G}_{+},x}$ is
locally contractive, as required. ∎

###  6.2. Construction of stable UCT Kirchberg algebras

We now describe how to construct a directed graph of (infinite cyclic) groups
whose $C^{*}$-algebra is a stable UCT Kirchberg algebra with any given
$K$-theory; together with Theorem 5.1, this essentially proves Theorem 6.2.
Our construction is inspired by the approach in [14], but is adjusted slightly
to work in our context. We begin by explaining how we can define a directed
graph of infinite cyclic groups from a pair of integer matrices.

######  Notation 6.7.

Let $J$ be a countable index set, and let $N\in M_{\lvert
J\rvert}(\mathbb{N})$ and $M\in M_{\lvert J\rvert}(\mathbb{Z})$ be two
matrices indexed over $J$ satisfying $N_{i,j}=0\iff M_{i,j}=0$ for all $i,j\in
J$. Define $\mathcal{G}_{+}^{N,M}=(\Gamma_{+},G)$ to be the directed graph of
groups where:

  * •

the underlying graph $\Gamma_{+}=(\Gamma^{0},\Gamma_{+}^{1},r,s)$ is given by

$\Gamma^{0}=J,\qquad\Gamma_{+}^{1}=\\{(i,j)\in J\times J:N_{i,j}>0\\},\qquad
r(i,j)=i,\qquad s(i,j)=j;$

  * •

all vertex and edge groups are infinite cyclic, with a choice of generator
$1_{i}\in G_{i}$ for each $i\in\Gamma^{0}$ and $1_{(i,j)}\in G_{(i,j)}$ for
each $(i,j)\in\Gamma_{+}^{1}$; and

  * •

for each $(i,j)\in\Gamma_{+}^{1}$, the monomorphisms $\alpha_{(i,j)}$ and
$\alpha_{\overline{(i,j)}}$ are defined by

$\alpha_{(i,j)}(1_{(i,j)})=N_{i,j}1_{i},\qquad\alpha_{\overline{(i,j)}}(1_{(i,j)})=M_{i,j}1_{j}.$

We also have the following canonical set of tranvsersals for
$\mathcal{G}^{N,M}_{+}$: for each $(i,j)\in\Gamma_{+}^{1}$, we let
$\Sigma_{(i,j)}=\\{0,1_{i},2\times 1_{i},\dots,(N_{i,j}-1)1_{i}\\}$.

######  Remark 6.8.

Let $N,M$ and $\mathcal{G}_{+}^{N,M}$ be as in Notation 6.7. The maps
$N,M\colon\mathbb{Z}[\Gamma^{0}]\to\mathbb{Z}[\Gamma^{0}]$ of Proposition 6.5
for $\mathcal{G}_{+}^{N,M}$ are precisely the maps given by left
multiplication by the matrices $N$ and $M$. Thus we have

$\displaystyle K_{0}(C^{*}(\mathcal{G}_{+}^{N,M}))$
$\displaystyle\cong\operatorname{coker}(1-N)\oplus\ker(1-M),\quad\text{and}$
$\displaystyle K_{1}(C^{*}(\mathcal{G}_{+}^{N,M}))$
$\displaystyle\cong\operatorname{coker}(1-M)\oplus\ker(1-N).$

In order to prove Theorem 6.2 we show that for any pair of countable abelian
groups $G_{0},G_{1}$ we can find suitable matrices $N,M$ such that
$C^{*}(\mathcal{G}_{+}^{N,M})$ is a UCT Kirchberg algebra with $K$-theory
$(G_{0},G_{1})$.

######  Construction 6.9.

Let $G_{0}$ and $G_{1}$ be countable abelian groups. There exist injective
homomorphisms $T,S\colon\mathbb{Z}^{\infty}\to\mathbb{Z}^{\infty}$ such that
$\operatorname{coker}T\cong G_{0}$ and $\operatorname{coker}S\cong G_{1}$. We
view these as elements of $M_{\infty}(\mathbb{Z})$, indexed over $\mathbb{N}$,
and we will write $\lvert T\rvert$ and $\lvert S\rvert$ for the matrices
obtained by taking element-wise absolute values of $T$ and $S$ respectively.
Define $X\in M_{\infty}(\mathbb{N})$ by

$X_{k,l}=\begin{cases}1&\text{if}\ \lvert k-l\rvert=1,\\\
0&\text{otherwise},\end{cases}$

for $k,l\in\mathbb{N}$, and define $Y\in M_{\infty}(\mathbb{N})$ by $Y=2\lvert
T\rvert+\lvert S\rvert+X$, both indexed over $\mathbb{N}$. Define matrices
$N\in M_{\infty}(\mathbb{N})$ and $M\in M_{\infty}(\mathbb{Z})$ in block form
by

$N=\begin{pmatrix}2I&T+Y\\\ I&I+Y\end{pmatrix}\quad\text{and}\quad
M=\begin{pmatrix}3I&S+2Y\\\ I&I+Y\end{pmatrix}.$

We index $N$ and $M$ over $\mathbb{N}\times\\{0,1\\}$, where the first block
of rows/columns corresponds to the indices $\mathbb{N}\times\\{0\\}$, and the
second block corresponds to the indices $\mathbb{N}\times\\{1\\}$.

######  Proposition 6.10.

The matrices $N,M$ of Construction 6.9 satisfy:

  1. (1)

$N_{i,j}=0\iff M_{i,j}=0$ for all $i,j\in\mathbb{N}\times\\{0,1\\}$;

  2. (2)

the maps $1-N$ and $1-M$ are injective; and

  3. (3)

$\operatorname{coker}(1-N)\cong G_{0}$ and $\operatorname{coker}(1-M)\cong
G_{1}$.

###### Proof.

To prove (1), it is enough to check that $(T+Y)_{k,l}=0\iff(S+2Y)_{k,l}=0$ for
all $k,l\in\mathbb{N}$. First note that for any integer $a\in\mathbb{Z}$, the
number $a+2\lvert a\rvert$ is always non-negative and is equal to $0$ if and
only if $a=0$. Thus we have that, for all $k,l\in\mathbb{N}$, both
$(T+Y)_{k,l}=(T_{k,l}+2\lvert T_{k,l}\rvert)+\lvert S_{k,l}\rvert+X_{k,l}$ and
$(S+2Y)_{k,l}=(S_{k,l}+2\lvert S_{k,l}\rvert)+4\lvert T_{k,l}\rvert+2X_{k,l}$
equal $0$ if and only if $T_{k,l}=S_{k,l}=X_{k,l}=0$, proving the claim.

For (2) and (3), note that

$1-N=\begin{pmatrix}-I&-T-Y\\\ -I&-Y\end{pmatrix}=\begin{pmatrix}I&I\\\
0&I\end{pmatrix}\begin{pmatrix}0&-T\\\ -I&0\end{pmatrix}\begin{pmatrix}I&Y\\\
0&I\end{pmatrix}$

and

$1-M=\begin{pmatrix}-2I&-S-2Y\\\ -I&-Y\end{pmatrix}=\begin{pmatrix}I&2I\\\
0&I\end{pmatrix}\begin{pmatrix}0&-S\\\ -I&0\end{pmatrix}\begin{pmatrix}I&Y\\\
0&I\end{pmatrix}.$

Since matrices of the form $\begin{pmatrix}I&*\\\ 0&I\end{pmatrix}$ are
invertible (with inverse $\begin{pmatrix}I&-*\\\ 0&I\end{pmatrix}$), we get
that

$\displaystyle\ker(1-N)$ $\displaystyle=\ker\begin{pmatrix}0&-T\\\
-I&0\end{pmatrix}=0;$ $\displaystyle\operatorname{coker}(1-N)$
$\displaystyle=\operatorname{coker}\begin{pmatrix}0&-T\\\
-I&0\end{pmatrix}=\operatorname{coker}T=G_{0};$ $\displaystyle\ker(1-M)$
$\displaystyle=\ker\begin{pmatrix}0&-S\\\ -I&0\end{pmatrix}=0;\ \text{and}$
$\displaystyle\operatorname{coker}(1-M)$
$\displaystyle=\operatorname{coker}\begin{pmatrix}0&-S\\\
-I&0\end{pmatrix}=\operatorname{coker}S=G_{1},$

as claimed. ∎

Remark 6.8 and Proposition 6.10 together give the following result.

######  Corollary 6.11.

Let $N$ and $M$ be as in Construction 6.9. Then
$K_{i}(C^{*}(\mathcal{G}^{N,M}_{+}))\cong G_{i}$ for $i=0,1$.

Before we study properties of $C^{*}(\mathcal{G}^{N,M}_{+})$, we make the
following observation about the graph of groups $\mathcal{G}^{N,M}_{+}$.

######  Remark 6.12.

Let $N$ and $M$ be as in Construction 6.9. Regardless of the groups
$G_{0},G_{1}$ used in the construction, the directed graph $\Gamma_{+}$
underlying $\mathcal{G}^{N,M}_{+}$ always has the following graph (which we
will call $\Gamma_{0}$) as a subgraph:

$\scriptstyle(0,0)$$\scriptstyle(0,1)$$\scriptstyle(1,0)$$\scriptstyle(1,1)$$\scriptstyle(2,0)$$\scriptstyle(2,1)$$\scriptstyle(3,0)$$\scriptstyle(3,1)$$\cdots$$\cdots$

This is the subgraph with adjacency matrix

$\begin{pmatrix}I&X\\\ I&X\end{pmatrix},$

where the top row of vertices corresponds to the vertices
$\mathbb{N}\times\\{0\\}$, and the bottom row of vertices corresponds to the
vertices $\mathbb{N}\times\\{1\\}$. Note that $\Gamma_{0}$ contains all edges
emitted from the vertices $\mathbb{N}\times\\{0\\}$ (the top row); moreover,
for each loop $e_{n}=((n,0),(n,0))$, $n\in\mathbb{N}$ in $\Gamma_{+}$, the
monomorphisms $\alpha_{e_{n}}$ and $\alpha_{\overline{e_{n}}}$ are defined by

$\alpha_{e_{n}}(1_{e_{n}})=2\times
1_{(n,0)}\quad\text{and}\quad\alpha_{\overline{e_{n}}}(1_{e_{n}})=3\times
1_{(n,0)}$

respectively.

######  Proposition 6.13.

For $N$ and $M$ as in Construction 6.9, the $C^{*}$-algebra
$C^{*}(\mathcal{G}_{+}^{N,M})$ is a stable UCT Kirchberg algebra.

###### Proof.

We apply Proposition 6.6. To see that $\Gamma_{+}$ is cofinal, note that the
subgraph $\Gamma_{0}$ described in Remark 6.12 is strongly connected (that is,
there is a directed path from any vertex in $\Gamma_{0}$ to any other vertex
in $\Gamma_{0}$): the vertices in the bottom row of the figure are strongly
connected via the horizontal edges between them, and one can travel between
the top and bottom rows via the vertical or diagonal edges. Since $\Gamma_{0}$
has the same vertex set as $\Gamma_{+}$, we have that $\Gamma_{+}$ is also
strongly connected and thus cofinal.

For (2) and (3), take the unique loop $e$ at $(0,0)\in\Gamma^{0}$. Since
$n_{e}=2$, the loop $e$ satisfies the condition in (2). Moreover, for
$\alpha=ee\dots$, the fraction $m_{e_{1}}\dots m_{e_{k-1}}/n_{e_{1}}\dots
n_{e_{k}}$ in (3) is equal to $3^{k-1}/2^{k}$, and
$\limsup_{k\to\infty}\langle
3^{k-1}/2^{k}\rangle=\limsup_{k\to\infty}2^{k}=\infty$; hence (3) is also
satisfied. Then Proposition 6.6 gives that $C^{*}(\mathcal{G}^{N,M}_{+})$ is a
UCT Kirchberg algebra. Finally, since $\Gamma_{+}$ has infinitely many
vertices, the algebra $C^{*}(\mathcal{G}_{+})$ is non-unital, and hence is
stable by [35, Theorem 1.2]. ∎

###### Proof of Theorem 6.2.

Write $G_{0}=K_{0}(A)$ and $G_{1}=K_{1}(A)$, and let $N$ and $M$ be as in
Construction 6.9. Proposition 6.13 gives that $C^{*}(\mathcal{G}^{N,M}_{+})$
is a stable UCT Kirchberg algebra, and Corollary 6.11 gives that the
$K$-theory of $C^{*}(\mathcal{G}^{N,M}_{+})$ is isomorphic to the $K$-theory
of $A$. Thus, the Kirchberg–Phillips classification theorem gives that
$C^{*}(\mathcal{G}_{+})\cong A$.

Now we show that $C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)\cong
C^{*}(\mathcal{G}_{+})$ for any $x\in\Gamma^{0}$. We know from Remark 5.13
that the $C^{*}$-algebras are stably isomorphic, so the crossed product
$C_{0}(\partial X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$ is also a
UCT Kirchberg algebra with $K$-theory $(G_{0},G_{1})$. All that remains is to
show that the crossed product is not unital (equivalently that the space
$\partial X_{\mathcal{G}_{+},x}$ is not compact); then [35, Theorem 1.2]
implies that it is stable, and again the Kirchberg–Phillips classification
theorem would give that $A\cong C^{*}(\mathcal{G}_{+})\cong C_{0}(\partial
X_{\mathcal{G}_{+},x})\rtimes\pi_{1}(\mathcal{G},x)$ as claimed.

Since the spaces $\partial X_{\mathcal{G}_{+},x}$ are isomorphic for each
$x\in\Gamma^{0}$, it is enough to show that $\partial X_{\mathcal{G}_{+},x}$
is not compact for a particular choice of $x\in\Gamma^{0}$. We choose $x$ to
be the vertex $(0,0)\in\Gamma^{0}$. Consider the open cover $\\{Z(\gamma
G_{s(\gamma)}):\gamma\in xF(\mathcal{G})\\}$ of $\partial
X_{\mathcal{G}_{+},x}$; we show that it does not admit a finite subcover.
Indeed, let $\gamma_{1},\dots,\gamma_{n}\in xF(\mathcal{G})$ be a finite set
of $\Sigma$-normalised $\mathcal{G}$-words in $xF(\mathcal{G})$ (where
$\Sigma$ is some fixed set of transversals for $\mathcal{G}$). Write $k$ for
the maximum length of $\gamma_{i}$, $i=1,\dots,n$, and write $e$ for the
unique loop in $\Gamma_{+}$ at $x$. Now consider the eventually directed
($\Sigma$-normalised) infinite $\mathcal{G}$-word
$\xi=\overline{e}\cdots\overline{e}1_{r(e)}ee\dots$ beginning with $k+1$
repetitions of the loop $\overline{e}$. We have that $\xi$ cannot have the
form $\gamma_{i}\alpha$ for any $i=1,\dots,n$ and any infinite
$\mathcal{G}_{+}$-word $\alpha$, since the edge $\overline{e}$ can only appear
in $\gamma_{i}$ and no $\gamma_{i}$ can contain $k+1$ copies of
$\overline{e}$. Hence $\xi\notin Z(\gamma_{i}G_{s(\gamma_{i})})$ for all
$i=1,\dots,n$, so $\\{Z(\gamma_{i}G_{s(i)})\\}_{i=1}^{n}$ is not a cover of
$\partial X_{\mathcal{G}_{+},x}$. This proves that $\partial
X_{\mathcal{G}_{+},x}$ is not compact, as claimed. ∎

## References

  * [1] C. Anantharaman-Delaroche and J. Renault.  Amenable groupoids, volume 36 of Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique].  L’Enseignement Mathématique, Geneva, 2000.  With a foreword by Georges Skandalis and Appendix B by E. Germain.
  * [2] Claire Anantharaman-Delaroche.  Purely infinite $C^{*}$-algebras arising from dynamical systems.  Bull. Soc. Math. France, 125(2):199–225, 1997.
  * [3] R. J. Archbold and J. S. Spielberg.  Topologically free actions and ideals in discrete $C^{*}$-dynamical systems.  Proc. Edinburgh Math. Soc. (2), 37(1):119–124, 1994.
  * [4] Hyman Bass.  Covering theory for graphs of groups.  J. Pure Appl. Algebra, 89(1-2):3–47, 1993.
  * [5] Lawrence G. Brown, Philip Green, and Marc A. Rieffel.  Stable isomorphism and strong Morita equivalence of $C^{*}$-algebras.  Pacific J. Math., 71(2):349–363, 1977.
  * [6] Nathan Brownlowe, Alexander Mundey, David Pask, Jack Spielberg, and Anne Thomas.  $C^{*}$-algebras associated to graphs of groups.  Adv. Math., 316:114–186, 2017.
  * [7] Nathan Brownlowe, Jack Spielberg, Anne Thomas, and Victor Wu.  Group actions on multitrees and the $k$-theory of their crossed products, 2023.  arXiv:2311.05285.
  * [8] Joachim Cuntz and Wolfgang Krieger.  A class of $C^{\ast}$-algebras and topological Markov chains.  Invent. Math., 56(3):251–268, 1980.
  * [9] Allan Donsig, Jennifer Gensler, Hannah King, David Milan, and Ronen Wdowinski.  On zigzag maps and the path category of an inverse semigroup.  Semigroup Forum, 100(3):790–805, 2020.
  * [10] Carla Farsi, Alex Kumjian, David Pask, and Aidan Sims.  Ample groupoids: equivalence, homology, and Matui’s HK conjecture.  Münster J. Math., 12(2):411–451, 2019.
  * [11] Eusebio Gardella, Shirly Geffen, Julian Kranz, and Petr Naryshkin.  Classifiability of crossed products by nonamenable groups.  J. Reine Angew. Math., 797:285–312, 2023.
  * [12] P. J. Higgins.  The fundamental groupoid of a graph of groups.  J. London Math. Soc. (2), 13(1):145–149, 1976.
  * [13] Paul Jolissaint and Guyan Robertson.  Simple purely infinite $C^{\ast}$-algebras and $n$-filling actions.  J. Funct. Anal., 175(1):197–213, 2000.
  * [14] Takeshi Katsura.  A class of $C^{*}$-algebras generalizing both graph algebras and homeomorphism $C^{*}$-algebras. IV. Pure infiniteness.  J. Funct. Anal., 254(5):1161–1187, 2008.
  * [15] Takeshi Katsura.  A construction of actions on Kirchberg algebras which induce given actions on their $K$-groups.  J. Reine Angew. Math., 617:27–65, 2008.
  * [16] Eberhard Kirchberg.  The classification of purely infinite $C^{*}$-algebras using Kasparov’s theory.  Preprint, 1994.
  * [17] Alex Kumjian and David Pask.  $C^{*}$-algebras of directed graphs and group actions.  Ergodic Theory Dynam. Systems, 19(6):1503–1519, 1999.
  * [18] Alex Kumjian and David Pask.  Higher rank graph $C^{\ast}$-algebras.  New York J. Math., 6:1–20, 2000.
  * [19] Marcelo Laca and Jack Spielberg.  Purely infinite $C^{*}$-algebras from boundary actions of discrete groups.  J. Reine Angew. Math., 480:125–139, 1996.
  * [20] Mark V. Lawson and Alistair R. Wallis.  Levi categories and graphs of groups.  Theory Appl. Categ., 32:Paper No. 23, 780–802, 2017.
  * [21] Paul S. Muhly, Jean N. Renault, and Dana P. Williams.  Equivalence and isomorphism for groupoid $C^{\ast}$-algebras.  J. Operator Theory, 17(1):3–22, 1987.
  * [22] Rui Okayasu.  $C^{*}$-algebras associated with the fundamental groups of graphs of groups.  Math. Scand., 97(1):49–72, 2005.
  * [23] Eduard Ortega and Enrique Pardo.  The tight groupoid of the inverse semigroups of left cancellative small categories.  Trans. Amer. Math. Soc., 373(7):5199–5234, 2020.
  * [24] Alan L. T. Paterson.  Groupoids, inverse semigroups, and their operator algebras, volume 170 of Progress in Mathematics.  Birkhäuser Boston, Inc., Boston, MA, 1999.
  * [25] Alan L. T. Paterson.  Graph inverse semigroups, groupoids and their $C^{\ast}$-algebras.  J. Operator Theory, 48(3, suppl.):645–662, 2002.
  * [26] N. Christopher Phillips.  A classification theorem for nuclear purely infinite simple $C^{*}$-algebras.  Doc. Math., 5:49–114, 2000.
  * [27] Iain Raeburn.  Graph algebras, volume 103 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2005.
  * [28] Jean Renault.  A groupoid approach to $C^{\ast}$-algebras, volume 793 of Lecture Notes in Mathematics.  Springer, Berlin, 1980.
  * [29] Jean N. Renault.  $C^{\ast}$-algebras of groupoids and foliations.  In Operator algebras and applications, Part 1 (Kingston, Ont., 1980), volume 38 of Proc. Sympos. Pure Math., pages 339–350. Amer. Math. Soc., Providence, RI, 1982.
  * [30] M. Rø rdam.  Classification of nuclear, simple $C^{*}$-algebras.  In Classification of nuclear $C^{*}$-algebras. Entropy in operator algebras, volume 126 of Encyclopaedia Math. Sci., pages 1–145. Springer, Berlin, 2002.
  * [31] Jean-Pierre Serre.  Trees.  Springer-Verlag, Berlin–Heidelberg–New York, 1980.
  * [32] Jack Spielberg.  Graph-based models for Kirchberg algebras.  J. Operator Theory, 57(2):347–374, 2007.
  * [33] Jack Spielberg.  Groupoids and $C^{*}$-algebras for left cancellative small categories.  Indiana Univ. Math. J., 69(5):1579–1626, 2020.
  * [34] Jean-Louis Tu.  La conjecture de Baum-Connes pour les feuilletages moyennables.  $K$-Theory, 17(3):215–264, 1999.
  * [35] Shuang Zhang.  Certain $C^{\ast}$-algebras with real rank zero and their corona and multiplier algebras. I.  Pacific J. Math., 155(1):169–197, 1992.