# Loose ear decompositions and their applications to right-angled Artin groups

Max Gheorghiu

###### Abstract

We characterise graph subdivisions, planar graphs and graph minors among
others in terms of right-angled Artin groups (RAAGs). For this, we determine
all sets of elements in RAAGs with ears as underlying graphs that are exactly
the sets of vertex generators. Generalising ear decompositions of graphs to
loose ear decompositions, we characterise both decompositions in terms of
RAAGs. The desired results follow as applications of loose ear decompositions
of RAAGs.

###### Contents

  1. 1 Introduction
  2. 2 Elements in ear RAAGs arsing from degree 2 vertices
  3. 3 Elements in ear RAAGs arsing from degree 1 vertices
  4. 4 Vertex bases in ear RAAGs and loose ear decompositions
  5. 5 Applications of loose ear decompositions of RAAGs
  6. Acknowledgement

##  1 Introduction

Assuming that every graph $\Gamma$ is finite, undirected and simple, we write
its vertex set as $V(\Gamma)$, its edge set as $E(\Gamma)$ and define its
associated right-angled Artin group (RAAG) as the group

$A(\Gamma):=\langle v\in V(\Gamma)\mid[v,w]=1\text{ whenever }\\{v,w\\}\in
E(\Gamma)\rangle\,.$

A vertex generator is a generator arising from a vertex $v\in V(\Gamma)$ and a
vertex basis is a generating set as in the above group presentation. The graph
$\Gamma$ is called the underlying graph of $A(\Gamma)$. The spirit of this
paper is influenced by a proposed dictionary between graph theoretic terms and
group theoretic terms that T. Koberda introduces and promotes in [6]. In
other words, the goal of this dictionary is to find for every property of a
graph a corresponding algebraic property of a RAAG. For the latter, no mention
of generators or relations ought to be made. Geometrically, one can interpret
this as a coordinate-free description. The graph theoretic properties we are
mainly interested in are graph subdivisions, planar graphs and graph minors
that we define as follows. An edge subdivision in a graph $\Gamma$ is defined
by inserting a new vertex $v$ to $\Gamma$ and replacing an edge with endpoints
$u$ and $w$ by an edge with endpoints $u$ and $v$ and another one with
endpoints $v$ and $w$. [4, p. 305] A graph subdivision is then defined as a
finite sequence of edge subdivision. [4, p. 306] A graph is planar if it can
be drawn in the plane without edge-crossings. [4, p. 298] Lastly, graph minors
can be thought as a generalisation of the notion of a subgraph. More
rigorously, $X$ is a minor of $Y$ if there is $S\subseteq V(Y)$ and a function
$f:S\rightarrow V(X)$ such that $f^{-1}(x)\leq Y$ is a connected subgraph and
there is an edge between $f^{-1}(x)$ and $f^{-1}(x^{\prime})$ if there is an
edge between $x,x^{\prime}\in V(X)$. [2, p. 20] Thus, we provide a first
characterisation of graph subdivisions, planar graphs and graph minors in
terms of RAAGs.

This solves two questions in [6]. Whether one can characterise graph
subdivisions in terms of RAAGs was asked on page 40. Question 5.2 asked to
characterise planar graphs in terms of RAAGs. Moreover, minors are an
important object in graph theory. Namely, a class of graphs $\mathcal{P}$ is
called minor-closed if any minor of a graph in $\mathcal{P}$ is again
contained in $\mathcal{P}$. A graph $H$ is a forbidden minor for the class
$\mathcal{P}$ if any graph in $\mathcal{P}$ does not contain $H$ as a minor.
[2, p. 369] According to [2, p. 374], “theorems that characterize a property
$\mathcal{P}$ by a set of forbidden minors are doubtless among the most
attractive results in graph theory”. Hence, we can now reformulate such
theorems in the language of RAAGs. Our characterisations pertain to the realm
of T. Koberda’s dictionary because they do not mention generators and
relations explicitly. But they do not fit properly into the dictionary because
they use generators and relations implicitly. Moreover, given a RAAG
$A(\Gamma)$, it is unclear how one could implement our characterisations into
an algorithm to determine whether $\Gamma$ possesses any of these graph
theoretic properties. It would be desirable if someone could find
characterisations of these properties by different means, in particular that
fitted properly into T. Koberda’s dictionary or allowed an algorithmic
implementation.

Our characterisations all depend on a generalisation of ear decompositions of
graphs that we call loose ear decompositions. An ear is a graph that consists
of a single path or a single cycle. [9, p. 252] We assume that every ear, path
and cycle contains more than one vertex. In order to take over a term for
paths to ears, we call one distinguished vertex of a cycle its end point and
all other vertices inner vertices (thus, one can think of a cycle as path
whose endpoints are identified). An ear decomposition of $\Gamma$ is a finite
sequence of ears $\\{\Gamma_{i}\\}_{i=1}^{m}$ contained in the graph $\Gamma$
and satisfying the following properties. The ear $\Gamma_{1}$ is a cycle. For
any $i>1$ only the endpoints of the ear $\Gamma_{i}$ are contained in the
previous ears $\bigcup_{j=1}^{i-1}\Gamma_{j}$, but none of its inner vertices
(if there are any). Finally, $\Gamma=\bigcup_{i=1}^{m}\Gamma_{i}$. [4, p.
235–237], [8, Definition 1] We define a loose ear decompositions of $\Gamma$
as a finite sequence of ears $\\{\Gamma_{i}\\}_{i=1}^{m}$ in the same way, but
without imposing that $\Gamma_{1}$ is a cycle or that the end points of
$\Gamma_{i}$ have to be contained in $\bigcup_{j=1}^{i-1}\Gamma_{j}$. Our main
technical tool is a characterisation of loose ear decompositions of $\Gamma$
in terms of its RAAG $A(\Gamma)$.

Accordingly, in the first sections, we consider ears and call RAAGs with ears
as underlying graphs ear RAAGs. In the first section, we characterise all
elements in ear RAAGs that arise from degree $2$ vertices without specifying
that these are generators. We determine in the second section when two such
elements arise from adjacent vertices as well as all elements that arise from
degree $1$ vertices. Again, this is done without specifying that the latter
elements are generators. We call these elements arising from degree $1$ or $2$
vertices pearls. In particular, pearls are vertex generators. In the third
section, we characterise the sets of pearls in ear RAAGs that correspond
exactly to vertex bases and call such sets pearl chains. This is non-trivial
as there is no guarantee to obtain a vertex basis just by picking vertex
generators. Although pearl chains do not fit into T. Koberda’s dictionary,
they still pertain to its realm because we do not state that they are actually
generating sets. Using them, we also characterise ear decompositions and loose
ear decomposition of a graph $\Gamma$ in terms of its associated RAAG
$A(\Gamma)$ in this section. To be more explicit, a loose ear decomposition of
$\Gamma$ is equivalent to a specific iterated amalgamated product of ear RAAGs
that is isomorphic to $A(\Gamma)$.

In the fourth section, we showcase applications of loose ear decompositions
and ear decompositions to RAAGs. First, we characterise graphs subdivisions
and planar graphs in term of their associated RAAGs. Then we describe graph
minors through RAAGs. This in turn allows us to determine other graph
theoretic properties algebraically by their associated RAAGs. For instance, if
$\Gamma$ is a graph, we provide conditions on the associated RAAG $A(\Gamma)$
determining when $\Gamma$ is a forests or an outerplanar graph. Graph minors
could be also used to obtain conditions on $A(\Gamma)$ for when $\Gamma$ is an
apex graph and embeds into a given surface without edge-crossings. In our last
applications, we restrict our attention to ear decompositions. Doing so, we
find algebraic criteria for $A(\Gamma)$ determining when $\Gamma$ is $2$-edge-
connected, $2$-vertex-connected, $3$-vertex-connected, a series-parallel
graph, a factor-critical graph and what the maximal size of a join in it is.

##  2 Elements in ear RAAGs arsing from degree 2 vertices

Being one of the central notions, let us characterise ear RAAGs among all
RAAGs. For this we require the following piece of notation.

######  Notation 2.1.

For a finitely generated group $G$, let $d(G)$ denote the minimal number of
generators of $G$.

######  Proposition 2.2.

If a RAAG $A(\Gamma)$ does not split as non-trivial free product and for any
$x\in A(\Gamma)$ we have $d(C(x))\leq 3$, then $A(\Gamma)$ is an ear RAAG.

######  Proof.

According to Proposition 3.6 in [6], the degree of every vertex in $\Gamma$ is
at most $2$. By Theorem 3.2 in [6], the graph $\Gamma$ is connected. If
$\Gamma$ has a vertex of degree $1$, then it is a path. If not, then it is a
cycle. $\square$

We also need an elementary result for which we have not found an explicit
proof in the literature.

######  Proposition 2.3.

For any RAAG $A(\Gamma)$ we have $d(A(\Gamma))=|V(\Gamma)|$.

######  Proof.

Because we can define $A(\Gamma)$ by a group presentation using the graph
$\Gamma$, we see that $|V(\Gamma)|\geq d(A(\Gamma))$. By this presentation, we
observe that $A(\Gamma)_{ab}=\mathbb{Z}^{|V(\Gamma)|}$. Using the projection
$A(\Gamma)\rightarrow A(\Gamma)_{ab}$ we infer that $d(A(\Gamma))\geq
d(\mathbb{Z}^{|V(\Gamma)|})=|V(\Gamma)|$. $\square$

Let us move over to characterising elements in an ear RAAG $A(\Gamma)$ that
arise from degree $2$ vertices in $\Gamma$.

######  Lemma 2.4.

Let $A(\Gamma)$ be an ear RAAG. Assume that there is $x\in A(\Gamma)$ such
that $A(\Gamma)/\langle\\!\langle x\rangle\\!\rangle$ is a RAAG with
$d(A(\Gamma))=d(A(\Gamma)/\langle\\!\langle x\rangle\\!\rangle)+1$. Assume
further that there are elements $a,b\in A(\Gamma)$ such that $\langle
a,b\rangle\cong F_{2}$, $\langle a,b\rangle\leq C(x)\leq\langle a,b,x\rangle$
and $\langle x\rangle\cap\langle a,b\rangle=\\{1\\}$. Then, up to isomorphism,
there is a vertex basis of $A(\Gamma)$ containing $x$ such that $x$ arises
from a degree $2$ vertex in $\Gamma$.

