arXiv:1607.04890v1 [math.GR] 17 Jul 2016

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE
GROUPS
S. V. IVANOV
Abstract. We study graphs of (generalized) joins and intersections of finitely
generated subgroups of a free group. We show how to disprove a lemma of
Imrich and Müller on these graphs and how to repair this lemma.

1. Introduction
Suppose that F is a free group of finite rank, r(F ) denotes the rank of F , and
r̄(F ) := max(r(F ) − 1, 0) is the reduced rank of F . Let H, K be finitely generated
subgroups of F and let hH, Ki denote the the subgroup generated by H, K, called
the join of H, K. Hanna Neumann [17] proved that r̄(H ∩K) ≤ 2r̄(H)r̄(K) and conjectured that r̄(H ∩ K) ≤ r̄(H)r̄(K). This problem, known as the Hanna Neumann
conjecture on subgroups of free groups, was solved in the affirmative by Friedman
[7] and Mineyev [15], see also Dicks’s proof [3]. Relevant results and generalizations
of this conjecture can be found in [2], [5], [6], [9], [10], [11], [18], [20].
Imrich and Müller [8] introduced the reduced rank r̄(hH, Ki) of the join hH, Ki
in this context and attempted to prove the following inequality
r̄(H ∩ K) ≤ 2r̄(H)r̄(K) − r̄(hH, Ki) min(r̄(H), r̄(K))

(1.1)

