THE GRAPH STRUCTURE OF GRAPH GROUPS THAT ARE SUBGROUPS OF
THOMPSON’S GROUP V

arXiv:1603.08433v1 [math.GR] 28 Mar 2016

NATHAN CORWIN AND KATHRYN HAYMAKER

Abstract. We determine exactly which graph products, also known as Right Angled Artin Groups, embed
into Richard Thompson’s group V . It was shown by Bleak and Salazar-Diaz that Z2 ∗ Z was an obstruction.
We show that this is the only obstruction. This is shown by proving a graph theory result giving an alternate
description of simple graphs without an appropriate induced subgraph.

In this note we discuss which graph groups, also known as right angled Artin groups, exist as subgroups
of Thompson’s group V . The group V was first discovered in 1965 by the logician Richard Thompson while
attempting to build algebras that encapsulate the properties of commutativity and associativity. Thompson’s
group V quickly drew the interest of group theorists after Thompson showed that V and a closely related
group, Thompson’s group T , were simple [2]. These were the first two known examples of finitely presented
infinite simple groups.
Despite interest in the group from various areas, the subgroup structure of V is not well understood.
Since V contains many products of its subgroups, it was commonly believed that all graph groups embed
in V . This was disproved in 2013 by Bleak and Salazar-Diaz [1] by showing Z2 ∗ Z does not embed in V .
Their motivation was related to computational complexity of the coword problem of groups and they only
considered this particular graph group. The goal of this note is to classify exactly which graph groups embed
in V .
We interpret the question of which graph groups embed in V as a graph theory question. In particular,
we provide a useful description of finite simple graphs that do not have, as an induced subgraph, the graph
associated to Z2 ∗ Z. We then show that graphs with this description correspond to graph groups that embed
in V . Therefore, all graph groups that do not contain Z2 ∗ Z embed in V . Equivalently, the only graph
groups that appear as subgroups of V are direct products of free groups.
The note is organized as follows. We give background and definitions in Sections 1 and 2. Section 1
discusses Thompson’s group V and graph groups. Relevant graph theory notions are explained in Section 2.
We then formally state and prove our results in Section 3.
1. Thompson’s group V and graph groups
A graph group is a group that in a sense lies between free products and commutative free products.
Given a finite simple graph Γ, the associated group G(Γ) = G is a group whose generators are in bijective
correspondence with the vertices of Γ. The only relations are that some generators commute. In particular,
two generators xi , xj commute exactly when there is an edge between the corresponding vertices.
A compete graph on n vertices corresponds to Zn while the empty graph on n vertices corresponds to the
free group Fn . As an intermediate example, consider the graph Γ in Figure 1a. The corresponding graph
group G(Γ) will have a presentation ha, b, c|ab = bai, which factors as Z2 ∗ Z. The graph of a pentagon shown
in Figure 1b represents a graph group that can not be described simply by using free products and direct
products.
One common interpretation of Thompson’s group V is as a particular subgroup of the homeomorphism
group of the Cantor set, with elements of V being the homeomorphisms that can be expressed as a finite
list of prefix replacements. It is difficult to give much more detail in a concise manner and the necessary
facts about V are listed below. For more details, readers are referred to either [2] — a standard introduction
to Thompson’s groups F, T, and V — or [1] which has a very readable explanation of V from a dynamical
viewpoint. The following lemmas are well-known.
Lemma 1.
(1) If H1 and H2 are subgroups of V , then there is a subgroup of V isomorphic to H1 × H2 .
(2) There is a subgroup of V isomorphic to the free group F2 .
1

2

NATHAN CORWIN AND KATHRYN HAYMAKER

(a) The graph associated with Z2 ∗ Z

(b) A Pentagon graph

Figure 1. Graph examples
As Z is a subgroup of F2 , there is a subgroup of V isomorphic to Z. Thus, by repeatedly applying (1) we
have that Zn is a subgroup of V for all positive integers n. Also, for any positive n, Fn < F2 , thus Fn < V .
Repeated applications of (1) show the following.
Lemma 2. If G is a direct product of (finitely generated) free groups, then there is a subgroup of V isomorphic
to G.
Lastly, we state the theorem of Bleak and Salazar-Dı́az mentioned in the introduction. The following is
Theorem 1.5 of [1].
Theorem 3. The group Z2 ∗ Z does not embed in V .
2. Relevant graph theory notions
A finite simple graph Γ is a set of vertices V (Γ) and edges E(Γ). E(Γ) can be any subset of V (Γ) × V (Γ),
where loops and multiedges are prohibited. That is, for any v ∈ V (Γ), (v, v) ∈
/ E(Γ), and an edge appears
in E(Γ) at most once. An induced subgraph of Γ is a subgraph that is obtained by deleting vertices from
V (Γ). The eccentricity (v) of a vertex v is the greatest geodesic distance between v and any other vertex.
It can be thought of as how far a vertex is from the vertex most distant from it in the graph.
We will be interested in two classes of graphs.
Definition Let N B be the class of all finite simple graphs Γ that do not have the graph in Figure 1a as
an induced subgraph. In other words, N B is the class of finite simple graphs Γ for which no three distinct
vertices a, b, c ∈ Γ have the property that (a, b) ∈ E(Γ) but both (a, c), (b, c) 6∈ E(Γ).
Definition Denote by GP the class of all finite simple graphs Γ for which there exists a partition P0 , P1 , . . . , Pn ,
of the vertices of Γ with all, except perhaps P0 , nonempty such that
• P0 is the set of all vertices of Γ with eccentricity one;
• if vi , vj ∈ Pk with k > 0, then (vi , vj ) 6∈ E(Γ);
• if vi ∈ Pi , vj ∈ Pj with i 6= j then (vi , vj ) ∈ E(Γ).
We call an associated partition a commuting partition.
In other words, a commuting partition separates the vertices of Γ into the set P0 of all vertices of eccentricity
one and sets P1 , . . . , Pn that individually form empty subgraphs, but which have all possible edges between
the subsets.
3. Results
We are now prepared to prove the main theorem of this note.
Theorem 4. The class N B is exactly the class GP.
Proof. First, suppose that Γ is not in N B. Say v1 , v2 , v3 ∈ V (Γ) are distinct with (v1 , v2 ) ∈ E(Γ) but
(v1 , v3 ), (v2 , v3 ) 6∈ E(Γ). Momentarily assume that P0 , P1 , . . . Pn is a commuting partition for Γ. We have
that v3 ∈ Pi with i > 0. Since every vertex in Pi is adjacent to every vertex in Pj where j 6= i, and v3 is
not adjacent to v1 , we must have that v1 ∈ Pi . Similarly, since v3 and v2 are not adjacent, v2 ∈ Pi . Thus,