######  Proof.

Let us write $|V(\Gamma)|=d(A(\Gamma))=n$. Assume by contradiction that $x=1$.
Our conditions imply that $C(x)=\langle a,b\rangle\cong F_{2}$. Because also
$C(x)=A(\Gamma)$, $d(A(\Gamma))=2$. By Proposition 2.3, the ear $\Gamma$ has
two vertices and is thus the path $P_{2}$. In particular,
$A(\Gamma)=\mathbb{Z}^{2}$. Hence, $x$ is a nontrivial element. As $\langle
x\rangle$ is normal in $C(x)=\langle a,b,x\rangle$, $C(x)$ is a semidirect
product of $\langle x\rangle$ and $\langle a,b\rangle$. Using that $x$ is
central in $C(x)$, $C(x)=\langle x\rangle\oplus\langle a,b\rangle$ is
isomorphic to $A(P_{3})=\mathbb{Z}\oplus F_{2}$ where $P_{3}$ is a path on
three vertices. Now we need to consider the two cases where $\Gamma$ is either
a path or a cycle.

Let us consider the former case. Note that $A(P_{2})=\mathbb{Z}^{2}$ implies
$n\geq 3$. Denote by $v_{1},\dots,v_{n}$ the vertices of $\Gamma$ where
$v_{1}$, $v_{n}$ are the endpoints and $v_{i}$ is adjacent to $v_{i+1}$. By
abuse of notation, we shall denote the corresponding vertex basis of
$A(\Gamma)$ also by $v_{1},\dots,v_{n}$. Writing $x$ as a word in these
generators, we would like to apply the centraliser theorem on page 44 from
Servatius’s paper [10] to $C(x)$. For this, we call a word in the vertex basis
$v_{1},\dots,v_{n}$ reduced if it cannot be shortened using free reductions or
commutations. Moreover a word is called cyclically reduced if it is remains
reduced after any cyclic permutation of its letters. [6, p. 15] Since the
statement of the lemma will not change under conjugation, we may assume that
$x$ is cyclically reduced. Define the support of $x$ to be the subset of our
vertex basis required to write $x$ as a reduced word and denote it by
$\mathrm{supp}(x)$. This notion is well defined in the sense that for reduced
words $w_{1}=w_{2}$ in $A(\Gamma)$ we have
$\mathrm{supp}(w_{1})=\mathrm{supp}(w_{2})$. [6, p. 15] Denote by
$\Lambda_{1},\dots,\Lambda_{k}\leq\Gamma$ the subgraphs such that the support
of $x$ can be written as a join
$\mathrm{supp}(x)=\Lambda_{1}\ast{}\dots\ast\Lambda_{k}$. Choose $u_{i}\in
A(\Lambda_{i})$ for $i\in\\{1,\dots,k\\}$ such that
$x=\prod_{i=1}^{k}u_{i}^{m_{i}}$ with $m_{i}$ maximal. By Servatius’s
centraliser theorem we can write

$C(x)=\prod_{i=1}^{k}\langle
u_{i}\rangle\oplus\langle\mathrm{link}(\mathrm{supp}(x))\rangle\,.$

Let us assume first that $\mathrm{link}(\mathrm{supp}(x))\neq\varnothing$. If
$v_{i},v_{j}\in\mathrm{link}(\mathrm{supp}(x))$ and $|i-j|>2$ then
$\mathrm{link}(v_{i})\cap\mathrm{link}(v_{j})=\varnothing$, so
$\mathrm{link}(\mathrm{supp}(x))=\varnothing$. Hence $|i-j|\leq 2$ for any two
elements $v_{i},v_{j}\in\mathrm{link}(\mathrm{supp}(x))$. This leaves us with
the following cases to consider:

  * •

Case 1: $x\in\langle v_{i}\rangle$ for $i\in\\{2,\dots,n-1\\}$.

  * •

Case 2: $x\in\langle v_{i}\rangle$ for $i\in\\{1,n\\}$.

  * •

Case 3: $\mathrm{supp}(x)=\\{v_{i},v_{i+2}\\}$ for $i\in\\{1,\dots,n-2\\}$.

Suppose now that $\mathrm{link}(\mathrm{supp}(x))=\varnothing$. Given that
$C(x)\cong\mathbb{Z}\oplus F_{2}$, $\mathrm{supp}(x)$ splits as a join of two
indecomposable subgraphs by Servatius’s centraliser theorem. As every join is
connected, $\mathrm{supp}(x)$ is a path. We shall outline briefly why the path
$P_{l}$ on $l$ vertices cannot split as a nontrivial join for $l\geq 4$. If it
did, then there would be $v_{i}$, $v_{i+1}$ not belonging to the same
component of the join. Then $v_{i+2}$ must be in the same component as
$v_{i}$, but $v_{i+3}$ cannot be in either of the components. If we impose
that $\mathrm{supp}(x)$ contains more than one element, then we are left with
the following cases:

  * •

Case 4: $\mathrm{supp}(x)=\\{v_{i},v_{i+1}\\}$ for $i\in\\{1,\dots,n-1\\}$.

  * •

Case 5: $\mathrm{supp}(x)=\\{v_{i},v_{i+1},v_{i+2}\\}$ for
$i\in\\{1,\dots,n-2\\}$.

Going through all the cases, we notice that only Case 1 yields
$C(x)\cong\mathbb{Z}\oplus F_{2}$ while all other cases yield
$C(x)\cong\mathbb{Z}^{2}$. We conclude that $x=v^{m}$ for
$m\in\mathbb{Z}\setminus\\{0\\}$. If $|m|>1$ then $A(\Gamma)/\langle\\!\langle
x\rangle\\!\rangle$ would contain torsion. Since RAAGs are torsion-free, [1,
p. 149] we see that $x=v_{i}^{\pm 1}$ where $v_{i}$ is a degree $2$ vertex.

Although this implies $d(A(\Gamma))=d(A(\Gamma)/\langle\\!\langle
x\rangle\\!\rangle)+1$, the reason why we include this condition in the lemma
is because of the case in which $\Gamma$ is a cycle instead of a path. More
specifically, if $C_{3}$ denotes the path on $3$ vertices, then
$A(C_{3})=\mathbb{Z}^{3}$ and thus $n\geq 4$. If we assume $n\geq 5$, then all
arguments we have developed for paths still pertain to cycles. Only for
$A(C_{4})$, Case 3 from above is different. For this, let
$V(C_{4})=\\{u_{1},v_{1},u_{2},v_{2}\\}$ where the vertices are adjacent in
the order they are written down and where $u_{1}$ is adjacent to $v_{2}$. Note
that $A(C_{4})=\langle u_{1},u_{2}\rangle\oplus\langle v_{1},v_{2}\rangle$ is
isomorphic to $F_{2}\oplus F_{2}$. Then Case 3 translates to having a word
$\xi$ in $v_{1}^{\pm 1},v_{2}^{\pm 1}$ such that $x=(1,\xi)$, which requires
the above condition.

We call an element in $e\in F_{2}$ primitive if there is an element $f\in
F_{2}$ such that $\\{e,f\\}$ is a generating set and extend this definition to
elements in $\mathbb{Z}^{2}$. In this case, we call $e$ and $f$ associated
primitives. Let us assume by contradiction that $\xi$ is not a primitive
element. According to 1.2 Theorem and 3.3 Corollary in R. P. Osborne and H.
Zieschang’s paper [7], this is equivalent for the image
$\overline{\xi}\in\mathbb{Z}^{2}$ in the abelianisation not to be primitive
for the following reason. For every primitive in the abelianisation
$\mathbb{Z}^{2}$ there is a primitive in $F_{2}$ mapping down to it and all
primitives in $F_{2}$ are of this form. Let us obtain now a more explicit
description of the primitives in $\mathbb{Z}^{2}$. If an element
$e\in\mathbb{Z}^{2}$ is primitive, then $\mathbb{Z}^{2}/e\cong\mathbb{Z}$ is
torsion-free. Thus, primitive elements in $\mathbb{Z}^{2}$ cannot be multiples
of other elements. Contrarily, assume that $e\in\mathbb{Z}^{2}$ is not a
multiple of another element. If $s,t\in\mathbb{Z}^{2}$ form a generating set,
then there are coprime integers $c,d$ such that $e=cs+dt$. According to
Bézout’s Theorem, there are integers $x,y$ such that $cx+dy=1$. Observing that
$s=x(cs+dt)+d(ys-xt)$ and $t=y(cs+dt)-c(ys-xt)$, we conclude that $e$ is
primitive. Therefore, our assumption implies that either $\overline{\xi}=0$ or
that there are $0\neq\overline{\eta}\in\mathbb{Z}^{2}$ and $k\geq 2$ such that
$k\cdot\overline{\eta}=\overline{\xi}$.

Let us assume first that $\overline{\xi}=0$. Then
$\xi\in\langle\\!\langle[v_{1},v_{2}]\rangle\\!\rangle$ and the projection
homomorphism to the abelianisation factors as $A(C_{4})\rightarrow
A(C_{4})/\langle\\!\langle x\rangle\\!\rangle\rightarrow\mathbb{Z}^{4}$. Using
the above mentioned condition in the proposition, this yields the
contradiction

$3=d(A(C_{4}))-1=d(A(C_{4})/\langle\\!\langle x\rangle\\!\rangle)\geq
d(\mathbb{Z}^{4})=4\,.$

Therefore $k\cdot\overline{\eta}=\overline{\xi}$. Then the abelianisation

$(A(C_{4})/\langle\\!\langle
x\rangle\\!\rangle)_{ab}\cong\big{(}F_{2}\oplus(F_{2}/\langle\\!\langle\xi\rangle\\!\rangle)\big{)}_{ab}\cong\mathbb{Z}^{2}\oplus(\mathbb{Z}^{2}/\langle\\!\langle\overline{\xi}\rangle\\!\rangle)\,.$

