# On the non-discreteness of automorphism groups of Cayley graphs of Coxeter
groups

Federico Berlai  Department of Mathematics, University of the Basque Country
UPV/EHU, Barrio Sarriena s/n, 48940 Leioa, Spain<EMAIL_ADDRESS>and  Michal Ferov  School of Information and Physical Sciences, University of
Newcastle, University Drive, NSW 2308, Australia<EMAIL_ADDRESS>
###### Abstract.

In this work we characterise Cayley graphs of Coxeter groups with respect to
the standard generating set that admit uncountable vertex stabilisers. As a
corollary, we fully identify finitely generated Coxeter groups for which the
automorphism group of their Cayley graph with respect to the standard
generating set is not discrete when equipped with the permutation topology. As
an application, we also provide new explicit constructions of vertex-
transitive graphs of infinite degree that have locally compact automorphism
groups.

###### Contents

  1. 1 Introduction
    1. 1.1 Previously known results
  2. 2 Preliminaries
    1. 2.1 Graphs
    2. 2.2 Permutation topologies
    3. 2.3 Coxeter groups
    4. 2.4 Reduced forms, parabolic subgroups
  3. 3 Good separating sets
  4. 4 Configurations of local actions
  5. 5 Beyond locally finite graphs

##  1\. Introduction

An automorphism group of a connected graph $\Delta=(V\Delta,E\Delta)$
naturally admits a topology, namely the pointwise-convergence topology, also
called the permutation topology, whose base of open sets at the identity is
given by the family

$U_{F}:=\bigl{\\{}\varphi\in\operatorname{Aut}(\Delta)\mid\varphi(x)=x\
\forall x\in F\bigr{\\}},$

where $F\subseteq V\Delta$ is finite. That is, basic open sets at the identity
are finite intersections of vertex stabilisers. This topology is totally
disconnected. Whenever the graph $\Delta$ is locally finite, it is also
locally compact, so the group $\operatorname{Aut}(\Delta)$ is a totally
disconnected locally compact (TDLC) topological group. For more details on
permutation topologies, we refer the reader to Subsection 2.2.

Being locally compact or not, this topology is second countable whenever the
vertex set of the graph $\Delta$ is at most countable, so that in this case
the group $\operatorname{Aut}(\Delta)$ is discrete if and only if it is
countable.

A natural problem, thus, is to find conditions on a countable graph $\Delta$
that assure this topology on $\operatorname{Aut}(\Delta)$ to be non-discrete
(or, equivalently, that assure that the group $\operatorname{Aut}(\Delta)$ is
not countable). This is a well-known problem that attracted attention from
several branches of mathematics. For instance, we must mention the seminal
paper [4] of Halin that provides a graph theoretical characterisation of
uncountability. Nevertheless, stronger forms of Halin’s result were already
known among (and published by) logicians (compare also [5]).

In this work we address the above-mentioned problem for a particular family of
graphs, that is, Cayley graphs of Coxeter groups (we redirect the interested
reader to Subsection 2.3 for the precise definitions and notation that will be
used throughout this paper). In Theorem A we fully characterise, in terms of
the defining graph $\Gamma$, those countably generated Coxeter groups
$W_{\Gamma}$ for which
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(W_{\Gamma},S)\bigr{)}$ has
uncountable vertex stabilisers.

If $G$ is a group and $S$ is a generating set for $G$, then Cayley’s theorem
asserts that $G$ is a subgroup of
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(G,S)\bigr{)}$, and in particular
it is the subgroup consisting of label-preserving automorphisms of the
labelled graph $\operatorname{Cay}(G,S)$.

It is worth mentioning that recently results with an opposite flavour
(compared to ours) appeared in the literature. Indeed, it has been proved in
[6, Theorem 7] (see also [7, Theorem 1.1]) that for any finitely generated
group $G$ which is not abelian nor generalised dicyclic, if $S_{0}$ is a
finite symmetric generating set for $G$ then
$G\cong\operatorname{Aut}\bigl{(}\operatorname{Cay}(G,S)\bigr{)}$, where $S$
is the new generating set $(S_{0}\cup S_{0}^{2}\cup
S_{0}^{3})\setminus\\{e\\}$. Thus, the results from [6, 7] mean that is it is
always possible to find generating sets so that the Cayley graph has as few
automorphisms as possible.

The impulse that led us to prove Theorem A came from [8]. Indeed, in [8]
Taylor considers the similar question for Cayley graphs of finitely generated
right-angled Artin groups with respect to the standard generating set, and
proves that their automorphism group is countable if and only if the defining
graph is complete, that is if and only if the corresponding right-angled Artin
group is a finitely generated free abelian group.

To be able to state Theorem A we will need to introduce now some notation.
Given an simplicial graph $\Gamma=(V\Gamma,E\Gamma)$, not necessarily finite,
and a _weight_ function $m\colon V\Gamma\times
V\Gamma\to\\{1,2,\dots\\}\cup\\{+\infty\\}$ satisfying

  1. $c_{1})$

$m(x,y)=m(y,x)$ for all $x,y\in V\Gamma$;

  2. $c_{2})$

$m(x,y)=1$ if and only if $x=y$;

  3. $c_{3})$

$m(x,y)=+\infty$ if and only if $\\{x,y\\}\notin E\Gamma$,

we can consider the Coxeter group (notice, it will be finitely generated
exactly when the graph $\Gamma$ is finite)

(1) $W_{\Gamma}:=\langle V\Gamma\mid(xy)^{m(x,y)}=e\quad\forall\,x,y\in
V\Gamma\rangle,$

where $(xy)^{+\infty}=e$ by definition means that there is no relation between
the two generators $x$ and $y$. We call $\Gamma=(V\Gamma,E\Gamma,m)$ a
weighted graph. Notice that the Coxeter group $W_{\Gamma}$ is a right-angled
Coxeter group whenever the weight function $m$ only takes values in
$\\{1,2,+\infty\\}$. In this case, we usually forget about this function and
plainly consider simplicial graphs $\Gamma=(V\Gamma,E\Gamma)$: for vertices
$x\neq y$, we have that $m(x,y)=2$ if and only if $\\{x,y\\}\in E\Gamma$, and
$m(x,y)=+\infty$ if and only if $\\{x,y\\}\notin E\Gamma$.

Let us denote by $\operatorname{\mathcal{A}}_{\Gamma}$ the automorphism group
of the Cayley graph of $W_{\Gamma}$ with respect to the standard generating
set $V\Gamma$. Moreover, let $\operatorname{Aut}(\Gamma)$ denote the group of
symmetries of $\Gamma$ that preserve weights (in particular, if we reduce our
attention to right-angled Coxeter groups, then this is the automorphism group
of the unweighted defining graph). Then we have the following statement.

######  Theorem A.

_Let $\Gamma$ be a countable weighted graph and let
$\operatorname{\mathcal{C}}_{\Gamma}$ be the Cayley graph of the Coxeter group
$W_{\Gamma}$ with respect to the standard generating set $V\Gamma$. The
automorphism group $\operatorname{\mathcal{A}}_{\Gamma}$ has uncountable
vertex stabilisers if and only if either $\operatorname{Aut}(\Gamma)$ is
uncountable or there exists $x\in V\Gamma$ and a non-trivial automorphism
$\alpha\in\operatorname{Aut}(\Gamma)$ such that
$\alpha\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$. _

When the graph $\Gamma$ is finite, its group of weight-preserving symmetries
$\operatorname{Aut}(\Gamma)$ will be finite as well, and in particular not
uncountable. Notice that $\Gamma$ is finite if and only if the Coxeter group
$W_{\Gamma}$ is finitely generated, if and only if $\mathcal{C}_{\Gamma}$ is
locally finite.

Thus, in that case (which is the case of interest for us), Theorem A says that
the TDLC group $\mathcal{A}_{\Gamma}$ has uncountable vertex stabilisers, and
in particular it is itself uncountable, if and only if there exists a vertex
$x$ in the finite graph $\Gamma$ that has some specific property.

Thus, we immediately deduce the following result for TDLC groups:

######  Corollary B.

_Let $\Gamma$ be a finite weighted graph and let
$\operatorname{\mathcal{C}}_{\Gamma}$ be the Cayley graph of the Coxeter group
$W_{\Gamma}$ with respect to the standard generating set $V\Gamma$. The group
$\operatorname{\mathcal{A}}_{\Gamma}$ is a non-discrete TDLC group if and only
if there exists $x\in V\Gamma$ and a non-trivial automorphism
$\alpha\in\operatorname{Aut}(\Gamma)$ such that
$\alpha\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$. _

From Theorem A we immediately notice that the situation for (right-angled)
Coxeter groups is diametrically opposed to the one of right-angled Artin
groups: there exist graphs $\Gamma$ such that
$\operatorname{\mathcal{A}}_{\Gamma}$ is countable, and $\Gamma$ admits an
induced subgraph $\Delta$ for which $\operatorname{\mathcal{A}}_{\Delta}$ is
uncountable. As an example, we can consider the graphs

$\Gamma$$\Delta$

Further, we also note that the Coxeter groups $W_{\Gamma}$ and $W_{\Delta}$
are quasi-isometric. This means that the property of having a non-discrete
group of automorphism of the Cayley graph (with respect to the standard
generating set) is not a quasi-isometry invariant within the class of Coxeter
groups.

The paper is organised as follows. In Section 2 we introduce standard notation
and definitions for graphs, Coxeter groups, permutation topologies, and
provide the first results concerning the geometry of Cayley graphs of Coxeter
groups, and their automorphisms. In Section 3 and Section 4 we prove Theorem
A, each section concerned with one implication. We develop the notion of _good
separating set_ in Definition 3.1. By Lemma 3.2, the presence of a good
separating set is equivalent to the condition appearing in Theorem A. We
conclude with Section 5, where we show that the tools developed for the
project can be also used to give explicit constructions of vertex transitive
graphs that are not locally finite and yet still have locally-compact group of
automorphisms.

###  1.1. Previously known results

When working on this article, the authors were not aware of any previously
published results on (non)discreteness of Automorphism groups of Cayley graphs
of Coxeter groups. Only when this project was finished, we found out about [2]
and [3].

The following is is a restatement of [3, Theorem 5.12]

######  Theorem 1.1.

For a finite graph $\Gamma$, if there exists $x\in V\Gamma$ and a non-trivial
automorphism $\alpha\in\operatorname{Aut}(\Gamma)$ such that
$\alpha\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$ then
the automorphism group
$\operatorname{Aut}(\operatorname{Cay}(W_{\Gamma},V\Gamma))$ is discrete, and
is the semidirect product of $W_{\Gamma}$ and $\operatorname{Aut}(\Gamma)$. If
not, then if the group $W_{\Gamma}$ is word-hyperbolic in the sense of Gromov,
the automorphism group
$\operatorname{Aut}(\operatorname{Cay}(W_{\Gamma},V\Gamma))$ is not discrete.

Compared to the above, Corollary B is more general, as it makes no assumptions
on the geometry of the group $W_{\Gamma}$.

The results presented in Graham Clarke’s master thesis, in particular [2,
Theorem 4.2 and Proposition 4.31], are equivalent to Corollary B. However, we
feel that our methods are more general and that our proofs are less technical.
In particular, we intend to use the machinery of configurations of local
actions in further projects.

### Acknowledgements

