# Detecting Quasiconvex Splittings in Hyperbolic Groups

Joseph Paul MacManus<EMAIL_ADDRESS>Mathematical Institute, Andrew
Wiles Building, Observatory Quarter, University of Oxford, Oxford, OX2 6GG, UK

(Date: February 5, 2023)

###### Abstract.

We present an algorithm which decides whether a given quasiconvex residually
finite subgroup $H$ of a hyperbolic group $G$ is associated with a splitting.
The methods developed also provide algorithms for computing the number of
filtered ends $\tilde{e}(G,H)$ of $H$ in $G$ under certain hypotheses, and
give a new straightforward algorithm for computing the number of ends $e(G,H)$
of the Schreier graph of $H$. Our techniques extend those of Barrett via the
use of labelled digraphs, the languages of which encode information on the
connectivity of $\partial G-\Lambda H$.

##  0\. Introduction

The study of decision problems within group theory is almost as old as the
definition of an abstract group itself, dating back to Dehn’s classical word,
conjugacy, and isomorphism problems. The classical theorems of Novikov–Boone
[31, 6] and Adian–Rabin [1, 33] state that these problems — among many, many
others — turn out to be undecidable in the class of finitely presented groups.
Thus, if we wish to search for effective solutions to group theoretical
problems, one must restrict their scope to some “nice” subclass of groups. One
such subclass is the class of hyperbolic groups. Introduced by Gromov in his
landmark essay [19], these are groups whose Cayley graphs possess geometric
properties reminiscent of negative curvature. Indeed, within this class many
problems become decidable. For example, the class of hyperbolic groups has
uniformly solvable word and conjugacy problems [9, ch. III.H], and more
recently it was shown that one can distinguish isomorphism classes of
hyperbolic groups [39, 12].

Another algorithmic problem which has received attention in recent years is
that of splitting detection. In the language of Bass–Serre theory [40], a
group $G$ splits over a subgroup $H$ if $G$ admits a minimal simplicial action
on a tree $T$ without inversions, and $H$ stabilises an edge in this action.
This problem could be traced back to the algorithm of Jaco–Oertel [22] which
decides if a given closed irreducible 3-manifold $M$ is Haken, or equivalently
if $\pi_{1}(M)$ splits over an infinite surface group. Splittings over finite
subgroups are called finite splittings, and a celebrated theorem of Stallings
[41, 42] states that a finitely generated group admits a finite splitting if
and only if it has more than one geometric end (cf. [38]). This provides a
powerful link between the coarse geometry of a group and its splitting
properties. Returning to the realm of hyperbolic groups, we have the following
unpublished result due to Gerasimov [17].

######  Theorem 0.1 (Gerasimov).

There is an algorithm which, upon input of a presentation of a hyperbolic
group $G$, will compute the number of ends of $G$.

In particular, one can effectively detect finite splittings of hyperbolic
groups. This result was later generalised by Diao–Feighn to finite graphs of
finitely generated free groups [13], by Dahmani–Groves [11] to relatively
hyperbolic groups, and by Touikan [44] to finitely presented groups with a
solvable word problem and no 2-torsion. Also worthy of mention is the
algorithm by Jaco–Letscher–Rubinstein for computing the prime decomposition of
a closed orientable 3-manifold [21], as well as the classical description of
the Grushko decomposition of a one-relator groups [28, Prop. II.5.13].

Finite splittings aside, the next logical step is to detect splittings over
two-ended (i.e. virtually cyclic) subgroups. This was achieved for
(relatively) hyperbolic groups independently by Barrett [3] and Touikan [44]
using quite distinct approaches. Note that Touikan’s algorithm here only
applies in the torsion-free case.

######  Theorem 0.2 (Barrett, Touikan).

There is an algorithm which, upon input of a presentation of a hyperbolic
group $G$, will decide if $G$ splits over a two-ended subgroup.

The algorithm of Barrett, which is of particular interest to us, makes use of
Bowditch’s deep theorem on two-ended splittings of hyperbolic groups [7]. This
theorem states that a one-ended hyperbolic group $G$ which is not virtually
Fuchsian will admit such a splitting if and only if $\partial G$ contains a
cut pair. In fact, Barrett applies this result to effectively construct
Bowditch’s canonical JSJ decomposition of a hyperbolic group.

In this paper we will aim to expand on the techniques of [3], and apply them
to larger splittings. We will restrict our attention to quasiconvex subgroups,
i.e. those subgroups whose inclusion maps are quasi-isometric embeddings,
since distorted subgroups exhibit global geometry which is harder to
understand on a local scale. If a group $G$ splits over a subgroup
commensurable with $H$, we say $H$ is associated with a splitting. Finding
sufficient conditions for a subgroup to be associated to a splitting is a
problem which has received a great amount of interest (e.g. [35, 36, 29, 37,
30]). Applying the results of [30] to the setting of quasiconvex subgroups of
hyperbolic groups, we are able to decide if a given quasiconvex subgroup is
associated to a splitting in most circumstances. There is a small technical
condition required to precisely state this result. We say that a subgroup
$H\leq G$ is lonely in $G$ if there does not exist any $H^{\prime}\leq G$
different from $H$ such that $H$ is commensurable with $H^{\prime}$. Also
recall that for a topological space $X$ we denote by $\pi_{0}(X)$ the set of
connected components of $X$. We then have the following statement.

######  Theorem 0.3 (cf. 4.6, 4.7).

There is an algorithm which takes in as input a one-ended hyperbolic group
$G$, generators of a quasiconvex subgroup $H$, such that either

  1. (1)

$\pi_{0}(\partial G-\Lambda H)$ is finite, or

  2. (2)

we know whether or not $H$ is lonely in $G$.

This algorithm will then decide if $H$ is associated with a splitting, and
will output such a splitting if one exists.

The reason for the technicality relating to (non-)lonely subgroups is that
while we may find no splitting over $H$ directly, it is possible that $G$ may
split over a finite index subgroup $K$ of $H$, where $H$ is a vertex group of
this splitting. If neither of the above two hypotheses are satisfied then it
is seemingly very difficult to detect splittings of the aforementioned form.
Further discussion of this issue is given in Section 4.3. An immediate
corollary of our result, which is nicer to state, is the following.

######  Corollary 0.4.

There is an algorithm which, upon input of a presentation of a one-ended
hyperbolic group $G$ and generators of a quasiconvex residually finite
subgroup $H$, will decide if $H$ is associated with a splitting.

It is unknown whether there exists a hyperbolic group which is not residually
finite, so this corollary applies in “most” cases, in some sense. Note also
that we could also easily drop the one-ended hypothesis by passing to a
maximal finite splitting of $G$.

In light of Stallings’ Theorem, it is a natural generalisation to define the
number of ends of a pair of groups $(G,H)$ where $H\leq G$. This definition
was first introduced by Houghton [20] and later explored in more depth in the
context of discrete groups by Scott [34]. The number of ends of the pair
$(G,H)$, denoted $e(G,H)$, can be identified with the number of geometric ends
of the quotient of the Cayley graph of $G$ by the left action of $H$. This
quotient graph is sometimes called the coset graph or Schreier graph of $H$.
It is not hard to show that if $G$ splits over $H$ then $e(G,H)\geq 2$, but
the converse does not hold. Our methods give a new proof of the following
theorem, originally due to Vonseel [45].

######  Theorem 0.5 (Vonseel, cf. 3.11).

There is an algorithm which, upon input of a one-ended hyperbolic group $G$
and generators of a quasiconvex subgroup $H$, will output $e(G,H)$.

There is a competing notion of “ends” of a pair of a groups which goes by
several names in the literature. This idea was considered independently by
Bowditch [8], Kropholler–Roller [27], and Geoghegan [16], who refer to this
invariant as coends, relative ends, and filtered ends respectively. See [37,
ch. 2] for a discussion on the equivalence of these three definitions. In this
paper we will adopt the terminology and notation of Geoghegan, and denote the
number of filtered ends of the pair $(G,H)$ by $\tilde{e}(G,H)$. This value
appears to be more resilient to calculation without extra hypotheses, but
nonetheless we have some partial results. Recall that the generalised word
problem for a finitely generated group $H$ is the problem of deciding whether,
given words $w_{0},\ldots w_{n}$ in the generators of $H$, whether
$w_{0}\in\langle w_{1},\ldots w_{n}\rangle_{H}$. We then have the following
statement.

######  Theorem 0.6 (cf. 3.12, 3.13).

There is an algorithm which takes in as input a one-ended hyperbolic group
$G$, and generators of a quasiconvex subgroup $H$. This algorithm will
terminate if and only if $\tilde{e}(G,H)$ is finite, and if it terminates will
output the value of $\tilde{e}(G,H)$.

Furthermore, if one is also given a solution to the generalised word problem
for $H$, then there is an algorithm which decides whether $\tilde{e}(G,H)\geq
N$ for any given $N\geq 0$.

We remark in Section 2.2 that $\tilde{e}(G,H)$ can be identified with the
number of components of $\partial G-\Lambda H$. Thus, the above algorithm
allows us to decide if $\partial G-\Lambda H$ is disconnected. It’s also worth
noting that if we know a priori that $\tilde{e}(G,H)$ is finite, for example
if $H$ is two-ended, then $\tilde{e}(G,H)$ is fully computable. We will also
see that the value of $\tilde{e}(G,H)$ is computable if $H$ is free. It does
not seem possible to decide in general if $\tilde{e}(G,H)=\infty$ using our
machinery for an arbitrary quasiconvex subgroup, without assuming further
hypotheses. We discuss this limitation in Section 3.4.

### Acknowledgements

My thanks go to Panos Papazoglou for suggesting this problem, and for many
helpful discussions. I’m also grateful to Sam Hughes and Ric Wade for their
detailed feedback, to Michah Sageev and Henry Wilton for fruitful exchanges,
and to Thomas Delzant for pointing me towards Vonseel’s work.

##  1\. Preliminaries

In this section we recall the basic notions and tools we require. We begin
with a look at almost invariant sets and (filtered) ends of pairs, before
briefly turning towards hyperbolic groups and their quasiconvex splittings.
Throughout this paper we will assume a working knowledge of Bass–Serre theory,
a good reference for which is [40].

###  1.1. Almost invariant subsets and (filtered) ends

We will need the idea of an almost invariant subset. A very good introduction
to the upcoming definitions can be found in [35], which features many helpful
examples. The reader should note however that this paper contains an error, a
correction of which can be found in [37].

First, some notation. In what follows, $G$ will be a finitely generated group
and $H\leq G$ a finitely generated subgroup. If $Z$ is a set upon which $H$
acts on the left, then denote by $H\backslash Z$ the quotient of $Z$ by this
action.

######  Definition 1.1.

Let $U$ and $V$ be two sets. Denote by $U\triangle V$ the symmetric difference
of $U$ and $V$, defined as

$U\triangle V:=(U-V)\cup(V-U).$

We say that two sets $U$, $V$ are almost equal if $U\triangle V$ is finite.

######  Definition 1.2.

Let $G$ act on the right on a set $Z$. We say that $U\subset Z$ is almost
invariant if for all $g\in G$, $Ug$ is almost equal to $U$.

######  Definition 1.3.

We say a subset $U\subset G$ is $H$-finite or small, if $U$ projects to a
finite subset of $H\backslash G$. If $U$ is not $H$-finite, then we say $U$ is
$H$-infinite, or large.

To ease notation, given a subset $X\subset G$ we will write $X^{\ast}:=G-X$.

######  Definition 1.4.

We say that a subset $X\subset G$ is $H$-almost invariant if it is invariant
under the left action of $H$, and $H\backslash X$ is almost invariant under
the right action of $G$ on $H\backslash G$. We say that $X$ is non-trivial if
both $X$ and $X^{\ast}$ are $H$-infinite.

Let $X$ and $Y$ be two non-trivial $H$-almost invariant subsets of $G$. We say
that $X$ and $Y$ are equivalent, if $X\triangle Y$ is $H$-finite.

######  Definition 1.5.

Let $X$ be an $H$-almost invariant subset. Given $g\in G$, we say that $gX$
crosses $X$ if all of

$gX\cap X,\ \ gX\cap X^{\ast},\ \ gX^{\ast}\cap X,\ \ gX^{\ast}\cap X^{\ast}$

are large. If there exists $g\in G$ such that $gX$ crosses $X$ then we say
that $X$ crosses itself. If $X$ does not cross itself, we say it is almost
nested. If one of the above intersections is empty, we say $X$ is nested.

It is easy to see that if $X$ and $Y$ are equivalent $H$-almost invariant
sets, then $X$ crosses itself if and only if $Y$ crosses itself.

######  Example 1.6.

Suppose a group $G$ splits as an amalgam or HNN extension over a subgroup $H$.
Then one can construct a non-trivial nested $H$-almost invariant subset
$X\subset G$ as follows. Let $T$ be the Bass-Serre tree of this splitting. We
now construct a $G$-equivariant map $\phi:G\to VT$, where $VT$ denotes the set
of vertices of $T$. Given $1\in G$, set $\phi(1)$ arbitrarily to some $w\in
VT$. For each $g\in G$, set $\phi(g)=g\phi(1)$. Since $G$ acts upon itself
freely and transitively, $\phi$ is well defined for all $g\in G$.

Given $\phi$ as above, let $e\in ET$ be the edge stabilised by $H$ with
endpoints $u,v$. Deleting the interior of $e$ separates $T$ into two
components, $T_{u}$ and $T_{v}$ containing $u$ and $v$ respectively. Set
$X=\phi^{-1}(VT_{u})$, then it is a simple exercise to check that $X$ is a
non-trivial nested $H$-almost invariant subset of $G$.

We can now state the following key theorem due to Scott–Swarup [36], which is
in some sense a converse to Example 1.6. Recall that a subgroup $H$ of $G$ is
said to be associated to a splitting if $G$ splits over a subgroup
commensurable with $H$.

######  Theorem 1.7 ([36, Thm. 2.8]).

Let $G$ be a finitely generated group, $H$ a finitely generated subgroup, and
$X$ an $H$-almost invariant subset of $G$. Suppose that $X$ is almost nested,
then $H$ is associated to a splitting.