contains the torsion element
$(1,\overline{\eta}\langle\\!\langle\overline{\xi}\rangle\\!\rangle)$. Since
abelianisations of RAAGs are torsion-free, our assumption has led to a
contradiction and $\xi\in\langle v_{1},v_{2}\rangle$ is a primitive element.
If $\xi$ together with $\zeta$ generate the subgroup $\langle
v_{1},v_{2}\rangle\cong F_{2}$ then $u_{1},u_{2},x,(1,\zeta)$ form another
vertex basis of $A(C_{4})$. In particular, $x$ arises here from a degree $2$
vertex. $\square$

######  Corollary 2.5.

Let $x\in A(\Gamma)$ satisfy the condition of the above lemma. If
$A(\Gamma)/\langle\\!\langle x\rangle\\!\rangle$ splits as a non-trivial free
product, then $\Gamma$ is a path. Otherwise it is a cycle.

######  Proof.

This follows from Theorem 3.2 in [6] and from the fact the the element $x$
corresponds to a degree $2$ vertex in $\Gamma$. $\square$

######  Definition 2.6.

A RAAG with a path (resp. cycle) as underlying graph is called a path RAAG
(resp. cycle RAAG).

##  3 Elements in ear RAAGs arsing from degree 1 vertices

We set up a few preliminary definitions for ear RAAGs in accordance to the
terminology in graph theory (where we replace the word “vertex” by “pearl”).
If $A(\Gamma)$ is an ear RAAG, then the elements of $A(\Gamma)$ satisfying the
conditions of the Lemma 2.4 are an example of what we call pearls. If
$A(\Gamma)$ is a path RAAG, then these elements are also an example of inner
pearls. However, if $A(\Gamma)$ is a cycle RAAG, then we call a distinguished
pearl of $A(G)$ the end pearl. All other pearls in a cycle RAAG are called
inner pearls. In order to define these notions rigorously at the end of this
section, we characterise both all elements in path RAAGs that arise from the
degree $1$ vertices as well as all pairs of elements in an ear RAAG that arise
from pairs of adjacent degree $2$ vertices. For the time being, an element in
$A(\Gamma)$ is called an inner pearl if it satisfies the conditions in Lemma
2.4.

######  Proposition 3.1.

Let $A(\Gamma)$ be an ear RAAG and $x,y\in A(\Gamma)$ be inner pearls such
that $y\in C(x)$ and $y\langle\\!\langle x\rangle\\!\rangle\neq 1$ in
$A(\Gamma)/\langle\\!\langle x\rangle\\!\rangle$. Then $x$ and $y$ form part
of vertex basis such that they arise from adjacent vertices.

######  Proof.

Although $x$ and $y$ are vertex generators arising from degree $2$ vertices,
they might not form part of any vertex basis together. Assume that $x$ arises
from a vertex $v_{i}$. Identifying these elements as before, we have
$C(x)=\langle v_{i-1},v_{i},v_{i+1}\rangle$. Following the proof of 2.4, there
are two cases we need to consider, the first one being $A(\Gamma)=F_{2}\oplus
F_{2}$ and the second one being $A(\Gamma)\neq F_{2}\oplus F_{2}$. The first
case corresponds to $\Gamma$ being a cycle on $4$ vertices. There, we can only
infer from that proof that $y$ is conjugate to a primitive element in either
of the $F_{2}$ factors in $A(\Gamma)$. Since $A(\Gamma)$ splits as a direct
product, $y$ is contained in one of the factors. If $x$ and $y$ were in the
same factor, then the condition $y\in C(x)$ would imply that $y\in\langle
x\rangle$ and thus $y=x^{\pm 1}$. But this violates the condition that
$y\langle\\!\langle x\rangle\\!\rangle$ does not vanish in
$A(\Gamma)/\langle\\!\langle x\rangle\\!\rangle$. Therefore, $x$ and $y$ are
not in the same $F_{2}$-factor. Given that both $x$ and $y$ are primitive, we
may choose associated primitives in the corresponding factors to complete
$\\{x,y\\}$ to a vertex basis. This shows that they arise from adjacent
vertices.

In the second case, another look at the proof of Lemma 2.4 reveals that $y$
stems from a vertex $v_{j}$ only up to conjugation. Thus, assume that $a\in
A(\Gamma)$ is such that $y=av_{j}a^{-1}$. Because no element in $C(x)=\langle
v_{i-1},v_{i},v_{i+1}\rangle$ vanishes in $A(\Gamma)/\langle\\!\langle
v_{k}\rangle\\!\rangle$ for $k\notin\\{i-1,i,i+1\\}$, we infer that
$j\in\\{i-1,i,i+1\\}$. The fact that $y=av_{j}a^{-1}$ does not vanish in
$A(\Gamma)/\langle\\!\langle x\rangle\\!\rangle$ implies that
$j\in\\{i-1,i+1\\}$. Assume by contradiction that $a\notin C(x)$. Writing $a$
as a word in the vertex generators $\\{v_{1},\dots,v_{n}\\}$, we may assume
that it is reduced. If none of the last letters of $a$ is in $C(v_{j})$ even
after commutation, then $y=av_{j}a^{-1}$ is also a reduced word. Whether $x$
and $y$ form part of a vertex basis is invariant under conjugation. Since $x$
is invariant under conjugation by elements in $C(x)$ and we obtain $y$ by
conjugating $v_{j}$ by $a$, we may further assume that none of the initial
letters of the word $a$ is in $C(x)$ even after commutation. This implies that
the word $[x,y]=v_{i}av_{j}a^{-1}v_{i}^{-1}av_{j}^{-1}a^{-1}$ is reduced. On
page 15 of [6], it is mentioned that the word problem in RAAGs can be solved
by free reductions and commutations. Therefore, $[x,y]\neq 1$ and $y\neq
C(x)$. This contradiction implies that $a\in C(x)$. In particular, conjugation
by $a^{-1}$ maps $\\{x,y\\}$ to the adjacent vertex generators
$\\{v_{i},v_{j}\\}$. $\square$

We call pearls such as in the above proposition adjacent. This notion is used
to characterise all elements in path RAAGs that arise from degree $1$
vertices.

######  Lemma 3.2.

Let $A(\Gamma)$ be an ear RAAG, $x\in A(\Gamma)$ an element and $y,z\in
A(\Gamma)$ adjacent inner pearls such that $x\in C(y)$ and such that
$A(\Gamma)/\langle\\!\langle y\rangle\\!\rangle$ splits as a free product with
one factor being $\mathbb{Z}$. Assume that $\\{x\langle\\!\langle
y\rangle\\!\rangle,z\langle\\!\langle y\rangle\\!\rangle\\}$ is a generating
set of $C(y)\langle\\!\langle y\rangle\\!\rangle/\langle\\!\langle
y\rangle\\!\rangle$ and that $x\langle\\!\langle y,z\rangle\\!\rangle\in
A(\Gamma)/\langle\\!\langle y,z\rangle\\!\rangle$ is not a multiple of an
another element. Then there is a vertex basis of $A(\Gamma)$ containing $x$,
$y$ and $z$ such that $x$ arises from a degree $1$ vertex in $\Gamma$, $y$
from its adjacent vertex and $z$ is adjacent to $y$.

######  Proof.

Note that all the conditions on the elements $x$, $y$ and $z$ are invariant
under conjugation. Since $y$ and $z$ are adjacent inner pearls, we may assume
that $y$ arises from a degree $2$ vertex $v_{i}$ and $z$ from either $v_{i-1}$
or $v_{i+1}$. As $A(\Gamma)/\langle\\!\langle y\rangle\\!\rangle$ splits as a
non-trivial free product, $A(\Gamma)$ is a path RAAG. More specifically, there
exist two paths $\Gamma^{\prime}$ and $\Gamma^{\prime\prime}$ such that
$\Gamma\setminus\\{y\\}=\Gamma^{\prime}\sqcup\Gamma^{\prime\prime}$ and
$A(\Gamma)/\langle\\!\langle y\rangle\\!\rangle=A(\Gamma^{\prime})\ast
A(\Gamma^{\prime\prime})$. We already know that there is also a splitting of
the form $A(\Gamma)/\langle\\!\langle y\rangle\\!\rangle=\mathbb{Z}\ast A$. By
to the Grushko Decomposition Theorem, [11, p. 168–169] we infer that
$A(\Gamma^{\prime})\cong\mathbb{Z}$ and $A(\Gamma^{\prime\prime})\cong A$.
Since isomorphic RAAGs have the same underlying graph, [6, Theorem 2.6] the
graph $\Gamma^{\prime}$ consists of a single vertex. If we assume that $v_{1}$
and $v_{n}$ are the endpoints of $\Gamma$, then the only choices of $y$
inducing an isolated vertex in $\Gamma\setminus\\{y\\}$ are $y=v_{2}$ and
$y=v_{n-1}$. Let us assume $y=v_{2}$. As $z$ is an inner pearl adjacent to
$y$, we have $z=v_{3}$.