When this work started, Federico Berlai was visiting the Department of
Mathematics of the University of the Basque Country UPV/EHU, whose hospitality
he greatly appreciates. Federico Berlai was supported by the Austrian Science
Foundation FWF, grant no. J4194, and gratefully acknowledges support from the
Basque Government Grant IT974-16, from the Spanish Government Grants
MTM2017-86802-P, partly with FEDER funds, and PID2020-117281GB-I00.

Majority of the work on this project was done while Michal Ferov was stuck in
Europe for 21 months due to Australian policy of closed borders during the
global pandemic of covid-19. During that time, and to the current day still,
Michal Ferov was supported by the Australian Research Council Laureate
Fellowship FL170100032 of professor George Willis.

The authors would like to thank Bruno Duchesne, Robert Kropholler, and Phillip
Wesolek for sharing with us an old unpublished preprint on related topics. We
thank Colin Reid for useful discussions and the suggestion to use our methods
to the setting of infinitely generated Coxeter groups. We thank Anne Thomas
for making us aware of a honours thesis written by her student Graham Clarke
[2] and the work of Haglund and Paulin [3].

##  2\. Preliminaries

In this section we fix the notation and collect known and preliminary results
that will be of use later. The neutral element of a group $G$ is denoted by
$e_{G}$, or simply by $e$ if the group is clear from the context. In case when
$G=\operatorname{Aut}(\Delta)$, where $\Delta$ is some graph, we will also use
$\operatorname{id}_{\Delta}$ to denote the neutral element in $G$, signifying
that it is the identity map $\operatorname{id}_{\Delta}\colon\Delta\to\Delta$.
Again, if the graph $\Delta$ is clear from the context we will omit the
subscript.

If $G$ is a group acting of a set $X$, then for a subset $S\subseteq X$ we
will use $\operatorname{stab}_{G}(S)$ to denote the _point-wise stabiliser_ of
$S$, i.e.

$\operatorname{stab}_{G}(S)=\\{g\in G\mid g\cdot s=s\mbox{ for all $s\in
S$}\\}.$

We will use the following conventions with respect to the naming of elements.
Given a Coxeter group $W_{\Gamma}$, we will denote by $x,y,\dots$ elements
from its (fixed) generating set $V\Gamma$, by $u,v,w,\dots$ the vertices in
its Cayley graph which we will identify with elements of the group
$W_{\Gamma}$, and by $U,V,W$ we will usually denote words over the alphabet
$V\Gamma$, i.e. elements of the free monoid $(V\Gamma)^{*}$ . The letter
$\sigma$ will usually denote an element from the automorphism group of the
graph $\Gamma$ associated to the Coxeter group, whereas $\alpha,\beta,\dots$
will denote elements of the automorphism group of the Cayley graph of
$W_{\Gamma}$.

###  2.1. Graphs

In this work we will focus at the same time on Cayley graphs, and on
simplicial graphs with weights associated to their edges. A Cayley graph of a
group $G$ with respect to a generating set $S$ is an $S$-labelled oriented
graph $\operatorname{Cay}(G,S)$, where the vertices of
$\operatorname{Cay}(G,S)$ are identified with elements of $G$ and an ordered
pair $(v,w)\in G\times G$ corresponds to an oriented edge labelled by $s\in S$
if and only if $w=vs$. In general, a Cayley graph may contain multiple edges
and loops. However, since in this note we will only consider Cayley graphs of
Coxeter groups generated by distinct non-trivial involutions, we might assume
that $\operatorname{Cay}(G,S)$ is a $S$-labelled simplicial graph, i.e. an
undirected graph without loops and multiple edges. When talking about
automorphisms of Cayley graphs, we will consider bijections of the vertex set
$G$ that preserve adjacency between vertices, but not necessarily the labels.

In the rest of this paper, by a graph we mean a simplicial graph, that is a
graph $\Gamma=(V\Gamma,E\Gamma)$ where $V\Gamma$ is a set and
$E\Gamma\subseteq\binom{V\Gamma}{2}$ is the set of edges, that is unoriented
pair of vertices, such that there are no loops (edges of the form $\\{x,x\\}$
for $x\in V\Gamma$) nor multiple edges between the same pair of vertices. Two
vertices $x,y\in V\Gamma$ are adjacent if $\\{x,y\\}\in E\Gamma$. A map
$\sigma\colon V\Gamma\to V\Gamma$ is an automorphism of the graph $\Gamma$ if
it is a bijection and $\\{v,w\\}\in E\Gamma$ if and only if
$\\{\sigma(v),\sigma(w)\\}\in E\Gamma$.

By a subgraph we will always mean an induced subgraph, i.e. a subgraph whose
edge set is fully determined by its vertices. Given two simplicial graphs
$\Gamma=(V\Gamma,E\Gamma)$ and $\Delta=(V\Delta,E\Delta)$, we say that
$\Gamma$ is an induced subgraph of $\Delta$ if $V\Gamma\subseteq V\Delta$ and
$V\Gamma=\binom{V\Gamma}{2}\cup E\Delta$.

Let $m\colon V\Gamma\times V\Gamma\to\\{1,2,\dots\\}\cup\\{+\infty\\}$ be a
function satisfying the following properties:

  1. $c_{1})$

$m(x,y)=m(y,x)$ for all $x,y\in V\Gamma$;

  2. $c_{2})$

$m(x,y)=1$ if and only if $x=y$;

  3. $c_{3})$

$m(x,y)=+\infty$ if and only if $\\{x,y\\}\notin E\Gamma$.

We call $(\Gamma,m)=(V\Gamma,E\Gamma,m)$ a _weighted graph_ and $m$ a _weight_
for $\Gamma$. When the context is clear, we will hide $m$ from the notation
and say that $\Gamma$ is a weighted graph.

A map $\sigma\colon V\Gamma\to V\Gamma$ is an automorphism of the weighted
graph $\Gamma$ if it is a bijection such that
$m(x,y)=m\bigl{(}\sigma(x),\sigma(y)\bigr{)}$ for all $x,y\in V\Gamma$. In
particular, if $\sigma$ is an automorphism of $\Gamma$ then $\\{x,y\\}\in
E\Gamma$ if and only if $\\{\sigma(x),\sigma(y)\\}\in E\Gamma$. The group of
automorphisms of a weighted graph $\Gamma$ is denoted by
$\operatorname{Aut}(\Gamma)$.

If $m$ is a weight such that $m(V\Gamma\times
V\Gamma)\subseteq\\{1,2,+\infty\\}$ then, by definition of weight, $m(x,y)=1$
if and only if $x=y$, and $m(x,y)=2$ if and only if $\\{x,y\\}\in E\Gamma$,
and $m(x,y)=+\infty$ if and only if $\\{x,y\\}\notin E\Gamma$. In this case, a
bijection of $V\Gamma$ is an automorphism of the weighted graph $(\Gamma,m)$
if and only if it is an automorphism of the unweighted graph $\Gamma$.

A proper subset of vertices $S\subsetneq V\Gamma$ is a _separating set_ if the
induced subgraph spanned by $V\Gamma\setminus S$ is disconnected. By
definition, if $\Gamma$ is already disconnected, the empty set is a separating
set for the graph $\Gamma$.

###  2.2. Permutation topologies

In this subsection we recall the notion of permutation topology and some basic
facts. Readers familiar with the terminology may wish to skip this subsection.

Let $X$ be a set and suppose that $G$ is a group acting on $X$. There is a
group topology on $G$ naturally arising from its action on $X$, namely the
_permutation topology_ or sometimes called the _point-wise convergence
topology_. The base of neighbourhoods of the identity consists of the
collection of sets of the form $\operatorname{stab}_{G}(F)$, where $F\subset
X$ is finite.

It then follows that for an element $g\in G$ its base of neighbourhoods
consists of all the sets of the form

$\mathcal{B}(g,F)=\\{f\in G\mid f\restriction_{F}=g\restriction_{F}\\}.$

where, again, the subset $F\subset X$ is finite.

The following statement then follows immediately from the definition.

######  Lemma 2.1.

A subgroup $H\leq G$ is open in the permutation topology on $G$ arising from
an action on a set $X$ if and only if it contains the pointwise stabiliser of
some finite set $F\subset X$.

Quite clearly, the kernel of the action is contained in every neighbourhood of
the identity, so it is the smallest (with respect to inclusion) open subset
containing the identity. In fact, the kernel of the action is the connected
component of the identity - it then follows that the permutation topology is
totally disconnected if an only if the action is faithful.

Further, if the action is faithful, then for each tuple of distinct elements
$f,g\in G$ there exists $x\in X$ such that $f\cdot x\neq g\cdot x$. In
particular, this means $\mathcal{B}(f,\\{x\\})$ and $\mathcal{B}(g,\\{x\\})$
are disjoint open neighbourhoods of $f$ and $g$ respectively. Conversely,
following the definition of permutation topology, we see that if the
permutation topology arising from the action on $X$ is not Hausdorff, then
there exists $g\in X$ contained in every neighbourhood of the identity,
therefore $g\cdot x=x$ for all $x\in X$.

The following lemma sums up the following two observations.

######  Lemma 2.2.

The permutation topology on $G$ is Hausdorff if and only if the action of $G$
on $X$ is faithful. Furthermore, $G$ is totally disconnected if and only if
the action is faithful.

Within the scope of this paper, $X$ will be a vertex transitive simplicial
graph, with $X=(VX,EX)$, where $VX$ denotes the set of vertices of $X$ and
$EX\subseteq\binom{VX}{2}$ denotes the set of edges of $X$, and
$G\leq\operatorname{Aut}(X)$. In particular, this means that $G$ is totally
disconnected. In the case when $X$ is locally finite, i.e. when each vertex is
adjacent to only finitely many vertices, it can be easily seen that
$\operatorname{Aut}(X)$ is locally compact.

###  2.3. Coxeter groups

The _right-angled Coxeter group_ $W_{\Gamma}$ (also abbreviated by RACG)
associated to a graph $\Gamma=(V\Gamma,E\Gamma)$ without weights is the group
given by the presentation

$W_{\Gamma}:=\langle V\Gamma\mid x^{2}=e\ \forall x\in V\Gamma,\,xy=yx\
\forall\\{x,y\\}\in E\Gamma\rangle.$

More generally, a _Coxeter group_ is a group (not necessarily finitely
generated) given by the presentation of the form

(2) $W:=\left\langle
x_{1},\dots,x_{n},\dots\mid\left(x_{i}x_{j}\right)^{m_{i,j}}=e\ \forall
i,j\right\rangle,$

where the exponents $m_{i,j}\in\\{1,2,\dots\\}\cup\\{+\infty\\}$ satisfy:

  1. (1)

$m_{i,j}=m_{j,i}$ for all $i,j$;

  2. (2)

$m_{i,j}=1$ if and only if $i=j$, that is, generators are involutions;

  3. (3)

if $m(x,y)=+\infty$ then, by definition, there is no relation between $x_{i}$
and $x_{j}$.

In the literature the set $S=\\{x_{1},\dots,x_{n}\\}$, when finite, is called
a _Coxeter generating set_ , and the pair $(W,S)$ is called a _Coxeter system_
, although in this paper we will not enforce this terminology.

To each Coxeter system (we maintain the notation of Equation (2)) we can
associate a weighted graph $\Gamma$ in the following way. The vertex set
$V\Gamma$ is defined to be the set $\\{x_{1},\dots,x_{n},\dots\\}$. Two
different vertices $x_{i}$ and $x_{j}$ are joined by an edge in $\Gamma$ if
and only if $m_{i,j}<+\infty$, and the weight map is defined as
$m(x_{i},x_{j}):=m_{i,j}$.