There is a generalisation of the above, which will be important to us.
Firstly, we must further loosen our requirements for nesting. Denote by
$\operatorname{Comm}_{G}(H)$ the commensurator of $H$ in $G$. That is,

$\operatorname{Comm}_{G}(H)=\\{g\in G:|H:H\cap H^{g}|<\infty,\ |H^{g}:H\cap
H^{g}|<\infty\\}.$

Then we have the following definition.

######  Definition 1.8.

Let $X\subset G$ be $H$-almost invariant. We say that $X$ is semi-nested if
$\\{g\in G:\textrm{$gX$ crosses $X$}\\}$ is contained in
$\operatorname{Comm}_{G}(H)$.

Informally, we relax our definition to allow crossings of $X$ by $gX$ on the
condition that $gH$ is “very close” to $H$. We then have the following useful
result, due to Niblo–Sageev–Scott–Swarup [30], which says that this relaxation
still produces splittings.

######  Theorem 1.9 ([30, Thm. 4.2]).

Let $G$ be a finitely generated group and $H$ a finitely generated subgroup.
Suppose that there exists a non-trivial $H$-almost invariant subset $X\subset
G$ which is semi-nested. Then $G$ splits over a subgroup commensurable with
$H$.

This idea of “crossings” of almost invariant sets is much more rich than what
is presented here, and pertains to the idea of “compatible” splittings. The
interested reader should consult [36], which features many helpful examples,
as a starting point.

There is a natural way to “count” these $H$-almost invariant subsets, which
provides a useful integer invariant of the subgroup. Let
$\mathcal{P}(H\backslash G)$ denote the power set of $H\backslash G$. Let
$\mathcal{F}(H\backslash G)$, denote the set of finite subsets. Under the
operation of symmetric difference $\triangle$, $\mathcal{P}(H\backslash G)$
can be seen as a $\mathbb{Z}_{2}$-vector space, and $\mathcal{F}(H\backslash
G)$ a subspace. The quotient space $\mathcal{E}(H\backslash
G):=\mathcal{P}(H\backslash G)/\mathcal{F}(H\backslash G)$ can be identified
naturally with the set of $H$-almost invariant sets of $G$, modulo
equivalence.

######  Definition 1.10.

Let $G$ be a group and $H\leq G$. We define the number of ends of the pair
$(G,H)$ as the rank of $\mathcal{E}(H\backslash G)$ as a
$\mathbb{Z}_{2}$-vector space. Denote by $e(G)=e(G,\\{1\\})$, and say that
$e(G)$ is the number of ends of $G$.

There is also the following characterisation of ends of pairs, which will be
helpful later. This result motivates the earlier description that $e(G,H)$
“counts” $H$-almost invariant subsets.

######  Proposition 1.11 ([34, Lem. 1.6]).

Let $G$ be a group, $H$ a subgroup, and $n\geq 0$. Then $e(G,H)\geq n$ if and
only if there exists a collection of $n$ pairwise disjoint $H$-almost
invariant subsets of $G$.

There is a more geometric intuition for the above, which can be seen in the
coset graph.

######  Proposition 1.12 ([34, Lem. 1.1]).

Let $\Gamma$ be a Cayley graph of $G$, and $H\subset G$. Then $e(G,H)$ is
equal to the number of ends of the coset graph $H\backslash\Gamma$.

From the above it is then clear that this definition generalises the standard
geometric notion of ends. This also provides a helpful way of seeing that the
number of geometric ends of a finitely generated group is indeed independent
of the choice of generating set.

There is another competing, but equally interesting notion of ends of a pair
of groups, namely the idea of filtered ends. This was considered independently
by Geoghegan [16, Ch. 14], Kropholler–Roller [27], and Bowditch [8]. We now
summarise the definition as it appears in [16]. We first need the following
technical preliminaries relating to filtrations.

Let $Y$ be a connected, locally finite cell complex. A filtration
$\mathcal{K}=\\{K_{i}\\}$ of $Y$ is an ascending sequence of subcomplexes
$K_{1}\subset K_{2}\subset\ldots\subset Y$ such that $\bigcup_{i}K_{i}=Y$. We
say that this filtration is finite if each $K_{i}$ is finite. We call the pair
$(Y,\mathcal{K})$ a filtered complex, and a map
$f:(Y,\mathcal{K})\to(X,\mathcal{L})$ between filtered complexes is called a
filtered map if the following four conditions hold:

  1. (1)

$\forall i$, $\exists j$ such that $f(K_{j})\subset L_{i}$,

  2. (2)

$\forall i$, $\exists j$ such that $f(K_{i})\subset L_{j}$,

  3. (3)

$\forall i$, $\exists j$ such that $f(Y-K_{j})\subset X-L_{i}$,

  4. (4)

$\forall i$, $\exists j$ such that $f(Y-K_{i})\subset X-L_{j}$.

We say that a homotopy $H_{t}$ between two filtered maps is a filtered
homotopy if $H_{t}$ is a filtered map for each $t$. Fix a basepoint $b\in Y$,
then a filtered ray based at b is a map $\gamma:[0,\infty)\to Y$ with
$\gamma(0)=b$, which is filtered with respect to the filtration
$\\{[0,i]:i\in\mathbb{N}\\}$ of $[0,\infty)$. We say that two filtered rays
based at $b$ are equivalent if there is a filtered homotopy between them
fixing $b$. A filtered end of $(Y,\mathcal{K})$ is an equivalence class of
filtered rays based at $b$. It is easy to see that the choice of $b$ does not
affect the number of filtered ends.

Let $G$ be a finitely generated group and $H$ a finitely generated subgroup.
Let $X_{G}$ be a Cayley complex for $G$, and let $p:X_{G}\to H\backslash
X_{G}$ denote quotient map. Choose a finite filtration
$\mathcal{K}=\\{K_{i}\\}$ of $H\backslash X_{G}$, and lift this to a
filtration $\mathcal{L}=\\{L_{i}\\}$ of $X_{G}$, where $L_{i}=p^{-1}(K_{i})$.

######  Definition 1.13.

The number of filtered ends of the pair $(G,H)$, denoted by $\tilde{e}(G,H)$,
is defined as the number of filtered ends of the filtered complex
$(X_{G},\mathcal{L})$.

Though it seems as though this definition depends on a choice of the
filtration $\mathcal{K}$, it is a helpful fact that it does not — see [16, Ch.
14] for details. While this definition is a little technical, we will see
later on that, in the case of quasiconvex subgroups of hyperbolic groups,
these filtered ends can be clarified by looking at the Gromov boundary. We
conclude this section with two results relating ends of pairs and filtered
ends of pairs.

######  Proposition 1.14 ([16, Prop. 14.5.3]).

Let $G$ be a group and $H$ be a finitely generated subgroup. Then
$e(G,H)\leq\tilde{e}(G,H)$.

Equality is certainly possible, but not true in general. A simple
counterexample is presented in [37, p. 32], which involves a one-sided
essential simple closed curve on a non-orientable surface. We finally conclude
with the following, which demonstrates the common thread between the two
competing definitions.

######  Proposition 1.15 ([37, Lem. 2.40]).

Let $G$ be a group and $H$ be a finitely generated subgroup of infinite index.
Then $\tilde{e}(G,H)>1$ if and only if there is some subgroup $K\leq H$ such
that $e(G,K)>1$.

###  1.2. Hyperbolic groups

Let $\delta\geq 0$, and recall that a geodesic metric space $X$ is
$\delta$-hyperbolic if every geodesic triangle in $X$ is $\delta$-slim. That
is, if every side of a geodesic triangle is contained in the
$\delta$-neighbourhood of the other two sides. We say that a finitely
generated group $G$ is hyperbolic if some (equivalently, any) Cayley graph of
$G$ is $\delta$-hyperbolic for some $\delta\geq 0$.

For the remainder of this section, let $\Gamma$ be a $\delta$-hyperbolic
Cayley graph of the finitely generated group $G$. We recall some basic facts
about hyperbolic groups which will be important later. The first is often
known as the visibility property.

######  Lemma 1.16.

For every $g,g^{\prime}\in\Gamma$, there is a geodesic ray $\gamma$ based at
$g^{\prime}$ which passes within $C=3\delta$ of $g$.

Viewing geodesic rays as “lines of sight” from the basepoint, we can imagine
this theorem as saying that every point in $\Gamma$ is (nearly) visible from
every other point.

The second result we need is the following, commonly known as the Morse Lemma.
This fact will play a fundamental role in much of the machinery of this paper.
Informally, it says that quasi-geodesics must stay uniformly close to
geodesics with the same endpoints.

######  Lemma 1.17.

Let $\lambda\geq 1$, $\varepsilon\geq 0$. Then there is some computable
$D=D(\delta,\lambda,\varepsilon)\geq 0$ such that
$(\lambda,\varepsilon)$-quasi-geodesics in $\Gamma$ are contained within the
$D$-neighbourhood of any geodesic with the same endpoints.

We now briefly introduce the Gromov boundary of a hyperbolic group. Consider
the set $\mathcal{R}=\mathcal{R}(\Gamma,1)$ of geodesic rays in $\Gamma$ based
at $1$. Throughout this paper we may abuse notation and identify a ray or path
with its image in $\Gamma$. We say that two such rays
$\gamma,\gamma^{\prime}\in\mathcal{R}$ are equivalent, and write
$\gamma\sim\gamma^{\prime}$, if their Hausdorff distance as subsets of
$\Gamma$ is finite. Let $\partial\Gamma=\mathcal{R}/\sim$, and call this set
the Gromov boundary of $\Gamma$. Given $\gamma\in\mathcal{R}$, denote by
$\gamma(\infty)$ its equivalence class in $\partial\Gamma$. We topologise
$\partial\Gamma$ as follows. Given $x,y,z\in\Gamma$, let

$(x\cdot y)_{z}=\tfrac{1}{2}(d(x,z)+d(y,z)-d(x,z))$

denote the Gromov product. For $p\in\partial\Gamma$, $r\geq 0$, let

$V(p,r)=\\{q\in\partial\Gamma:\textrm{$\exists\gamma\in p,\gamma^{\prime}\in
q$ such that $\liminf_{t\to\infty}(\gamma(t)\cdot\gamma^{\prime}(t))_{1}\geq
r$}\\}.$

Given $p\in\partial\Gamma$, we set $\\{V(p,r):r\geq 0\\}$ as a basis of
neighbourhoods about $p$. This topologises $\partial\Gamma$. Informally, two
rays are “close” in $\partial\Gamma$ if they fellow-travel for a long time. It
can be seen that, up to homeomorphism, $\partial\Gamma$ does not depend on a
choice of basepoint, or even on the choice of Cayley graph $\Gamma$. Thus, we
may abuse notation and write $\partial G$.

One can also define the sequential boundary of $\Gamma$. Fix a basepoint
$z\in\Gamma$. We say that a sequence $(p_{n})\in\Gamma^{\mathbb{N}}$ tends to
infinity if $\liminf_{n,m\to\infty}(p_{n}\cdot p_{m})_{z}=\infty$. We say two
such sequences $(p_{n})$, $(q_{m})$ are equivalent if
$\liminf_{n,m\to\infty}(p_{n}\cdot q_{m})_{z}=\infty$. One can then define
$\partial\Gamma$ as the set of equivalence classes of sequences which tend to
infinity, and topologise it in a similar way. Given a sequence $(p_{n})$ which
tends to infinity, denote by $\lim_{n\to\infty}p_{n}$ its equivalence class in
$\partial\Gamma$. This definition is equivalent to the previous [24, Prop.
2.14]. Other equivalent variations of this construction are possible, and can
be found in [24].

We can extend the definition of the Gromov product to $\partial\Gamma$, by
defining

$(p\cdot q)_{z}=\sup\left\\{\liminf_{n,m\to\infty}(p_{n}\cdot
q_{m})_{z}:(p_{n})\in p,\ (q_{m})\in q\right\\},$

for $p,q\in\partial\Gamma$, $z\in\Gamma$. Using this extension there is a
natural way to put a metric on $\partial G$, though the metric is not
canonical, as it depends on some chosen parameters. In particular, a visual
metric on $\partial\Gamma$ with parameter $a$ and multiplicative constants
$k_{1}$, $k_{2}$ is a metric $\rho$ satisfying

$k_{1}a^{-(p\cdot q)_{1}}\leq\rho(p,q)\leq k_{2}a^{-(p\cdot q)_{1}}$

for every $p,q\in\partial\Gamma$. See [9, p. 434] for how to construct such a
metric given suitable parameters.

Note that the number of connected components of the boundary can be identified
with the number of ends $e(G)$ of $G$. In particular, the boundary
$\partial\Gamma$ is connected if and only if $G$ is one-ended. Thus by
Stallings’ Theorem for ends of groups (see e.g. [38]) we have that $\partial
G$ is connected if and only if $G$ admits no finite splitting.

We conclude this section with an important and deep result due to
Bestvina–Mess [5], Bowditch [7], and Swarup [43]. This result essentially
quantifies the connectedness of the boundary and relates it to the local
geometry of the Cayley graph. Let $C=3\delta$ as in Lemma 1.16, and let
$M=6C+2\delta+3$. We then have the following.

######  Definition 1.18.

We say that $\Gamma$ satisfies $\ddagger_{n}$ for $n\geq 1$ if for every
$R\geq 0$ and every $x,y\in\Gamma$ such that $d(x,1)=d(y,1)=R$ and $d(x,y)\leq
M$ we have that there is a path through $\Gamma-B_{1}(R)$ connecting $x$ to
$y$, of length at most $n$.

######  Theorem 1.19 ([5, Props. 3.1, 3.2]).

Let $G$ be a hyperbolic group, with $\delta$-hyperbolic Cayley graph $\Gamma$.
Then $\partial G$ is connected if and only if there exists $n\geq 1$ such that
$\Gamma$ satisfies $\ddagger_{n}$.

Note that through the algorithm presented in [11], one can decide if a given
hyperbolic group $G$ is one-ended, and if so this algorithm will output $n$
such that $\ddagger_{n}$ holds in the Cayley graph associated to the given
generators of $G$. Their algorithm also applies to relatively hyperbolic
groups, but we will not use that here.

###  1.3. Quasiconvex subgroups and splittings