Because $x\in C(y)$, we see that $x\in\langle v_{1},v_{2},v_{3}\rangle$. Note
that $x\langle\\!\langle y\rangle\\!\rangle$ and $z\langle\\!\langle
y\rangle\\!\rangle$ are associated primitives in
$\big{\langle}v_{1}\langle\\!\langle y\rangle\\!\rangle,v_{3}\langle\\!\langle
y\rangle\\!\rangle\big{\rangle}\cong F_{2}$. If we restrict the projection
$A(\Gamma)/\langle\\!\langle y\rangle\\!\rangle\rightarrow
A(\Gamma)/\langle\\!\langle y,z\rangle\\!\rangle$ to $C(y)\langle\\!\langle
y\rangle\\!\rangle/\langle\\!\langle y\rangle\\!\rangle$, then we obtain a
homomorphism
$\varphi:F_{2}\rightarrow\mathbb{Z}=\big{\langle}v_{1}\langle\\!\langle
y,z\rangle\\!\rangle\big{\rangle}$. By the universal property of the
abelianisation $(F_{2})_{ab}\cong\mathbb{Z}^{2}$, $\varphi$ factors as
$F_{2}\rightarrow\mathbb{Z}^{2}\rightarrow\mathbb{Z}$. If we view
$x\langle\\!\langle y\rangle\\!\rangle$ as an element of $F_{2}$, then we know
from the proof of Lemma 2.4 that its image $\overline{x\langle\\!\langle
y\rangle\\!\rangle}$ in the abelianisation $\mathbb{Z}^{2}$ is also a
primitive element. In particular, there are coprime integers $c$, $d$ such
that $\overline{x\langle\\!\langle
y\rangle\\!\rangle}=c\cdot\overline{v_{1}\langle\\!\langle
y\rangle\\!\rangle}+d\cdot\overline{v_{3}\langle\\!\langle
y\rangle\\!\rangle}$. Therefore, $\varphi(x)=cv_{1}\langle\\!\langle
y,z\rangle\\!\rangle$. The condition that $x\langle\\!\langle
y,z\rangle\\!\rangle$ is not a multiple of another element implies that $c=\pm
1$. According to Corollary 3.3 in [7], there is, up to conjugacy, a unique
primitive element in $F_{2}$ mapping down to $\overline{x\langle\\!\langle
y\rangle\\!\rangle}$ in the abelianisation. For any cyclic permutation $f$ of
the word $v_{1}^{c}v_{3}^{d}$ the element $f\langle\\!\langle
y\rangle\\!\rangle$ has this property. There is such $f$ together with a
reduced word $a$ in the letters $\\{v_{1}^{\pm 1},v_{3}^{\pm 1}\\}$ such that
$afa^{-1}\langle\\!\langle y\rangle\\!\rangle$ is a reduced word in
$\\{v_{1}^{\pm 1}\langle\\!\langle y\rangle\\!\rangle,v_{3}^{\pm
1}\langle\\!\langle y\rangle\\!\rangle\\}$ and $x\langle\\!\langle
y\rangle\\!\rangle=afa^{-1}\langle\\!\langle y\rangle\\!\rangle$. Whether
$\\{x\langle\\!\langle y\rangle\\!\rangle,z\langle\\!\langle
y\rangle\\!\rangle\\}$ generates $C(y)\langle\\!\langle
y\rangle\\!\rangle/\langle\\!\langle y\rangle\\!\rangle$ is invariant under
conjugation by $v_{3}^{\pm 1}\langle\\!\langle y\rangle\\!\rangle$. Thus, we
may assume that the initial letter of $a$ is not $v_{3}\langle\\!\langle
y\rangle\\!\rangle$ or $v_{3}^{-1}\langle\\!\langle y\rangle\\!\rangle$. If
the word $a$ is nontrivial after this last conjugation, then we obtain the
contradiction that $x\langle\\!\langle y\rangle\\!\rangle$ and
$z\langle\\!\langle y\rangle\\!\rangle$ do not generate $C(y)\langle\\!\langle
y\rangle\\!\rangle/\langle\\!\langle y\rangle\\!\rangle$. We conclude that
there are integers $\gamma,\delta\in\mathbb{Z}$ such that $x\langle\\!\langle
y\rangle\\!\rangle=v_{3}^{\gamma}v_{1}^{c}v_{3}^{\delta}\langle\\!\langle
y\rangle\\!\rangle$.

Therefore, there is $b\in\langle\\!\langle y\rangle\\!\rangle$ such that
$x=v_{3}^{\gamma}v_{1}^{c}v_{3}^{\delta}b$. We may write $b$ as a reduced word
in the letters $v_{1}^{\pm 1},\dots,v_{n}^{\pm 1}$. Here, $n\geq 4$ as
$A(\Gamma)$ contains the two inner pearls $y$ and $z$. Assume by contradiction
that $b$ contains at least one letter $v_{j}$ or $v_{j}^{-1}$ for $j\geq 4$.
Let $u$ be the first instance of such a letter in $b$ and $w$ the last one.
Note that $x=v_{3}^{\gamma}v_{1}^{c}v_{3}^{\delta}b$ as well as
$v_{3}^{\gamma}v_{1}^{c}v_{3}^{\delta}$, the first letters in $b$ before $u$
and the last letters after $w$ are contained in the subgroup $C(y)$. If
$b^{\prime}$ denotes the subword of $b$ starting in $u$ and ending in $w$,
then we infer that $b^{\prime}$ is also contained in $C(y)$. The initial and
terminal letters of $b$ not being in $C(y)$, the word
$[y,b^{\prime}]=v_{2}b^{\prime}v_{2}^{-1}b^{\prime-1}$ is reduced. As at the
end of the proof of Proposition 3.1, we deduce the contradiction that
$b^{\prime}\notin C(y)$. Thus, $b$ can be written as a reduced word in the
letters $v_{1}^{\pm 1},v_{2}^{\pm 1},v_{3}^{\pm 1}$. Since
$b\in\langle\\!\langle y\rangle\\!\rangle$, we can insert words of the form
$ee^{-1}$ into $b$ so that it becomes a product of terms $gy^{\pm 1}g^{-1}$
with $g$ a word in the letters $v_{1}^{\pm 1},v_{2}^{\pm 1},v_{3}^{\pm 1}$.
Noting that $C(y)=\langle v_{1},v_{2},v_{3}\rangle$, we conclude that
$b=v_{2}^{\eta}$ for $\eta\in\mathbb{Z}$. In particular,
$x=v_{3}^{\gamma}v_{1}^{c}v_{3}^{\delta}v_{2}^{\eta}$. According to the
treatment of automorphisms of RAAGs on page 25 of [6], we may apply so-called
dominated transvections mapping $v_{1}$ to $v_{1}v_{2}^{\pm 1}$,
$v_{1}v_{3}^{\pm 1}$ or $v_{3}^{\pm 1}v_{1}$ and leaving all other vertex
generators unchanged. Therefore, we may assume that $x=v_{1}^{c}$ for $c=\pm
1$, $y=v_{2}$ and $z=v_{3}$. Invoking again [6, p. 25], we may apply the so-
called vertex inversion mapping $v_{1}$ to $v_{1}^{-1}$ and leaving all the
other vertex generators invariant. Hence, $x=v_{1}$, $y=v_{2}$ and $z=v_{3}$.
$\square$

Lemma 2.4 and Lemma 3.2 suggest that we can characterise all elements in an
ear RAAG that arise from a degree $1$ vertex or a degree $2$ vertex. However,
this is not the case. Namely, inspecting the conditions of the lemmas, we see
that they do not cover all ear RAAGs. More specifically, Lemma 2.4 cannot be
applied to $A(\Gamma)$ if $\Gamma$ is a path $P_{2}$ on two vertices or a
cycle $C_{3}$ on three vertices. Lemma 3.2 fails for $A(\Gamma)$ if $\Gamma$
is a path $P_{3}$ on three vertices. In these three cases, specifying which
vertices are end points or inner vertices already determines the underlying
graph. Thus, the task in these cases is to specify a vertex basis without
saying upfront that the elements are generators. This is done in the following
proposition.

######  Proposition 3.3.

If $x,y\in A(P_{2})=\mathbb{Z}^{2}$ are such that $x$ and $y\langle
x\rangle\in A(P_{2})/\langle x\rangle$ are not multiples of other elements,
then $\\{x,y\\}$ is a vertex basis of $A(P_{2})$. Moreover if $\xi,\eta,\zeta$
are elements in $A(C_{3})=\mathbb{Z}^{3}$ such that
$A(C_{3})/\langle\zeta\rangle\cong\mathbb{Z}^{2}$ and
$\xi\langle\zeta\rangle,\eta\langle\zeta\rangle\in A(C_{3})/\langle\xi\rangle$
satisfy the same conditions as $x$ and $y$ above, then $\xi,\eta,\zeta$ form a
vertex basis of $A(C_{3})$. Lastly, if $\chi,a,b\in A(P_{3})=\mathbb{Z}\oplus
F_{2}$ satisfy the conditions of Lemma 2.4, then they form a vertex basis with
$\chi$ corresponding to the inner vertex and $a$ and $b$ to the endpoints.

######  Proof.

At the end of the proof of Lemma 2.4, we did not only define primitive
elements in $\mathbb{Z}^{2}$, but we also demonstrated that an element in
$\mathbb{Z}^{2}$ is primitive if and only if it is no multiple of another
element. Thus, $x$ is a primitive element and $y\langle x\rangle$ generates
$A(P_{2})/\langle x\rangle\cong\mathbb{Z}$. For any element $g\in A(P_{2})$
there is $c\in\mathbb{Z}$ such that $g\langle x\rangle=c\cdot y\langle
x\rangle$ and $d\in\mathbb{Z}$ such that $g=d\cdot x+c\cdot y$. Therefore,
$\\{x,y\\}$ is a vertex basis of $A(P_{2})$. Going over to
$\xi,\eta,\zeta\in\mathbb{Z}^{3}$, let $h\in\mathbb{Z}^{3}$ be an element.
Since $\xi\langle\zeta\rangle$, $\eta\langle\zeta\rangle$ form a generating
set of $\mathbb{Z}^{3}/\langle\zeta\rangle\cong\mathbb{Z}^{2}$, there are
$\gamma,\delta\in\mathbb{Z}$ such that
$h\langle\xi\rangle=\gamma\cdot\xi\langle\zeta\rangle+\delta\cdot\eta\langle\zeta\rangle$.
There is $\epsilon\in\mathbb{Z}$ such that
$h=\epsilon\cdot\xi+\gamma\cdot\eta+\delta\cdot\zeta$, proving that
$\\{\xi,\eta,\zeta\\}$ is a vertex basis of $A(C_{3})$. In the last case,
Lemma 2.4 implies that $\chi$ arises from the only inner vertex of $P_{3}$. As
$A(P_{3})=\langle\chi\rangle\oplus\langle a,b\rangle$ with $\chi$ being a
central element, $\\{\chi,a,b\\}$ is a vertex basis of $A(P_{3})$. $\square$

Being able to characterise all elements in an ear RAAG that arise from a
degree $1$ or $2$ vertex in the underlying graph, we can rigorously define
pearls.

######  Definition 3.4.