Therefore, any Coxeter group is of the form

(3) $W_{\Gamma}:=\langle V\Gamma\mid(xy)^{m(x,y)}=e\,\,\forall x,y\in
V\Gamma\rangle,$

where $(\Gamma,m)$ is a weighted graph. Again, $(xy)^{+\infty}=e$ means that
there is no relation imposed between the generators $x$ and $y$.

Notice that a Coxeter group is a right-angled Coxeter group if and only if its
weight function satisfies $m(V\Gamma\times
V\Gamma)\subseteq\\{1,2,+\infty\\}$. That is, we can think of right-angled
Coxeter groups as Coxeter groups in which all edges have weight equal to two.

Given a Coxeter group $W_{\Gamma}$, we denote by
$\operatorname{\mathcal{C}}_{\Gamma}$ the Cayley graph of $W_{\Gamma}$ with
respect to the generating set $V\Gamma$, that is the graph whose vertex set is
$W_{\Gamma}$, and such that two vertices $v,w\in W_{\Gamma}$ are joined by an
edge if and only if there exists $x\in V\Gamma$ satisfying $v=wx$. In this
case, the edge $\\{v,w\\}$ is _labelled_ by the letter $x$, that is
$\operatorname{\mathcal{C}}_{\Gamma}$ is labelled by the set $V\Gamma$.

Notice that the Cayley graph is regular, connected, and each vertex has
valency $\lvert V\Gamma\rvert$, each incident edge being labelled by exactly
one element of $V\Gamma$. In particular, this Cayley graph will be locally
finite if and only if the generating set $V\Gamma$ is finite. Given a vertex
$v$ in the Cayley graph and a natural number $n$, we denote by $B(v,n)$ the
ball of radius $n$ in $\operatorname{\mathcal{C}}_{\Gamma}$ around the vertex
$v$.

We denote by $\operatorname{\mathcal{A}}_{\Gamma}$ the group of automorphisms
$\operatorname{Aut}(\operatorname{\mathcal{C}}_{\Gamma})$. When the graph
$\Gamma$ is clear from the context, we will often drop the subscript $\Gamma$
to ease notation. We are not imposing that elements of
$\operatorname{\mathcal{A}}_{\Gamma}$ preserve labels.

###  2.4. Reduced forms, parabolic subgroups

Suppose that $\Gamma$ is an unweighted graph (or, equivalently, a graph with a
weight function whose images are contained in $\\{1,2,+\infty\\}$). Given a
pair of vertices $x,y\in V\Gamma$, that is a pair of canonical generators of
the right-angled Coxeter group $W_{\Gamma}$, we have that $x$ and $y$ are
joined by an edge in $\Gamma$ if and only if, for any vertex $v$ in the Cayley
graph $\operatorname{\mathcal{C}}_{\Gamma}$, we find an embedded cycle of
length four in $\operatorname{\mathcal{C}}_{\Gamma}$ that has $v$ as a vertex
and where opposite sides of the square are labelled by $x$ and $y$
respectively (compare with Figure 1). We call such embedded cycle a _commuting
square_ at $v$ with labels $x$ and $y$.

$v$$vx$$vy$$vxy$ Figure 1. Commuting square at $v$.

The same observation extends to weighted graphs, that is to Cayley graphs of
Coxeter groups: given any vertex $v$ in $\operatorname{\mathcal{C}}_{\Gamma}$,
two generators $x$ and $y$ will alternatively label the edges of an embedded
cycle of even length $2l$ (one of whose vertices is $v$) if and only if
$\\{x,y\\}\in E\Gamma$ and $m(x,y)=l$. We call this embedded cycle the
_relation cycle_ of $x$ and $y$ at the vertex $v$. That is, commuting squares
are exactly the relation cycles of length four.

To prove Lemma 2.8 we need some notions for Coxeter groups. Let
$\Gamma=(V\Gamma,E\Gamma,m)$ be a weighted simplicial graph, and consider the
free monoid $V\Gamma^{*}$, that is the set of finite sequences of
$V\Gamma$-elements, which we call _words_. The elements $x_{1},\dots,x_{r}$ in
a word $W=(x_{1},\dots,x_{r})\in V\Gamma^{*}$ are called the _syllables_ of
the word, and we say that $r$ is the _length_ of the word, writing $r=|W|$. We
will use $\epsilon$ to denote the empty word.

Any such finite sequence $(x_{1},\dots,x_{r})$, or word, defines a group
element via the evaluation map $\omega:V\Gamma^{*}\to W_{\Gamma}$ defined by

$\omega\bigl{(}x_{1},\dots,x_{r}\bigr{)}:=x_{1}\dots x_{r}\in W_{\Gamma},$

where $\omega(\epsilon):=e\in W_{\Gamma}$. We say that the word
$(x_{1},\dots,x_{r})$ represents the group element
$\omega\bigl{(}x_{1},\dots,x_{r}\bigr{)}$. Notice that different words may
represent the same group element.

Let us consider the following _elementary simplifications_ on $V\Gamma^{*}$:

  * $s_{1})$

if $y\in V\Gamma$ and two consecutive syllables of $(x_{1},\dots,x_{r})$ are
equal to $y$, then remove these two syllables to obtain a sequence of length
$r-2$;

  * $s_{2})$

if $x,y\in V\Gamma$ and $m(x,y)$ consecutive syllables of
$(x_{1},\dots,x_{r})$ are alternatively equal to $x$ and $y$, then in these
$m(x,y)$ syllables replace all occurrences of $x$ with $y$ and vice versa.

If a word $w_{2}$ can be obtained from a word $w_{1}$ with finitely many
elementary simplifications, then $\omega(w_{1})=\omega(w_{2})$. We call the
second kind of simplification a _braid relation_. Rephrasing it, a braid
relation is a substitution of the form

$\bigl{(}x_{1},\dots,\underbrace{x,y,x,\dots}_{\text{length
}m(x,y)},\dots,x_{r}\bigr{)}\quad\longmapsto\quad\bigl{(}x_{1},\dots,\underbrace{y,x,y,\dots}_{\text{length
}m(x,y)},\dots,x_{r}\bigr{)}$

among finite sequences in $V\Gamma^{*}$. In particular, it must be that
$m(x,y)\neq+\infty$ for a braid relation to occur. Moreover, as they are
tautologically true, we will never consider braid relations for $x=y$, that is
for $m(x,y)=1$, as in this case the braid relation does not modify the
sequence. Braid relations do not affect length of words, whereas a
simplification of the first kind reduces the length by two.

In the context of right-angled Coxeter groups, a braid relation is called
_syllable swapping_ , because in that case we replace the subword $(x,y)$ with
the word $(y,x)$.

The following fundamental result (compare [1, Theorem 3.3.1]) characterises
words of minimal length among words representing a given element $g\in
W_{\Gamma}$.

######  Theorem 2.3.

Let $W_{\Gamma}$ be a Coxeter group and $w_{1},w_{2}\in V\Gamma^{*}$ be two
words of minimal length representing an element $g\in W_{\Gamma}$. Then
$w_{1}$ can be obtained from $w_{2}$ applying a finite number of braid
relations, and vice versa.

If $g\in W_{\Gamma}$ is an element of the Coxeter group $W_{\Gamma}$, with
$\lVert g\rVert$ we denote the length of any word $w\in V\Gamma^{*}$ of
minimal length representing the element, i.e.

$\|g\|=\min_{W\in V\Gamma^{*}}\\{|W|\mid\omega(W)=g\\}$

An automorphism $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ and a vertex
$v$ in the Cayley graph $\operatorname{\mathcal{C}}_{\Gamma}$ uniquely define
an automorphism $\sigma(\alpha,v)\in\operatorname{Aut}(\Gamma)$, as follows.
As $\alpha$ is an automorphism, it induces a bijection between the edges
incident to $v$ and the edges incident to $\alpha(v)$, and therefore a
bijection $\sigma(\alpha,v)\colon V\Gamma\to V\Gamma$ between their labels. We
call $\sigma(\alpha,v)$ the _local action of $\alpha$ at $v$_ and we claim
that this map is an automorphism of the weighted graph $\Gamma$, that is, it
preserves the weights $m(x,y)$ for all $x,y\in V\Gamma$.

To demonstrate this, let $\\{x_{1},x_{2}\\}\in E\Gamma$ be an edge, and let
$w_{1},w_{2}$ be vertices in the Cayley graph
$\operatorname{\mathcal{C}}_{\Gamma}$ adjacent to $v$ such that
$\\{v,w_{1}\\}$ is labelled by $x_{1}$ and $\\{v,w_{2}\\}$ is labelled by
$x_{2}$. In the Cayley graph $\operatorname{\mathcal{C}}_{\Gamma}$ we then see
two relation cycles of length $2m(x_{1},x_{2})$ at the vertices $v$ and
$\alpha(v)$, labelled by $x_{1},x_{2}$ and by $\alpha(x_{1}),\alpha(x_{2})$
respectively ($m(x_{1},x_{2})=2$ in Figure 2, and different colours correspond
to different labels: blue for $x_{1}$, red for $x_{2}$, cyan for the label of
$\\{\alpha(v),\alpha(w_{1})\\}$, magenta for the label of
$\\{\alpha(v),\alpha(w_{2})\\}$).

$v$$w_{2}$$w_{1}$$w$

$\alpha(v)$$\alpha(w_{2})$$\alpha(w_{1})$$\alpha(w)$

Figure 2. Graph automorphisms preserve the length of embedded cycles.

Because $\alpha$ is an automorphism, the relation cycle at $v$ with labels
$x_{1}$ and $x_{2}$ must be mapped to the relation cycle at $\alpha(v)$ with
labels $\sigma(\alpha,v)(x_{1})$ and $\sigma(\alpha,v)(x_{2})$. Therefore
$\sigma(\alpha,v)(x_{1})$ and $\sigma(\alpha,v)(x_{2})$ are joined by an edge
in $\Gamma$ and
$m(x_{1},x_{2})=m\bigl{(}\sigma(\alpha,v)(x_{1}),\sigma(\alpha,v)(x_{2})\bigr{)}$,
that is the bijection $\sigma(\alpha,v)$ preserves weights. Therefore
$\sigma(\alpha,v)\in\operatorname{Aut}(\Gamma)$. This means that we can think
of $\sigma$ as a well defined map

$\sigma\colon\operatorname{\mathcal{A}}_{\Gamma}\times
W_{\Gamma}\to\operatorname{Aut}(\Gamma)$

and, similarly, for a given $\alpha\in\operatorname{\mathcal{A}}\Gamma$ the
map $\sigma(\alpha,-)\colon W_{\Gamma}\to\operatorname{Aut}(\Gamma)$ is well-
defined.

######  Definition 2.4.

Let $\Gamma$ be a weighted graph and consider the Cayley graph
$\operatorname{\mathcal{C}}_{\Gamma}$ of the associated Coxeter group. We say
that $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ is

  1. (1)

a _translation_ if $\sigma(\alpha,v)=\operatorname{id}_{\Gamma}$ for all $v\in
W_{\Gamma}$, that is for all edges $\\{v,w\\}$ in
$\operatorname{\mathcal{C}}_{\Gamma}$ the edges $\\{v,w\\}$ and
$\\{\alpha(v),\alpha(w)\\}$ have the same label;

  2. (2)