Recall that a subset of a geodesic space is termed convex if it contains any
geodesic between any two of its points. This notion is too precise for the
setting of groups, so we must “quasify” it.

Let $Q\geq 0$, and let $G$ be a hyperbolic group with Cayley graph $\Gamma$.
Then a subgroup $H\leq G$ is called $Q$-quasiconvex if for every
$h,h^{\prime}\in H$, any geodesic path between $h,h^{\prime}$ in $\Gamma$ is
contained in the closed $Q$-neighbourhood of $H$. The quasiconvexity of $H$
does not depend on the choice of Cayley graph for $G$, given that $G$ is
hyperbolic, and quasiconvex subgroups of hyperbolic groups are also
hyperbolic. The following characterisation of quasiconvexity will be
important.

######  Lemma 1.20.

Let $G$ be a hyperbolic group, $H\leq G$ a finitely generated subgroup, and
fix word metrics on these groups. Then $H$ is quasiconvex if and only if the
inclusion map $H\hookrightarrow G$ is a $(\lambda,\varepsilon)$-quasi-
isometric embedding for some $\lambda\geq 1$, $\varepsilon\geq 0$.

Moreover, given a presentation of $G$ and generators of $H$, if $H$ is
quasiconvex then these constants can be found algorithmically.

The above follows immediately from Kapovich’s algorithm [23] for computing the
quasiconvexity constant $Q$, together with [9, ch. III.$\Gamma$, Lem. 3.5].

Quasiconvex subgroups interact with the Gromov boundary in a very controlled
way. Informally, if $H\leq G$ is a quasiconvex subgroup, then this induces an
inclusion $\partial H\hookrightarrow\partial G$. More precisely, we need the
idea of “limit sets” in the boundary.

######  Definition 1.21.

Let $G$ be a hyperbolic group with Cayley graph $\Gamma$, and $H$ some
subgroup of $G$. Then define the limit set of $H$ as

$\Lambda H=\\{p\in\partial\Gamma:\textrm{$p=\lim_{n\to\infty}h_{n}$ for some
$h_{n}\in H$}\\}.$

It is a standard fact that if $H$ is quasiconvex then $\Lambda H\cong\partial
H$, and $\Lambda H$ is a closed $H$-invariant subset of $\partial G$ (see e.g.
[24]). Combining Lemmas 1.16 and 1.17 we immediately arrive at the following,
which will play a big role in the next section.

######  Lemma 1.22.

Let $\Gamma$ be a $\delta$-hyperbolic Cayley graph of a hyperbolic group $G$,
and let $H$ be a $Q$-quasiconvex subgroup. There exists some computable
constant $\eta=\eta(\delta,Q)>0$ with the following property. If $\gamma$ is a
geodesic ray in $\Gamma$ based at 1 such that $\gamma(\infty)\in\Lambda H$,
then $\gamma$ is contained in the closed $\eta$-neighbourhood of $H$.

Another important fact about quasiconvex subgroups of hyperbolic groups is
that they are “almost” self-commensurating. More formally we have the
following classical result due to Arzhantseva [2] and Kapovich–Short [26].

######  Theorem 1.23 ([2, Thm. 2]).

Let $G$ be a hyperbolic group and $H$ a quasiconvex subgroup. Then $H$ has
finite index in $\operatorname{Comm}_{G}(H)$.

######  Corollary 1.24.

Let $H$ be a quasiconvex subgroup of a hyperbolic group $G$. Then the
commensurator $\operatorname{Comm}_{G}(H)$ is the unique maximal finite index
overgroup of $H$.

###### Proof.

Let $K\leq G$ be some finite index overgroup of $H$, and let $k\in K$. Clearly
$H^{k}\subset K$, so $H^{k}\cap H\leq H\cap K=H$ and $H^{k}$ has finite index
in $K$. Then

$|K:H\cap H^{k}|=|K:H|\cdot|H:H\cap H^{k}|,$

so $|H:H\cap H^{k}|<\infty$. Similarly, $|H^{k}:H\cap H^{k}|<\infty$, and so
$k\in\operatorname{Comm}_{G}(H)$. ∎

We conclude this section with a description of the vertex groups of a
splitting in which the edge groups are quasiconvex. We say that a subgroup is
full if it does not have any finite index overgroups.

######  Proposition 1.25 ([7, Prop. 1.2]).

Let $G$ be a one-ended hyperbolic group, and suppose that $G$ splits over a
quasiconvex subgroup as an amalgam or an HNN extension. Then the vertex groups
of this splitting are full quasiconvex.

###### Proof.

The fact that they are quasiconvex is proven in [7], so we will just show here
that they are necessarily also full.

Let $G$ act simplicially, minimally, and without inversions on a tree $T$ with
a single edge orbit, such that the edge stabilisers are quasiconvex. Let $v$
be a vertex of $T$, and let $G_{v}$ denote the stabiliser of $v$. Suppose that
$G_{v}$ is not full, so there is finite index overgroup $K>G_{v}$. Then the
$K$-orbit of $v$ is finite, so there is some finite subtree $\Sigma\subset T$
stabilised by $K$. Let $u$ be the geometric center of $\Sigma$. If $u$ is a
midpoint of an edge $e$, then it must be the case that the action of $K$
inverts this edge. We assumed that $G$ acts without inversions so this cannot
happen, and so $u$ is a vertex of $T$. Since $u$ is distinct from $v$ (else
$K=G_{v}$), we see that there is a vertex $w$ adjacent to $v$ such that

$G_{v}\leq G_{w}\leq K.$

In particular, $G_{v}$ has finite index in $G_{w}$.

Let $e$ be the edge connecting $v$ to $w$. We split into two cases. Firstly,
suppose that this splitting is an amalgam. Then $G_{e}=G_{v}\cap G_{w}=G_{v}$,
but then the given splitting is of the form $G=G_{w}\ast_{G_{v}}G_{v}$, and so
$G_{w}=G$ and $G$ fixes a point on $T$.

Suppose instead that $G$ acts on $T$ with a single vertex orbit, i.e. that
this splitting is an HNN extension. Then there is some $g\in G$ such that
$G_{w}=G_{v}^{g}$. Suppose that $G_{w}>G_{v}$, then we find the following
sequence

$G_{v}<G_{v}^{g}<G_{v}^{g^{2}}<G_{v}^{g^{3}}<G_{v}^{g^{4}}<\ldots,$

where each has finite index in the last. But then $G_{v}$ has no maximal
finite index overgroup, which contradicts Corollary 1.24 since $G_{v}$ is
quasiconvex. Thus $G_{w}=G_{v}=G_{e}$. In particular, by translating this
picture around we see that the stabiliser of every edge in $T$ is equal to the
stabiliser of either of its endpoints. Since $T$ is connected, it follows that
$G_{v}$ actually fixes $T$ pointwise and is in fact the kernel of the action
of $G$ on $T$. Thus, $G_{v}$ is a normal subgroup of $G$. Since $G_{v}$ is
quasiconvex, this can only happen if $G_{v}$ is finite or has finite index in
$G$ [26]. By assumption, $G$ is one-ended and so $G_{v}$ has finite index in
$G$. But then $G$ must act on $T$ with a global fixed point. With this
contradiction, we conclude that $G_{v}$ must be full. ∎

The above allows us to prove the following dichotomy, which is helpful when
detecting splittings. Recall that a subgroup $H$ is said to be lonely if there
does not exist another subgroup $H^{\prime}$ distinct from $H$ such that $H$
is commensurable with $H^{\prime}$.

######  Proposition 1.26.

Let $G$ be a hyperbolic group and $H$ a quasiconvex subgroup such that either

  1. (1)

$H\neq\operatorname{Comm}_{G}(H)$, or

  2. (2)

$H$ is lonely.

Then $H$ is associated with a splitting if and only if there is some semi-
nested $H$-almost invariant set $X$.

###### Proof.

Applying Theorem 1.9, it is clear that if we have a semi-nested $H$-almost
invariant set then $H$ is associated to a splitting.

Conversely, suppose that $G$ splits over a subgroup $H^{\prime}$ commensurable
with $H$. If $H$ is lonely then the result is clear as we necessarily split
over $H$, thus there is a nested $H$-almost invariant set as in Example 1.6.
So assume instead that $H\neq\operatorname{Comm}_{G}(H)$. We now split into
two cases.

Firstly, suppose that $H^{\prime}$ has infinite index in the vertex group(s)
of its splitting. We have by Theorem 1.23 that $\operatorname{Comm}_{G}(H)$ is
commensurable with $H^{\prime}$, so it will be strictly contained in a vertex
group of this splitting, up to conjugacy. We can then transform our splitting
over $H$ easily into a splitting over $C:=\operatorname{Comm}_{G}(H)$ via e.g.

$G=A\ast_{H^{\prime}}B=A\ast_{H^{\prime}}(C\ast_{C}B)=(A\ast_{H^{\prime}}C)\ast_{C}B.$

The HNN case is similar. Since we have a non-trivial splitting over $C$, there
is an almost nested $C$-almost invariant set by Example 1.6. Clearly such a
set is also $H$-almost invariant, and so we are done.

Suppose instead that $H^{\prime}$ has finite index in one of the vertex
stabilisers. By Proposition 1.25 we know that the vertex groups of the
splitting over $H^{\prime}$ are full, so by Corollary 1.24 we deduce that one
vertex group of the splitting over $H^{\prime}$ is precisely
$\operatorname{Comm}_{G}(H)$. Let $T$ be the Bass-Serre tree of this
splitting. Then $H$ fixes a vertex of $T$, namely the vertex stabilised by
$\operatorname{Comm}_{G}(H)$. Let $e\in ET$ be the edge stabilised by
$H^{\prime}$ with endpoints $v,u\in VT$, and suppose without loss of
generality that $H$ fixes $v$. Then the $H$-orbit of $e$ is a finite
collection of edges abutting $v$. Since $H\neq\operatorname{Comm}_{G}(H)$
there are multiple $H$-orbits of edges abutting $v$. Let $F=\\{he:h\in H\\}$.
Then deleting the interior of the edges in $F$ separates $T$ into a disjoint
collection of subtrees. Let $T_{v}$ be the subtree which contains $v$, then
set $X=\phi^{-1}(VT_{v})$, where $\phi:G\to T$ is the map constructed in
Example 1.6. It is clear that $X$ is a non-trivial $H$-almost invariant set,
and

$\\{g\in G:\textrm{$gX$ crosses $X$}\\}\subset
G_{v}=\operatorname{Comm}_{G}(H),$

where $G_{v}\leq G$ is the stabiliser of $v$. Thus $X$ is semi-nested by
definition. ∎

##  2\. Limit Set Complements

The key aim of this section is to understand the connectivity of $\partial
G-\Lambda H$ via local geometry. In particular we will generalise a toolbox
introduced by Barrett in [3].

###  2.1. Annular neighbourhoods

The Gromov boundary encodes a wide variety of data about our group, but we
cannot access it directly. Thus, we must characterise the presence of the
topological features we care about via some kind of equivalent local geometric
feature in the Cayley graph.

For what follows we will need to fix some notation. Throughout this section
$G$ will be a one-ended hyperbolic group with $\delta$-hyperbolic Cayley graph
$\Gamma$, and $H$ will be a $Q$-quasiconvex subgroup with a fixed finite
generating set $Y$. Note that given a presentation of a hyperbolic group, one
can effectively compute the hyperbolicity constant $\delta$ of the
corresponding Cayley graph via [32]. Given $x,y\in\Gamma$, we may denote by
$[x,y]$ a choice of geodesic path between $x$ and $y$. Let $C=3\delta$ as in
Lemma 1.16, $D=D(1,0)$ as in Lemma 1.17. Fix a visual metric $\rho$ on
$\partial G$, with parameter $a$ and multiplicative constants $k_{1}$,
$k_{2}$. We will make use of some methods from [5], so recall Theorem 1.19 and
fix $n\geq 0$ such that $\ddagger_{n}$ holds in $\Gamma$. Finally, choose
$\lambda\geq 1$, $\varepsilon\geq 0$ such that the inclusion map
$H\hookrightarrow G$ is a $(\lambda,\varepsilon)$-quasi-isometric embedding as
in Lemma 1.20, and $\eta=\eta(\delta,Q)$ as in Lemma 1.22.

######  Lemma 2.1.

Let $p\in\partial G-\Lambda H$. Then for $\gamma\in p$, we have that

$\lim_{t\to\infty}d(\gamma(t),H)=\infty.$

###### Proof.

Suppose not, so $\liminf_{t\to\infty}d(\gamma(t),H)<\infty$. Then there exists
a sequence $t_{i}\to\infty$, and some $A\geq 0$ such that
$d_{G}(\gamma(t_{i}),H)<A$ for all $i$. Let $h_{i}\in H$ be such that
$d_{G}(\gamma(t_{i}),h_{i})<A$.

Recall that we fixed a generating set $Y$ of $H$, and thus a word metric on
$H$. Let $\delta_{H}$ be such that $H$ is $\delta_{H}$-hyperbolic. Choose
geodesic rays $\mu_{i}$ in $H$ based at $1$ such that $\mu_{i}$ passes within
$3\delta_{H}$ of $h_{i}$. Let $\iota:H\hookrightarrow G$ be the inclusion map,
which is a $(\lambda,\varepsilon)$-quasi-isometric embedding. Then
$\iota(\mu_{i})$ is a $(\lambda,\varepsilon)$-quasi-geodesic ray at 1. Let
$\nu_{i}$ be a geodesic ray in $\Gamma$ with the same endpoints as
$\iota(\mu_{i})$. Then

$d(\nu_{i},\gamma(t_{i}))<A+3\lambda\delta_{H}+\varepsilon+D(\lambda,\varepsilon),$

for every $i$. It is now routine to see that $\nu_{i}(\infty)\to p$ in
$\partial G$. But $\Lambda H$ is a closed subset of $\partial G$, so
$p\in\Lambda H$. This is a contradiction, so the lemma follows. ∎

We now introduce some notation borrowed from [3]. Let $0\leq r\leq K\leq R$ be
constants, where $R$ is possibly infinite. Denote by $N_{R}(H)$ the closed
$R$-neighbourhood of $H$ in $\Gamma$, and by $N_{r,R}(H)$ the annular region