under the assumption that if H ∗ , K ∗ are free factors of H, K, resp., then the equality
H ∗ ∩K ∗ = H∩K implies that H = H ∗ and K = K ∗ . We remark that this inequality
provides a stronger than Hanna Neumann conjecture’s bound for r̄(H ∩K) whenever
r̄(hH, Ki) > max(r̄(H), r̄(K)) and this looks quite remarkable. We also note that
(1.1) was an improvement of an earlier result of Burns [1], see also [16], [19], stating
that
r̄(H ∩ K) ≤ 2r̄(H)r̄(K) − min(r̄(H), r̄(K)).
Later Kent [14] discovered a serious gap in the proof of a key lemma of Imrich–
Müller [8, p. 195] and gave his own proof to the inequality (1.1) under the weakened
assumption that H ∩ K 6= {1}. Kent [14, p. 312] remarks that the lemma in [8]
“would be quite useful, and though its proof is incorrect, we do not know if the
lemma actually fails”. In this note we give an example that shows that the lemma
of [8] is indeed false. On positive side, we suggest a repair for this lemma so that
the arguments of Imrich–Müller [8] could be saved. Our approach seems to be
of independent interest and can be outlined as follows. Given subgroups H, K of
a free group F with H ∩ K 6= {1}, we modify H, K, F by certain deformations
e K
e would satisfy
of Stallings graphs of H, K, F so that the modified subgroups H,
e
e
e
e
e
e
e Ki).
e
r̄(H) = r̄(H), r̄(K) = r̄(K), r̄(H ∩ K) = r̄(H ∩ K), and r̄(hH, Ki) ≥ r̄(hH,
2010 Mathematics Subject Classification. Primary 20E05, 20E07, 20F65, 57M07.
Supported in part by the NSF under grant DMS 09-01782.
1

2

S. V. IVANOV

e Ki,
e
Furthermore, our modification is done so that Stallings graphs of subgroups hH,
e K
e have vertices of degree 2 or 3 only and every vertex of the graph of hH,
e Ki
e
H,
e
e
of degree 3 has a preimage of degree 3 in the graph of H or K. These properties
mean that the lemma of Imrich–Müller [8, p. 195] holds in a modified setting and
the arguments of Imrich–Müller are retained otherwise. As an application of this
strategy developed in Sect. 3, we will prove Theorem 4.1 in Sect. 4. Theorem 5.1
in Sect. 5 deals with a natural question related to our main construction used in
proofs of key Lemmas 3.4–3.5.
2. A Counterexample to Imrich–Müller Lemma
Similarly to Stallings [20], see also [2], [14], [13], we consider finite graphs associated with finitely generated subgroups of a free group F . We consider the ambient
free group F as the fundamental group of a finite connected graph U , F = π1 (U ),
without vertices of degree 1. Let H, K be finitely generated subgroups of F and let
X, Y denote finite graphs associated with H, K, resp. Recall that there are locally
injective graph maps ϕX : X → U , ϕY : Y → U . Conjugating H, K if necessary, we
may assume that the graphs X, Y have no vertices of degree 1, i.e., core(X) = X
and core(Y ) = Y , where core(Γ) is the subgraph of a graph Γ consisting of all edges
that can be included into circuits of Γ.
Let S(H, K) denote a set of representatives of those double cosets HtK ⊆ F , t ∈
F , that have the property HtKt−1 6= {1}. Recall that the connected components
of the core W := core(X ×U Y ) of the pullback X ×U Y of graph maps ϕX : X → U ,
ϕY : Y → U are in bijective correspondence with elements of the set S(H, K), see
[2], [13], [18]. Hence, we can write
_
Wt ,
W =
t∈S(H,K)

W

where
denotes a disjoint union. In addition, if Wt is a connected component of
W that corresponds to t ∈ S(H, K), then
r̄(H ∩ tKt−1 ) = |EWt | − |V Wt |,
where EΓ is the set of (nonoriented) edges of a graph Γ, V Γ is the set of vertices
of Γ and |A| is the cardinality of a set A. Using notation r̄(Γ) := |EΓ| − |V Γ|, we
have
X
X
r̄(H ∩ tKt−1 ).
r̄(Wt ) =
r̄(W ) =
t∈S(H,K)

t∈S(H,K)

W
For S1 ⊆ S(H, K), S1 6= ∅, denoting W (S1 ) := s∈S1 Ws , we obtain
X
X
r̄(H ∩ sKs−1 ) = r̄(H, K, S1 ).
r̄(Ws ) =
r̄(W (S1 )) =
s∈S1

(2.1)

t∈S1

Let αX : W (S1 ) → X, αY : W (S1 ) → Y denote the restrictions on W (S1 ) ⊆
X ×U Y of the pullback projection maps
ᾱX : X ×U Y → X,

ᾱY : X ×U Y → Y,

resp. Consider the pushout P of these maps αX : W (S1 ) → X, αY : W (S1 ) → Y .
The corresponding pushout maps are denoted βX : X → P , βY : Y → P . We also
consider the Stallings graph Z corresponding to the subgroup hH, K, S1 i of F . It
is clear from the definitions that there are graph maps γ : P → Z and δ : Z → U
such that the diagram depicted in Fig. 1 is commutative.

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE GROUPS

αX

X

3

βX
γ

W (S1 )

P

αY

Z

δ

U

βY
Y
Figure 1

As was found out by Kent [14, Fig. 1], one has to distinguish between P and Z
as P 6= Z in general. Since the map δ : Z → U is locally injective and P 6= Z,
we see that the map γ : P → Z need not be locally injective, hence, γ factors
out through a sequence of edge foldings and r̄(P ) ≥ r̄(Z). According to Kent [14],
the erroneous identification P = Z is the source of a mistake in a key lemma of
Imrich–Müller [8, p. 195]. Recall that this lemma claims, in our terminology, that
if Z is an almost trivalent graph, i.e., every vertex of Z has degree 3 or 2, then
every vertex of Z of degree 3, has a preimage of degree 3 in X or Y . Kent [14]
explains in detail a mistake in the proof of this lemma and comments that, while
the proof of lemma of [8, p. 195] can be somewhat corrected if one replaces Z by
P , the subsequent arguments of Imrich–Müller rely on the property that Z = U
is trivalent, the property that the graph P does not possess. Furthermore, Kent
[14, p. 312] points out that the lemma in [8] “would be quite useful, and though its
proof is incorrect, we do not know if the lemma actually fails”.
We now present an example that shows that the lemma of [8] does fail. Consider
subgroups
−1
2
−1
H = hb1 b2 a2 b−1
i,
2 b1 , a1 , a1 b1 b3 a3 (a1 b1 b3 )

K=

−1
hb1 b2 a2 b−1
2 b1 ,

a31 ,

−1

a1 b1 b3 a3 (a1 b1 b3 )

(2.2)

i

(2.3)

of a free group F = π1 (U ) whose graphs X, Y, Z, resp., are depicted in Fig. 2, where
the base vertices of X, Y, Z are dashed circled.
a2

a3

a1
b2 b1
X

a2

b1 b3

a1
b2 b1

a1

Y
a2

a3

b2
Z

b3
b1

a1

Figure 2

a1

a3
b1 b3
a1

4

S. V. IVANOV

It is easy to check that S(H, K) has a single element, say S(H, K) = {1}, and
−1 6
−1
H ∩ K = hb1 b2 a2 b−1
i.
2 b1 , a1 , a1 b1 b3 a3 (a1 b1 b3 )

Furthermore, the graphs W, P look like those in Fig. 3. Hence, we can see that Z
is a trivalent graph that has a vertex of degree 3, which is the center of Z, without
a preimage of degree 3 in X ∨ Y , as desired.
a2
a3
a2
a1
a3
b2 b1

b1 b3
b2

W

a51

P

b1

b3
b1

a1
Figure 3
3. Fixing the Lemma of Imrich and Müller
We now discuss how to do certain deformations over the graphs W (S), X, Y, P ,
Z, U to achieve the situation when P = Z = U , U is almost trivalent and lemma
of [8, p. 195] would hold for Z.
Our idea could be illustrated by the remark that, when studying graphs W (S),
X, Y, P , Z, U , or corresponding subgroups, we can replace the ambient group F =
π1 (U ) by Fb = π1 (Z), i.e., we can replace the graph U by Z. We can go further
and replace the group F = π1 (U ) with Fe = π1 (P ) by using the pushout graph P
in place of U .
Either of these replacements U → Z, U → P results in obvious cosmetic changes
to subgroups H, K, to sets S(H, K), S1 ⊆ S(H, K), and to subgroups H ∩ sKs−1 ,
s ∈ S1 , hH, K, S1 i.
Either of these replacements U → Z, U → P preserves the graphs W (S), X, Y ,
P and the maps αX , αY , βX , βY . The replacement U → Z turns δ into the identity
map and the replacement U → P turns both δ, γ into the identity maps. Otherwise,
the structure of the diagram depicted on Fig. 1 is retained. In particular, the ranks
r̄(H), r̄(K), r̄(W (S)) do not change but the rank r̄(P ) could increase as r̄(P ) ≥ r̄(Z)
originally.
For future references, we record this replacement in the following.
Lemma 3.1. Replacing the graph U in the diagram depicted in Fig. 1 by P and
changing the maps γ : P → Z, δ : Z → U by γ = δ = idU , resp., and changing
the maps ϕX : X → U , ϕY : Y → W
U by βX : X → P , βY : Y → P , resp.,
preserve the properties that W (S1 ) = s∈S1 Ws consists of connected components
of core(X ×U Y ) and that P = X ∨W (S1 ) Y . In particular, this replacement does
not change the ranks r̄(X), r̄(Y ), r̄(W (S1 )) but could increase r̄(Z).
Proof. If (e1 , e2 ) is an edge of W (S1 ) ⊆ core(X ×U Y ), where ϕX αX ((e1 , e2 )) = e1
is an edge of X and ϕY αY ((e1 , e2 )) = e2 is an edge of Y , then the edges e1 , e2 are
identified in P , whence, (e1 , e2 ) is also an edge of X ×P Y . Since core(W (S1 )) =
W (S1 ), it follows that core(X ×P Y ) contains all edges (e1 , e2 ) of W (S1 ), hence,
core(X×P Y ) will contain the graphs naturally isomorphic to connected components

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE GROUPS

5

W
of the graph W (S1 ) = s∈S1 Ws . Therefore, the original pushout P = X ∨W (S1 ) Y
will also be preserved.
Since r̄(P ) ≥ r̄(Z) for the original graphs P, Z and since P = Z = U after the
replacement U → P , we see that the rank r̄(Z) could increase after the replacement.

Suppose that v is a vertex of U . Subdividing the edges incident to v if necessary,
we may assume that every oriented edge e of U whose terminal vertex, denoted
e+ , is e+ = v has the initial vertex, denoted e− , of degree 2, deg e− = 2. Hence,
we may assume that U contains a subgraph St(v) isomorphic to a star with deg v
rays whose center is v. Let T be a tree whose vertices of degree 1 are in bijective
correspondence with vertices of degree 1 of St(v) whose set we denote by V1 St(v).
Taking St(v) out of U and putting the tree T in place of St(v), using the bijective
correspondence to identify vertices of degree 1 of (U \ St(v)) ∪ V1 St(v) and those of
T , results in a transformation of U which we call an elementary deformation of U
around v by means of T . It is clear that the obtained graph UT := (U \ St(v)) ∪ T
is homotopically equivalent to U and π1 (UT ) is isomorphic to F = π1 (U ). We lift
this elementary deformation of the star around v in U to all the graphs X, Y, W, Z
by replacement of stars around preimages of the vertex v by trees isomorphic to
suitable subtrees of T and change, accordingly, the maps αX , αY , βX , βY , ϕX , ϕY .
The new graphs and maps obtained this way we denote by XT , YT , W (S1 )T , PT , ZT ,
αXT , αYT , βXT , βYT , ϕXT , ϕYT , γT , δT .
Clearly, r̄(QT ) = r̄(Q), where Q ∈ {X, Y, W, Z, U }. As far as the new pushout
graph PT is concerned, we can only claim that r̄(PT ) ≥ r̄(P ) which would be
analogous to the following.
Lemma 3.2. Let P = Z = U , let γ, δ be identity maps and let the graphs XT , . . .,
UT be obtained from X, . . ., U by an elementary deformation around a vertex v ∈
V U by means of a tree T . Then the map δT : ZT → UT is an isomorphism, i.e.,
the graphs ZT , UT are naturally isomorphic. Furthermore, the restriction of the
map δT γT : PT → UT is bijective on the set γT−1 δT−1 (UT \ T ) and the subgraph
Tb := γT−1 δT−1 (T ) of PT is connected. In particular, r̄(PT ) ≥ r̄(P ) and the equality
holds if and only if Tb is a tree.
Proof. It follows from the definitions that if we collapse edges of T ⊂ UT into a
point then we obtain the graph U back. Similarly, collapsing lifts of the edges of
T in QT , Q ∈ {X, Y, W (S1 ), P }, into points, we obtain the original graph Q. This
observation, together with the local injectivity of the map δT , implies that ZT = UT
and that the graph Tb := γT−1 δT−1 (T ) is connected.
Furthermore, the graph PT consists of a subgraph isomorphic to (UT \ T ) ∪
V1 T , where V1 T is the set of vertices of T of degree 1, along with the graph Tb =
γT−1 δT−1 (T ) which is mapped by δT γT to T . Surjectivity of the restriction of δT γT
on Tb follows from connectedness of Tb.

The graph Tb of Lemma 3.2 can be regarded as a “blow-up” of the vertex v ∈ V U .
b
If T turns out to be a tree, then our attempt to nontrivially “blow up” the vertex
v is unsuccessful. On the other hand, if Tb is not a tree, then we can increase r̄(U )
by invoking Lemma 3.1 and picking PT in place of U .

6

S. V. IVANOV

It is of interest to note that even when P = Z = U and r̄(PT ) = r̄(P ), i.e., Tb is
a tree, the tree Tb might look different from T , in this connection, see Lemma 3.4
and its proof.
The following is due to Kent [14]. We provide a proof for completeness.
Lemma 3.3. Every vertex of P of degree at least 3 has a preimage in X ∨ Y of
degree at least 3.
Proof. Arguing on the contrary, assume that u ∈ V P has degree deg u > 2 and
every lift v ∈ V X ∨ V Y of u has degree 2. Let v, v ′ ∈ V X ∨ V Y be two arbitrary
lifts of u. It follows from the definitions of P, W (S1 ) that there is a sequence of
vertices v1 = v, . . . , vk = v ′ in V X ∨ V Y with the following properties:
(a) The vertices v1 = v, . . . , vk = v ′ are mapped by βX , βY to u and have degree
2;
(b) For every i = 1, . . . , k − 1, the vertices vi , vi+1 belong to distinct connected
components of X ∨ Y ;
(c) For every i = 1, . . . , k − 1, there is a vertex wi ∈ V W of degree 2 such that
either αX (wi ) = vi , αY (wi ) = vi+1 if vi ∈ V X or αY (wi ) = vi , αX (wi ) = vi+1 if
vi ∈ V Y .
It is clear from these properties and from the definitions of the graphs P, W (S1 )
that the vertices v1 = v, . . . , vk = v ′ ∈ V X ∨ V Y will be identified in the pushout P
so that the resulting vertex will have degree 2. Since v, v ′ ∈ V X ∨ V Y were chosen
arbitrarily, it follows that the degree of u ∈ V P is also 2. This contradiction to
deg u > 2 proves our claim.

We say that T is a trivalent tree if every vertex of T has degree 1 or 3.
Lemma 3.4. Suppose that P = Z = U and v0 is a vertex of U of degree at least 4.
Then there is an elementary deformation of U around v0 by means of a trivalent
tree T such that either r̄(PT ) > r̄(P ) or the following are true: r̄(PT ) = r̄(P ), the
subgraph Tb = γT−1 δT−1 (T ) of PT is a tree and
X
X
max(deg v − 3, 0) <
max(deg v − 3, 0).
v∈V PT

v∈V P

Proof. Denote deg v0 = m0 > 3. Let e1 , . . . , em0 be all of the oriented edges of U
that end in v0 . By Lemma 3.3, there is a vertex v1 ∈ V X ∨ V Y , say v1 ∈ V X, such
that βX (v1 ) = v0 and deg v1 = m1 , where 3 ≤ m1 ≤ m0 . Reindexing if necessary,
we may assume that if f1 , . . . , fm1 are all of the edges of X that end in v1 , then
βX (fi ) = ei , i = 1, . . . , m1 .
Let T be a trivalent tree with m0 vertices of degree 1. Let UT denote the graph
obtained from U by an elementary deformation around v0 by means of T .
Let ui denote the vertex of T which becomes (ei )− in UT , i = 1, . . . , m0 . Here we
are assuming that deg(ei )− = 2 for every i as in the definition of an elementary deformation around v. It follows from Lemma 3.2 that if the subgraph Tb = γT−1 δT−1 (T )
b and our lemma is
is not a tree for some T , that is, if r̄(Tb) ≥ 0, then r̄(ZbT ) > r̄(Z)
b
proven. Hence, we may assume that T is a tree for every trivalent tree T .
Suppose that Tb contains no vertex of degree m0 for some T . Then, obviously,
X
X
max(deg v − 3, 0) <
max(deg v − 3, 0)
v∈V UT

and our lemma is true.

v∈V U

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE GROUPS

7

Thus we may suppose that, for every trivalent tree T , Tb is a tree which contains
a vertex u
b of degree m0 , i.e., Tb is homeomorphic to a star.
It follows from the definitions of the graphs PT , Tb that the minimal subtree S of
T that contains the vertices u1 , . . . , um1 (recall ui = (ei )− in PT ) is isomorphic to
a subtree Sb of Tb. Indeed, a copy of S will show up in XT in place of a star around
the vertex v1 of X, hence, a copy Sb of S will also show up in PT as a subgraph of
Tb. Since T is trivalent and Tb is a tree that has m0 vertices of degree 1, one vertex
u
b of degree m0 and other vertices of degree 2, it follows that Sb contains a single
vertex of degree ≥ 3 which implies m1 = 3. Since T is an arbitrary trivalent tree,
we may pick a tree T = T12 that has adjacent vertices w12 , w3 of degree 3 such that
w12 is adjacent to both u1 , u2 and w3 is adjacent to u3 , see Fig. 4(a). Note that,
in this case, S is the subtree of T = T12 that contains vertices u1 , u2 , u3 , w12 , w3
and has 4 edges that connect these vertices, see Fig. 4(a).
u1

w12

w3

u4
Figure 4(a)

u2

T13
w13

...
u2

u1

u3

T12

w2

u m0

...
u3

u m0

u4
Figure 4(b)

Since the image w
b12 of w12 in Sb has degree 3, we have deg w
b12 = m0 in Tb12 . This,
b
in particular, means that every preimage of w3 in T12 has degree 2 and adjacent to
a preimage of w12 .
Consider a vertex u ∈ V Q, Q ∈ {X, Y }, such that βQ (u) = v0 . Let g1 , . . . , gk be
all of the oriented edges of Q that end in u. We claim that the set {βQ (g1 ), . . . , βQ (gk )}
may not contain both e3 and ej , where j > 3. Arguing on the contrary, assume
that
{e3 , ej } ⊆ {βQ (g1 ), . . . , βQ (gk )}.
(3.1)
Then a star neighborhood of u in Q would turn in QT12 into a tree isomorphic to
a subtree Su of T12 which contains vertices w3 , u3 , uj , see Fig. 4(a). Clearly, either
deg w3 = 3 in Su or deg w3 = 2 in Su and then Su contains no vertex w12 . In either
case, a copy of Su is present in Tb12 which is impossible because, as we saw above,
every preimage of w3 in Tb12 has degree 2 and adjacent to a preimage of w12 . Thus
the inclusion (3.1) is impossible.
Recall that we can pick any trivalent tree T , in particular, we can pick a tree
T = T13 that has adjacent vertices w13 , w2 of degree 3 such that w13 is adjacent to
both u1 , u3 and w2 is adjacent to u2 , see Fig. 4(b).
Repeating the above argument with indices 2 and 3 switched, we can show that
{e2 , ej } 6⊆ {βQ (g1 ), . . . , βQ (gk )}
for every j > 3.
Similarly, switching indices 1 and 3, we prove that
{e1 , ej } 6⊆ {βQ (g1 ), . . . , βQ (gk )}
for every j > 3.

8

S. V. IVANOV

Now we see that for every vertex u ∈ V X ∨ V Y such that βQ (u) = v0 , where
Q ∈ {X, Y }, the edges g1 , . . . , gk of Q that end in u have the following property:
either
{βQ (g1 ), . . . , βQ (gk )} ⊆ {e1 , e2 , e3 }

or {βQ (g1 ), . . . , βQ (gk )} ⊆ {e4 , . . . , em0 }.

Since the edges of X ∨ Y are identified in the pushout P = X ∨W (S1 ) Y if and
only if their βX -, βY -images in P are equal, it follows that the terminal vertex of
e1 , e2 , e3 must be different in P from the terminal vertex of an edge ej where j ≥ 4.
This contradiction to the definition of the edges e1 , . . . , em0 of U completes the
proof.

We are now ready to prove our key lemma.
Lemma 3.5. Suppose that the graphs X, Y, W (S1 ), P, Z, U and corresponding maps
αX , . . . , δ are defined as in Fig. 1. Then there exists a finite sequence τ of alternating replacements as in Lemma 3.1 and elementary deformations as in Lemma 3.4
that result in graphs X τ , Y τ , W (S1 )τ , P τ , Z τ , U τ that have the following properties: r̄(X τ ) = r̄(X), r̄(Y τ ) = r̄(Y ), r̄(W (S1 )τ ) = r̄(W (S1 )), P τ = Z τ = U τ ,
r̄(P τ ) ≥ r̄(P ), every vertex of U τ has degree 3 or 2 and every vertex of degree 3 of
U τ has a preimage of degree 3 in X τ or Y τ .
Proof. Applying Lemma 3.1, we may assume that P = Z = U . If every vertex
of U has degree 2 or 3, then our claim holds true as follows from Lemma 3.3.
Hence, we may assume that U contains a vertex v0 of degree at least 4. In view of
Lemma 3.4, by checking all possible elementary deformations of U around v0 , we
can find an elementary deformation by means of a trivalent tree T such that either
r̄(PT ) > r̄(P ) or r̄(PT ) = r̄(P ) and
X
X
max(deg v − 3, 0) <
max(deg v − 3, 0).
v∈V P

v∈V PT

Invoking Lemma 3.1, we replace UT with PT and, completing one cycle of changes in
graphs X, Y, W (S1 ), P, Z, U , we rename Q := QT , where Q ∈ {X, Y, W (S1 ), P, Z, U },
and start over.
Observe that the rank r̄(Z) = r̄(hH, K, S1 i) is bounded above by the number of
generators r(H) + r(K) + |S1| and this bound does not change as we perform cycles
of changes of graphs X, Y, W (S1 ), P, Z, U , because |S1 | is equal to the number of
connected components of W (S1 ) and r̄(H) = r̄(X), r̄(K) = r̄(Y ). This implies that
the number
X
max(deg v − 3, 0)
v∈V Z

is bounded above by 2r̄(Z) ≤ 2(r(H) + r(K) + |S1 |). Thus the total number of
cycles will not exceed 2(r(H) + r(K) + |S1 |)2 and our lemma is proved.

Note that the arguments of the proof of Lemma 3.5 provide an algorithm that
deterministically constructs the desired graphs X τ , Y τ , W (S1 )τ , P τ , Z τ , U τ in
polynomial space (of size of input which are graphs X, Y, W (S1 ), P, Z, U along
with associated maps αX , . . . , δ).
Lemma 3.6. r̄(Z) ≤ r̄(X) + r̄(Y ).

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE GROUPS

9

Proof. In view of Lemma 3.5, we may assume that Stallings graphs X, Y, Z of
subgroups H, K, hH, K, S1 i satisfy the conclusion of Lemma 3.5. Then all of the
vertices of X, Y, Z have degree 2 or 3. Hence, 2r̄(U ) = |V3 U |, where V3 U is the set
of vertices of degree 3 of U . Similarly, we have 2r̄(X) = |V3 X| and 2r̄(Y ) = |V3 Y |.
Now application of Lemma 3.3 yields |V3 Z| ≤ |V3 X| + |V3 Y | which implies the
desired inequality r̄(Z) ≤ r̄(X) + r̄(Y ).

4. Applications
As an application of Lemma 3.5, we state and prove a couple of specific inequalities for reduced ranks of the generalized intersections and joins of subgroups in free
groups.
Theorem 4.1. Let H, K be finitely generated subgroups of a free group F . Let
S(H, K) ⊆ F denote a set of representatives of those double cosets HtK ⊆ F ,
t ∈ F , that have the property HtKt−1 6= {1}, and let S1 ⊆ S(H, K) be nonempty.
Then r̄(hH, K, S1 i) ≤ r̄(H) + r̄(K) and
X
r̄(H, K, S1 ) :=
r̄(H ∩ sKs−1 )
s∈S1

≤ 2r̄(H)r̄(K) − r̄(hH, K, S1 i) min(r̄(H), r̄(K)).

(4.1)

Moreover,
r̄(H, K, S1 ) ≤ 21 (r̄(H)+r̄(K)−r̄(hH, K, S1 i))(r̄(H)+r̄(K)−r̄(hH, K, S1 i)+1). (4.2)
Note that the inequality (4.1) is a strengthened version of (1.1) and this strengthening is analogous to a strengthened version of the Hanna Neumann conjecture
introduced by Walter Neumann [18]. We also remark that the inequality (4.1) in
the cases when S0 = {1} and S0 = S(H, K) is due to Kent [14] and the inequality
(4.2) is shown by Dicks [4] who also obtained other inequalities.
It is worthwhile to mention that the natural question on the existence of a bound
that would be a stronger version of (4.1), in which the first term would have the
coefficient 1 in place of 2 and the second negative term would contain the factor
r̄(hH, K, S1 i) with some coefficient, has a negative solution. Indeed, according
to [12], there are finitely generated subgroups H, K of a free group F such that
r̄(H, K, S(H, K)) = r̄(H)r̄(K) > 0 and r̄(hH, K, S(H, K)) > C for any constant
C > 0.
Proof. In view of Lemma 3.5, we may assume that Stallings graphs X, Y, Z of
subgroups H, K, hH, K, S1 i, resp., and graphs W (S1 )τ , P τ satisfy the conclusion
of Lemma 3.5. Recall that r̄(H) = r̄(X), r̄(K) = r̄(Y ) and r̄(hH, K, S1 i) ≤ r̄(Z) =
r̄(U ),
As before, if Q is a graph whose vertices have degree 2 or 3, then V3 Q denotes
the set of vertices of Q of degree 3. Recall that 2r̄(Q) = |V3 Q|.
For every v ∈ V U , denote
−1
kv := |V3 X ∩ βX
(v)|,

ℓv := |V3 Y ∩ βY−1 (v)|,

m := |V3 W (S1 )|,

n := |V3 U |.

We also let V3 U := VB U ∨ VX U ∨ VY U , where VB U is the set of vertices of U
that have preimages of degree 3 in both X and Y , VX U is the set of vertices of
U that have preimages of degree 3 in X only, and VY U is the set of vertices of U
that have preimages of degree 3 in Y only. Denote nB := |VB U |, nX := |VX U |,
−1
nY := |VY U |. We let V3 X = V31 X ∨ V32 X, where V31 X := βX
(VX U ) and V32 X :=

10

S. V. IVANOV

−1
βX
(VB U ). Similarly, we let V3 Y = V31 Y ∨ V32 Y , where V31 Y := βY−1 (VY U ) and
V32 Y := βY−1 (VB U ). Denote

k := |V3 X|, k1 := |V31 X|, k2 := |V32 X|, ℓ := |V3 Y |, ℓ1 := |V31 Y |, ℓ2 := |V32 Y |.
Clearly, k = k1 + k2 , ℓ = ℓ1 + ℓ2 , n = nB + nX + nY , k1 ≥ nX , ℓ1 ≥ nY , and
X
X
m≤
kv ℓv =
kv ℓv .
v∈V U

v∈VB U

We now continue with arguments
P similar to those of Imrich-Müller [8] that follow
the proof of their lemma. Since v∈VB U ℓv = ℓ2 and ℓ = ℓ1 + ℓ2 , we obtain
X
X
m≤
kv ℓv = kℓ −
(k − kv )ℓv − kℓ1
v∈VB U

≤ kℓ −

v∈VB U

X

(k − kv ) − kℓ1 = kℓ − knB + k2 − kℓ1

v∈VB U

≤ kℓ − k(nB + nY − 1).

(4.3)

Switching X and Y , we analogously obtain
m ≤ kℓ − ℓ(nB + nX − 1).

(4.4)

Assume that nB = 0. Then r̄(W (S1 )) = 0 and the inequality (4.1) is equivalent
to
0 ≤ 2r̄(X)r̄(Y ) − min(r̄(X), r̄(Y ))r̄(Z)
which is equivalent to r̄(Z) ≤ 2 max(r̄(X), r̄(Y )). Since r̄(Z) ≤ r̄(X) + r̄(Y ) by
Lemma 3.6, it follows that (4.1) holds true. A reference to Lemma 3.6 also proves
that
r̄(hH, K, S1 i) ≤ r̄(Z) ≤ r̄(X) + r̄(Y ) = r̄(H) + r̄(K).
Suppose that nB ≥ 1. Since nB + nX + nY = 2r̄(U ), it follows that
nX + nY ≤ 2r̄(U ) − 1.
Hence, min(nX , nY ) ≤ r̄(U ) − 1 and max(nB + nX − 1, nB + nY − 1) ≥ r̄(U ).
Therefore, the inequalities (4.3)–(4.4) imply that
2r̄(W (S1 )) = m ≤ 4r̄(X)r̄(Y ) − 2 min(r̄(X), r̄(Y ))r̄(Z).
Dividing by 2, we obtain the required bound (4.1).
Observe that Lemma 3.6 together with the foregoing classification of vertices
of degree 3 in graphs W (S), X, Y, P = Z = U make it possible to produce other
inequalities for r̄(H, K, S1 ) = r̄(W (S1 )) that
P would involve r̄(hH, K, S1 i) = r̄(Z).
For example, when maximizing the sum v∈V U kv ℓv which gives an upper bound
for m = 2r̄(W (S1 )), we may assume that there is a single vertex v such that both
kv , ℓv > 0, whence nB = 1, k2 = kv and ℓ2 = ℓv . We may further assume that
k1 = nX , ℓ1 = nY . Indeed, if, say k1 > nX , then we could increase kv by k1 − nX
and decrease k1 by k1 − nX making thereby k2 ℓ2 = kv ℓv greater. Hence, to get an
upper bound for m, we can maximize the product k2 ℓ2 = (k − k1 )(ℓ − ℓ1 ) subject to
k1 + ℓ1 + 1 = n. Since k, ℓ, n are fixed positive even integers, equal to 2r̄(X), 2r̄(Y ),
2r̄(Z), resp., it follows that the product (k − k1 )(ℓ − n + 1 − k1 ) has the maximum
at k1 = 21 (k − ℓ + n). Since k1 is an integer, it follows that (k − k1 )(ℓ − n + 1 − k1 )

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE GROUPS

11

has a maximal value for integer k1 when k1 = 12 (k − ℓ + n) or k1 = 21 (k − ℓ + n) − 1.
This means that, unconditionally, we have
m ≤ (k − k1 )(ℓ − n + 1 − k1 ) ≤ 12 (k + ℓ − n + 2) · 21 (k + ℓ − n).
Equivalently,
2r̄(W (S1 )) = m ≤ (r̄(X) + r̄(Y ) − r̄(Z) + 1)(r̄(X) + r̄(Y ) − r̄(Z))
which implies the bound (4.2). Theorem 4.1 is proved.



5. One More Question
One might wonder what would be the conditions that guarantee the existence
of a nontrivial “blow-up” of a vertex v0 of the graph P = Z = U by an elementary
deformation around v0 , as defined in Sect. 3. Here we present a result that provides
a criterion for the existence of such a “blow-up” of a vertex v0 of U , i.e., the existence
of an elementary deformation around a vertex v0 by means of a tree T such that
r̄(PT ) > r̄(P ).
Assume that P = Z = U and the maps γ, δ in Fig. 1 are identity maps on U .
Let v0 be a fixed vertex of U and let D denote the set of all oriented edges of U
that end in v0 .
A vertex v of one of the graphs W (S1 ), X, Y is called a v0 -vertex if the image of
v under βX αX , βX , βY , resp., is v0 .
For every v0 -vertex v ∈ V Q, where Q ∈ {X, Y, W (S1 )}, define the set D(v) ⊆ D
~ so that the terminal vertex
so that e ∈ D(v) if and only if there is an edge f ∈ EQ
f+ of f is v and the image of the edge f in U is e.
Consider a partition D = A ∨ B of the set D into two nonempty subsets A, B.
A v0 -vertex v ∈ V Q, where Q ∈ {X, Y, W (S1 )}, is said to be of type {A, B} if
both intersections D(v) ∩ A and D(v) ∩ B are nonempty. The set of all vertices of
type {A, B} of a graph Q, where Q ∈ {X, Y, W (S1 )}, is denoted V{A,B} Q.
Consider a bipartite graph Ψ({A, B}) whose set of vertices
V Ψ({A, B}) = VX Ψ({A, B}) ∨ VY Ψ({A, B})
consists of two disjoint parts
VX Ψ({A, B}) := V{A,B} X

and

VY Ψ({A, B}) := V{A,B} Y.

Two vertices vX ∈ VX Ψ({A, B}) and vY ∈ VY Ψ({A, B}) are connected in
Ψ({A, B}) by an edge if and only if there is a vertex v ∈ W (S1 ) such that
αX (v) = vX , αY (v) = vY and v ∈ V{A,B} W (S1 ).
Theorem 5.1. Suppose P = Z = U , v0 is a vertex of U . The equality r̄(PT ) =
r̄(UT ) = r̄(U ) holds for every elementary deformation around v0 by means of a
tree T if and only if the following conditions hold. For every partition D = A ∨ B
with nonempty A, B if the graph Ψ({A, B}) contains k connected components, then
W
there exists a partition D = k+1
i=1 Ci such that, for every i, Ci is nonempty and
either Ci ⊆ A or Ci ⊆ B. Next, for every vertex v ∈ V Q, where Q ∈ {X, Y }, such
that βQ (v) = v0 , the intersection D(v) ∩ A is either empty or D(v) ∩ A ⊆ CivA
for some ivA , ivA = 1, . . . , k + 1, and the intersection D(v) ∩ B is either empty or
D(v) ∩ B ⊆ CivB for some ivB , ivB = 1, . . . , k + 1.

12

S. V. IVANOV

Proof. First we introduce the notation we will need below. As above, let T be a
tree whose set of vertices of degree 1 is D′ . If H ′ ⊆ D′ is a nonempty subset of
vertices of degree 1 in T , we let MT (H ′ ) denote the minimal subtree of T that
contains H ′ . Clearly, the set of vertices of degree ≤ 1 of MT (H ′ ) is H ′ . Note that
MT (H ′ ) = H ′ if H ′ consists of a single vertex. If E ⊆ D, then E ′ ⊆ D′ denotes
the image of E under the map d → d′ for every d ∈ D.
For every vertex v ∈ V Q, where Q ∈ {X, Y, W (S1 )}, consider a tree MT (D(v))
which is isomorphic to the subtree MT (D(v)′ ) of T and let
ζv : MT (D(v)) → T

(5.1)

denote the natural monomorphism whose image is MT (D(v)′ ).
If w is a vertex of W (S1 ), then the tree MT (D(αX (w))) contains a subtree
isomorphic to MT (D(w)) which we denote MT,X (D(w)).
Similarly, the tree MT (D(αY (w))) contains a subtree isomorphic to MT (D(w)),
denoted MT,Y (D(w)).
It follows from the definitions that the graph Tb = γT−1 δT−1 (T ) can be described
as follows. Tb is the union of graphs MT (D(v)) over all v ∈ V Q, Q ∈ {X, Y }, which
are identified along their subgraphs of the form MT,X (D(w)) = MT,Y (D(w)) over
all w ∈ V W (S1 ).
Now assume that the equality r̄(PT ) = r̄(UT ) holds for every tree T or, equivalently, see Lemma 3.2, the graph Tb is a tree for every T . Note that Tb being a tree
need not imply that Tb is naturally isomorphic to T .
Let D = A ∨ B be a partition of D with nonempty A, B. Our goal is to find a
W
partition D = k+1
i=1 Ci with the properties described in Theorem 5.1.
Consider a trivalent tree T = T ({A, B}) such that T contains a nonoriented edge
e so that the graph T \ {e} consists of two connected components TeA , TeB such
that A′ ⊆ V TeA and B ′ ⊆ V TeB .
Note that the tree MT (D(v)), where v ∈ V Q, Q ∈ {X, Y, W (S1 )}, contains
an edge f with ζv (f ) = e, where ζv is defined by (5.1), if and only if v has type
{A, B}. Hence, the set γT−1 δT−1 (e) consists of images of such edges f of MT (D(v))
with ζv (f ) = e.
Furthermore, let v, v ′ ∈ V{A,B} X ∨ V{A,B} Y be two vertices that belong to
the same connected component of Ψ({A, B}). Then there exists a sequence v =
v1 , v2 , . . . , vℓ = v ′ of vertices in the graph Ψ({A, B}) so that vi , vi+1 are connected
by an edge. It follows from the definitions that the edges f1 , f2 , . . . , fℓ such that
ζvi (fi ) = e, i = 1, . . . , ℓ, are identified in Tb. Conversely, it follows from the definitions in a similar fashion that if v, v ′ ∈ V{A,B} X ∨ V{A,B} Y and the edges f, f ′ such
that ζv (f ) = e = ζv′ (f ′ ) are identified in Tb, then v, v ′ belong to the same connected
component of Ψ({A, B}). These remarks prove that there is a bijection between the
set γT−1 δT−1 (e) = {f1 , . . . , fk } ⊆ Tb and the set of connected components of the graph
Ψ({A, B}). Since Tb is a tree with |D| vertices of degree 1 whose set we denote D′′ ,
it follows that the graph Tb − (γT−1 δT−1 (e)) splits into k + 1 connected components
Wk+1
which induce a partition D′′ = i=1 Ci′′ , where for every i, Ci′′ is nonempty and
W
′′
either Ci′′ ⊆ A′′ or Ci ⊆ B ′′ . Then D = k+1
i=1 Ci , where Ci is the image of Ci
′′
under the map d → d for every d ∈ D, provides a desired partition for D because,
for every v0 -vertex v ∈ V Q, where Q ∈ {X, Y }, the vertices of A′′ ∩ D(v)′′ ⊆ D′′
and those of B ′′ ∩ D(v)′′ are connected in Tb − (γT−1 δT−1 (e)) by images of edges of

ON JOINS AND INTERSECTIONS OF SUBGROUPS IN FREE GROUPS

13

MT (D(v)) − ζv−1 ({e}) of Tb. Therefore, D(v) ∩ A ⊆ CivA for some ivA whenever the
intersection D(v) ∩ A is not empty and D(v) ∩ B ⊆ CivB for some ivB whenever
the intersection D(v) ∩ B is nonempty.
Now we will prove the converse. Assume that for every partition D = A ∨ B
W
there exists a partition D = k+1
i=1 Ci with the properties of Theorem 5.1. Arguing
on the contrary, suppose that there is a tree T for which the graph Tb is not a tree.
Pick a shortest circuit p in Tb of positive length. Let e be a nonoriented edge of T
such that e ∈ δT γT (p). The graph T − {e} consists of two connected components
TeA , TeB which define a partition D′ = A′ ∨ B ′ , where A′ ⊆ TeA , B ′ ⊆ TeB , and
both A′ , B ′ are nonempty. Let k denote the number of connected components of
the graph Ψ({A, B}). It is clear from Lemma 3.2 and the definitions that k ≥ 1.
W
According to our assumption, there exists a partition D = k+1
i=1 Ci , where, for
every i, Ci is nonempty, Ci ⊆ A or Ci ⊆ B, and, for every v0 -vertex v ∈ V Q, where
Q ∈ {X, Y }, we have that D(v) ∩ A ⊆ CivA for some ivA whenever D(v) ∩ A is
nonempty and we have that D(v) ∩ B ⊆ CivB for some ivB whenever D(v) ∩ B is
nonempty.
As above, we observe that if v, v ′ ∈ V{A,B} X ∨V{A,B} Y are two vertices, then the
′
b
edges ζv−1 (e), ζv−1
′ (e) are identified in T if and only if v, v belong to the same connected component of the graph Ψ({A, B}). This implies that the edges γT−1 δT−1 (e) ⊆
Tb are in bijective correspondence with connected components of Ψ({A, B}). Hence,
there are k edges in γT−1 δT−1 (e). Denote γT−1 δT−1 (e) = {f1 , . . . , fk }. Since identification of subgraphs
MT,X (D(w)) ⊆ MT (D(αX (w)))

and MT,Y (D(w)) ⊆ MT (D(αY (w)))
Wk+1
in process of construction of Tb respects the partition D′ = i=1 Ci′ , it follows that
the graph Tb consists of pairwise disjoint subgraphs S1 , . . . , Sk+1 , where
δT γT (Sj ) ∩ D′ = Cj′ ,

j = 1, . . . , k + 1,

which are joined by k nonoriented edges of γT−1 δT−1 (e). Collapsing subgraphs
S1 , . . . , Sk+1 into points, we see that Tb turns into a tree with k nonoriented edges
and k + 1 vertices. Consequently, a shortest circuit in Tb of positive length may not
contain any edge of γT−1 δT−1 (e). This contradiction to the choice of the path p and
the edge e in δT γT (p) completes the proof of Theorem 5.1.

References
[1]
[2]
[3]
[4]
[5]
[6]
[7]

[8]

R. G. Burns, On the intersection of finitely generated subgroups of a free group, Math. Z.
119(1971), 121–130.
W. Dicks, Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated
graph conjecture, Invent. Math. 117(1994), 373–389.
W. Dicks, Simplified Mineyev, preprint, http://mat.uab.cat/∼dicks/SimplifiedMineyev.pdf
W. Dicks, unpublished manuscript.
W. Dicks and S. V. Ivanov, On the intersection of free subgroups in free products of groups,
Math. Proc. Cambridge Phil. Soc. 144(2008), 511–534.
W. Dicks and S. V. Ivanov, On the intersection of free subgroups in free products of groups
with no 2-torsion, Illinois J. Math. 54(2010), 223–248.
J. Friedman, Sheaves on graphs, their homological invariants, and a proof of the Hanna Neumann conjecture: with an appendix by Warren Dicks, Mem. Amer. Math. Soc. 233(2014),
no. 1100. xii+106 pp.
W. Imrich and T. Müller, On Howson’s theorem, Arch. Math. 62 (1994), 193–198.

14

S. V. IVANOV

[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]

S. V. Ivanov, On the intersection of finitely generated subgroups in free products of groups,
Internat. J. Algebra and Comp. 9(1999), 521–528.
S. V. Ivanov, Intersecting free subgroups in free products of groups, Internat. J. Algebra
and Comp. 11(2001), 281–290.
S. V. Ivanov, On the Kurosh rank of the intersection of subgroups in free products of groups,
Adv. Math. 218(2008), 465–484.
S. V. Ivanov, On a conjecture of Imrich and Müller, submitted.
I. Kapovich and A. G. Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra
248(2002), 608–668.
R. P. Kent IV, Intersections and joins of free groups, Alg. Geom. Topology 9(2009), 305–
325.
I. Mineyev, Submultiplicativity and the Hanna Neumann conjecture, Ann. Math. 175(2012),
393–414.
P. Nickolas, Intersections of finitely generated free groups, Bull. Austral. Math. Soc.
31(1985) 339–348.
H. Neumann, On the intersection of finitely generated free groups, Publ. Math. 4(1956),
186–189; Addendum, Publ. Math. 5(1957), 128.
W. D. Neumann, On the intersection of finitely generated subgroups of free groups, Lecture
Notes in Math. (Groups-Canberra 1989) 1456(1990), 161–170.
B. Servatius, A short proof of a theorem of Burns, Math. Z. 184(1983), 133–137.
J. R. Stallings, Topology of finite graphs, Invent. Math. 71(1983), 551–565.

Department of Mathematics, University of Illinois, Urbana, IL 61801, U.S.A.
E-mail address: ivanov@illinois.edu