an _almost translation_ if $\sigma(\alpha,v)=\sigma(\alpha,w)$ for all
vertices $v,w$ in $\operatorname{\mathcal{C}}_{\Gamma}$.

Equivalently, one can say that $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$
is a translation if and only if $\sigma(\alpha,v)=\operatorname{id}_{\Gamma}$
for all $v\in W_{\Gamma}$, and that $\alpha$ is an almost translation if and
only if the map $\sigma(\alpha,-)$ is constant.

We call these automorphisms translations because they correspond to left
multiplications by $W_{\Gamma}$-elements, as recorded in Lemma 2.6.

Given $w\in W_{\Gamma}$, let us define $L_{w}\colon W_{\Gamma}\to W_{\Gamma}$
as $L_{w}(v):=wv$. As the Cayley graph $\operatorname{\mathcal{C}}_{\Gamma}$
is a right-Cayley graph, $L_{w}$ is an element of the automorphism group of
$\operatorname{\mathcal{C}}_{\Gamma}$, that is
$L_{w}\in\operatorname{\mathcal{A}}_{\Gamma}$. In the following lemma we
record that $w\mapsto L_{w}$ is an injective homomorphism whose image is the
subgroup generated by translations of $\operatorname{\mathcal{C}}_{\Gamma}$.
More generally, this lemma works for any group, not just for Coxeter groups,
and any generating set.

######  Lemma 2.5.

Let $G$ be a group, let $S$ be a generating set for $G$, and consider the
(right) Cayley graph $\operatorname{Cay}(G,S)$. The map $w\mapsto L_{w}$ is an
injective homomorphism, and therefore $G$ embeds as a subgroup of
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(G,S)\bigr{)}$.

Moreover, if two translations $\alpha$ and $\beta$ in
$\operatorname{Cay}(G,S)$ are such that $\alpha(v)=\beta(v)$ for some vertex
$v\in\operatorname{Cay}(G,S)$, then $\alpha=\beta$. In particular, the set of
all translations in $\operatorname{Cay}(G,S)$ is a subgroup isomorphic to $G$.

###### Proof.

The map $\iota\colon
G\to\operatorname{Aut}\bigl{(}\operatorname{Cay}(G,S)\bigr{)}$ defined by
$w\mapsto L_{w}$ is an injective homomorphism by Cayley’s theorem, and $L_{w}$
is a label-preserving for any $w\in G$.

Let $v\in\operatorname{Cay}(G,S)$ be such that $\alpha(v)=\beta(v)$. Thus, as
$\alpha$ and $\beta$ are label-preserving, we deduce that they agree on the
ball of radius one around $v$, that is $\alpha(u)=\beta(u)$ for all $u\in
B(v,1)$. As the Cayley graph is a connected graph, repeating this argument
shows that $\alpha=\beta$.

To prove that the image of the map $\iota$ is the set of translations in the
group $\operatorname{Aut}\bigl{(}\operatorname{Cay}(G,S)\bigr{)}$, that is the
set of label-preserving automorphisms, consider a translation
$\alpha\in\operatorname{Aut}\bigl{(}\operatorname{Cay}(G,S)\bigr{)}$. Then
$\alpha(e)=L_{\alpha(e)}(e)$, and thus by what proved so far
$\alpha=L_{\alpha(e)}$. ∎

Thus, the subgroup of label-preserving automorphisms of a Cayley graph
$\operatorname{Cay}(G,S)$ does not depend on the choice of generating set $S$.
Specialising Lemma 2.5 to our case of interest, that is to Coxeter groups, we
obtain:

######  Lemma 2.6.

Let $\alpha$ and $\beta$ be two translations in
$\operatorname{\mathcal{A}}_{\Gamma}$ whose image coincide on a vertex
$v\in\operatorname{\mathcal{C}}_{\Gamma}$. Then $\alpha=\beta$. In particular,
the set of all translations in $\operatorname{\mathcal{A}}_{\Gamma}$ is a
subgroup isomorphic to $W_{\Gamma}$.

In view of Lemma 2.6, with a slight abuse of notation we denote the set of
translations by $W_{\Gamma}$. Thus, the expressions $y\in W_{\Gamma}$ and
$L_{y}\in W_{\Gamma}$ make both sense. The first will mean that we are
considering the element $y$ is in the group $W_{\Gamma}$, whereas the second
will mean that we are considering the translation $L_{y}$ in
$\operatorname{\mathcal{A}}_{\Gamma}$.

######  Lemma 2.7.

The subgroup of $\operatorname{\mathcal{A}}_{\Gamma}$ generated by almost
translations that fix the identity element is isomorphic to
$\operatorname{Aut}(\Gamma)$.

###### Proof.

Given $\sigma\in\operatorname{Aut}(\Gamma)$ we construct an almost translation
$\alpha$ that fixes the identity vertex and such that
$\sigma(\alpha,v)=\sigma$ for any vertex
$v\in\operatorname{\mathcal{C}}_{\Gamma}$, and we will then prove that the map
$\sigma\mapsto\alpha$ is an isomorphism.

The construction is clear if $\sigma=\operatorname{id}_{\Gamma}$ is the
identity automorphism, because we choose $\alpha$ to be the identity
automorphism of $\operatorname{\mathcal{C}}_{\Gamma}$. Hence, suppose
$\sigma\neq\operatorname{id}_{\Gamma}$. Incident to any vertex there are
exactly $\lvert V\Gamma\rvert$ edges, each one being labelled by a different
vertex of $\Gamma$.

Let us define the automorphism $\alpha$. First of all, we impose that
$\alpha(e)=e$. If $w\in B(e,1)\setminus\\{e\\}$ is a vertex such that the edge
$\\{e,w\\}$ is labelled by the letter $x$ and $\sigma(x)=y\in V\Gamma$, then
we define $\alpha(w):=\tilde{w}$, where $\\{e,\tilde{w}\\}$ is the (unique)
edge in $\operatorname{\mathcal{C}}_{\Gamma}$ incident to $e$ that is labelled
by $y$. Notice that $\tilde{w}\in B(e,1)\setminus\\{e\\}$. This just means
that $\sigma(\alpha,e)=\sigma$.

To complete the definition of $\alpha$ we proceed as follows, inductively. Let
$w\in\operatorname{\mathcal{C}}_{\Gamma}$ be a vertex at distance $l\geqslant
1$ from $e$, consider a path $\gamma$ with vertices
$(e,w_{1},w_{2},\dots,w_{l}=w)$ of length $l$ that connects $e$ to $w$ in
$\operatorname{\mathcal{C}}_{\Gamma}$, and suppose that $\alpha$ has already
been defined on $B(e,l-1)$. Therefore $w_{l-1}$ is a vertex at distance $l-1$
from $e$, and by inductive hypothesis $\alpha(w_{l-1})$ has been defined. Then
$\alpha(w)$ is defined to be the (unique) vertex such that, if the edge
$\\{w_{l-1},w_{l}\\}$ has label $x$, then the edge
$\\{\alpha(w_{l-1}),\alpha(w)\\}$ has label $\sigma(x)$.

We claim that this is well-defined, that is the assignment does not depend on
the path connecting $e$ to $w$. Indeed, consider another path
$\gamma^{\prime}=(e,w_{1}^{\prime},w_{2}^{\prime},\dots,w_{l}^{\prime}=w)$ of
length $l$ connecting $e$ to $w$ in $\operatorname{\mathcal{C}}_{\Gamma}$, let
$w_{\gamma}$ and $w_{\gamma^{\prime}}$ be the two vertices obtained when
considering $\gamma$ and $\gamma^{\prime}$. We want to prove that
$w_{\gamma}=w_{\gamma^{\prime}}$.

The claim is clear if $w_{l-1}=w_{l-1}^{\prime}$, that is if the two paths
share the last edge. It can also be shown that if the word that can be read on
$\gamma^{\prime}\circ\gamma^{-1}$ is of the form $(xy)^{l}$ for some
$\\{x,y\\}\in E\Gamma$, then $w_{\gamma}=w_{\gamma^{\prime}}$. For the general
case, suppose that the last edge of $\gamma$ and $\gamma^{\prime}$ are
different. From Theorem 2.3 we know that the words read on $\gamma$ and
$\gamma^{\prime}$ can be obtained from one another by applying finitely many
braid relations. In particular, the label $x$ of $\\{w_{l-1},w\\}$ and the
label $y$ of $\\{w_{l-1}^{\prime},w\\}$ must be joined by an edge in $\Gamma$.
Therefore, we can reduce this case to the previous, that is a tail subpath of
$\gamma$ and of $\gamma^{\prime}$ belong to a induced circle of length
$2m_{x,y}$ in $\operatorname{\mathcal{C}}_{\Gamma}$, and thus
$w_{\gamma}=w_{\gamma^{\prime}}$.

That is, we defined a bijection $\alpha$ of the vertices of the Cayley graph
which preserves adjacency between vertices, that is an automorphism of the
Cayley graph $\operatorname{\mathcal{C}}_{\Gamma}$.

It is now easy to check that $\sigma\mapsto\alpha$ is a homomorphism of
groups, and that it is indeed injective and surjective. ∎

With a slight abuse of notation, we will identify $\operatorname{Aut}(\Gamma)$
with the subgroup of $\operatorname{\mathcal{A}}_{\Gamma}$ consisting of
almost translations that fix the identity vertex.

Of course, there is nothing special about the identity vertex, and therefore
we have:

######  Lemma 2.8.

Let $\Gamma$ be a graph, $\sigma\in\operatorname{Aut}(\Gamma)$, and $v$ be a
vertex in $\operatorname{\mathcal{C}}_{\Gamma}$. Then there exists an
automorphism $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ such that
$\alpha(v)=v$ and such that $\sigma(\alpha,w)=\sigma$ for all vertices $w$ in
$\operatorname{\mathcal{C}}_{\Gamma}$.

Any almost translation that fixes a vertex in
$\operatorname{\mathcal{C}}_{\Gamma}$ is conjugated to an element of
$\operatorname{Aut}(\Gamma)$, that is to an almost translation that fixes the
identity vertex. Indeed, if $\alpha$ is such that $\alpha(v)=v$ for some
$v\in\operatorname{\mathcal{C}}_{\Gamma}$ then

$\alpha=L_{v}\beta L_{v^{-1}},$

where $R_{v}\in W_{\Gamma}$ and
$\beta\in\operatorname{Aut}(\Gamma)\leqslant\operatorname{\mathcal{A}}_{\Gamma}$.
Moreover, if $w$ is another fixed point of $\alpha$ then $L_{v}\beta
L_{v^{-1}}=L_{w}\beta L_{w^{-1}}$. We have that
$\sigma(\alpha,v)=\sigma(\beta,e)$.

In the next corollary we maintain the notation of Lemma 2.8.

######  Corollary 2.9.

Let $\Gamma$ be a graph, $\sigma\in\operatorname{Aut}(\Gamma)$, and $v$ be a
vertex in $\operatorname{\mathcal{C}}_{\Gamma}$. The automorphism $\alpha$
fixes pointwise the set

$\Bigl{\\{}w\in V\Gamma\mid\begin{array}[]{c}\hbox{there is a path in
$\operatorname{\mathcal{C}}_{\Gamma}$ connecting $w$ to $v$}\\\ \hbox{whose
edges are all labelled by fixed points of $\sigma$}\end{array}\Bigr{\\}}.$

######  Lemma 2.10.