$N_{r,R}(H)=\\{x\in\Gamma:r\leq d(x,H)\leq R\\}.$

Let $C_{K}(H)=\\{x\in\Gamma:d(x,H)=K\\}$, and finally let $A_{r,R,K}(H)$ be
the union of the components of $N_{r,R}(H)$ which intersect $C_{K}(H)$. The
geometric significance of $A_{r,R,K}(H)$ is that we take an annular region
about $H$, but discard the components which are “too close” to $H$. This is
illustrated in Figure 1. Following Barrett, we will demonstrate a
correspondence between the components of $\partial G-\Lambda H$ and the
components of $A_{r,R,K}(H)$, provided $r$, $R$, and $K$ are sufficiently
large.

${\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}H}$$C_{K}(H)$$N_{r,R}(H)$$\Gamma$$A_{r,R,K}(H)$
Figure 1. The region $A_{r,R,K}(H)$ surrounding $H$. In this cartoon $H$ is
depicted as a line for illustrative purposes.

Next, we introduce “shadows”. Given a component $U$ of $A_{r,\infty,K}(H)$,
define its shadow $\mathcal{S}U$ as the set of points $p\in\partial G$ such
that for any ray $\gamma\in p$ based at $1$, we have that $\gamma(t)$ is in
$U$ for all sufficiently large $t$. We also extend the definition of a shadow
to a union of components $V=\bigcup_{i}U_{i}$ by defining
$\mathcal{S}V=\bigcup_{i}\mathcal{S}U_{i}$.

We now prove five lemmas, generalised from [3]. Originally, these results
related to bi-infinite geodesics, but careful inspection of their proofs
reveals that we only really need the fact that a geodesic path in a hyperbolic
space is a quasiconvex set. This allows us to generalise some of the machinery
in this paper from geodesics to quasiconvex subgroups. Apart from some small
changes, the following proofs are practically reproduced verbatim from [3].

######  Lemma 2.2 ([3, Lem. 1.17]).

For $r>\eta$, $K\geq r$, we have that

$\partial G-\Lambda H=\bigcup_{U}\mathcal{S}U,$

where $U$ ranges over the connected components of $A_{r,\infty,K}(H)$.
Moreover, $\mathcal{S}U\cap\mathcal{S}V=\emptyset$ for distinct components
$U$, $V$.

###### Proof.

It is clear from the definition of $\mathcal{S}U$ that distinct components
have disjoint shadows. Since $r>\eta$, we have by Lemma 1.22 that
$\mathcal{S}U$ and $\Lambda H$ are disjoint. Now let $p\in\partial G-\Lambda
H$. We need to check that $p\in\mathcal{S}U$ for some component $U$ of
$A_{r,\infty,K}(H)$. Let $\gamma\in p$, then there is some $t_{0}$ such that
for $t\geq t_{0}$ we have that $d(\gamma(t),H)\geq r+D$.

Let $U$ be the component of $A_{r,\infty,K}(H)$ containing $\gamma(t)$ for
$t\geq t_{0}$. We claim that if $\gamma^{\prime}$ is another ray in $p$, then,
$\gamma^{\prime}(t^{\prime})$ lies in $U$ for sufficiently large $t^{\prime}$.
We know that the Hausdorff distance between $\gamma$ and $\gamma^{\prime}$ is
at most $D$. In particular, for every $t^{\prime}$ there is some $t$ such that
$d(\gamma(t),\gamma^{\prime}(t^{\prime}))\leq D$, and by the triangle
inequality $t$ and $t^{\prime}$ satisfy $|t-t^{\prime}|\leq D$. Then if
$t^{\prime}\geq t_{0}+D$, we must have that $t\geq t_{0}$, and so the segment
between $\gamma^{\prime}(t^{\prime})$ and $\gamma(t)$ lies in
$A_{r,\infty,K}(H)$, and thus $\gamma^{\prime}(t^{\prime})\in U$. It follows
$p\in\mathcal{S}U$. ∎

######  Lemma 2.3 ([3, Lem. 1.18]).

Let $r>\eta$ and $K\geq r+Q+\delta+C$. Then for every component $U$ of
$A_{r,\infty,K}(H)$, we have that $\mathcal{S}U$ is non-empty.

###### Proof.

Let $x\in C_{K}(H)\cap U$, and using Lemma 1.16 choose a geodesic ray $\gamma$
based at 1 which passes within $C$ of $x$, say $d(\gamma(t),x)\leq C$. Since
$K>r+C$, we have that $\gamma(t)\in U$. In particular,

$d(\gamma(t),H)>r+Q+\delta.$

Suppose now that for some $t^{\prime}\geq t$, we have that
$d(\gamma(t^{\prime}),H)\leq r$. Let $y\in H$ be a nearest point projection of
$\gamma(t^{\prime})$. Then consider the geodesic triangle
$[1,y,\gamma(t^{\prime})]$, where the segment $[1,\gamma(t^{\prime})]$ is
precisely an initial segment of $\gamma$. Then $\gamma(t)$ is either
$\delta$-close to $[y,\gamma(t^{\prime})]$ or $[1,y]$. In any case,

$d(\gamma(t),H)\leq r+Q+\delta,$

which is a contradiction. Thus $\gamma(t^{\prime})\in U$ for every
$t^{\prime}\geq t$. It now follows by an argument similar to that in the proof
of Lemma 2.2 that $\gamma(\infty)\in\mathcal{S}U$. ∎

######  Lemma 2.4 ([3, Lem. 1.19]).

Let $r>\eta$, $K>r$, then for every component $U$ of $A_{r,\infty,K}(H)$, we
have that $\mathcal{S}U$ is open and closed in $\partial G-\Lambda H$.

###### Proof.

Let $\gamma\in p\in\mathcal{S}U$, and for $t\geq 0$ let

$V_{t}(\gamma)=\\{\beta(\infty):\text{$\beta$ is a ray based at 1},\
d(\gamma(t),\beta(t))<2\delta+1\\}.$

As $t$ varies, this forms a basis of neighbourhoods about $p$. By Lemma 2.1
there exists a $t_{0}$ such that for all $t\geq t_{0}$, we have that

$d(\gamma(t),H)>r+Q+7\delta+1.$

We claim that $V_{t_{0}}(\gamma)\subseteq\mathcal{S}U$, which implies that
$\mathcal{S}U$ is open.

Let $\beta\in q\in V_{t_{0}}(\gamma)$, so by definition we have
$d(\beta(t_{0}),\gamma(t_{0}))<2\delta+1$. Then consider another ray
$\beta^{\prime}\in q$ also, so
$d(\beta(t_{0}),\beta^{\prime}(t_{0}))<4\delta$. We need to show that
$\beta^{\prime}(t)\in U$ for all $t\geq t_{0}$. Suppose this is not the case.
We have that $\beta^{\prime}(t_{0})$ is in $U$, so for this not to hold we
must have that $\beta^{\prime}$ “leaves” $U$ at some point. Thus for some
$t^{\prime}\geq t_{0}$, we have that $d(\beta^{\prime}(t^{\prime}),H)\leq r$,
say for some $y\in H$ we have $d(\beta^{\prime}(t^{\prime}),y)\leq r$.

$\gamma$$\beta$$\beta^{\prime}$$t^{\prime}$$y$$t_{0}$$t_{0}$$t_{0}$$\leq
2\delta+1$$\leq 4\delta$$H$$\leq\ r$$1$$\leq\delta?$$\leq\delta?$$\leq Q$
Figure 2. Bounding the distance between $\gamma(t_{0})$ and $H$.

Consider a geodesic path $[1,y]$. Since $H$ is $Q$-quasiconvex this path is
contained in the $Q$-neighbourhood of $H$. Combine this with the fact that the
triangle $[1,\beta^{\prime}(t^{\prime}),y]$ is $\delta$-slim, then inspection
of Figure 2 reveals that

$d(\gamma(t_{0}),H)\leq r+Q+7\delta+1.$

This is a contradiction, so $\mathcal{S}U$ is open.

To conclude, note that the shadows $\mathcal{S}U$ form a disjoint open cover
of $\partial G-\Lambda H$. It follows that that they must also be closed. ∎

For the next lemma, recall that $a_{1}$, $a_{2}$ and $k$ denote the parameters
of our fixed visual metric on $\partial G$. Also recall that $n$ has been
fixed so that $\ddagger_{n}$ holds in $\Gamma$.

######  Lemma 2.5 ([3, Lem. 1.20]).

Suppose that $r$ satisfies

$r>2\log_{a}\left(\frac{k_{2}(n-1)}{k_{1}(1-a^{-1})}\right)+M+8\delta+\eta+C,$

and let $K>r$. Then for every component $U$ of $A_{r,\infty,K}(H)$,
$\mathcal{S}U$ is contained within exactly one connected component of
$\partial G-\Lambda H$. Moreover, every component of $\partial G-\Lambda H$ is
path connected.

###### Proof.

Let $p,q\in\mathcal{S}U$, and let $\alpha_{1}\in p$, $\alpha_{2}\in q$. Then
there is some $t_{1}$, $t_{2}$ such that
$\alpha_{1}(t_{1}),\alpha_{2}(t_{2})\in U$. Let $\phi:[0,\ell]\to U$ be a path
connecting $\alpha_{1}(t_{1})$ to $\alpha_{2}(t_{2})$, parameterised by arc
length.

We follow the methodology of Bestvina–Mess [5] and “project” this path to the
boundary. For every $i\in\mathbb{Z}\cap[0,\ell]$, let $\beta_{i}$ be a ray
from $1$, passing through a point $\beta_{i}(m_{i})=z_{i}$ such that
$d(z_{i},\phi(i))\leq C$. We will show that $\beta_{i}(\infty)$ and
$\beta_{i+1}(\infty)$ can be connected by a path in $\partial G$ avoiding
$\Lambda H$. This implies the result. Note that each $\beta_{i}(\infty)$ is
not in $\Lambda H$, since $r\geq\eta+C$.

For notational convenience, assume that $i=0$. Let $n$ be such that
$\ddagger_{n}$ holds in $\Gamma$. For every $n$-adic $t\in[0,1]$, by induction
on the power $k$ of the denominator we define $\beta_{t}$, satisfying

$d(\beta_{j/n^{k}}(m_{i}+k),\beta_{j+1/n^{k}}(m_{i}+k))\leq M,$

where $M=6C+2\delta+3$, for each $0\leq j<n^{k}$. Note that the base case of
this induction holds because $M\geq 2C+1$. Secondly, the triangle inequality
then gives the following lower bound:

$\displaystyle(\beta_{j/n_{k}}(\infty)\cdot\beta_{j+1/n_{k}}(\infty))_{1}$
$\displaystyle\geq\liminf_{n_{1},n_{2}}(\beta_{j/n_{k}}(n_{1})\cdot\beta_{j+1/n_{k}}(n_{2}))_{1}$
$\displaystyle\geq(\beta_{j/n_{k}}(m_{0}+k)\cdot\beta_{j+1/n_{k}}(m_{0}+k))_{1}$
$\displaystyle=m_{0}+k-M/2.$

We therefore deduce that

$\rho(\beta_{j/n_{k}}(\infty),\beta_{j+1/n_{k}}(\infty))\leq
k_{2}a^{-m_{0}-k+M/2}.$

Inductively applying the triangle inequality and summing the geometric series,
we thus obtain the bound that for every $n$-adic rational $t\in[0,1]$, we have

$\rho(\beta_{0}(\infty),\beta_{t}(\infty))\leq\frac{k_{2}(n-1)a^{-m_{0}+M/2}}{1-a^{-1}}.$

We then define a path $\psi:[0,1]\to\partial G$ by
$\psi(t)=\beta_{t}(\infty)$, for every $n$-adic $t$, and extending to $[0,1]$
continuously. We have shown that this path is contained within a ball of
radius

(2.1) $\frac{k_{2}(n-1)a^{-m_{0}+\frac{M}{2}}}{1-a^{-1}}$

around $\beta_{0}(\infty)$.

We now seek to place a lower bound on $\rho(\beta_{0}(\infty),\Lambda H)$ in
terms of $m_{0}$. Let $\gamma$ be a ray from 1 with limit in $\Lambda H$. So
$\gamma$ is contained in the $\eta$-neighbourhood of $H$. By [9, ch. III.H,
3.17] we have that

(2.2)
$(\beta_{0}(\infty)\cdot\gamma(\infty))_{1}\leq\liminf_{n_{1},n_{2}}(\beta_{0}(n_{1})\cdot\gamma(n_{2}))+2\delta.$

So let $n_{1},n_{2}\geq m_{0}$. We will show that
$(\beta_{0}(n_{1})\cdot\gamma(n_{2}))_{1}$ can be approximated by
$(\beta_{0}(m_{0})\cdot\gamma(m_{0}))_{1}$. Since $d(\beta_{0}(m_{0}),H)\geq
r>\delta+\eta$, we have that $d(\beta_{0}(m_{0}),\gamma)>\delta$. So there
exists some $a\in[\beta_{0}(n_{1}),\gamma(n_{2})]$ such that
$d(\beta_{0}(m_{0}),a)\leq\delta$. Similarly, we have that
$d(\gamma(m_{0}),\beta_{0})>\delta$, as $r>2\delta+\eta$. Thus again there
exists a point $b\in[\beta_{0}(n_{1}),\gamma(n_{2})]$ such that
$d(\gamma(m_{0}),b)\leq\delta$.

We now check that $a$ and $b$ are “in order”. Suppose that $b$ is closer to
$\beta_{0}(n_{1})$ than $a$. Then by considering the geodesic triangle
$[a,\beta_{0}(m_{0}),\beta_{0}(n_{1})]$, we see that $d(b,\beta_{0})\leq
2\delta$. But this implies that $d(\beta_{0}(m_{0}),\gamma(m_{0}))\leq
6\delta$, which is a contradiction since $r>6\delta+\eta$. Therefore the
picture we have looks something like Figure 3.

$\gamma$$\beta_{0}$$\beta_{0}(n_{1})$$\gamma(n_{2})$$1$$\leq\delta$$\leq\delta$$a$$b$$\beta_{0}(m_{0})$$\gamma(m_{0})$
Figure 3. The point $a$ is closer to $\beta_{0}(n_{1})$ than $b$.