Let $A(\Gamma)$ be an ear RAAG. An element $x\in A(\Gamma)$ is called a pearl
if it satisfies the conditions of Lemma 2.4, of Lemma 3.2 or of Proposition
3.3. It is called an end pearl if it arises from a degree $1$ vertex in a path
(as specified in Lemma 3.2 or in Proposition 3.3) or if it is marked as a
distinguished element in a cycle RAAG. All other pearls are called inner
pearls. Two pearls $x$ and $y$ are called adjacent if they satisfy one of the
following. They are inner pearls satisfying the conditions of Proposition 3.1.
Or $x$ is an end pearl and $y$ an inner pearl such that they fulfil the
conditions of Lemma 3.2 together with another inner vertex $z$. Or they
satisfy the conditions of Proposition 3.3 for $A(P_{2})$, those for $A(C_{3})$
together with another pearl $\zeta$ or those for $A(P_{3})$ together with
another end pearl $b$.

##  4 Vertex bases in ear RAAGs and loose ear decompositions

In Proposition 3.3, we might have succeeded in determining the vertex bases
only for those ear RAAGs whose underlying graphs have at most three vertices.
However, in general, there is no guarantee that a set of adjacent pearls forms
a vertex basis. To give an example, let us consider $A(C_{4})=F_{2}\oplus
F_{2}$. Assume that the first $F_{2}$-factor is generated by $x$ and $y$ and
the other $F_{2}$-factor by $a$ and $b$. The pearl $x$ is adjacent to
$bab^{-1}$ where the latter is adjacent to $y$. In turn, $y$ is adjacent to
$aba^{-1}$ where $aba^{-1}$ is adjacent to $x$. However, the elements
$x,y,bab^{-1},aba^{-1}$ generate a subgroup isomorphic to $F_{2}\oplus F_{2}$
that is not equal to all of $A(C_{4})$. The following proposition sets the
base to assemble pearls into vertex bases.

######  Proposition 4.1.

Let $A(\Gamma)$ be an ear RAAG with $d(A(\Gamma))>3$ and $x,y,z\in A(\Gamma)$
be inner pearls such that $y,z\in C(x)$ and $y\langle\\!\langle
x\rangle\\!\rangle,z\langle\\!\langle x\rangle\\!\rangle$ form a generating
set of $C(x)\langle\\!\langle x\rangle\\!\rangle/\langle\\!\langle
x\rangle\\!\rangle$. Then $x$, $y$ and $z$ form part of vertex basis such that
the vertex corresponding to $x$ is adjacent to the one corresponding to $y$ as
well as the one corresponding to $z$.

######  Proof.

As $A(\Gamma)\neq A(C_{3})$ by Proposition 2.3, all inner pearls satisfy the
conditions in Lemma 2.4. By the proof of Proposition 3.1, we first need to
consider the case where $A(\Gamma)=F_{2}\oplus F_{2}$. Since
$y\langle\\!\langle x\rangle\\!\rangle$, $z\langle\\!\langle
x\rangle\\!\rangle$ do not vanish in $A(\Gamma)/\langle\\!\langle
x\rangle\\!\rangle$, it follows from this proof that $x$ is a primitive
element in one $F_{2}$-factor while $y$ and $z$ are primitive elements in the
other $F_{2}$-factor. Because the quotient $C(x)\langle\\!\langle
x\rangle\\!\rangle/\langle\\!\langle x\rangle\\!\rangle$ is isomorphic to the
latter $F_{2}$-factor, $y$ and $z$ are associated primitives in this factor.
If $x$ and $t$ are associated primitives in their $F_{2}$-factors, then
$\\{x,y,z,t\\}$ is a vertex basis of $A(\Gamma)=F_{2}\oplus F_{2}$ of the
desired form. Again by the proof of Proposition 3.1, suppose that
$A(\Gamma)\ncong F_{2}\oplus F_{2}$, that $x$ corresponds to a vertex $v_{i}$
and that there are words $a,b\in C(v_{i})$ such that $y=av_{j}a^{-1}$ and
$z=bv_{k}b^{-1}$ for $j,k\in\\{i-1,i+1\\}$. Conjugating by $a^{-1}$ yields
$y=v_{j}$, $x=v_{i}$ and $z=ev_{k}e^{-1}$ for $e\in C(v_{i})$. We may assume
that $e$ is a reduced word in $v_{i-1}^{\pm 1},v_{i+1}^{\pm 1}$ that does not
end in the letter $v_{k}$ or $v_{k}^{-1}$. Whether $y\langle\\!\langle
x\rangle\\!\rangle=v_{j}\langle\\!\langle v_{i}\rangle\\!\rangle$ and
$z\langle\\!\langle x\rangle\\!\rangle=ev_{k}e^{-1}\langle\\!\langle
v_{i}\rangle\\!\rangle$ generate $\big{\langle}v_{i-1}\langle\\!\langle
x\rangle\\!\rangle,v_{i+1}\langle\\!\langle
x\rangle\\!\rangle\,\big{\rangle}\cong F_{2}$ is invariant under conjugation.
Thus, we may further assume that the word $e$ does not start in $v_{j}$ or
$v_{j}^{-1}$. If $e$ was still nontrivial, then $\\{y\langle\\!\langle
x\rangle\\!\rangle,z\langle\\!\langle x\rangle\\!\rangle\\}$ would not a be
generating set of $C(x)\langle\\!\langle x\rangle\\!\rangle/\langle\\!\langle
x\rangle\\!\rangle$. Therefore $e=1$, $y=v_{j}$ and $z=v_{k}$. Since $j\neq
k$, we conclude that $\\{x,y,z\\}=\\{v_{i-1},v_{i},v_{i+1}\\}$. $\square$

######  Lemma 4.2.

Let $A(\Gamma)$ be a path RAAG. Let $\\{p_{1},\dots,p_{m}\\}\subseteq
A(\Gamma)$ be a set of pearls with the following properties. The triples
$\\{p_{1},p_{2},p_{3}\\}$ and $\\{p_{m-2},p_{m-1},p_{m}\\}$ satisfy the
conditions of Lemma 3.2 where $p_{1}$ and $p_{m}$ are the end pearls. The
inner pearls $p_{i-1}$, $p_{i}$, $p_{i+1}$ satisfy the conditions of
Proposition 4.1 for any $i\in\\{3,\dots,m-2\\}$. Then
$\\{p_{1},\dots,p_{m}\\}$ is a vertex basis.

######  Proof.

If $v_{1},\dots,v_{n}$ denote the vertices of $\Gamma$, then we may assume by
Lemma 3.2 that $p_{1}=v_{1}$, $p_{2}=v_{2}$ and $p_{3}=v_{3}$. Since $p_{3}$
is an inner pearl, we see that $m\geq 4$. If $m\neq 4$, then $p_{4}$ is not an
end pearl and we have at least one triple $\\{p_{i-1}$, $p_{i}$, $p_{i+1}\\}$
satisfying the conditions of Proposition 4.1 for $i\in\\{3,\dots,m-2\\}$.
Assume by induction that $p_{i-1}=v_{i-1}$ and $p_{i}=v_{i}$. Following the
proof of that proposition, there is $c\in\mathbb{Z}$ such that
$p_{i+1}=v_{i-1}^{c}v_{i+1}v_{i-1}^{-c}$. By the treatment of RAAG
automorphism in [6, p. 25], we can apply the so-called partial conjugation
that conjugates all vertex generators arising from the connected component of
$A(\Gamma)\setminus\mathrm{star}(v_{i-1})$ containing $v_{i+1}$ by the element
$v_{i-1}$ and that leaves all other vertex generators invariant. Since this
completes the inductive step, we need to find an isomorphism of $A(\Gamma)$
that leaves $p_{1},\dots,p_{m-1}$ invariant and maps $p_{m}$ to $v_{m}$. This
is constructed in the proof of Lemma 3.2. Namely, in the first step, we deduce
that $p_{m}=v_{m-2}^{\gamma}v_{m}^{d}v_{m-2}^{\delta}v_{m-1}^{\eta}$ for
$\gamma,\delta\in\mathbb{Z}$ and $d=\pm 1$. The desired isomorphism is
obtained by the dominated transvections and vertex inversions mapping $p_{m}$
to $v_{m}$. $\square$

######  Lemma 4.3.

Let $A(\Gamma)$ be a cycle RAAG with $d(A(\Gamma))>3$. Let
$\\{p_{1},\dots,p_{m}\\}\subseteq A(\Gamma)$ be a set of pearls such that for
any $i\in\\{1,\dots,m\\}$ the triple $\\{p_{i-1},p_{i},p_{i+1}\\}$ satisfies
the conditions of Proposition 4.1 where we consider the indices modulo $m$. If
either $m=d(A(\Gamma))=4$ or $d(A(\Gamma))\geq 5$, then
$\\{p_{1},\dots,p_{m}\\}$ is a vertex basis.

######  Proof.

If $m=d(A(\Gamma))=4$, then $A(\Gamma)=F_{2}\oplus F_{2}$. Applying
Proposition 4.1 to the triple $\\{p_{1},p_{2},p_{3}\\}$, we deduce that
$p_{1}$ and $p_{3}$ are associate primitives in one $F_{2}$-factor while
$p_{2}$ is a primitive element in the other $F_{2}$-factor. By the triple
$\\{p_{2},p_{3},p_{4}\\}$, we conclude that $p_{2}$ and $p_{4}$ are associate
primitives of the respective $F_{2}$-factor. In particular,
$\\{p_{1},p_{2},p_{3},p_{4}\\}$ is a vertex basis. Suppose now that
$d(A(\Gamma))\geq 5$. If $v_{1},\dots,v_{n}$ denote the vertices of $\Gamma$,
then we may assume that $p_{1}=v_{1}$, $p_{2}=v_{2}$ and $p_{3}=v_{3}$ by
Proposition 4.1. Following the proof of this proposition with the triple
$\\{p_{2},p_{3},p_{4}\\}$, there is $c_{2}\in\mathbb{Z}$ such that
$p_{4}=v_{2}^{c_{2}}v_{4}v_{2}^{-c_{2}}$. Assume by induction that there are
words $w_{i}=\prod_{j=2}^{i-2}v_{j}^{c_{j}}$ such that
$p_{i}=w_{i}v_{i}w_{i}^{-1}$. Since $w_{i-1}v_{i-2}^{c_{i-2}}=w_{i}$ and
$v_{i-2}\in C(v_{i-1})$, conjugating the triple $\\{p_{i-1},p_{i},p_{i+1}\\}$
by $w_{i}^{-1}$ yields $\\{v_{i-1},v_{i},w_{i}^{-1}p_{i+1}w_{i}\\}$. Using the
latter triple, there is $c_{i-1}\in\mathbb{Z}$ such that
$w_{i}^{-1}p_{i+1}w_{i}=v_{i-1}^{c_{i-1}}v_{i+1}v_{i-1}^{-c_{i-1}}$ by the
proof of Proposition 4.1. Conjugating the last equality by $w_{i}$ completes
the inductive step. As $\Gamma$ is a cycle, we infer that