The subgroup of $\operatorname{\mathcal{A}}_{\Gamma}$ generated by almost
translations is isomorphic to $W_{\Gamma}\rtimes\operatorname{Aut}(\Gamma)$.
In particular, if the simplicial graph $\Gamma$ is finite, then
$W_{\Gamma}\rtimes\operatorname{Aut}(\Gamma)$ is finitely generated.

###### Proof.

It is clear that $W_{\Gamma}$ and $\operatorname{Aut}(\Gamma)$, that is the
subgroup of translations and the subgroup of almost translation fixing the
identity vertex, intersect trivially.

Let us now consider an almost translation $\alpha$ that does not fix any
vertex in $\operatorname{\mathcal{C}}_{\Gamma}$, suppose it is not a
translation, that is $\sigma(\alpha,-)\neq\operatorname{id}_{\Gamma}$, so that
$\alpha(e)\neq e$. Let us consider the translation $L_{\alpha(e)}\in
W_{\Gamma}$ that maps the vertex $e$ to the vertex $\alpha(e)$. Then we have
that

$\alpha=\bigl{(}L_{\alpha(e)}\cdot(L_{\alpha(e)})^{-1}\bigr{)}\cdot\alpha=L_{\alpha(e)}\cdot\bigl{(}(L_{\alpha(e)})^{-1}\cdot\alpha\bigr{)}.$

Notice that $(L_{\alpha(e)})^{-1}\cdot\alpha$ is an almost translation, and by
construction it fixes the identity vertex, that is, it is an element of
$\operatorname{Aut}(\Gamma)$. Thus, any almost translation in
$\operatorname{\mathcal{A}}_{\Gamma}$ can be expressed as a product of an
element from $W_{\Gamma}$ and an element from $\operatorname{Aut}(\Gamma)$.

Moreover, the subgroup $W_{\Gamma}$ of translation is normal in the subgroup
of $\operatorname{\mathcal{A}}_{\Gamma}$ of almost translations. Indeed, if
$\alpha$ is an almost translation and $L_{w}\in W_{\Gamma}$, then
$\alpha^{-1}L_{w}\alpha=L_{\alpha(w)}$.

Therefore, the subgroup of almost translations splits as the semidirect
product $W_{\Gamma}\rtimes\operatorname{Aut}(\Gamma)$. If the graph $\Gamma$
is finite, then $W_{\Gamma}$ is finitely generated and
$\operatorname{Aut}(\Gamma)$ is finite, so that
$W_{\Gamma}\rtimes\operatorname{Aut}(\Gamma)$ must be finitely generated as
well. So, the lemma is proved. ∎

We finish this section with three examples, the first of a two-ended right-
angled Coxeter group, the second of a one-ended right-angled Coxeter group,
and the third of a infinitely-ended one. The first two examples have Cayley
graphs with countable automorphism group, whereas the third has a Cayley graph
with uncountable automorphism group.

######  Example 2.11.

As an example of two-ended right-angled Coxeter group, let us consider the
graph $\Gamma$

that is a complete graph on four vertices with an edge removed, all of whose
edges have weight two. Its Cayley graph is

and the automorphism $\operatorname{\mathcal{A}}_{\Gamma}$ is countable by
Proposition 3.4.

######  Example 2.12.

Suppose that $\Gamma=C_{4}$ is a cycle of lenght four all of whose edges have
weight two (that is, the corresponding Coxeter group is right-angled), and
$\sigma\in\operatorname{Aut}(\Gamma)$ is the reflection along the dashed axis

Let $v$ be a vertex in $\operatorname{\mathcal{C}}_{\Gamma}$ (in the picture
$v$ is at distance one from the identity vertex), which in this case is the
infinite two-dimensional grid depicted in the following picture. The
automorphism $\sigma$ induces the automorphism
$\alpha\in\operatorname{\mathcal{C}}_{\Gamma}$, which is the reflection along
the dashed diagonal passing through $v$, such that $\sigma(\alpha,v)=\sigma$.

$e$$v$

If $\beta$ is the reflection along the dashed diagonal passing through $e$,
then $\alpha=L_{v}\beta L_{v^{-1}}$. The axes of the two reflexions $\alpha$
and $\beta$ are perpendicular because the automorphism $L_{v}$ fixes the edge
$\\{e,v\\}$ inverting the two vertices, that is $L_{v}(e)=v$ and $L_{v}(v)=e$.
Notice that $\sigma(\alpha,v)=\sigma(\beta,e)$.

More generally, if we consider a cycle $C_{n}$ of length $n\geqslant 4$, we
obtain a tessellation of the plane by squares.

In the Cayley graph $\operatorname{Cay}(C_{5})$ at any vertex $v$ there are
five, that is $\lvert V{C_{5}}\rvert$, incident vertices that form commuting
squares (corresponding to edges of the cycle $C_{5}$):

$v$

This pattern covers a plane and the automorphism group of such Cayley graphs
is finitely generated, and therefore countable, as we will deduce from
Proposition 3.4.

######  Example 2.13.

Let us now consider the disconnected graph $\Gamma$

where the only edge has weight two. Let $\Gamma_{1}$ denote the connected
component with two vertices and one edge, and let $\Gamma_{2}$ be the
connected component consisting of one vertex. We have that
$\operatorname{Aut}(\Gamma_{1})=\\{e,\sigma\\}$ is the cyclic group of order
two and that $\operatorname{\mathcal{C}}_{\Gamma_{1}})$ is a commuting square.
Let $v$ be a vertex of $\operatorname{\mathcal{C}}_{\Gamma_{1}})$. In view of
Corollary 2.9, the automorphism $\sigma$ (which switches the two vertices of
$\Gamma_{1}$) induces an automorphism
$\alpha\in\operatorname{Aut}\bigl{(}\operatorname{\mathcal{C}}_{\Gamma_{1}})\bigr{)}$
fixing the vertex $v$, the reflection along the following dashed line (and
along a diagonal in each square in the Cayley graph):

$v$

Colouring each generator of $W_{\Gamma}$ with a different colour (blue for the
vertex in $\Gamma_{2}$ red and olive for the two vertices in $\Gamma_{1}$), we
have the following situation

$v$${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}a}}$${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\alpha(a)}}$${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}b}}$${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\alpha(b)}}$

where we depicted the vertices $a$ and $b$ and their respective images under
the automorphism $\alpha$.

##  3\. Good separating sets

In this section we prove one implication of Theorem A. A fundamental notion
allowing us to do so is the one of a _good separating set_.

######  Definition 3.1.

Let $S\subsetneq\Gamma$ be a proper separating set, so that $\Gamma\setminus
S=C_{1}\sqcup\dots\sqcup C_{n}$ is the disjoint union of $n\geqslant 2$
connected components. Suppose that there exists a non-empty set
$I\subsetneq\\{1,\dots,n\\}$ with the property that, fixing
$\Gamma_{1}:=S\sqcup\bigsqcup_{i\in I}C_{i}$ and
$\Gamma_{2}:=S\sqcup\bigsqcup_{i\notin I}C_{i}$, such that there exists a non-
trivial $\alpha\in\operatorname{Aut}(\Gamma_{1})$ such that
$\alpha\restriction_{S}=\operatorname{id}_{S}$. Then we call $S$ a _good
separating set_.

Notice that $S$ can be the empty set. For instance, the only good separating
set for the graph considered in Example 2.13 is the empty set. The idea behind
the definition is the following. In the presence of a proper separating set
$S$, the Coxeter group $W_{\Gamma}$ splits properly as the amalgamated product
$W_{\Gamma}=W_{\Gamma_{1}}\ast_{W_{S}}W_{\Gamma_{2}}$, where $\Gamma_{1}$ and
$\Gamma_{2}$ are given as in Definition 3.1. If the separating set $S$ is a
good separating set, then we can permute non-trivially the canonical
generators of $\Gamma_{1}$, fixing pointwise the ones of $W_{S}$. The
geometric intuition is that we are able to produce non-trivial automorphisms
of any coset of $W_{\Gamma_{1}}$ inside (the Cayley graph of) $W_{\Gamma}$
that extend to the rest of the graph $\operatorname{\mathcal{C}}_{\Gamma}$. In
Corollary 4.4 we will exploit this idea to prove that in the presence of a
good separating set the automorphism of the Cayley graph is uncountable.

We can characterise good separating sets in terms of stars of vertices in the
graph $\Gamma$. In the following lemma we maintain the notation of Definition
3.1.

######  Lemma 3.2.

Let $\Gamma$ be a finite simplicial graph. The following conditions are
equivalent:

  1. (1)

there exists a vertex $v\in V\Gamma$ and a non-trivial
$\alpha\in\operatorname{Aut}(\Gamma)$ such that
$\alpha\restriction_{\operatorname{star}(v)}=\operatorname{id}_{\Gamma}$;

  2. (2)

$\Gamma$ admits a good separating set;

  3. (3)

there exist distinct elements $\alpha,\beta\in\operatorname{Aut}(\Gamma_{1})$
such that $\alpha\restriction_{S}=\beta\restriction_{S}$.

###### Proof.

Suppose that there exists a vertex $v\in V\Gamma$ such that
$\alpha\restriction_{\operatorname{star}(v)}=\operatorname{id}$. As
$\alpha\neq\operatorname{id}_{\Gamma}$, we have that
$\Gamma\setminus\operatorname{star}(v)\neq\emptyset$. Therefore,
$\operatorname{link}(v)$ is a good separating set, and the first condition
implies the second.

On the other hand, suppose that there exists a good separating set $S$ with
non-trivial associated automorphism $\alpha\in\operatorname{Aut}(\Gamma_{1})$
such that $\alpha\restriction_{S}=\operatorname{id}$. For any vertex
$v\in\Gamma_{2}\setminus S$ we have that
$\alpha\restriction_{\operatorname{star}(v)}=\operatorname{id}$, that is, the
second condition implies the first.

To conclude the proof, the second condition implies the third, where $\alpha$
is the non-trivial automorphism provided by the good separating set
$\beta=\operatorname{id}_{\Gamma}$, and the third condition implies the second
considering the non-trivial automorphism
$\alpha^{-1}\beta\in\operatorname{Aut}(\Gamma)$. ∎

The following will be the key lemma to prove the main result of this section.

######  Lemma 3.3.

Let $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$, let $v$ be a vertex in
$\operatorname{\mathcal{C}}_{\Gamma}$ and $x\in V\Gamma$. Then

$\sigma(\alpha,v)\restriction_{\operatorname{star}(x)}=\sigma(\alpha,vx)\restriction_{\operatorname{star}(x)}.$

###### Proof.

Let $y\in\operatorname{link}(x)$, so that in the Cayley graph
$\operatorname{\mathcal{C}}_{\Gamma}$ we see an relation cycle of length
$2m(x,y)$ incident at $v$ and labelled alternatively by $x$ and $y$ (in Figure
3 the general case on the left-hand side, and the right-angled case, that is
$m(x,y)=2$, on the right-hand side).

$v$$vy$$vx$$vxy$

$v$$vy$$vx$$vxy$

Figure 3. Relation cycle, commuting square.

The edges $\\{v,vy\\}$ and $\\{vx,vxy\\}$ are labelled by $y$. Moreover, as
$\alpha$ is an automorphism of the graph
$\operatorname{\mathcal{C}}_{\Gamma}$, it must map the relation cycle to a
relation cycle of the same length, and in particular
$\sigma(\alpha,v)(y)=\sigma(\alpha,vx)(y)$, that is $\sigma(\alpha,v)$ and
$\sigma(\alpha,vx)$ coincide on $\operatorname{link}(x)$.