We can thus conclude that

$d(\beta_{0}(n_{1}),\gamma(n_{2}))=d(\beta_{0}(n_{1}),a)+d(a,b)+d(b,\gamma^{\prime}(n_{2})).$

We can then compute the following inequality.

$\displaystyle(\beta_{0}(n_{1})\cdot\gamma(n_{2}))_{1}-(\beta_{0}(m_{0}))\cdot\gamma(m_{0}))_{1}$
$\displaystyle=\frac{1}{2}[n_{1}+n_{2}-d(\beta_{0}(n_{1}),\gamma(n_{2}))]$
$\displaystyle\hskip
10.00002pt-\frac{1}{2}[2m_{0}-d(\beta_{0}(m_{0}),\gamma(m_{0}))]$
$\displaystyle=\frac{1}{2}[(n_{1}-m_{0})+(n_{2}-m_{0})$ $\displaystyle\hskip
10.00002pt+d(\beta_{0}(m_{0}),\gamma(m_{0}))-d(\beta_{0}(n_{1}),\gamma(n_{2}))]$
$\displaystyle=\frac{1}{2}[d(\beta_{0}(n_{1}),\beta_{0}(m_{0}))-d(\beta_{0}(n_{1}),a)$
$\displaystyle\hskip
11.00008pt+d(\gamma(n_{2}),\gamma(m_{0}))-d(\gamma(n_{2}),b)$
$\displaystyle\hskip 11.00008pt+d(\beta_{0}(m_{0}),\gamma(m_{0}))-d(a,b)]$
$\displaystyle\leq\frac{1}{2}[\delta+\delta+2\delta]=2\delta.$

Applying the bound (2.2), it follows that

$\displaystyle(\beta_{0}(\infty)\cdot\gamma(\infty))_{1}$
$\displaystyle\leq(\beta_{0}(m_{0})\cdot\gamma(m_{0}))_{1}+4\delta$
$\displaystyle=\frac{1}{2}[2m_{0}-d(\beta_{0}(m_{0}),\gamma(m_{0}))]+4\delta$
$\displaystyle\leq m_{0}-\frac{1}{2}(r-\eta)+4\delta.$

This then implies the following lower bound on the distance between
$\gamma(\infty)$ and $\beta_{0}(\infty)$:

$\rho(\beta_{0}(\infty),\gamma(\infty))\geq
k_{1}a^{-m_{0}-4\delta+\frac{r-\eta}{2}}.$

We combine this inequality with (2.1), and a simple calculation reveals that
our choice of $r$ ensures that the path constructed between $p$ and $q$ avoids
$\Lambda H$. The result follows. ∎

######  Lemma 2.6 ([3, Lem. 1.21]).

If $R>4\delta+Q+\max\\{r+4\delta+1,K\\}$, then the inclusion

$A_{r,R,K}(H)\hookrightarrow A_{r,\infty,K}(H)$

induces a bijection between connected components.

###### Proof.

Surjectivity is obvious since $R\geq K$, so we need only show injectivity. Let
$x,y\in C_{K}(H)$ lie in the same component of $A_{r,\infty,K}(H)$. We claim
that the shortest path between $x$ and $y$ in $N_{r,\infty}(H)$ actually lies
inside $N_{r,R}(H)$, which implies the result.

Let $\phi:[0,\ell]\to\Gamma$ be the shortest such path, parameterised by
length. Then suppose that for some $s\in[0,\ell]$, we have that
$d(\phi(s),H)>R$. Let $[t_{0},t_{1}]\subset[0,\ell]$ be the maximal
subinterval containing $s$, such that for all $t\in[t_{0},t_{1}]$, we have

$d(\phi(t),H)\geq r+4\delta+1.$

We claim that $\phi|_{[t_{0},t_{1}]}$ is an $(8\delta+2)$-local geodesic.
Indeed, for any $t\in[t_{0},t_{1}]$, we have that the segment

$\phi|_{[t-4\delta-1,t+4\delta+1]\cap[t_{0},t_{1}]}$

is contained in $N_{r+4\delta+1,\infty}(H)$. Therefore, any segment from
$\phi(\max\\{t_{0},t-4\delta-1\\})$ to $\phi(\min\\{t_{1},t+4\delta+1\\})$
lies in $N_{r,\infty}(H)$. By the minimality of $\phi$, it follows that
$\phi|_{[t_{0},t_{1}]}$ is an $(8\delta+2)$-local geodesic. Apply [9, ch.
III.H, 1.13], we then have that any geodesic path between $\phi(t_{0})$ and
$\phi(t_{1})$ is contained in the $2\delta$-neighbourhood of
$\phi|_{[t_{0},t_{1}]}$. Maximality of $[t_{0},t_{1}]$ means that either
$t_{0}=0$, or $d(\phi(t_{0}),H)=r+4\delta+1.$ In both cases, it follows that
$d(\phi(t_{0}),H)\leq\max\\{r+4\delta+1,K\\}$. Identical reasoning also shows
that $d(\phi(t_{1}),H)\leq\max\\{r+4\delta+1,K\\}$.

$H$$\phi(t_{0})$$\phi(t_{1})$$\phi(s)$$\leq\max\\{r\ +4\delta+1,\
K\\}$$s_{0}$$s_{1}$$\leq 2\delta$$\leq 2\delta?$$\leq 2\delta?$$\leq Q$ Figure
4. The point $\phi(s)$ cannot be too far from $H$.

Let $s_{0}$, $s_{1}$ be closest-point projections of $\phi(t_{0})$,
$\phi(t_{1})$ respectively. Now, consider the quadrilateral
$[s_{0},s_{1},\phi(t_{1}),\phi(t_{0})]$. Any quadrilateral in $\Gamma$ is
$2\delta$-thin, so by inspecting Figure 4 we see that in any case, there is a
path from $\phi(s)$ to $H$ of length at most
$4\delta+Q+\max\\{r+4\delta+1,K\\}=R$. This contradicts our choice of $s$, and
so the result follows. ∎

In summary, the above lemmas give us the following.

######  Proposition 2.7.

Let $G$ be a one-ended hyperbolic group with $\delta$-hyperbolic Cayley graph
$\Gamma$, and let $H$ be a $Q$-quasiconvex subgroup. Then there exist
computable values $r\leq K\leq R$, such that the map

$\pi_{0}(A_{r,R,K}(H))\rightarrow\pi_{0}(A_{r,\infty,K}(H))\xrightarrow{\mathcal{S}}\pi_{0}(\partial
G-\Lambda H)$

is a well-defined bijection.

For the remainder of this paper we fix $r$, $R$, $K$ such that the above is
satisfied. We conclude this section with a final remark that $H$ acts on
$\pi_{0}(A_{r,R,K}(H))$ and $\pi_{0}(\partial G-\Lambda H)$ by permutations,
and the above bijection is easily seen to be equivariant with respect to this
action.

###  2.2. Ends of pairs, revisited

We will conclude this section by using the above machinery to relate the
number of (filtered) ends of a quasiconvex subgroup to its limit set
complement. We begin with the following characterisation of filtered ends.

######  Theorem 2.8.

Let $G$ be a one-ended hyperbolic group and $H$ a quasiconvex subgroup. Then
$\tilde{e}(G,H)$ is equal to the number of components of $\partial G-\Lambda
H$.

###### Proof.

Let $N\in\mathbb{N}\cup\\{\infty\\}$ denote the number of components of
$\partial G-\Lambda H$. Choose a ray $\gamma_{i}$ based in each component
$C_{i}$ of $\partial G-\Lambda H$. If $i\neq j$, it is easy to see that there
is no filtered homotopy between $\gamma_{i}$ and $\gamma_{j}$. This proves
that $\tilde{e}(G,H)\geq N$.

Conversely, fix a component $C$ of $\partial G-\Lambda H$. It is clear if
$\gamma$ is a ray such that $\gamma(\infty)\in C$, then $\gamma$ is a filtered
ray. Now, if $\gamma^{\prime}$ is another ray such that
$\gamma^{\prime}(\infty)\in C$, then by Lemma 2.5 we have that $C$ is path
connected. So consider a path through $C$ between $\gamma(\infty)$ and
$\gamma^{\prime}(\infty)$, then it is easy to see that this induces a filtered
homotopy between $\gamma$ and $\gamma^{\prime}$ in the Cayley complex. Thus,
$\tilde{e}(G,H)\leq N$. ∎

Note that $H$ acts on $\partial G-\Lambda H$ by homeomorphisms. In particular,
$H$ permutes the connected components of this set. This gives us the
following.

######  Theorem 2.9.

Let $G$ be a one-ended hyperbolic group and $H$ a quasiconvex subgroup. Then
$e(G,H)$ is equal to the number of $H$-orbits of components of $\partial
G-\Lambda H$.

###### Proof.

Recall by Proposition 1.12 that $e(G,H)$ is equal to the number of ends of the
coset graph $H\backslash\Gamma$. Note that each right coset $Hg$ satisfies the
following: $d(x,H)$ is constant across all $x\in Hg$. We call this value the
height of a coset. It is easy to see that at any given height there is only
finitely many cosets.

Now, we will form the coset graph of $H$ by a sequence of identifications, in
a way which will make the conclusion clear. First, identify all cosets which
lie in $N_{r}(H)$ to points. Next, identify all points in
$N_{r,R}(H)-A_{r,R,K}(H)$ which lie in the same coset. Now, in each component
of $A_{r,\infty,K}(H)$, identify vertices which lie in the same coset of $H$.
At this stage, it is clear we have a graph with $\tilde{e}(G,H)$ ends. The
only remaining identifications to be made are identifying some of these
“ends”. We have that the number of ends of the final graph is then equal to
the number of $H$-orbits of components of $A_{r,\infty,K}(H)$, which is equal
to the number of $H$-orbits of components of $\partial G-\Lambda H$. But the
number of ends of this graph is equal to $e(G,H)$ by Proposition 1.12, and so
the result follows. ∎

The results of this section lead us to a straightforward proof of the
following corollary.

######  Corollary 2.10.

Let $G$ be a one-ended hyperbolic group, and $H$ a quasiconvex subgroup. Then
$e(G,H)$ is finite. In particular, $e(G,H)\leq|B_{2l+R}(1)|$, where $l$ is the
longest length of a given generator of $H$.

###### Proof.

The action of $H$ on the components of $\partial G-\Lambda H$ is induced by
the action of $H$ on the components of $A_{r,R,K}(H)$. The latter is a locally
finite graph on which $H$ acts cocompactly, and so this must have finitely
many $H$-orbits of connected components, since the quotient graph is finite.
It follows that there can only be finitely many $H$-orbits of components of
$\partial G-\Lambda H$, and the result follows by Theorem 2.9. The precise
bound follows from just bounding above the size of a fundamental domain for
the action of $H$ on $A_{r,R,K}(H)$. ∎

The above results thus give us a full description of all possible $H$-almost
invariant subsets of $G$, up to equivalence: any such set is equivalent to
some union of $H$-orbits of components of $A_{r,\infty,K}(H)$. To ease
notation, if $U$ is a union of connected components of $A_{r,\infty,K}(H)$,
then let

$U^{\ast}:=A_{r,\infty,K}(H)-U.$

It is easy to see that the symmetric difference $U^{\ast}\triangle(G-U)$ is
$H$-finite, so this overloading of notation is not a problem for our purposes.

Now, note that if $U$ is a connected component of $A_{r,\infty,K}(H)$, then
$gU$ is a connected component of $A_{r,\infty,K}(gH)$. The connected
components of the latter are in one-to-one correspondence with the components
of $\partial G-\Lambda gH$, and we can define $\mathcal{S}(gU)$ in the obvious
way to realise this correspondence. Note that one has to be careful with the
choice of basepoint, but this doesn’t really matter as if we increase $r$
accordingly for each $g$, then it is easy to see that the choice of basepoint
does not affect the properties of $\mathcal{S}$. We conclude this section by
characterising via the boundary what it means for an $H$-almost invariant set
$X$ to cross itself, in the sense of Definition 1.5.

######  Proposition 2.11.

Let $X\subset G$ be an $H$-almost invariant set, and let $U$ be the unique
union of connected components of $A_{r,\infty,K}(H)$ which is equivalent to
$X$. Then $X$ crosses itself if and only if there exists $g\in G$ such that

$\mathcal{S}U\cap\mathcal{S}(gU^{\ast}),\ \ \
\mathcal{S}U\cap\mathcal{S}(gU),\ \ \
\mathcal{S}(U^{\ast})\cap\mathcal{S}(gU),\ \ \
\mathcal{S}(U^{\ast})\cap\mathcal{S}(gU^{\ast})$

are all non-empty.

###### Proof.

It can be seen that $U\cap gU$ is $H$-infinite if and only if it contains
arbitrarily large balls [30, Remark 1.13]. This clearly implies that
$\mathcal{S}U\cap\mathcal{S}(gU)\neq\emptyset$.

Conversely, $\mathcal{S}U\cap\mathcal{S}(gU)$ is an open subset of $\partial
G$, so if it is non-empty then it contains some open ball
$B\subset\mathcal{S}U\cap\mathcal{S}(gU)$. It is follows quickly from this
that $U\cap gU$ must contain balls of arbitrary diameter. By symmetry in the
other four cases, the result follows. ∎

##  3\. Detection via Digraphs

So far, we have related the connectivity of the limit set complement to the
connectivity of a certain subgraph of the Cayley graph, but this subgraph is
still infinite. In order to obtain any sort of algorithm we will need some way
of understanding the global connectivity properties by looking only at a
finite piece.

In this section, we will make headway towards this goal by constructing a
certain labelled digraph, whose connectivity and language encodes a great deal
of information about the properties of the subgraph $A_{r,R,K}(H)$.

###  3.1. Digraphs and their languages

We begin by briefly introducing labelled digraphs. This area has many
applications to the study of subgroups of free groups, and a good survey of
this rich theory can be found in [25].

######  Definition 3.1 (Labelled digraphs).

Let $S$ be a finite set of symbols, closed under taking formal inverses, i.e.
$S=S^{-1}$. An $S$-digraph $\Delta$ is a finite graph where every edge is
oriented and is labelled by some $s\in S$.