$\Big{(}\prod_{j=2}^{m-1}v_{j}^{c_{j}}\Big{)}v_{1}\Big{(}\prod_{j=2}^{m-1}v_{j}^{c_{j}}\Big{)}^{-1}=p_{1}=v_{1}\,.$

Conjugating by $v_{2}^{-c_{2}}$ and multiplying by $v_{1}^{-1}$, we deduce
that

$\Big{(}\prod_{j=3}^{m-1}v_{j}^{c_{j}}\Big{)}v_{1}\Big{(}\prod_{j=3}^{m-1}v_{j}^{c_{j}}\Big{)}^{-1}v_{1}^{-1}=1\,.$

If $c_{j}\neq 0$ for any $j\in\\{3,\dots,m-1\\}$, then the left hand side
would be a reduced word in $v_{1}^{\pm 1},\dots,v_{n}^{\pm 1}$. As seen at the
end of the proof of Proposition 3.1, this word cannot equal the identity. This
contradiction implies that $w_{i}=v_{2}^{c_{2}}$ and
$p_{i}=v_{2}^{c_{2}}v_{i}v_{2}^{-c_{2}}$ for any $i\in\\{4,\dots,m\\}$.
Because $p_{1},p_{2},p_{3}\in C(v_{2})$, conjugating by $v_{2}^{-c_{2}}$
yields $p_{i}=v_{i}$ for every $i\in\\{1,\dots,m\\}$. Finally, since the
triple $\\{p_{m-1},p_{m},p_{1}\\}$ satisfies the conditions of Proposition
4.1, $v_{m}$ is adjacent to $v_{1}$ and $\\{p_{1},\dots,p_{m}\\}$ is a vertex
basis. $\square$

Having been able to characterise vertex bases in ear RAAG without specifying
that the elements in question are vertex generators, we can make the following
definition.

######  Definition 4.4.

Let $A(\Gamma)$ be an ear RAAG. A pearl chain $\\{p_{1},\dots,p_{n}\\}$ is a
set of pearls in $A(\Gamma)$ that satisfies the conditions of Proposition 3.3,
of Lemma 4.2 or of Lemma 4.3. An ear RAAG together with a pearl chain
$(A(\Gamma),\\{p_{1},\dots,p_{n}\\})$ is called a decorated ear RAAG.

Pearl chains in turn enable us to characterise loose ear decompositions by
RAAGs.

######  Theorem 4.5.

Suppose
$\big{\\{}(A(\Gamma_{i}),\\{p_{i,1},\dots,p_{i,n_{i}}\\})\big{\\}}_{i=1}^{m}$
is a finite sequence of decorated ear RAAGs. Define $G_{1}:=A(\Gamma_{1})$
together with the distinguished elements $\\{p_{1,1},\dots,p_{1,n_{1}}\\}$.
Assuming that we have defined the group $G_{k}$ and have kept track of the
distinguished elements $p_{i,j}$ for $i\in\\{1,\dots,k\\}$ and
$j\in\\{1,\dots,n_{i}\\}$, we define
$G_{k+1}:=G_{k}\ast_{H_{k}}A(\Gamma_{k+1})$ where

$H_{k}=\\{1\\},\,H_{k}=\\{p_{k+1,1}=p_{i_{1},j_{1}}\\}\text{ or
}H_{k}=\\{p_{k+1,1}=p_{i_{1},j_{1}},p_{k+1,n_{k+1}}=p_{i_{2},j_{2}}\\}\,,$

$i_{1},i_{2}\in\\{1,\dots,k\\}$, $j_{1}\in\\{1,\dots,n_{i_{1}}\\}$ and
$j_{2}\in\\{1,\dots,n_{i_{2}}\\}$ . Then $G_{m}$ is a RAAG whose underlying
graph $\Gamma$ has the following loose ear decomposition. We define
$\Gamma_{1}^{\prime}:=\Gamma_{1}$. If we denote by $v_{i,j}$ the vertex in
$\Gamma_{i}$ corresponding to the pearl $p_{i,j}\in A(\Gamma_{i})$, we
construct the graph $\Gamma_{k+1}^{\prime}$ from $\Gamma_{k}^{\prime}$ and
$\Gamma_{k+1}$ as a disjoint union, by identifying only $v_{k+1,1}$ with
$v_{i_{1},j_{1}}$ or by identifying both $v_{k+1,1}$ with $v_{i_{1},j_{1}}$
and $v_{k+1,n_{k+1}}$ with $v_{i_{2},j_{2}}$ depending on the corresponding
move in the RAAGs. Finally,
$\Gamma=\Gamma_{m}^{\prime}=\bigcup_{i=1}^{m}\Gamma_{i}$.

On the other hand, if we are given a loose ear decomposition of $\Gamma$ by
the ears $\Gamma_{1},\dots,\Gamma_{m}$, then the iterated amalgamated product
of $A(\Gamma_{1}),\dots,A(\Gamma_{m})$ constructed as above is isomorphic to
the RAAG $A(\Gamma)$.

######  Proof.

Recall that pearl chains are vertex bases of ear RAAGs. Thus, in the above
iterated amalgamated products, we are identifying vertex generators of two
RAAGs, giving the presentation of another RAAG. The resulting group
presentation is in bijective correspondence with the associated loose ear
decomposition. $\square$

######  Remark 4.6.

Ear decompositions are the special case of loose ear decompositions where the
first ear is a cycle and the endpoints of each subsequent ear are contained
the previous ears. Hence, we can reformulate the above theorem for ear
decompositions if we use the appropriate identifications and amalgamated
products.

######  Definition 4.7.

A (loose) ear decomposition of a RAAG $A(\Gamma)$ is a specification of ear
RAAGs $A(\Gamma_{1})$, …, $A(\Gamma_{m})$ and of an iterated amalgamated
product representing $A(\Gamma)$ as in Theorem 4.5. We call the set of
elements $\\{p_{i,j}\mid 1\leq i\leq m,1\leq j\leq n_{i}\\}$ of $A(\Gamma)$
the pearls of the (loose) ear decomposition.

In the same way as there are many possible choices of vertex bases for a RAAG,
there is no unique choice of a pearl chain for an ear RAAG. In particular,
(loose) ear decomposition of RAAGs are not unique. It is also unclear whether
there is an algorithm to determine a (loose) ear decomposition of a given
RAAG. In the proof of Theorem 4.5, we used the underlying graph of a given
RAAG, but to our knowledge, there is no algorithm to determine it. Theorem 2.6
in [6] states that the group cohomology ring of a RAAG characterises its
underlying graph. We are not aware of an algorithm to determine the cohomology
of RAAGs, either. Since all our subsequent results make use of (loose) ear
decompositions, it is also unclear whether they allow an algorithmic
implementation.

##  5 Applications of loose ear decompositions of RAAGs

Our first application of loose ear decompositions is a characterisation of
graph subdivisions in terms of RAAGs. For this, it is more convenient to
consider the reverse procedure of an edge subdivision. Namely, a vertex
smoothing is the process of removing a degree 2 vertex from a graph and
connecting its former neighbours by an edge [4, p. 305].

######  Proposition 5.1.

Suppose that $A(\Gamma)$ is a RAAG. If we are given a loose ear decomposition
of $A(\Gamma)$, then a vertex smoothing of $v\in V(\Gamma)$ determines a
homomorphism of RAAGs $A(\Gamma)\rightarrow A(\Gamma)/\langle\\!\langle
p,[q,r]\rangle\\!\rangle$ where $p$ is the pearl corresponding to $v$ and $q$,
$r$ denote its adjacent pearls. On the other hand, let $p^{\prime}$ be a pearl
in a loose ear decomposition of $A(\Gamma)$ and $q^{\prime}$, $r^{\prime}$ be
its unique adjacent pearls. Then the homomorphism $A(\Gamma)\rightarrow
A(\Gamma)/\langle\\!\langle
p^{\prime},[q^{\prime},r^{\prime}]\rangle\\!\rangle$ determines a vertex
smoothing of $\Gamma$.

######  Proof.

Given a loose ear decomposition of $A(\Gamma)$, denote by $p$ the pearl
corresponding to $v$ and by $q$ and $r$ its adjacent pearls. Because the RAAG
$A(\Gamma)$ can be defined by a group presentation using the pearls of the
loose ear decomposition, smoothing out the vertex $v$ corresponds to the
homomorphism of RAAGs $A(\Gamma)\rightarrow A(\Gamma)/\langle\\!\langle
p,[q,r]\rangle\\!\rangle$. For the other implication, the vertex $v^{\prime}$
associated to the pearl $p^{\prime}$ has two unique neighbours. The
homomorphism $A(\Gamma)\rightarrow A(\Gamma)/\langle\\!\langle
p^{\prime},[q^{\prime},r^{\prime}]\rangle\\!\rangle$ corresponds to smoothing
out the vertex $v^{\prime}$. $\square$

######  Definition 5.2.

A homomorphism $\varphi:A(\Gamma)\rightarrow A(\Lambda)$ as in the previous
proposition is called a smoothing homomorphism.

######  Lemma 5.3.

Let $A(\Gamma)$ and $A(\Lambda)$ be RAAGs. Then $\Gamma$ is a graph
subdivision of $\Lambda$ if and only if $A(\Gamma)\cong A(\Lambda)$ or there
exists a finite sequence of smoothing homomorphisms
$\\{\varphi_{i}:A(\Gamma_{i})\rightarrow A(\Gamma_{i-1})\\}_{i=1}^{m}$ such
that $A(\Gamma_{m})=A(\Gamma)$ and $A(\Gamma_{0})\cong A(\Lambda)$.