Clearly, we also have that $\sigma(\alpha,v)(x)=\sigma(\alpha,vx)(x)$, because
the vertices $v$ and $vx$ are joined in $\operatorname{\mathcal{C}}_{\Gamma}$
by the edge labelled by $x$. Therefore the lemma is proved. ∎

In view of Lemma 3.2, the presence of a good separating set in $\Gamma$ is
equivalent to the condition appearing in the statement of Theorem A, that is,
to the existence of some $x\in V\Gamma$ and some non-trivial
$\alpha\in\operatorname{Aut}(\Gamma)$ such that
$\alpha\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$.

Thus, in Proposition 3.4 we prove that if the graph $\Gamma$ is finite and
does not admit any good separating set, then the automorphism group
$\operatorname{\mathcal{A}}_{\Gamma}$ only admits finite vertex stabilisers.
Notice that, in general, the group $\operatorname{\mathcal{A}}_{\Gamma}$ can
be uncountable even if the graph $\Gamma$ is finite (Example 2.13 provides an
example of an uncountable $\mathcal{A}_{\Gamma}$ with $\lvert
V\Gamma\rvert=3$).

######  Proposition 3.4.

Let $\Gamma$ be a connected, simplicial graph, and suppose that there is no
good separating set in $\Gamma$. Then all elements in
$\operatorname{\mathcal{A}}_{\Gamma}$ are almost translations, that is
$\operatorname{\mathcal{A}}_{\Gamma}=W_{\Gamma}\rtimes\operatorname{Aut}(\Gamma)$.
In particular, if $\Gamma$ is finite then the automorphism group is finitely
generated, and therefore countable.

###### Proof.

Let $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$, $v$ be a vertex in
$\operatorname{\mathcal{C}}_{\Gamma}$ and $x\in V\Gamma$. By Lemma 3.3 we have
that
$\bigl{(}\sigma(\alpha,v)^{-1}\circ\sigma(\alpha,vx)\bigr{)}\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$,
and it must then be that $\sigma(\alpha,v)=\sigma(\alpha,vx)$, because by
Lemma 3.2 for all non-trivial $\sigma\in\operatorname{Aut}(\Gamma)$ and for
all $x\in V\Gamma$ we have that
$\sigma\restriction_{\operatorname{star}(x)}\neq\operatorname{id}_{\Gamma}$.

Therefore, for all $x\in V\Gamma$ we have that
$\sigma(\alpha,v)=\sigma(\alpha,vx)$. Repeating this process and applying it
inductively on the vertices of the spheres of increasing radius, we conclude
that $\alpha$ is an almost translation.

Whenever $\Gamma$ is a finite graph, $\operatorname{\mathcal{A}}_{\Gamma}$ is
finitely generated, and therefore countable, in view of Corollary 2.10. ∎

##  4\. Configurations of local actions

In this section we will prove the converse implication of Theorem A, that is
that the existence of a good separating set in $\Gamma$ forces the
automorphism group $\mathcal{A}_{\Gamma}$ to be uncountable.

The following two notions will be helpful to do so.

######  Definition 4.1.

We say that $\overline{\sigma}\in\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$ is a
_legal configuration of local actions_ (a _legal configuration_ for short) if
there exists $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ such that
$\overline{\sigma}(v)=\sigma(\alpha,v)$ for all $v\in W_{\Gamma}$. We will use
the symbol $\Sigma_{\Gamma}$ to denote the set of all legal configurations in
$\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$.

We say that $\overline{\sigma}\in\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$
_satisfies the $(*)$-condition_ if for all $v\in W_{\Gamma}$ and all $x\in
V\Gamma$ we have

$\overline{\sigma}(v)\restriction_{\operatorname{star}(x)}=\overline{\sigma}(vx)\restriction_{\operatorname{star}(x)}.$

In particular, given an automorphism $\alpha\in\mathcal{A}_{\Gamma}$, by
definition, the element $\overline{\sigma}_{\alpha}:=\\{\sigma(\alpha,u)\mid
u\in W_{\Gamma}\\}\in\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$ is a legal
configuration of local actions. On the other hand, Lemma 3.3 assures that it
satisfies the $(*)$-condition.

We will see in the following result that these two notions, that is the one of
legal configurations and the $(*)$-condition, are equivalent.

######  Lemma 4.2.

Let $\overline{\sigma}\in\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$ be
arbitrary. Then $\overline{\sigma}\in\Sigma_{\Gamma}$ if and only if
$\overline{\sigma}$ satisfies the $(*)$-condition.

###### Proof.

If $\overline{\sigma}\in\Sigma_{\Gamma}$ then, by definition, there exists
$\alpha\in\mathcal{A}_{\Gamma}$ such that
$\overline{\sigma}(v)=\sigma_{\Gamma}(\alpha,v)$ for all $v\in W_{\Gamma}$.
Lemma 3.3 assures us that $\overline{\sigma}$ satisfies the $(*)$-condition.

Now, suppose that
$\overline{\sigma}\in\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$ satisfies the
$(*)$-condition. We will construct
$\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ such that
$\sigma_{\Gamma}(\alpha,v)=\overline{\sigma}(v)$ for all $v\in W_{\Gamma}$.
First, we inductively construct a sequence of maps $\alpha_{n}\colon B(e,n)\to
B(e,n)$, where $B(e,n)$ is the ball of radius $n$ centred at the identity
vertex $e$ in the graph $\operatorname{\mathcal{C}}_{\Gamma}$.

For $n=0$ we simply have $\alpha_{0}(e):=e$. For $n\geqslant 1$ we inductively
define $\alpha_{n}(v):=\alpha_{n-1}(v)$ if $v\in B(e,n-1)$. On the other hand,
if $v\in\partial B(e,n)$, as the Cayley graph is connected, there exists (at
least) a generator $x\in V\Gamma$ such that $vx\in B(e,n-1)$; in this case we
define

$\alpha_{n}(v):=\underbrace{\alpha_{n-1}(vx)}_{\in
V\mathcal{C}_{\Gamma}}\underbrace{\overline{\sigma}(vx)(x)}_{\in V\Gamma}\in
V\mathcal{C}_{\Gamma}$

By definition, the vertex $\alpha_{n}(v)$ is the unique vertex in the Cayley
graph $\mathcal{C}_{\Gamma}$ connected to the vertex $\alpha_{n-1}(vx)$ by an
edge labelled by $\overline{\sigma}(vx)(x)$.

We will use induction on $n$ to show that $\alpha_{n}\colon B(e,n)\to B(e,n)$
is a graph automorphism for all natural numbers $n\in\mathbb{N}$, that is, it
is a bijection of the set $B(e,n)$ that preserves edges.

Clearly, for $n=0$ the claim holds. Now, let us assume that $\alpha_{i}$ is a
well-defined graph automorphism for all $i\leq n$, and consider
$\alpha_{n+1}\colon B(e,n+1)\to B(e,n+1)$.

First, we show that $\alpha_{n+1}$ is well-defined on all vertices of
$B(e,n+1)$. By the induction hypothesis $\alpha_{n+1}$ is well-defined on
$B(e,n)$; thus, let $w\in{\partial B(e,n+1)}$ and suppose that there are two
distinct generators $x,y\in V\Gamma$ and $u,v\in B(e,n)$ such that $ux=w=vy$.
First, we show that

$\alpha_{n}(v)\overline{\sigma}(v)(x)=\alpha_{n}(u)\overline{\sigma}(u)(y).$

To this end, let $W_{u}=(x_{1},\dots,x_{n})$ and $W_{v}=(y_{1},\dots,y_{n})$
be two reduced words representing $u$ and $v$, respectively (thus,
${x_{1},y_{1},}\dots,{x_{n},y_{n}\in V\Gamma}$). It immediately follows that
both $W=(x_{1},\dots,x_{n},x)$ and $W^{\prime}=(y_{1},\dots,y_{n},y)$ are
reduced words representing $w$. By Theorem 2.3, we see that $W^{\prime}$ can
be obtained from $W$ by applying a finite number of braid relations. In
particular, we see that $\\{x,y\\}\in E\Gamma$: let $m=m(x,y)$ be the
corresponding weight. Thus, we have a relation cycle of $x$ and $y$ at the
vertex $w\in\mathcal{C}_{\Gamma}$, given by the following vertices:

$\begin{split}u_{0}=u,\qquad u_{1}=uy,&\qquad u_{2}=uyx,\qquad\dots\\\
u_{2m-3}=u(yx)^{m-2}y,\qquad&u_{2m-2}=u(yx)^{m-1}.\end{split}$

We have that

$u_{2m-2}=u(yx)^{m-1}=u(yx)^{m}xy=uxy=wy=v$

and that $u_{0},u_{1},\dots,u_{2m-2}\in B(e,n)$. Clearly, the vertices
$u_{0},u_{1},\dots,u_{2m-2}$ form a path in $B(e,n)$ labelled by $y$ and $x$
(it is the relation cycle of $x$ and $y$ at $w$). In particular, we see that

$\displaystyle\overline{\sigma}(u_{0})(x)=\dots=\overline{\sigma}(u_{2m_{1}})(x)=x^{\prime}$
$\displaystyle\overline{\sigma}(u_{0})(y)=\dots=\overline{\sigma}(u_{2m_{1}})(y)=y^{\prime}$

because $\overline{\sigma}$ satisfies the $(*)$-condition. Clearly,
$\\{x^{\prime},y^{\prime}\\}\in E\Gamma$ as well, with
$m(x^{\prime},y^{\prime})=m$. Consequently, we see that the path

$P=(u_{0},u_{1},\dots,u_{2m-2})\subseteq B(e,n+1)$

with alternating labels $y,x$ maps onto a path

$P^{\prime}=\bigl{(}\alpha_{n}(u_{0}),\alpha_{n}(u_{1}),\dots,\alpha_{n}(u_{2m-2})\bigr{)}\subseteq
B(e,n+1)$

with alternating labels $y^{\prime},x^{\prime}$ and that the path $P^{\prime}$
uniquely completes to a circuit with alternating labels
$x^{\prime},y^{\prime}$. In particular

$\alpha_{n+1}(ux)=\alpha_{n}(u)\overline{\sigma}(u)(x)=\alpha_{n}(v)\overline{\sigma}(y)=\alpha_{n+1}(vy).$

We see that $\alpha_{n+1}\colon B(\operatorname{id},n+1)\to
B(\operatorname{id},n+1)$ is well-defined.

To see that $\alpha_{n+1}$ preserves edges, we need to show that for all
$u,v\in B(e,n+1)$ we have that $\\{\alpha_{n+1}(u),\alpha_{n+1}(v)\\}\in
E\operatorname{\mathcal{C}}_{\Gamma}$ whenever $\\{u,v\\}\in
E\operatorname{\mathcal{C}}_{\Gamma}$. From the definition of $\alpha_{n+1}$
we clearly see that if $v=ux$ and $\|u\|<\|v\|$, then the vertices
$\alpha_{n+1}(u)$ and $\alpha_{n+1}(v)$ are connected by an edge labelled by
$\overline{\sigma}(u)(x)$.