We also require that if there is a directed edge $e$ labelled by $s\in S$ from
$v$ to $v^{\prime}$, then there is an edge labelled by $s^{-1}$ from
$v^{\prime}$ to $v$, which we denote by $e^{-1}$.

Note that in this definition we allow the possibility of single-edge loops,
and we do not require our graphs to be connected. We now set up some notation.

We write $V\Delta$ for the vertex set of $\Delta$. Denote by $o(e)$ and $t(e)$
the initial and terminal vertices of the oriented edge $e$, respectively.
Denote by $\operatorname{Lab}(e)$ the label of the oriented edge $e$, so
$\operatorname{Lab}(e^{-1})=\operatorname{Lab}(e)^{-1}$. A path through
$\Delta$ is a sequence of oriented edges $e_{1}e_{2}\ldots e_{n}$ such that
$o(e_{i+1})=t(e_{i})$. We call this path a loop if $o(e_{1})=t(e_{n})$. We
define the inverse of the path $p$ as the path $p^{-1}:=e^{-1}_{n}\ldots
e^{-1}_{1}$. Given $p$ as above, define $o(p)=o(e_{1})$, $t(p)=t(e_{n})$. We
say that two paths $p$, $q$ are freely equal $o(p)=o(q)$, $t(p)=t(q)$, and the
words $\operatorname{Lab}(p)$ and $\operatorname{Lab}(q)$ are equal in the
free group $F(S)$.

Given a set of symbols $S$, denote by $S^{\ast}$ the set of finite strings in
$S$. If $p=e_{1}\ldots e_{n}$ is a path through $\Delta$, define its label
$\operatorname{Lab}(p)\in S^{\ast}$ as the formal string
$\operatorname{Lab}(p)=\operatorname{Lab}(e_{1})\ldots\operatorname{Lab}(e_{n})$.
We have the following definition.

######  Definition 3.2.

Let $\Delta$ be an $S$-digraph, and let $v$, $v^{\prime}$ be vertices of
$\Delta$. Define the language of $\Delta$ from $v$ to $v^{\prime}$ as the set

$\mathcal{L}(\Delta,v,v^{\prime})=\\{\operatorname{Lab}(p):\text{$p$ is a path
in $\Delta$ from $v$ to $v^{\prime}$}\\}\subset S^{\ast}.$

Let $H$ be a group and $S\subset H$ a finite symmetric subset. Denote by
$\pi:S^{\ast}\to H$ the obvious projection. Then we have the following key
lemma.

######  Lemma 3.3.

Let $\Delta$ be an $S$-digraph, where $S$ is a finite subset of a group $H$.
Then for every pair $v_{0},v_{1}$ of vertices of $\Delta$, there is a finitely
generated subgroup $K_{v_{0}}\leq H$ and a finite subset
$T_{v_{0},v_{1}}\subset H$ such that

$\pi(\mathcal{L}(\Delta,v_{0},v_{1}))=\bigcup_{t\in
T_{v_{0},v_{1}}}K_{v_{0}}t.$

Moreover, $T_{v_{0},v_{1}}$ and generators of $K_{v_{0}}$ can be computed
effectively.

###### Proof.

To ease notation, let $\mathcal{L}=\mathcal{L}(\Delta,v_{0},v_{1})$. We first
construct $K_{v_{0}}$ and $T_{v_{0},v_{1}}$. Consider the following sets of
paths through $\Delta$.

  * •

$\Pi(v,v^{\prime})=\\{p:\textrm{$p$ is a simple path through $\Delta$ with
$o(p)=v$, $t(p)=v^{\prime}$}\\}$,

  * •

$\Lambda(v)=\\{\ell:\textrm{$\ell$ is a simple loop through $\Delta$ with
$o(\ell)=t(\ell)=v$}\\}$,

  * •

$\Lambda^{\prime}(v)=\\{p\ell p^{-1}:v^{\prime}\in V\Delta,\
\ell\in\Lambda(v^{\prime}),\ p\in\Pi(v,v^{\prime})\\}$.

Intuitively, $\Lambda^{\prime}(v)$ is the set of “lollipop loops” based at
$v$, which are formed by attaching a simple loop to a simple path and its
inverse. Let
$Y=\\{\pi(\operatorname{Lab}(\gamma)):\gamma\in\Lambda^{\prime}(v_{0})\\}$,
and set $K_{v_{0}}=\langle Y\rangle$. Also define

$T_{v_{0},v_{1}}=\\{\pi(\operatorname{Lab}(p)):p\in\Pi(v_{0},v_{1})\\}.$

The rest of this proof will be dedicated to showing the following statement.
We claim that every path $\gamma$ through $\Delta$ with $o(\gamma)=v_{0}$ is
freely equal to a path of the form $\alpha_{1}\ldots\alpha_{r}q$, where each
$\alpha_{i}\in\Lambda(v_{0})$ and $q\in\Pi(v_{0},t(\gamma))$. From this the
lemma follows immediately.

With the above claim in mind, let $\gamma$ be a path in $\Delta$ from $v_{0}$
to $v_{1}$ and assume without loss of generality that
$\operatorname{Lab}(\gamma)$ is freely reduced. If $\gamma$ is a simple path
or simple loop then the statement is trivial, so assume $\gamma$ self-
intersects somewhere away from $o(\gamma)=v_{0}$. We then proceed by induction
on the length of $\gamma$. We may decompose $\gamma$ into the form

$\gamma=p_{0}\ell_{1}p_{1}\ell_{2}p_{2}\ldots\ell_{k}p_{k},$

where the $p_{j}$ are (possibly trivial) simple paths such that
$t(p_{j})=o(p_{j+1})$ and each $\ell_{j}$ is a non-trivial simple loop in
$\Lambda(o(p_{j}))$. For each $1\leq j\leq k$ let

$\ell^{\prime}_{j}:=p_{0}p_{1}\ldots p_{j-1}\ell_{j}p_{j-1}^{-1}\ldots
p_{1}^{-1}p_{0}^{-1}.$

Inspection reveals then that $\gamma$ is freely equal to the path
$\gamma^{\prime}:=\ell_{1}^{\prime}\ell_{2}^{\prime}\ldots\ell_{k}^{\prime}p_{0}p_{1}\ldots
p_{k}$. Consider the subpath $\gamma_{j}=p_{0}\ldots p_{j}$. Each $\gamma_{j}$
is a path of strictly shorter length than $\gamma$. By the inductive
hypothesis we have that $\gamma_{j}$ is of the form $s_{1}\ldots s_{k}q$ where
each $s_{i}\in\Lambda^{\prime}(v_{0})$ and $q\in\Pi(v_{0},t(p_{j}))$. Now we
have that

$\ell_{j+1}^{\prime}=\gamma_{j-1}\ell_{j}\gamma_{j-1}^{-1}=s_{1}\ldots
s_{i}q\ell_{j}q^{-1}s_{i}^{-1}\ldots s_{1}^{-1}.$

Since $q\ell_{j}q^{-1}\in\Lambda^{\prime}(v_{0})$, we have that
$\ell_{j}^{\prime}$ is thus freely equal to a path of the form
$\alpha_{1}\ldots\alpha_{r}$ where each
$\alpha_{i}\in\Lambda^{\prime}(v_{0})$. If we apply the inductive hypothesis
once more to $\gamma_{k}$, then the claim follows. ∎

###  3.2. Adjacency digraphs

Let $G$ be a finitely generated group and $\Gamma$ a Cayley graph of $G$. Let
$H$ be a finitely generated subgroup of $G$. Let $F\subset\Gamma$ be a finite
subgraph, and consider $X={HF}$. Then $X$ is a subgraph of $\Gamma$ on which
$H$ acts cocompactly. We say that $F$ is a finite $H$-cover of $X$. In
principle, $X$ will have many finite $H$-covers.

Given such a finite set of vertices $F$, we form its $H$-adjacency set, or
just its adjacency set $S_{F}$ as follows. Let

$S_{F}=\\{s\in H:s\neq 1,\ sF\cap F\neq\emptyset\\}.$

Informally, $S_{F}$ is the finite set containing $s\in H$ such that $sF$
intersects $F$. Note that $S_{F}$ is symmetric, i.e $S_{F}=S_{F}^{-1}$. The
fact that $S_{F}$ is finite follows from $F$ being finite and $\Gamma$ being
locally finite.

We form the $S_{F}$-digraph $\Delta_{F}$, called the $F$-adjacency graph, as
follows. The vertex set $V\Delta_{F}$ is precisely the set $\pi_{0}(F)$ of
connected components of $F$, and there is a directed edge labelled by $s\in
S_{F}$ from $v$ to $v^{\prime}$ if $v\cap sv^{\prime}\neq\emptyset$. In
particular, this implies that $v$ and $sv^{\prime}$ are contained in the same
connected component of $X$. It is easy to check that $\Delta_{F}$ is indeed a
well-defined digraph. See Figure 5 for an example of this construction.

$A$$B$$C$$D$$aA$$aB$$aC$$aD$$bA$$bB$$bC$$bD$$A$$B$$C$$D$$\Longrightarrow$$\Delta_{F}$$a$$a$$a$$a$$b$$b$$b$$b$$F\cup
aF\cup bF$ Figure 5. An example of the construction of an adjacency digraph.
Here, $\pi_{0}(F)=\\{A,B,C,D\\}$ and $S_{F}=\\{a,b,a^{-1},b^{-1}\\}$. Due to
symmetry we have not drawn the translates of $F$ by $a^{-1}$ or $b^{-1}$, nor
the corresponding edges of $\Delta_{F}$.

The relevance of the adjacency digraph $\Delta_{F}$ to our problem is given by
the following lemma.

######  Lemma 3.4.

Let $v,v^{\prime}\in\pi_{0}(F)$, and $h\in H$. Then $v$ and $hv^{\prime}$ are
contained in the same connected component of $X={HF}$ if and only if
$h\in\pi(\mathcal{L}(\Delta_{F},v,v^{\prime}))$.

###### Proof.

Firstly, suppose that $h=\pi(w)$, where $w=s_{1}\ldots
s_{n}\in\mathcal{L}(\Delta_{F},v,v^{\prime})$. Let $\gamma=e_{1}\ldots e_{n}$
be a path through $\Delta_{F}$ between $v$ and $v^{\prime}$ labelled by $w$,
so $e_{i}$ is labelled by $s_{i}$. Let $v=v_{0}$ and $v_{i}=t(e_{i})$ for each
$1\leq i\leq n$. Observe that by definition we have that $v_{i}$ intersects
$s_{i+1}v_{i+1}$ in $\Gamma$, and so $s_{i+1}v_{i+1}$ and $v_{i}$ must be
contained within the same component of $X$. Since
$w\in\mathcal{L}(\Delta_{F},v,v^{\prime})$, we have that $v_{n}=v^{\prime}$.
Note also that $s_{i+1}\ldots s_{n}\in\mathcal{L}(\Delta_{F},v_{i},v_{n})$. We
proceed by induction on $n$. Clearly if $n=1$, then the result is true by the
definition of $\Delta_{F}$.

Suppose then that $n>1$. Then $w^{\prime}=s_{2}\ldots
s_{n}\in\mathcal{L}(\Delta_{F},v_{2},v_{n})$. Let
$h^{\prime}=\pi(w^{\prime})$, then by the inductive hypothesis we have that
$v_{1}$ and $h^{\prime}v_{n}$ are contained within the same component of $X$.
Then $v_{0}$ is contained within the same component as $s_{1}v_{1}$ by
definition. But this is contained in the same component as
$s_{1}h^{\prime}v_{n}=hv^{\prime}$.

Conversely, suppose that $v$ and $hv^{\prime}$ lie in the same component of
$X$ for some $h\in H$. Let $\gamma$ be a path through $X$ between $v$ and
$hv^{\prime}$. The path $\gamma$ will pass through a sequence of translates of
components of $F$, say

$v=h_{0}v_{0},\ h_{1}v_{1},\ h_{2}v_{2},\ \ldots,\ h_{l}v_{l}=hv^{\prime},$

where $h_{i}\in H$, $h_{0}=1$, $v_{i}\in\pi_{0}(F)$, and $h_{i-1}v_{i-1}\cap
h_{i}v_{i}\neq\emptyset$ for every $1\leq i\leq n$. By definition, we then
have that $s_{i}:=h_{i-1}^{-1}h_{i}\in S_{F}$, and there is an edge in
$\Delta_{F}$ from $v_{i-1}$ to $v_{i}$ labelled by $s_{i}$. We thus deduce
that $s_{1}\ldots s_{n}\in\mathcal{L}(\Delta_{F},v,v^{\prime})$. Since
$h=s_{1}\ldots s_{n}$, the result follows. ∎

The next result is a characterisation of when the graph $X=HF$ has only
finitely many components. Given $v,v^{\prime}\in\pi_{0}(F)$, recall the
definition of $K_{v}$ and $T_{v,v^{\prime}}$ from Lemma 3.3.

######  Lemma 3.5.

Let $F$ be a finite $H$-cover of $X={HF}$. Then $X$ has finitely many
connected components if and only if for every $v\in\pi_{0}(F)$ we have that
$K_{v}$ has finite index in $H$.

###### Proof.

By Lemmas 3.3 and 3.4, note that $h\in K_{v}$ if and only if there is a path
through $X$ from $v$ to $hv$, and thus the same also holds for $h^{\prime}v$
and $h^{\prime}hv$ for any $h^{\prime}\in H$. So suppose first that some
$K_{v}$ has finite index in $H$ and let $T$ be a finite left-transversal of
$K_{v}$. Then $TK_{v}v=Hv$, and this intersects at most $|T|$ components of
$X$. Repeat this for every $v\in\pi_{0}(F)$ and see that $X$ has at most

$\sum_{v\in\pi_{0}(F)}|H:K_{v}|<\infty$

components.