THE GRAPH STRUCTURE OF GRAPH GROUPS THAT ARE SUBGROUPS OF THOMPSON’S GROUP V

3

v1 , v2 ∈ Pi implies (v1 , v2 ) 6∈ E(Γ) but we are assuming (v1 , v2 ) ∈ E(Γ). This contradiction shows that there
can not be a commuting partition for Γ thus Γ is not in GP. Equivalently, GP ⊂ N B.
Now, assume that Γ ∈ N B. We will give an algorithm to partition the vertices, then we will show the
resulting partition is a commuting partition.
For the initial step, set P0 = {v ∈ V (Γ)|(v) = 1}. For the recursive step, assume that P0 , P1 , . . . , Pk is a
partial partition of Γ. Let Sk = ∪ki=0 Pi and Rk = V (Γ) \ Sk . If Sk = V (Γ), then the already built Pi ’s are
a partition of Γ and we stop. Otherwise, choose wk ∈ Rk . Set Pk+1 = {v ∈ Rk |(wk , v) 6∈ E(Γ)}. As Γ is
simple, wk ∈ Pk+1 . Therefore, the size of Rk+1 is always at least one smaller than Rk and, as V (Γ) is finite,
this process must terminate.
We now show the resulting partition is a commuting partition. By construction, P0 is exactly as required
and Pi is nonempty if i > 0.
For condition (ii), consider vi , vj ∈ Pk+1 . If either is wk then by construction they are not adjacent.
Otherwise neither are adjacent to wk and thus can’t be adjacent to each other as Γ is in N B and this would
form an inadmissible induced subgraph.
For condition (iii), if vi ∈ Pi , vj ∈ Pj with i < j, we again consider cases. If vi = wi−1 , then we conclude
that (vi , vj ) ∈ E(Γ) as this is the only reason vj would have been excluded from Pi . Otherwise, we have
(vi , wi−1 ) 6∈ E(Γ) and (vj , wi−1 ) ∈ E(Γ). As Γ is in N B, we must have (vi , vj ) ∈ E(Γ) or else vi , vj , wi−1
forms an inadmissible induced subgraph.
We conclude that the partition is a commuting partition hence Γ is in GP.

Lemma 5. Let Γ be in GP. Then, the corresponding group G(Γ) is a subgroup of V .
Proof. Let P be a commuting partition for Γ. For each i, consider the induced subgraph Γi formed by
looking at only the vertices in Pi . The induced subgraph Γ0 corresponds to a group G0 ' Z|P0 | . For
each positive i, the induced subgraph Γi corresponds to a group Gi ' F|Pi | . As vertices from different
elements of the partition have an edge between them, the corresponding generators of G(Γ) commute. Thus,
G(Γ) ' G0 × G1 × · · · × Gk . This is a subgroup of V by Lemma 2.

Corollary 6. Each of the following is true:
• A graph group embeds into V if and only if its associated graph is in GP.
• A graph group embeds into V if and only if it is the direct product of free groups.
• Z2 ∗ Z is the only obstruction to a graph group embedding into V .
Proof. Lemma 5 proved that if Γ is in GP, then G(Γ) embeds into V . Theorem 3 implies that if Γ is not in
N B then G(Γ) does not embed into V and Theorem 4 shows that N B is equivalent to GP. Therefore, if Γ
is not in GP then G(Γ) does not embed into V .

References
[1] Collin Bleak and Olga Salazar-Dı́az. Free products in R. Thompson’s group V . Trans. Amer. Math. Soc., 365(11):5967–5997,
2013.
[2] James W Cannon, William J Floyd, and Walter R Parry. Introductory notes on Richard Thompson’s groups. Enseignement
Mathématique, 42:215–256, 1996.
Department of Mathematics - Hill Center Rutgers, The State University of New Jersey 110 Frelinghuysen Rd.
Piscataway, NJ 08854-8019
E-mail address: nacorwin@math.rutgers.edu
Department of Mathematics and Statistics - St. Augustine Center, Villanova University 800 Lancaster Avenue
Villanova, PA 19085
E-mail address: kathryn.haymaker@villanova.edu