Now assume that there are $u,v\in\partial B(e,n+1)$ such that $\|u\|=\|v\|$
and that there is $x\in V\Gamma$ such that $u=vx$. Let
$W_{u}=(x_{1},\dots,x_{n})$ and $W_{v}=(y_{1},\dots,y_{n})$, where
$x_{1},y_{1},\dots,x_{n},y_{n}\in V\Gamma$, be some reduced expressions for
$u$ and $v$, respectively. We see that the word
$W=(y_{1},\dots,y_{n},x,x_{n}^{-1},\dots,x_{1}^{-1})$ is an expression for
$vxu^{-1}=1$. Clearly, $\lvert W\rvert=2n+1$. However, the elementary
simplification on $(s_{1})$ shortens the word by exactly $2$ letters, meaning
that the word $W$ can never be reduced to the empty string, which is a
contradiction. We see that no such $u,v$ and $x$ can occur and, therefore, the
map $\alpha_{n+1}$ preserves edges.

Finally, we show that $\alpha_{n+1}$ is a bijection. Let us note that it is
clear from the construction that $\alpha_{n+1}$ is injective on $B(w,1)$ for
every $w\in B(e,n)$. Now suppose that there are $u,v\in B(e,n+1)$ such that
$\alpha_{n+1}(u)=\alpha_{n+1}(v)$. Since $\alpha_{n+1}$ is injective on
$B(e,n)$, we see that $\\{u,v\\}\cap\partial B(e,n+1)\neq\emptyset$. Without
loss of generality we may assume that $u\in B(e,n+1)$; let $u^{\prime}\in
B(e,n)$ and $x\in V\Gamma$ be such that $u=u^{\prime}x$. Clearly
$\alpha_{n+1}(u)\in B\bigl{(}\alpha_{n}(u^{\prime}),1\bigr{)}$, so
$n-1\leq\|\alpha_{n+1}(u)\|\leq n+1$.

Suppose that $\|\alpha_{n+1}(u)\|=n$, and let
$(x_{1}^{\prime},\dots,x_{n}^{\prime})$ and
$(y_{1}^{\prime},\dots,y_{n}^{\prime})$, where
$x_{1}^{\prime},y_{1}^{\prime},\dots,x_{n}^{\prime},y_{n}^{\prime}\in V\Gamma$
be some reduced expressions for $\alpha_{n+1}(u)$ and
$\alpha_{n+1}(u^{\prime})$. It then follows that the expression

$W=(x_{1}^{\prime},\dots,x_{n}^{\prime},\overline{\sigma}(u^{\prime})(x),y_{n}^{\prime},\dots,y_{1}^{\prime})$

represents the trivial element and therefore can be reduced to the empty
string, which is a contradiction because the simplification $(s_{1})$ always
reduces by 2 syllables and $|W|=2n+1$. Thus $\|\alpha_{n+1}(u)\|\neq n$.

To see that $\|\alpha_{n+1}(u)\|=n+1$ we consider the partition
$V\Gamma=V_{+}\cup V_{-}$, where $z\in V_{+}$ if
$\|u^{\prime}z\|>\|u^{\prime}\|$ and $z\in V_{-}$ if
$\|u^{\prime}z\|<\|u^{\prime}\|$. As $\alpha_{n+1}$ must stabilise set-wise
the ball $B(e,j)$ for all $j\leq n$, we see that
$\overline{\sigma}(u)(V_{-})=V_{-}$. We immediately deduce that
$\overline{\sigma}(u)(V_{+})=V_{+}$ as well, as otherwise $\alpha_{n+1}$ would
not be injective. As $\|u^{\prime}x\|=n+1>n=\|u\|$ we see that $x\in V_{+}$
and, consequently $\|\alpha_{n+1}(u)\|=n+1$. This then implies that
$\|v\|=n+1$ as well, so both $u,v\in\partial B(e,n+1)$. Let us pick
$v^{\prime}\in B(e,n)$ and $y\in V\Gamma$ be such that $v=v^{\prime}y$. By
definition,

$\alpha_{n+1}(u)=\alpha_{n+1}(u^{\prime})\overline{\sigma}(u^{\prime})(x)=\alpha_{n+1}(v^{\prime})\overline{\sigma}(v^{\prime})(y)=\alpha_{n+1}(v).$

The rest of the proof is analogous to the first part, showing that

$\alpha_{n+1}^{-1}\colon B(e,n+1)\to B(e,n+1)$

is a well-defined function.

We have constructed a sequence of partial maps $\alpha_{n}\colon B(e,n)\to
B(e,n)$, for all $n\in\mathbb{N}$, such that $\alpha_{n}$ is a graph
automorphism and $\alpha_{n}\restriction_{B(e,m)}=\alpha_{m}$ whenever $m<n$.
We now define a new map
$\alpha\colon\operatorname{\mathcal{C}}_{\Gamma}\to\operatorname{\mathcal{C}}_{\Gamma}$
as

$\alpha(v)=\alpha_{n}(v)\quad\mbox{ whenever }\quad v\in B(e,n).$

It immediately follows from what we proved so far that
$\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ and
$\sigma(\alpha,v)=\overline{\sigma}(v)$ for all $v\in W_{\Gamma}$. Thus,
$\overline{\sigma}$ is a legal configuration of local actions, and the proof
is complete. ∎

Clearly, every $\alpha\in\operatorname{\mathcal{A}}_{\Gamma}$ is fully
determined by a pair $(w,\overline{\sigma})\in
W_{\Gamma}\times\Sigma_{\Gamma}$, where $w=\alpha(e)$ and
$\overline{\sigma}(v)=\sigma(\alpha,v)$ for all $v\in W_{\Gamma}$. In
particular, the group $\operatorname{\mathcal{A}}_{\Gamma}$ is in bijection
with the set $W_{\Gamma}\times\Sigma_{\Gamma}$ and, consequently, the
stabiliser $\operatorname{stab}_{\operatorname{\mathcal{A}}_{\Gamma}}(e)$ is
in bijection with the set $\Sigma_{\Gamma}$.

######  Lemma 4.3.

Suppose that the the graph $\Gamma$ contains a good separating set
$S\subseteq\Gamma$, and let $\Gamma_{1}$ be the corresponding subgraph such
that there is a non-trivial $\nu\in\operatorname{Aut}(\Gamma_{1})$ with
$\nu\restriction_{S}=\operatorname{id}_{S}$. Then
$\lvert\Sigma_{\Gamma}\rvert\geq 2^{\lvert W_{\Gamma}/W_{\Gamma_{1}}\rvert}$.

###### Proof.

First, let $\nu^{\prime}\in\operatorname{Aut}(\Gamma)$ denote the extension of
$\nu$ to the whole of $\Gamma$, i.e.

$\nu^{\prime}(x)=\begin{cases}\nu(x)&\quad\mbox{if }x\in\Gamma_{1};\\\
x&\quad\mbox{otherwise}.\end{cases}$

Let $\chi\subseteq W_{\Gamma}/W_{\Gamma_{1}}$ be arbitrary. We define an
element $\overline{\nu}_{\chi}\in\operatorname{Aut}(\Gamma)^{W_{\Gamma}}$ in a
following way:

$\overline{\nu}_{\chi}(w)=\begin{cases}\nu^{\prime}&\quad\mbox{if
$wW_{\Gamma_{1}}\in\chi$};\\\
\operatorname{id}_{\Gamma}&\quad\mbox{otherwise}.\end{cases}$

We claim that $\overline{\nu}_{\chi}\in\Sigma_{\Gamma}$, that is
$\overline{\nu}_{\chi}$ is a legal configuration of local actions. Let $w\in
W_{\Gamma}$ and $x\in V\Gamma$ be arbitrary. If
$wW_{\Gamma_{1}}=wxW_{\Gamma_{1}}$ then, by definition,
$\overline{\nu}_{\chi}(w)=\overline{\nu}_{\chi}(wx)$. Now, let us suppose that
$wW_{\Gamma_{1}}\neq wxW_{\Gamma_{1}}$. This means that $x\in
V\Gamma\setminus\Gamma_{1}$ and, in particular,
$\operatorname{star}(x)\subseteq(V\Gamma\setminus\Gamma_{1})\cup S$. We
immediately see that
$\overline{\nu}_{\chi}(w)\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$
and, similarly, that
$\overline{\nu}_{\chi}(wx)\restriction_{\operatorname{star}(x)}=\operatorname{id}_{\Gamma}$.
Following Lemma 4.2, $\overline{\nu}_{\chi}$ is a legal configuration. This
means that $\Sigma_{\Gamma}$ contains a subset of cardinality
$2^{|W_{\Gamma}/W_{\Gamma_{1}}|}$, therefore

$2^{|W_{\Gamma}/W_{\Gamma_{1}}|}\leq|\Sigma_{\Gamma}|$

and the lemma is proved. ∎

As we discussed earlier, the stabiliser
$\operatorname{stab}_{\operatorname{\mathcal{A}}_{\Gamma}}(e)$ is in bijection
with the set $\Sigma_{\Gamma}$ in a natural way. Also, one can verify that if
$S\subset V\Gamma$ is a good separating set and $\Gamma_{1}$ is the
corresponding factor, then the subgroup $W_{\Gamma_{1}}$ has infinite index in
$W_{\Gamma}$. Combining these with the simple observation that
$\operatorname{stab}_{\operatorname{\mathcal{A}}_{\Gamma}}(w)=w\operatorname{stab}_{\operatorname{\mathcal{A}}_{\Gamma}}(e)w^{-1}$
we get:

######  Corollary 4.4.

Let $\Gamma$ be a finite weighted graph. If $\Gamma$ admits a good separating
set, then the group $\operatorname{\mathcal{A}}_{\Gamma}$ admits uncountable
vertex stabilisers.

######  Remark 4.5.

For an example when the separating set is not empty, we can consider the graph

$v_{1}$$v_{2}$

and the automorphism $\alpha$ that interchanges the vertices $v_{1}$ and
$v_{2}$ and fixes the other two vertices. Corollary 4.4 guarantees that the
automorphism group of the Cayley graph $\operatorname{\mathcal{C}}_{\Gamma}$
is uncountable. If $v\in\operatorname{\mathcal{C}}_{\Gamma}$ is a vertex, the
automorphism $\alpha_{v}$ is given by reflection around the diagonal square

$v$

Also, notice that Corollary 4.4 provides examples of one-ended right-angled
Coxeter groups whose Cayley graph has uncountable automorphism group. For
instance, one can consider the following graph.

From Proposition 3.4 we immediately deduce that Cayley graphs of right-angled
Coxeter groups associated to _path graphs_ $P_{n}$ and to _cycle graphs_
$C_{n}$ are countable.

A path graph, denoted $P_{n}$, is a connected graph with $n$ vertices, of
which exactly two have valency one, whereas the remaining $n-2$ have valency
two, and all edged have weight two. A cycle graph, denoted $C_{n}$, is a
connected graph with $n$ vertices of valency two and edges with weight two.

It is not true that if $\Delta$ is an induced subgraph of $\Gamma$ then
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(W_{\Delta})\bigr{)}$ is a
subgroup of $\operatorname{\mathcal{A}}_{\Gamma}$. Consider the full graph
$\Delta$ on two vertices, and let $\Gamma=P_{3}$, so that $\Delta$ is an
induced subgraph of $\Gamma$. It is easy to recognize that the group
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(W_{\Delta})\bigr{)}$ is not a
subgroup of
$\operatorname{Aut}\bigl{(}\operatorname{\mathcal{C}}_{\Gamma}\bigr{)}$.
Indeed $W_{\Delta}\cong\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ and
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(W_{\Delta})\bigr{)}$ is the
dihedral group $D_{8}$, the reflection group of a square. In particular, there
is an element of order four in
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(W_{\Delta})\bigr{)}$. On the
other hand, there is no element of order four in
$\operatorname{\mathcal{A}}_{\Gamma}$.