Conversely, fix $v\in\pi_{0}(F)$ such that $|H:K_{v}|=\infty$ and let
$T=\\{h_{i}:i\in\mathbb{N}\\}$ be an infinite left-transversal in $H$ of
$K_{v}$. We claim that every $h_{i}v$ lies in a distinct component of $X$.
Indeed, suppose that $h_{i}v$ and $h_{j}v$ were contained in the same
component of $X$ for some $i\neq j$. Then by Lemmas 3.3 and 3.4 we have that
$h_{i}^{-1}h_{j}\in K_{v}$. This contradicts our choice of $T$, so the lemma
follows. ∎

It is clear that $H$ permutes the connected components of $X$. Note that if
$X$ is connected then $\Delta_{F}$ is certainly connected, though the converse
is not necessarily true. Instead, the number of connected components of
$\Delta_{F}$ actually encodes the following.

######  Lemma 3.6.

The number of connected components of $\Delta_{F}$ is equal to the number of
$H$-orbits of components of $X={HF}$.

###### Proof.

By Lemma 3.4 we see that $v,v^{\prime}\in\pi_{0}(F)$ are connected by a path
in $\Delta_{F}$ if and only if $v$ is joined by a path through $X$ to some
$H$-translate of $v^{\prime}$. The lemma then follows immediately. ∎

###  3.3. First algorithms

The first application of our digraph machinery is the following. Throughout
this subsection we fix constants $0\leq r\leq K\leq R<\infty$ and a Cayley
graph $\Gamma$ of our one-ended hyperbolic group $G$.

######  Proposition 3.7.

Let $H$ be a quasiconvex subgroup of a one-ended hyperbolic group $G$. Then
there is an algorithm which, given $x\in G$, will decide if $x\in
A_{r,R,K}(H)$.

###### Proof.

First, we show that one can decide membership of $N_{r,R}(H)$. Given $x\in G$,
compute the finite balls $U_{1}=B_{r}(x)$, $U_{2}=B_{R}(x)$ in $\Gamma$. Then
$x\in N_{r,R}(H)$ if and only if $U_{1}\cap H=\emptyset$ and $U_{2}\cap
H\neq\emptyset$. This is decidable, since membership of $H$ is decidable.
Similarly, we can decide membership of $C_{K}(H)$. If $x$ is not in
$N_{r,R}(H)$, then terminate and return ‘no’.

Now, note that $H$ acts cocompactly on $N_{r,R}(H)$, so compute a finite
$H$-cover $F$ containing $x$. This can be achieved by, for example, letting
$l$ be the length of the longest given generator of $H$, and choosing
$F=N_{r,R}(H)\cap B_{2l+R}(x)$. Let $v_{x}\in\pi_{0}(F)$ be the component of
$F$ containing $x$. We now form the adjacency digraph $\Delta_{F}$, and mark
the vertices $v\in\pi_{0}(F)$ which intersect $C_{K}(H)$ in $\Gamma$. One can
then check that $x\in A_{r,R,K}(H)$ if and only if $v_{x}$ lies in a connected
component of $\Delta_{F}$ containing a marked vertex. ∎

We now have the following algorithms, which will allow us to distinguish
(filtered) ends from one another.

######  Proposition 3.8.

There is an algorithm which, given $x,y\in A_{r,R,K}(H)$, will decide if $x$
and $y$ lie in distinct $H$-orbits of connected components of $A_{r,R,K}(H)$.

###### Proof.

Use Proposition 3.7 to compute a finite $H$-cover $F$ of $A_{r,R,K}(H)$, and
let $v_{x},v_{y}\in\pi_{0}(F)$ be such that $x\in v_{x}$, $y\in v_{y}$. Then,
as remarked in the proof of Lemma 3.6, we need only form the adjacency digraph
$\Delta_{F}$ and check whether $v_{x}$ and $v_{y}$ lie in the same connected
component of $\Delta_{F}$. ∎

######  Proposition 3.9.

There is an algorithm which, given $x,y\in A_{r,R,K}(H)$ and a solution to the
generalised word problem for $H$, will decide if $x$ and $y$ lie in distinct
connected components of $A_{r,R,K}(H)$.

###### Proof.

Find a finite $H$-cover $F$ for $A_{r,R,K}(H)$ containing both $x$ and $y$.
Let $v_{x},v_{y}\in\pi_{0}(F)$ be the components of $F$ containing $x$ and $y$
respectively. By Lemma 3.4, we have that $x$ and $y$ are contained in the same
component if and only if $1\in\pi(\mathcal{L}(\Delta_{F},v_{x},v_{y}))$. Form
the subgroup $K_{v_{x}}$ and set of words $T_{v_{x},v_{y}}$ as in Lemma 3.3,
then $x$ and $y$ lie in different components if and only if
$T_{v_{x},v_{y}}\cap K_{v_{x}}$ is empty. Using our given solution to the
generalised word problem in $H$, this is decidable. ∎

We now turn to reproving Proposition 3.9, but we drop the hypothesis that $H$
has a solvable generalised word problem and replace it with the condition that
$H$ has finitely many filtered ends in $G$. The key observation that makes
this problem tractable in this case is the following.

######  Proposition 3.10.

If $A_{r,R,K}(H)$ has finitely many components, then there is an algorithm
which, given $x,y\in A_{r,R,K}(H)$, will decide if $x$ and $y$ lie in distinct
connected components of $A_{r,R,K}(H)$.

###### Proof.

It is known by Lemma 3.5 that, for every $v\in\pi_{0}(F)$, the subgroup
$K_{v}\leq H$ constructed in Lemma 3.3 has finite index in $H$. In particular,
$K_{v}$ is quasiconvex in $H$, and so we can decide membership of $K_{v}$. The
algorithm then proceeds exactly as in Proposition 3.9. ∎

###  3.4. Counting (filtered) ends of pairs

We conclude this section by giving algorithms to compute $e(G,H)$ and
$\tilde{e}(G,H)$. Fix constants $0\leq r\leq K\leq R<\infty$ such that
Proposition 2.7 is satisfied. Let $F$ be a finite $H$-cover for
$A_{r,R,K}(H)$, and form the adjacency digraph $\Delta_{F}$. Note that the
construction of this digraph is completely effective. We immediately have the
following new algorithm for computing $e(G,H)$, which was first shown to be
computable by Vonseel [45].

######  Theorem 3.11.

There is an algorithm which, upon input of a one-ended hyperbolic group $G$
and generators of a quasiconvex subgroup $H$, will output $e(G,H)$.

###### Proof.

One simply counts connected components of $\Delta_{F}$. The construction of
$\Delta_{F}$ is completely effective, so the result follows immediately from
Lemma 3.6 and Theorem 2.9. ∎

Computing $\tilde{e}(G,H)$ poses more problems. In particular, we need to
somehow be able to decide if $K_{v}$ has finite index in $H$, which can be
seen to be undecidable for an arbitrary choice of $H$ via the Rips
Construction (see e.g. [4]). Thus, in light of Lemma 3.5 we cannot expect to
be able to decide if $\tilde{e}(G,H)=\infty$ without either adding further
hypotheses to $H$ (e.g. this is decidable if $H$ is free [25]), or somehow
further controlling the structure of $A_{r,R,K}(H)$. It is not clear whether
the latter of these is even possible, which suggests this problem may be
undecidable for arbitrary choices of quasiconvex $H\leq G$. We can however at
least give the following two algorithms.

######  Theorem 3.12.

There is an algorithm which, upon input of a one-ended hyperbolic group $G$,
generators of a quasiconvex subgroup $H$, a solution to the generalised word
problem for $H$, and an integer $N\geq 0$, will decide whether
$\tilde{e}(G,H)\geq N$. In particular, we can decide if $\partial G-\Lambda H$
is connected.

###### Proof.

Compute a finite $H$-cover $F_{0}$ of $A_{r,R,K}(H)$, then inductively define
$F_{i+1}:=YF_{i}\cup F_{i}$, where $Y$ is a symmetric generating set for $H$.
Thus we have an increasing sequence of $H$-covers $(F_{i})$, where each
strictly contains the last. For each $i$, let $N_{i}$ denote the number of
components of $A_{r,R,K}(H)$ which intersect $F_{i}$. This number is
computable by Proposition 3.9, and we can conclude that $e(G,H)\geq N_{i}$. If
there is some $i$ such that $N_{i}=N_{i+1}$, then since $Y$ is a generating
set, it follows that $N_{j}=N_{i}$ for all $j>i$. Given $N$ as input, our
algorithm will run until $N_{i}\geq N$ for some $i$, or terminate if the
sequence $(N_{i})_{i}$ stabilises. By the above, this will always halt. ∎

######  Theorem 3.13.

There is an algorithm which, upon input of a one-ended hyperbolic group $G$
and generators of a quasiconvex subgroup $H$, will terminate if and only if
$\tilde{e}(G,H)$ is finite. Moreover, upon termination it will output the
value of $\tilde{e}(G,H)$.

###### Proof.

We proceed as before and compute a finite $H$-cover $F_{0}$ of $A_{r,R,K}(H)$,
then inductively define $F_{i+1}:=YF_{i}\cup F_{i}$, where $Y$ is a symmetric
generating set for $H$. Thus, we have an increasing sequence of $H$-covers

$F_{0}\subset F_{1}\subset F_{2}\subset\ldots,$

where each strictly contains the last. Moreover,
$\bigcup_{i}F_{i}=A_{r,R,K}(H)$. For each $i\geq 0$ we now run the following
search. For each component of $YF_{i}$, search for a path through
$A_{r,R,K}(H)$ into $F_{i}$. If this process terminates for a given $i\geq 0$
then it follows from an easy induction argument that there is a path from any
point in $A_{r,R,K}(H)=HF_{i}$ back to $F_{i}$ travelling through
$A_{r,R,K}(H)$. In particular, this means that every connected component of
$A_{r,R,K}(H)$ intersects $F_{i}$.

Clearly such an $F_{i}$ exists if and only if $A_{r,R,K}(H)$ has finitely many
components, which is equivalent to the condition that $\tilde{e}(G,H)<\infty$
by Proposition 2.7 and Theorem 2.8. If we do find such an $F_{i}$ then to
compute the exact value of $\tilde{e}(G,H)$ we may use Proposition 3.10 to
decide how many distinct components of $A_{r,R,K}(H)$ intersect $F_{i}$. By
our choice of $F_{i}$, this will then be precisely the total number of
components of $A_{r,R,K}(H)$. ∎

##  4\. Searching for Splittings and Crossings

In this section we apply the above tools to the problem of deciding if a given
quasiconvex subgroup is associated with a splitting. In short, we run two
searches in parallel – one search for a splitting and another search for
obstructions to splittings.

###  4.1. An algorithm to search for splittings

The first step to searching for splittings over subgroups commensurable with
$H$ is to be able to recognise such subgroups. We will achieve this by
deciding membership of $\operatorname{Comm}_{G}(H)$.

######  Proposition 4.1.

Let $G$ be a hyperbolic group, then there is an algorithm which, on input of
generators of a quasiconvex subgroup $H$, will decide if $|G:H|<\infty$.

###### Proof.

We have that $|G:H|$ is finite if and only if $\partial G=\Lambda H$. By
Proposition 2.7 this is true if and only if $A_{r,R,K}(H)=\emptyset$ for
suitably chosen $r,R,K$. This can be decided by computing a finite $H$-cover
$F$ of $N_{r,R}(H)$ as in the proof of Proposition 3.7 and checking if $F$
intersects $C_{K}(H)$. ∎

######  Proposition 4.2.

Let $G$ be a hyperbolic group. Given generators of a quasiconvex subgroup
$H\leq G$, then membership of the commensurator $\operatorname{Comm}_{G}(H)$
is decidable.

###### Proof.

Let $g\in G$, then since $G$ is hyperbolic we have that $H^{g}$ is
quasiconvex. Moreover, $H\cap H^{g}$ is quasiconvex and we can compute an
explicit generating set for this group via [18]. We then use Proposition 4.1
to decide if $|H:H\cap H^{g}|$ and $|H^{g}:H\cap H^{g}|$ are finite. This
decides whether $g\in\operatorname{Comm}_{G}(H)$. ∎

Note that $\operatorname{Comm}_{G}(H)$ is itself quasiconvex, and so given a
generating set of this subgroup we would have that the membership problem
would be decidable via Kapovich’s algorithm. However, we are not given
generators of $\operatorname{Comm}_{G}(H)$, but of $H$. So, what the above
proposition tells us is that we can decide membership of the commensurator in
spite of this problem. Applying this observation, we produce the following
algorithm which searches for splittings where the edge group is commensurable
with $H$.

######  Proposition 4.3.

There is an algorithm which takes in as input a one-ended hyperbolic group $G$
and generators of a quasiconvex subgroup $H$, and terminates if and only if
$H$ is associated with a splitting.

###### Proof.

Enumerate presentations of $G$ via Tietze transformations. If a given
presentation has the general form of an amalgam or HNN extension, run
Kapovich’s algorithm [23] on the generators of the edge group, which
terminates if and only if this subgroup is quasiconvex and outputs a
quasiconvexity constant $Q$ if it does terminate. This procedure enumerates
splittings of $G$ over quasiconvex subgroups.

Given a particular quasiconvex splitting of $G$, say over $H^{\prime}$, we can
decide if $H^{\prime}$ is commensurable with $H$ as follows. Using Proposition
4.2 we decide if $H^{\prime}\leq\operatorname{Comm}_{G}(H)$ and
$H\leq\operatorname{Comm}_{G}(H^{\prime})$. It is easy to check these two
relations hold if and only if $H$ is commensurable with $H^{\prime}$. This
completes the algorithm. ∎

###  4.2. An algorithm to search for crossings

Recall Proposition 2.11, which characterised crossings via intersections of
shadows in $\partial G$. We now characterise these intersections via local
geometry, and present an algorithm which terminates if and only if such a
crossing exists. We first need the following technical lemma.

######  Lemma 4.4.

Let $U_{1}$, $U_{2}$ be unions of connected components of $A_{r\infty,K}(H)$
The intersection $\mathcal{S}U_{1}\cap\mathcal{S}(gU_{2})$ is non-empty if and
only if there exists some $x\in U_{1}\cap gU_{2}$ such that

$d(x,H)>K\ \ \ \ \textrm{and}\ \ \ \ d(x,gH)>K+5\delta+|g|.$

###### Proof.