######  Proof.

The case where the graphs $\Gamma$ and $\Lambda$ are isomorphic corresponds to
the case where $A(\Gamma)$ and $A(\Lambda)$ are isomorphic, which is covered
by [6, Theorem 2.6]. Assume that the graphs $\Gamma$ and $\Lambda$ are not
isomorphic. Every smoothing homomorphism corresponds to a vertex smoothing
which corresponds uniquely to an edge subdivision. Hence, for a graph
subdivision of $\Gamma$, we can construct the corresponding sequence of
smoothing homomorphisms. If we are given a sequence of smoothing homomorphisms
instead, we invoke [6, Theorem 2.6] to obtain the underlying edge subdivisions
forming the graph subdivision. $\square$

Graph subdivisions can be used to characterise planar graphs in terms of
RAAGs. For this, let $K_{5}$ be the complete graph on $5$ vertices and
$K_{3,3}$ be the complete bipartite graph obtained as a join of two graphs of
$3$ isolated vertices.

######  Theorem 5.4.

Let $A(\Gamma)$ be a RAAG. Assume that
$\\{\varphi_{i}:A(\Gamma_{i})\rightarrow A(\Gamma_{i-1})\\}_{i=1}^{m}$ is a
sequence of smoothing homomorphisms such that $A(\Gamma_{m})=A(\Gamma)$ and
such that there is no smoothing homomorphism from $A(\Gamma_{0})$ to any other
RAAG. Then the graph $\Gamma$ is planar if and only $A(\Gamma_{0})$ does not
contain $\mathbb{Z}^{5}$ as a subgroup and does not possess a loose ear
decomposition with pearls $\\{p_{i},q_{i}\\}_{i=1}^{3}$ such that the
subgroups $P:=\langle p_{1},p_{2},p_{3}\rangle$ and $Q:=\langle
q_{1},q_{2},q_{3}\rangle$ are isomorphic to $F_{3}$ and $\langle
P,Q\rangle\cong F_{3}\oplus F_{3}$.

######  Proof.

As $\Gamma$ is a subdivision of $\Gamma_{0}$, the former graph is planar if
and only if the latter one is. [4, Proposition 7.5.15] The graph $\Gamma_{0}$
is not a subdivision of another graph by our assumptions. This together with
Kuratowski’s Theorem [4, Theorem 7.4.1] implies that $\Gamma_{0}$ is planar if
and only if it does not contain a copy of $K_{5}$ or $K_{3,3}$ as a subgraph.
According to [6, Theorem 3.5], $\Gamma_{0}$ contains $K_{5}$ as a subgraph if
and only if $A(\Gamma_{0})$ contains $\mathbb{Z}^{5}$ as a subgroup. If
$u_{i}$ are the vertices corresponding to the pearls $p_{i}$ and $v_{i}$ the
ones corresponding to $q_{i}$, then $P$ (respectively $Q$) is isomorphic to
$F_{3}$ if and only if there are no edges between the vertices $u_{i}$
(respectively $v_{i}$) by [6, Theorem 3.2]. Using [6, Theorem 3.1], $\langle
P,Q\rangle$ decomposes as non-trivial direct product only if the vertices
$u_{i}$ form a non-trivial join with the vertices $v_{j}$, meaning a copy of
$K_{3,3}$. $\square$

Moving forward, the following equivalent formulation of graph minors allows us
to describe them in terms of RAAGs. An edge contraction of a graph consists of
identifying two adjacent vertices while deleting the edge between them [2, p.
21].

######  Proposition 5.5.

Let $X$ and $Y$ be graphs. Then $X$ is a minor of $Y$ if and only if there are
finite sequences of graphs $\\{A_{i}\\}_{i=1}^{a}$, $\\{B_{j}\\}_{j=1}^{b}$
and $\\{C_{k}\\}_{k=1}^{c}$ with $A_{1}=Y$, $A_{a}=B_{1}$, $B_{b}=C_{c}$,
$C_{1}=X$ and the following properties. The graph $A_{i+1}$ is obtained from
$A_{i}$ by a vertex deletion, $B_{j+1}$ from $B_{j}$ by an edge contraction
and $C_{k}$ from $C_{k+1}$ by an edge deletion.

We can visualise the sequences of graphs as

${X=C_{1}}$${Y=A_{1}}$${A_{a}=B_{1}}$${B_{b}=C_{c}}$vertex deletionsedge
contractionsedge deletions

######  Proof.

It follows from [2, Corollary 1.7.2] that $\\{A_{i}\\}_{i=1}^{a}$,
$\\{B_{j}\\}_{j=1}^{b}$ and $\\{C_{k}\\}_{k=1}^{c}$ give rise to a graph
minor. On the other hand, assume that $f:S\subseteq V(Y)\rightarrow V(X)$ is a
function describing $X$ as a minor of $Y$. We can retrieve the subset $S$ of
$V(Y)$ by a sequence of vertex deletions. For any $x\in X$, edge contractions
ensure to contract every subgraph $f^{-1}(x)$ to a single vertex. We then
obtain $X$ by a sequence of edge deletions. $\square$

Choosing a loose ear decomposition, the vertex deletion $A_{i}\rightsquigarrow
A_{i+1}$ corresponds to a homomorphism $A(A_{i})\rightarrow
A(A_{i})/\langle\\!\langle p\rangle\\!\rangle$ where $p$ is a pearl and
$A(A_{i})/\langle\\!\langle p\rangle\\!\rangle\cong A(A_{i+1})$. We call such
a homomorphism a pearl deletion. The edge contraction $B_{j}\rightsquigarrow
B_{j+1}$ corresponds to a homomorphism $A(B_{j})\rightarrow
A(B_{j})/\langle\\!\langle pq^{-1}\rangle\\!\rangle$ where $p$ and $q$ are
adjacent pearls and $A(B_{j})/\langle\\!\langle pq^{-1}\rangle\\!\rangle\cong
A(B_{j+1})$. As we identify the pearls $p$ and $q$, we call such a
homomorphism an identification homomorphism. Lastly, the edge deletion
$C_{k+1}\rightsquigarrow C_{k}$ corresponds to a homomorphism
$A(C_{k})\rightarrow A(C_{k})/\langle\\!\langle[p,q]\rangle\\!\rangle$ where
$p$ and $q$ are not adjacent and
$A(C_{k})/\langle\\!\langle[p,q]\rangle\\!\rangle\cong A(C_{k+1})$. Since we
impose that two elements commute, we call such a homomorphism an abelianising
homomorphism. We reformulate the above proposition as

######  Theorem 5.6.

Let $A(\Gamma)$ and $A(\Lambda)$ be RAAGs. Then $\Lambda$ is a minor of
$\Gamma$ if and only if there exists a sequence of pearl deletions
$\\{A(A_{i})\rightarrow A(A_{i+1})\\}_{i=1}^{a}$, one of identification
homomorphisms $\\{A(B_{j})\rightarrow A(B_{j+1})\\}_{j=1}^{b}$ and one of
abelianising homomorphisms $\\{A(C_{k})\rightarrow A(C_{k+1})\\}_{k=1}^{c}$
such that $A(\Gamma)\cong A(A_{1})$, $A(A_{a})\cong A(B_{1})$, $A(B_{b})\cong
A(C_{c})$ and $A(C_{1})\cong A(\Lambda)$.

This can be pictorially summarised as

${A(\Lambda)=A(C_{1})}$${A(\Gamma)=A(A_{1})}$${A(A_{a})=A(B_{1})}$${A(B_{b})=A(C_{c})}$abelianising
homomorphismspearl deletionsidentifying homomorphisms

######  Definition 5.7.

If two RAAGs $A(\Gamma)$ and $A(\Lambda)$ satisfy the conditions of the
previous theorem, then $A(\Lambda)$ is a called a RAAG minor of $A(\Gamma)$.

The key of characterising minor-closed properties in terms of RAAGs is the
following theorem corresponding to Theorem 12.7.1 and Corollary 12.7.2 in [2]:

######  Theorem 5.8 (Robertson-Seymour).

Any minor-closed graph property can be characterised by a finite set of
forbidden minors.

All our applications of RAAGs to graph minors are based on this theorem. For
instance,

######  Proposition 5.9.

Let $A(\Gamma)$ be a RAAG. Then $\Gamma$ is a forest if and only if
$A(\Gamma)$ does not contain $\mathbb{Z}^{3}$ as a RAAG minor.

######  Proof.

A graph is a forest if it does not contain a cycle, meaning a subdivision of
$C_{3}$ where $A(C_{3})=\mathbb{Z}^{3}$. $\square$

######  Theorem 5.10.

Let $A(\Gamma)$ be a RAAG. Then $\Gamma$ is planar if and only if $A(\Gamma)$
does not contain $\mathbb{Z}^{5}$ or $F_{3}\oplus F_{3}$ as RAAG minors.

######  Proof.

According to Wagner’s Theorem [2, Theorem 4.4.6], a graph is planar if and
only it does not contain $K_{5}$ or $K_{3,3}$ as a minor where
$A(K_{5})=\mathbb{Z}^{5}$ and $A(K_{3,3})=F_{3}\oplus F_{3}$. $\square$

For any embedding of a planar graph $\Gamma$ into $\mathbb{R}^{2}$ without
edge crossings, the connected components of $\mathbb{R}\setminus\Gamma$ are
called faces. [2, p. 92] The graph $\Gamma$ is called outerplanar if all its
vertices lie on the boundary of the unique unbounded face. [2, p. 115].

######  Lemma 5.11.

Let $A(\Gamma)$ be a RAAG. Then $\Gamma$ is outerplanar if and only if it does
not contain $\mathbb{Z}^{4}$ or $F_{2}\oplus F_{3}$ as RAAG minors.

######  Proof.

A graph $\Gamma$ is outerplanar if and only if it does not contain the
complete graph $K_{4}$ or the complete bipartite graph $K_{2,3}$ as minors [2,
p. 115], where $A(K_{4})=\mathbb{Z}^{4}$ and $A(K_{2,3})=F_{2}\oplus F_{3}$.
$\square$