More is true. Indeed, from what we proved we immediately observe that there
are graphs $\Gamma$ with induced subgraphs $\Delta$ such that
$\operatorname{\mathcal{A}}_{\Gamma}$ is countable, but
$\operatorname{Aut}\bigl{(}\operatorname{Cay}(W_{\Delta})\bigr{)}$ is
uncountable. As an example, we can take $\Gamma=P_{4}$, and $\Delta$ to be the
graph obtained from $\Gamma$ by removing a vertex of valency two. In this
case, the Cayley graph of $W_{\Gamma}$ is

Figure 4. Cayley graph of $W_{\Gamma}$, for $\Gamma=P_{4}$.

and has countable automorphism group by Proposition 3.4.

This should be compared with the case of right-angled Artin groups [8], where
this behaviour is not present.

##  5\. Beyond locally finite graphs

Even though the main aim of this note was to classify those finitely generated
Coxeter groups whose Cayley graph (with respect to the standard generating
set) has a nondiscrete automorphism group, the tools we developed to do so
allow us to construct explicit examples of vertex-transitive graphs of
infinite degree that still have locally compact automorphism groups. In
particular in Example 5.3 gives construction of a graph with compact vertex
stabilisers and Example 5.4 given an explicit construction of a graph such
that edge stabilisers are compact-open but vertex stabilisers are not compact.

Before we proceed, let us recall some standard notation. Given a simplicial
graph $\Gamma=(V\Gamma,E\Gamma)$, we will use $\Gamma^{c}$ to denote the
_complement graph_ of $\Gamma$, i.e $V\Gamma^{C}=V\Gamma$ and
$E\Gamma^{c}=\binom{V\Gamma}{2}\setminus E\Gamma$. Quite clearly,
$\operatorname{Aut}(\Gamma^{c})$ is naturally isomorphic to
$\operatorname{Aut}(\Gamma)$ in an obvious way:
$\phi\in\operatorname{Sym}(V\Gamma)$ is an automorphism of $\Gamma$ is and
only if it is an automorphism of $\Gamma^{c}$.

######  Lemma 5.1.

Suppose that $\Gamma$ is an infinite tree without leaves. Then $\Gamma^{c}$
does not admit a good separating set.

###### Proof.

We will use Lemma 3.2.

Let $v\in V\Gamma$ and suppose that $\alpha\in\operatorname{Aut}(\Gamma)$ is a
automorphism such that
$\alpha\restriction_{\operatorname{star}_{\Gamma^{c}}(v)}=\operatorname{id}_{\Gamma}$.
Following the definition of the complement graph, we see that
$\operatorname{star}_{\Gamma^{c}}(v)=V\Gamma\setminus\operatorname{star}_{\Gamma}(v)$,
therefore $\alpha$ must fix all vertices of the tree $\Gamma$ outside of
$V\Gamma\setminus\operatorname{star}_{\Gamma}(v)$. Since $\Gamma$ does not
have any leaves, we see that $v$ is adjacent to at least two distinct
vertices, denote them $u_{1},u_{2}$. By a similar argument, we see that
$u_{1}$ must be adjacent to some vertex $u_{1}^{\prime}$ outside of
$\operatorname{star}_{\Gamma}(v)$ and $u_{2}$ must be adjacent to some
$u_{2}^{\prime}$ outside of $\operatorname{star}_{\Gamma}(v)$. By assumption,
$u_{1}^{\prime}$ and $u_{2}^{\prime}$ are fixed by $\alpha$. Since $\Gamma$ is
a tree, the sequence of vertices
$(u_{1}^{\prime},u_{1},v,u_{2},u_{2}^{\prime})$ is the unique path between
$u_{1}^{\prime}$ and $u_{2}^{\prime}$ and therefore the vertices
$u_{1},v,u_{2}$ must be fixed by $\alpha$ as well. Since $\Gamma$ does not
have any leaves, we see that if $u\in\operatorname{star}_{\Gamma}(v)$ is a
neighbour of $v$ it must be adjacent to some $u^{\prime}\in
V\Gamma\setminus\operatorname{star}_{\Gamma}(v)$. Again, $u^{\prime}$ must be
fixed by $\alpha$ by assumption and therefore, since $(v,u,u^{\prime})$ is the
unique path from $v$ to $u^{\prime}$, we see that $u$ must be fixed as well.
It then follows that $\alpha=\operatorname{id}_{\Gamma}$.

Therefore, for every vertex $v\in V\Gamma$ and every
$\alpha\in\operatorname{Aut}(\Gamma)\setminus\operatorname{id}_{\Gamma}$ we
have that
$\alpha\restriction_{\operatorname{star}_{\Gamma}(v)}\neq\operatorname{id}_{\Gamma}$,
and thus, by Lemma 3.2, $\Gamma$ does not admit a good separating set. ∎

The main idea behind the constructions presented in this section relies on the
following application of Proposition 3.4

######  Lemma 5.2.

Suppose that $\Gamma$ is a simplicial graph which does not admit a good
separating set. Then for any $v\in W_{\Gamma}$, the stabiliser
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$, where
$\operatorname{\mathcal{A}}=\operatorname{Aut}(\operatorname{Cay}(W_{\Gamma},V\Gamma))$
is isomorphic to $\operatorname{Aut}(\Gamma)$ as a topological group.

###### Proof.

As the graph $\Gamma$ does not admit a good separating set, we see that
$\operatorname{\mathcal{A}}_{\Gamma}\simeq
W_{\Gamma}\rtimes\operatorname{Aut}(\Gamma)$ by Proposition 3.4. In
particular, we see that for any $v\in W_{\Gamma}$ we have that
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ is isomorphic to
$\operatorname{Aut}(\Gamma)$ as a group. It remains to show that the
isomorphism is continuous.

If the graph $\Gamma$ is finite, then both
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ and
$\operatorname{Aut}(\Gamma)$ are finite and therefore discrete. It follows
trivially that $\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ and
$\operatorname{Aut}(\Gamma)$ are isomorphic as topological groups as well.

Let $v\in W_{\Gamma}$ be arbitrary and let
$\phi\colon\operatorname{Aut}(\Gamma)\to\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$
be the map sending $\sigma\in\operatorname{Aut}(\Gamma)$ to $\alpha_{\sigma}$,
where $\alpha_{\sigma}$ is the unique element of
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ such that
$\sigma(\alpha_{\sigma},u)=\sigma$ for all $u\in W_{\Gamma}$. Let
$\mathcal{O}\subseteq\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ be
open. Without loss of generality we may assume that there are
$\beta\in\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ and a finite set
$F\subseteq W_{\Gamma}$ such that

$\mathcal{O}=\beta\operatorname{stab}_{A}(F)\cap\operatorname{stab}_{\operatorname{\mathcal{A}}}(v).$

In fact, since the elements of
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ are fully determined by
their action on the neighbourhood of $v$, we may assume that $F\subseteq
B(1,v)$. This means that there are $x_{1},\dots,x_{n}\in V\Gamma$ such that
$F=\\{vx_{1},\dots,vx_{n}\\}$ and, clearly,

$\phi^{-1}(\mathcal{O})=\\{\sigma^{\prime}\in\operatorname{Aut}(\Gamma)\mid\sigma^{\prime}\restriction_{F^{\prime}}=\sigma(\beta,v)\restriction_{F^{\prime}}\\},$

where $F^{\prime}=\\{x_{1},\dots,x_{n}\\}\subseteq V\Gamma$, so we see that
$\phi^{-1}(\mathcal{O})$ is open in the permutation topology on
$\operatorname{Aut}(\Gamma)$ and therefore $\phi$ is continuous. The proof
that $\phi^{-1}$ is continuous is essentially the same and is left as an
exercise.

We see that
$\phi\colon\operatorname{Aut}(\Gamma)\to\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$
is both a group isomorphism and a homeomorphism of topological spaces,
therefore $\operatorname{Aut}(\Gamma)$ and
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(v)$ are isomorphic as
topological groups. ∎

We now use Lemma 5.1 and Lemma 5.2 to give explicit constructions of vertex
transitive graphs of infinite degree with locally compact group of
automorphisms.

######  Example 5.3.

Suppose that $\Gamma$ is an infinite regular rooted tree of finite degree.
Then $\operatorname{Cay}(W_{\Gamma^{c}},V\Gamma^{c})$ is a vertex-transitive
graph of infinite degree such that
$\operatorname{\mathcal{A}}=\operatorname{Aut}(\operatorname{Cay}(W_{\Gamma^{c}},V\Gamma^{c}))$
is locally compact group with compact vertex-stabilisers. In particular, for
any $w\in W_{\Gamma^{c}}$ we see that
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(w)$ is isomorphic (as a
topological group) to $\operatorname{Aut}(\mathcal{T}_{d})$.

######  Example 5.4.

Suppose that $\Gamma=\mathcal{T}_{d}$ is an infinite $d$-regular tree. Then
$\operatorname{Cay}(W_{\Gamma^{c}},V\Gamma^{c})$ is a vertex-transitive graph
of infinite degree such that
$\operatorname{\mathcal{A}}=\operatorname{Aut}(\operatorname{Cay}(W_{\Gamma^{c}},V\Gamma^{c}))$
is locally compact group such that edge stabilisers are compact but vertex
stabilisers are not. In particular, for any $w\in W_{\Gamma^{c}}$ and $x\in
V\Gamma^{c}$ we see that $\operatorname{stab}_{\operatorname{\mathcal{A}}}(w)$
is isomorphic (as a topological group) to
$\operatorname{Aut}(\mathcal{T}_{d})$ and
$\operatorname{stab}_{\operatorname{\mathcal{A}}}(\\{w,wx\\})$ is isomorphic
to a vertex stabiliser in $\operatorname{Aut}(\mathcal{T}_{d})$, i.e.
$\operatorname{Aut}(T_{d,d-1}^{*})$, where $T_{d,d-1}^{*}$ is a infinite
rooted tree such that the root has $d$ children and every other vertex has
exactly $d-1$ children.

## References

  * [1] Anders Björner and Francesco Brenti.  Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics.  Springer, New York, 2005.
  * [2] Graham Clarke.  Automorphisms of geometric structures associated to coxeter groups, 2011\.
  * [3] Frédéric Haglund and Frédéric Paulin.  Simplicité de groupes d’automorphismes d’espaces à courbure négative.  In The Epstein birthday schrift, volume 1 of Geom. Topol. Monogr., pages 181–248. Geom. Topol. Publ., Coventry, 1998.
  * [4] R. Halin.  Automorphisms and endomorphisms of infinite locally finite graphs.  Abh. Math. Sem. Univ. Hamburg, 39:251–283, 1973.
  * [5] Wilfried Imrich and Simon M. Smith.  On a theorem of Halin.  Abh. Math. Semin. Univ. Hambg., 87(2):289–297, 2017.
  * [6] Paul-Henry Leemann and Mikael de la Salle.  Cayley graphs with few automorphisms.  J. Algebraic Combin., 53(4):1117–1146, 2021.
  * [7] Paul-Henry Leemann and Mikael de la Salle.  Cayley graphs with few automorphisms: the case of infinite groups.  Ann. H. Lebesgue, 5:73–92, 2022.
  * [8] Thomas Taylor.  Automorphisms of cayley graphs of right-angled artin groups.  Honours thesis, University of Newcastle, 2017.