Firstly, suppose that such an $x$ exists, then let $\gamma$ be a ray based at
1 passing within $C=3\delta$ of $x$, as in Lemma 1.16. As in the proof of
Lemma 2.3 we see that $\gamma(\infty)\in\mathcal{S}U_{1}$ since $\gamma$
passes within $C$ of $C_{K}(H)$. Secondly, let $\gamma^{\prime}$ be a geodesic
ray based at $g$ such that $\gamma^{\prime}(\infty)=\gamma(\infty)$. Then the
Hausdorff distance between $\gamma$ and $\gamma^{\prime}$ is at most
$5\delta+|g|$ (apply e.g. [14, Exc. 11.86]). Again, as in the proof of Lemma
2.3 we see that $\gamma^{\prime}(\infty)\in\mathcal{S}(gU_{2})$, and we’re
done.

Conversely, let $\gamma\in p\in\mathcal{S}U_{1}\cap\mathcal{S}(gU_{2})$. By
the definition of $\mathcal{S}$ we have that there is some $t_{0}$ such that
for all $t\geq t_{0}$, $\gamma(t)\in U_{1}\cap gU_{2}$. Moreover, by Lemma 2.1
we have for $i=1,2$ that $d(\gamma(t),H_{i})\to\infty$ as $t\to\infty$. Thus,
by setting $x=\gamma(t)$ for some sufficiently large $t$, we are done. ∎

We’re now ready to search for crossings. This algorithm will check every
choice of $H$-almost invariant set and search for any crossings. It will
terminate if and only if it finds a crossing for every such choice. Note that
since $e(G,H)<\infty$ by Corollary 2.10, there is only finitely many possible
$H$-almost invariant sets to check, up to equivalence.

######  Proposition 4.5.

There exists an algorithm which, on input of a one-ended hyperbolic group $G$
and generators of a quasiconvex subgroup $H$, will terminate if and only if
for every choice $X\subset G$ of $H$-almost invariant set, we have that $X$ is
not semi-nested.

###### Proof.

We begin by picking representative choices for every equivalence class of non-
trivial $H$-almost invariant subsets $X_{1},\ldots,X_{n}$. In particular, each
$X_{i}$ is a union of $H$-orbits of connected components of
$A_{r,\infty,K}(H)$. For notational convenience we identify $X_{i}^{\ast}$
with its representative in this list.

Enumerate elements $g\in G-\operatorname{Comm}_{G}(H)$ via Proposition 4.2.
For each $i=1,\ldots,n$ search for some $x_{i,1}\in X_{i}\cap gX_{i}$,
$x_{i,2}\in X_{i}\cap g(X_{i}^{\ast})$, $x_{i,3}\in X_{i}^{\ast}\cap gX_{i}$,
and $x_{i,4}\in X_{i}^{\ast}\cap g(X_{i}^{\ast})$ such that the conditions in
Lemma 4.4 are met for each $x_{i,j}$. We terminate our search if and only if
we find such an $x_{i,j}$ for every $i$, $j$. By Proposition 2.11 and Lemma
4.4 this will terminate if and only if every $H$-almost invariant subset is
not semi-nested. ∎

###  4.3. Splitting detection

We now present the final result of this paper, an algorithm to detect
splittings over quasiconvex subgroups. We split this algorithm into two cases,
and firstly we consider the situation that we know a priori that our subgroup
has finitely many filtered ends.

######  Theorem 4.6.

There is an algorithm which, upon input of a one-ended hyperbolic group $G$
and generators of a quasiconvex subgroup $H$ such that
$\tilde{e}(G,H)<\infty$, will decide whether $H$ is associated with a
splitting. Furthermore, if such a splitting exists then the algorithm will
output this splitting.

###### Proof.

Let $U_{1},\ldots,U_{n}$ be the components of $A_{r,\infty,K}(H)$, and let
$H^{\prime}\leq H$ be a finite index subgroup which fixes each individual
component, so each $U_{i}$ is an $H^{\prime}$-almost invariant subset. Any
other subgroup which is commensurable with $H$ will have the same set of
filtered ends, so this is the “finest” set of $H^{\prime\prime}$-almost
invariant subsets for any subgroup $H^{\prime\prime}$ commensurable with $H$.
It therefore follows that if $H^{\prime}$ does not admit a semi-nested
$H^{\prime}$-almost invariant set, then neither does any other subgroup which
is commensurable with $H$.

With the above in mind we run two algorithms in parallel. We search for a
splitting over a subgroup commensurable with $H$ via Proposition 4.3, and
concurrently run the algorithm in Proposition 4.5 on $H^{\prime}$. By the
above discussion exactly one of these will terminate, and if the former
algorithm terminates then it will output a presentation of a splitting over a
subgroup commensurable with $H$. ∎

Indeed, if $\tilde{e}(G,H)$ is not finite then we cannot rely on the machinery
used above, as the stabiliser of some component of $\partial G-\Lambda H$ may
have infinite index in $H$. Moreover, referring back to the discussion in
Section 3.4, we are unlikely to be able to decide if $\tilde{e}(G,H)$ is
finite for arbitrary quasiconvex $H$, at least with just the current tools
presented in this paper.

Recall that a subgroup $H$ in $G$ is said to be lonely if there is no subgroup
$H^{\prime}\neq H$ such that $H$ is commensurable to $H^{\prime}$. For a
quasiconvex subgroup $H$ of a hyperbolic group $G$, this condition is
equivalent to saying that $H=\operatorname{Comm}_{G}(H)$ and $H$ has no finite
quotients.

######  Theorem 4.7.

There is an algorithm which, upon input of a one-ended hyperbolic group $G$,
generators of a quasiconvex subgroup $H$, and knowledge of whether $H$ is
lonely in $G$, will decide whether $H$ is associated with a splitting.
Furthermore, if such a splitting exists then the algorithm will output this
splitting.

###### Proof.

Firstly, begin running the algorithm from Proposition 4.3, which will
terminate if and only if $H$ is associated with a splitting.

Concurrently we run the following. If $H$ is not lonely, then simultaneously
search for an element $g\in\operatorname{Comm}_{G}(H)-H$ and a finite index
subgroup $H^{\prime}$ of $H$. If we find the former then continue, and if we
find the latter then replace $H$ with $H^{\prime}$ and then continue. At least
one of these will terminate, and this ensures that
$H\neq\operatorname{Comm}_{G}(H)$. If $H$ is lonely, then just continue. We
now run the algorithm presented in Proposition 4.5. By Proposition 1.26,
exactly one of these two procedures will terminate, and if the first algorithm
terminates then it will output a presentation of a splitting over a subgroup
commensurable with $H$. ∎

It is conjectured that the problem of deciding whether a given hyperbolic
group has a finite quotient is undecidable, and in fact this problem is known
to be equivalent to the well-known conjecture that there exists a hyperbolic
group which is not residually finite [10]. Assuming this conjecture, it would
be undecidable whether a given quasiconvex subgroup is lonely. This means that
the hypothesis in Theorem 4.7 is likely necessary unless we place further
restrictions on $H$, such as requiring $H$ be residually finite.

We conclude by noting that one can easily drop the condition that $G$ be one-
ended. Indeed, if $H$ is finite then it is associated to a splitting if and
only if $e(G)\geq 1$. Otherwise, we may apply [11] to a maximal finite
splitting of $G$, which necessarily exists due to the accessibility result of
Dunwoody [15]. Then, $H$ is associated to a splitting of $G$ if and only if
$H$ is associated to a splitting of some one-ended vertex group of this
maximal finite splitting, up to conjugacy.

## References

  * [1] S. I. Adian.  Unsolvability of some algorithmic problems in the theory of groups.  Trudy Moskovskogo Matematicheskogo Obshchestva, 6:231–298, 1957\.
  * [2] G. N. Arzhantseva.  On quasiconvex subgroups of word hyperbolic groups.  Geometriae dedicata, 87(1):191–208, 2001.
  * [3] B. Barrett.  Computing JSJ decompositions of hyperbolic groups.  Journal of Topology, 11(2):527–558, 2018.
  * [4] G. Baumslag, C. F. Miller III, and H. Short.  Unsolvable problems about small cancellation and word hyperbolic groups.  Bulletin of the London Mathematical Society, 26(1):97–101, 1994\.
  * [5] M. Bestvina and G. Mess.  The boundary of negatively curved groups.  Journal of the American Mathematical Society, 4(3):469–481, 1991\.
  * [6] W. W. Boone.  The word problem.  Proceedings of the National Academy of Sciences, 44(10):1061–1065, 1958.
  * [7] B. H. Bowditch.  Cut points and canonical splittings of hyperbolic groups.  Acta mathematica, 180(2):145–186, 1998.
  * [8] B. H. Bowditch.  Splittings of finitely generated groups over two-ended subgroups.  Transactions of the American Mathematical Society, 354(3):1049–1078, 2002.
  * [9] M. R. Bridson and A. Haefliger.  Metric spaces of non-positive curvature, volume 319.  Springer Science & Business Media, 2013.
  * [10] M. R. Bridson and H. Wilton.  The triviality problem for profinite completions.  Inventiones mathematicae, 202(2):839–874, 2015.
  * [11] F. Dahmani and D. Groves.  Detecting free splittings in relatively hyperbolic groups.  Transactions of the American Mathematical Society, pages 6303–6318, 2008.
  * [12] F. Dahmani and V. Guirardel.  The isomorphism problem for all hyperbolic groups.  Geometric and Functional Analysis, 21(2):223–300, 2011.
  * [13] G.-A. Diao and M. Feighn.  The grushko decomposition of a finite graph of finite rank free groups: an algorithm.  Geometry & Topology, 9(4):1835–1880, 2005.
  * [14] C. Druţu and M. Kapovich.  Geometric group theory, volume 63.  American Mathematical Soc., 2018.
  * [15] M. J. Dunwoody.  The accessibility of finitely presented groups.  Inventiones mathematicae, 81:449–458, 1985.
  * [16] R. Geoghegan.  Topological methods in group theory, volume 243.  Springer Science & Business Media, 2007.
  * [17] V. V. Gerasimov.  Detecting connectedness of the boundary of a hyperbolic group.  Unpublished, 1999.
  * [18] R. Gitik.  On intersections of conjugate subgroups.  International Journal of Algebra and Computation, 27(04):403–419, 2017.
  * [19] M. Gromov.  Hyperbolic groups.  In Essays in group theory, pages 75–263. Springer, 1987.
  * [20] C. H. Houghton.  Ends of locally compact groups and their coset spaces.  Journal of the Australian Mathematical Society, 17(3):274–284, 1974\.
  * [21] W. Jaco, D. Letscher, and J. H. Rubinstein.  Algorithms for essential surfaces in 3-manifolds.  Contemporary Mathematics, 314:107–124, 2002.
  * [22] W. Jaco and U. Oertel.  An algorithm to decide if a 3-manifold is a Haken manifold.  Topology, 23(2):195–209, 1984.
  * [23] I. Kapovich.  Detecting quasiconvexity: algorithmic aspects.  Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), 25:91–99, 1996.
  * [24] I. Kapovich and N. Benakli.  Boundaries of hyperbolic groups.  arXiv preprint math/0202286, 2002.
  * [25] I. Kapovich and A. Myasnikov.  Stallings foldings and the subgroup structure of free groups.  arXiv preprint math/0202285, 2002.
  * [26] I. Kapovich and H. Short.  Greenberg’s theorem for quasiconvex subgroups of word hyperbolic groups.  Canadian Journal of Mathematics, 48(6):1224–1244, 1996.
  * [27] P. H. Kropholler and M. A. Roller.  Relative ends and duality groups.  Journal of Pure and Applied Algebra, 61(2):197–210, 1989.
  * [28] R. C. Lyndon, P. E. Schupp, R. Lyndon, and P. Schupp.  Combinatorial group theory, volume 188.  Springer, 1977.
  * [29] G. Niblo.  The singularity obstruction for group splittings.  Topology and its Applications, 119(1):17–31, 2002.
  * [30] G. Niblo, M. Sageev, P. Scott, and G. A. Swarup.  Minimal cubings.  International Journal of Algebra and Computation, 15(02):343–366, 2005.
  * [31] P. S. Novikov.  On the algorithmic unsolvability of the word problem in group theory.  Trudy Matematicheskogo Instituta imeni VA Steklova, 44:3–143, 1955\.
  * [32] P. Papasoglu.  An algorithm detecting hyperbolicity.  Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), 25:193–200, 1996.
  * [33] M. O. Rabin.  Recursive unsolvability of group theoretic problems.  Annals of Mathematics, pages 172–194, 1958.
  * [34] P. Scott.  Ends of pairs of groups.  Journal of Pure and Applied Algebra, 11(1-3):179–198, 1977.
  * [35] P. Scott.  The symmetry of intersection numbers in group theory.  Geometry & Topology, 2(1):11–29, 1998.
  * [36] P. Scott and G. A. Swarup.  Splittings of groups and intersection numbers.  Geometry & Topology, 4(1):179–218, 2000.
  * [37] P. Scott and G. A. Swarup.  Regular neighbourhoods and canonical decompositions for groups.  Société mathématique de France, 2003.
  * [38] P. Scott and T. Wall.  Topological methods in group theory.  In Homological group theory (Proc. Sympos., Durham, 1977), volume 36, pages 137–203, 1979.
  * [39] Z. Sela.  The isomorphism problem for hyperbolic groups I.  Annals of Mathematics, pages 217–283, 1995.
  * [40] J.-P. Serre.  Trees.  Springer Science & Business Media, 2002.
  * [41] J. R. Stallings.  On torsion-free groups with infinitely many ends.  Annals of Mathematics, pages 312–334, 1968.
  * [42] J. R. Stallings.  Group theory and three-dimensional manifolds.  Yale University Press, 1972.
  * [43] G. Swarup.  On the cut point conjecture.  Electronic Research Announcements of the American Mathematical Society, 2(2):98–100, 1996.
  * [44] N. Touikan.  Detecting geometric splittings in finitely presented groups.  Transactions of the American Mathematical Society, 370(8):5635–5704, 2018.
  * [45] A. Vonseel.  Ends of Schreier graphs of hyperbolic groups.  Algebraic & Geometric Topology, 18(5):3089–3118, 2018.