In this manner, one could characterise more graph theoretic properties in
terms of RAAGs. For example, a graph is embeddable in a given surface $S$ if
and only if it does not contain any of a finite set of forbidden minors. [2,
Corollary 12.7.3]. As soon as such a finite set is known, one can write down
the associated RAAGs. Furthermore, a graph $\Gamma$ is called an apex graph if
there exists a vertex $v$ such that $\Gamma\setminus\\{v\\}$ is planar. [5, p.
809] It is known that apex graphs can be also characterised by a finite set of
forbidden minors, but it is unknown what these are. [5, p. 809] As soon as
this is known, one could characterise apex graphs by looking at their RAAGs.

In our last applications, we specifically want to restrict our attention to
ear decompositions. Let us introduce two notions of connectivity for graphs. A
graph is called $k$-vertex-connected if removing at most $k-1$ vertices does
not disconnect it, while removing $k$ (specific) vertices does. [9, p. 237]
Similarly, a graph is $k$-edge-connected if removing at most $k-1$ edges does
not disconnect it, but removing $k$ (particular) edges does. [9, p. 237].

######  Theorem 5.12.

Let $\Gamma$ be a graph. Then $\Gamma$ is $2$-edge-connected if and only if
the RAAG $A(\Gamma)$ admits an ear decomposition.

######  Proof.

This follows from Theorem 15.17 in [9]. $\square$

According page 252 of [9], we call an ear decomposition
$\\{\Gamma_{i}\\}_{i=1}^{m}$ of a graph $\Gamma$ proper if for any $i>1$ the
ear $\Gamma_{i}$ is a path. Call the corresponding decomposition of
$A(\Gamma)$ also a proper ear decomposition.

######  Lemma 5.13.

Let $\Gamma$ be a graph such that $d(A(\Gamma))\geq 2$. Then $\Gamma$ is
$2$-vertex-connected if and only if $A(\Gamma)$ has a proper ear
decomposition.

######  Proof.

Since $|V(\Gamma)|=d(A(\Gamma))\geq 2$ by Proposition 2.3, this follows from
Theorem 15.16 in [9]. $\square$

######  Lemma 5.14.

Let $\Gamma$ be a graph. Then $\Gamma$ is $3$-vertex-connected if and only if
$A(\Gamma)$ has an ear decomposition
$\\{(A(\Gamma_{i}),\\{p_{i,1},\dots,p_{i,n_{i}}\\})\\}_{i=1}^{m}$ with $m>1$
and pearls $p_{1,k}$, $p_{1,k+1}$, $p_{j,2}$ having the following properties.

  1. 1.

The index $1\neq j$ is the first one for which the ear RAAG $A(\Gamma_{j})$
contains the element $p_{j,2}\in A(\Gamma)$.

  2. 2.

The index $j$ is the last one for which $d(A(\Gamma_{j}))>2$ where $p_{j,2}$
is its only inner pearl.

  3. 3.

The pearls $p_{1,k+1}$ and $p_{j,2}$ are adjacent in an ear RAAG other than
$A(\Gamma_{1})$ and $A(\Gamma_{j})$.

  4. 4.

For any pearl $p_{a,b}$ with $a<m$ there is are indices $a^{\prime}$,
$b^{\prime}$ such that $a<a^{\prime}$ and $p_{a,b}=p_{a^{\prime},b^{\prime}}$.

######  Proof.

This lemma is a translation of Theorem 10 of [8] in terms of RAAGs. $\square$

After these connectivity results, let us consider series-parallel graphs that
can be defined as follows according to [3, p. 41]. A graph consisting $\Gamma$
of a single edge is series-parallel graph where we call its two vertices
$s_{\Gamma}$, $t_{\Gamma}$ its terminals. If $(X,s_{X},t_{X})$ and
$(Y,s_{Y},t_{Y})$ are two series parallel graphs, then we can form a new
series parallel graph $(\Gamma,s_{\Gamma},t_{\Gamma})$ by identifying $s_{X}$
with $s_{Y}$, declaring this to be $s_{\Gamma}$ and doing the same for
$t_{X}$, $t_{Y}$ and $t_{\Gamma}$. We could equally define a different series-
parallel graph $(\Lambda,s_{\Lambda},t_{\Lambda})$ by identifying $t_{X}$ with
$s_{Y}$ and declaring the terminals to be $s_{X}$ and $t_{Y}$. These graphs
are related to a particular form of ear decomposition. A nested ear
decomposition of a graph $\Gamma$ is a loose ear decomposition
$\\{\Gamma_{i}\\}_{i=1}^{m}$ consisting of paths and satisfying the following
conditions. For any $1<i$ there is $1\leq j<i$ such that the endpoints of
$\Gamma_{i}$ are contained in $\Gamma_{j}$. If the endpoints of $\Gamma_{i}$
and $\Gamma_{j}$ lie in $\Gamma_{k}$, then the subpath in $\Gamma_{k}$ between
the endpoints of $\Gamma_{i}$ contains either both or none of endpoints of
$\Gamma_{j}$. [3, p. 43] Contrary to ear decompositions, the first ear of a
nested ear decomposition is not a cycle. Call the corresponding loose ear
decomposition of $A(\Gamma)$ a nested ear decomposition. We reformulate
Theorem 1 in [3] as

######  Lemma 5.15.

Let $\Gamma$ be a RAAG. Then $\Gamma$ is a series-parallel graph if and only
if $A(\Gamma)$ has a nested ear decomposition. In this case, the terminals of
$\Gamma$ correspond to the end pearls of the first ear RAAG in the nested ear
decomposition of $A(\Gamma)$.

A graph $\Gamma$ is called factor-critical if for every vertex $v\in
V(\Gamma)$ the graph $\Gamma\setminus\\{v\\}$ has a perfect matching [9, p.
425], meaning a subset $M\subseteq E(\Gamma\setminus\\{v\\})$ such that any
two elements of $M$ are disjoint and every vertex in $\Gamma\setminus\\{v\\}$
is covered by at least an edge in $M$ [9, p. 23]. Then Theorem 24.9 in [9] can
be rephrased as

######  Lemma 5.16.

Let $\Gamma$ be a graph. Then $\Gamma$ is factor-critical if and only if
$A(\Gamma)$ has an ear decomposition $\\{A(\Gamma_{i})\\}_{i=1}^{m}$ such that
$d(A(\Gamma_{i}))$ is odd if $A(\Gamma_{i})$ is a cycle RAAG and even if
$A(\Gamma_{i})$ is a path RAAG.

Lastly, for an ear RAAG $A(\Gamma)$, set the quantity
$E(A(\Gamma))=\lfloor\frac{1}{2}d(A(\Gamma))\rfloor$ if $\Gamma$ is a cycle
and $E(A(\Gamma))=\lfloor\frac{1}{2}(d(A(\Gamma))-1)\rfloor$ if $\Gamma$ is a
path. One can think of $E(A(\Gamma))$ as roughly half the edges of $\Gamma$.

######  Proposition 5.17.

Let $\Gamma$ be a $2$-vertex-connected graph. Then the following hold.

  1. 1.

If $\\{A(\Gamma_{i})\\}_{i=1}^{m}$ is any ear decomposition of $A(\Gamma)$,
then $m=|E(\Gamma)|-|V(\Gamma)|+1$. In terms of group cohomology over a field
$F$, this is equivalent to

$m=\mathrm{dim}_{F}\big{(}H_{F}^{2}(A(\Gamma),F)\big{)}-\mathrm{dim}_{F}\big{(}H_{F}^{1}(A(\Gamma),F)\big{)}+1\,.$

  2. 2.

The maximum size of a join in $\Gamma$ is equal to

$\mathrm{min}\Bigg{\\{}\sum_{i=1}^{m}E(A(\Gamma_{i}))\mid\\{A(\Gamma_{1})\\}_{i=1}^{m}\text{
ear decomposition of }A(\Gamma)\Bigg{\\}}\,.$

######  Proof.

The first part is due to [9, p. 511] and [6, Proposition 2.4], where the
second part is a reformulation of [9, Theorem 29.11]. $\square$

## Acknowledgement

I am indebted to Thomas Koberda for pointing out that it is unclear whether
the results of this paper can be algorithmically implemented.

## References

  * [1] R. Charney.  An introduction to right-angled Artin groups.  Geometriae Dedicata, 125(1):141–158, 2007.
  * [2] R. Diestel.  Graph Theory, volume 173 of Graduate Texts in Mathematics.  Springer Nature, 5th edition, 2017.
  * [3] D. Eppstein.  Parallel recognition of series-parallel graphs.  Information and Computation, 98(1):41–55, 1992.
  * [4] J. L. Gross et al.  Graph Theory and Its Applications.  Textbooks in Mathematics. CRC Press, 3rd edition, 2019.
  * [5] A. Gupta and R. Impagliazzo.  Computing planar intertwines.  In Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 802–811, San Juan, PR, USA, October 1991. IEEE.
  * [6] T. Koberda.  Geometry and combinatorics via right-angled artin groups.  arXiv e-prints, page arXiv:2103.09342, March 2021.
  * [7] R. P. Osborne and H. Zieschang.  Primitives in the free group on two generators.  Inventiones Mathematicae, 63(1):17–24, 1981.
  * [8] J. M. Schmidt.  Mondshein sequences (a.k.a. (2,1)-orders).  SIAM Journal on Computing, 45(6):1985–2003, 2016.
  * [9] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics.  Springer-Verlag Berlin Heidelberg, 2004.  Volume A-C.
  * [10] H. Servatius.  Automorphisms of graph groups.  Journal of Algebra, 126(1):34–60, 1989.
  * [11] J. Stallings.  Coherence of 3-manifold fundamental groups.  In Séminaire Bourbaki vol. 1975/76 Exposés 471–488, volume 567 of Lecture Notes in Mathematics, pages 167–173. Springer-Verlag Berlin Heidelberg, 1977.

Department of Mathematics, University of British Columbia, 125-1984
Mathematics Road, Vancouver, BC, V6T 1Z2, Canada
Email address<EMAIL_ADDRESS>
URL: https://www.math.ubc.ca/user/2675