arXiv:1607.08303v2 [] 1 Jan 2018

THE INTERSECTION OF SUBGROUPS IN FREE GROUPS AND
LINEAR PROGRAMMING
S. V. IVANOV
Abstract. We study the intersection of finitely generated subgroups of free
groups by utilizing the method of linear programming. We prove that if H1
is a finitely generated subgroup of a free group F , then the WN-coefficient
σ(H1 ) of H1 is rational and can be computed in deterministic exponential
time in the size of H1 . This coefficient σ(H1 ) is the minimal nonnegative real
number such that, for every finitely generated subgroup H2 of F , it is true
that r̄(H1 , H2 ) ≤ σ(H1 )r̄(H1 )r̄(H2 ), where r̄(H) := max(r(H) − 1, 0) is the
reduced rank of H, r(H) is the rank of H, and r̄(H1 , H2 ) is the reduced rank
of the generalized intersection of H1 and H2 . We also show the existence of
a subgroup H2∗ = H2∗ (H1 ) of F such that r̄(H1 , H2∗ ) = σ(H1 )r̄(H1 )r̄(H2∗ ), the
Stallings graph Γ(H2∗ ) of H2∗ has at most doubly exponential size in the size
of H1 and Γ(H2∗ ) can be constructed in exponential time in the size of H1 .

1. Introduction
Let F be a finitely generated free group, let r(F ) denote the rank of F and let
r̄(F ) := max(r(F ) − 1, 0) denote the reduced rank of F . Let H1 and H2 be finitely
generated subgroups of F . Hanna Neumann [18] proved that
r̄(H1 ∩ H2 ) ≤ 2r̄(H1 )r̄(H2 )
and conjectured that r̄(H1 ∩ H2 ) ≤ r̄(H1 )r̄(H2 ).
These result and conjecture of Hanna Neumann were strengthened by Walter Neumann [19] by considering a generalized intersection of H1 and H2 . Let
S(H1 , H2 ) denote a set of representatives of those double cosets H1 tH2 of F , t ∈ F ,
that have the property H1 ∩ tH2 t−1 6= {1}. Walter Neumann [19] proved that the
set S(H1 , H2 ) is finite, the reduced rank r̄(H1 , H2 ) of the generalized intersection
of H1 and H2 satisfies
X
r̄(H1 ∩ sH2 s−1 ) ≤ 2r̄(H1 )r̄(H2 ),
(1.1)
r̄(H1 , H2 ) :=
s∈S(H1 ,H2 )

and he conjectured that
r̄(H1 , H2 ) =

X

r̄(H1 ∩ sH2 s−1 ) ≤ r̄(H1 )r̄(H2 ).

(1.2)

s∈S(H1 ,H2 )

This strengthened version of the Hanna Neumann conjecture was proved by Friedman [7] and Mineyev [17], see also Dicks’s proof [3] and a proof in [13].
2010 Mathematics Subject Classification. Primary 20E05, 20E07, 20F65; Secondary 68Q25,
90C90.
Key words and phrases. Free groups, intersection of subgroups, rank, linear programming.
Supported in smaller part by the NSF under grant DMS 09-01782.
1

2

S. V. IVANOV

Now suppose that H1 is a fixed finitely generated subgroup of F . We will say
that a real number σ(H1 ) ≥ 0 is the Walter Neumann coefficient for H1 , or, briefly,
the WN-coefficient for H1 , if, for every finitely generated subgroup H2 of F , we
have
r̄(H1 , H2 ) ≤ σ(H1 )r̄(H1 )r̄(H2 )
(1.3)
and σ(H1 ) is minimal with this property. It is clear that if H1 is noncyclic then


r̄(H1 , H2 )
σ(H1 ) = sup
r̄(H1 )r̄(H2 )
H2
over all finitely generated noncyclic subgroups H2 of F .
In this article, we are concerned with algorithmic computability of the WNcoefficient σ(H1 ) for a finitely generated subgroup H1 of F and with other properties
of this number σ(H1 ). Utilizing the method of linear programming, we will prove
the following.
Theorem 1.1. Suppose that F is a free group of finite rank and H1 is a finitely
generated noncyclic subgroup of F . Then the following are true.
(a) There exists a linear programming problem (LP-problem) associated with H1
P(H1 ) = max{cx | Ax ≤ b}

(1.4)

with integer coefficients whose solution is equal to −σ(H1 )r̄(H1 ).
(b) There is a finitely generated subgroup H2∗ of F , H2∗ = H2∗ (H1 ) which corresponds to a vertex solution of the dual problem
P∗ (H1 ) = min{b⊤ y | A⊤ y = c⊤ , y ≥ 0}
of the primal LP-problem (1.4) such that r̄(H1 , H2∗ ) = σ(H1 )r̄(H1 )r̄(H2∗ ). In par1
ticular, the WN-coefficient σ(H1 ) of H1 is rational and satisfies r̄(F
) ≤ σ(H1 ) ≤ 1.
∗
Furthermore, if Γ(H1 ) and Γ(H2 ) denote the Stallings graphs representing the
subgroups H1 and H2∗ , resp., |EΓ| denotes the number of oriented edges in the graph
Γ, and m − 1 is the rank of F , then the size of Γ(H2∗ ) is at most doubly exponential
in the size of Γ(H1 ), specifically,
|EΓ(H1 )|/2+2 log2 m

|EΓ(H2∗ )| < 22

.

(c) Assume that H1 is given by a finite generating set or by its Stallings graph.
Then, in deterministic exponential time in the size of the input, one can write
down and solve the LP-problem (1.4) associated with H1 . In particular, the WNcoefficient σ(H1 ) of H1 is computable in deterministic exponential time in the size
of the input.
In addition, the Stallings graph Γ(H2∗ ) of the subgroup H2∗ of part (b) can be
constructed in deterministic exponential time in the size of the input.
We remark that the results similar to those of Theorem 1.1 are obtained by the
author [14] for factor-free subgroups of free products of finite groups. However,
the arguments of [14] do not apply to free products of infinite groups and here we
develop analogous techniques suitable for free groups. For a generalization of the
conjecture (1.2) to subgroups of free products of groups and relevant results, the
reader is referred to articles [5], [6], [11], [13], [14].
Similarly to [14], the correspondence between subgroups H2 and vectors y(H2 )
of the feasible polyhedron {y | A⊤ y = c⊤ , y ≥ 0} of the dual LP-problem P∗ (H1 ),

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

3

mentioned in part (b) of Theorem 1.1, plays an important role in proofs and is
reminiscent of the correspondence between (resp. almost) normal surfaces in 3dimensional manifolds and their (resp. almost) normal vectors in the Haken theory
of normal surfaces and its generalizations, see [8], [9], [10], [12], [15]. In particular,
the idea of a vertex solution works equally well both in the context of almost normal surfaces [12], see also [9], [15], and in the context of subgroups of free groups,
providing in either situation both the connectedness of the underlying object associated with a vertex solution and an upper bound on the size of the underlying
object.
It is worthwhile to mention that our construction of the Stallings graph Γ(H2∗ )
in part (c) of Theorem 1.1 is somewhat succinct (cf. the definition of succinct
representations of graphs, see [20]) in the sense that, despite the fact that the
size of Γ(H2∗ ) could be doubly exponential, we are able to give a description of
Γ(H2∗ ) in exponential time. In particular, the vertices of Γ(H2∗ ) are represented by
exponentially long bit strings and the edges of Γ(H2∗ ) are drawn in blocks. As a
result, we can find out in exponential time whether two given vertices of Γ(H2∗ ) are
connected by an edge.
In view of Theorem 1.1, it is of interest to look at two properties of finitely
generated subgroups of free groups introduced by Dicks and Ventura [4]. Recall
that a finitely generated subgroup H of a free group F is called compressed, see [4],
if, for every subgroup K of F such that H ⊆ K, we have r̄(H) ≤ r̄(K). A finitely
generated subgroup H of a free group F is called inert, see [4], if for every subgroup
K of F , one has r̄(H ∩ K) ≤ r̄(K). It is immediate from the definitions that every
inert subgroup is compressed. The problem whether every compressed subgroup is
inert is stated by Dicks and Ventura [4] and it is still unresolved.
We say that a finitely generated subgroup H of a free group F is strongly inert
if, for every subgroup K of F , we have r̄(H, K) ≤ r̄(K). Clearly, a strongly inert
subgroup is inert. It would be of interest to find an example, if it exists, to distinguish between these two classes of inert and strongly inert subgroups and, more
generally, to find a finitely generated noncyclic subgroup H of F such that


r̄(H ∩ K)
< σ(H),
sup
r̄(H)r̄(K)
K
where the supremum, as before, is taken over all finitely generated noncyclic subgroups K of F n
. Anotheronatural question is to find an algorithm that computes this
r̄(H∩K)
number supK r̄(H)r̄(K)
which could be called the Hanna Neumann coefficient of
H.
While we are not able to distinguish between these three classes of compressed,
inert, and strongly inert subgroups of F , our algorithms and their running times,
that recognize two of these classes, are quite different.
Theorem 1.2. Suppose that F is a free group of finite rank and H is a finitely
generated noncyclic subgroup of F given by a finite generating set or by its Stallings
graph. Then the following hold true.
(a) There is an algorithm that decides, in deterministic exponential time in the
size of H, whether H is strongly inert.
(b) There is an algorithm that verifies, in nondeterministic polynomial time in
the size of H, whether H is not compressed.

4

S. V. IVANOV

Summarizing, we see that the decision problem that inquires whether a finitely
generated subgroup H of F is strongly inert is in EXP, the decision problem that
asks whether H is inert is not known to be decidable, and the decision problem that
inquires whether H is compressed is in coNP (for the definition of computational
complexity classes EXP, coNP see [1] or [20]).
2. Preliminaries
Suppose that X is a graph. Let V X denote the set of vertices of X and let EX
be the set of oriented edges of X. If e ∈ EX then e−1 denotes the edge with the
opposite orientation, e−1 6= e.
For e ∈ EX, let e− and e+ denote the initial and terminal, resp., vertices of e.
A path p = e1 · · · ek , where ei ∈ EX, (ei )+ = (ei+1 )− , i = 1, . . . , k − 1, is called
reduced if, for every i = 1, . . . , k − 1, one has ei 6= e−1
i+1 . The length of a path
p = e1 · · · ek is k, denoted |p| = k. The initial vertex of p is p− = (e1 )− and the
terminal vertex of p is p+ = (ek )+ . A path p is closed if p− = p+ .
If p = e1 · · · ek is a closed path, then a cyclic permutation p̄ of p is a path of
the form e1+i e2+i · · · ek+i , where i = 0, 1, . . . , k and the indices are considered
mod k. The subgraph of X that consists of edges of all closed paths p of X such
that |p| > 0 and every cyclic permutation of p is reduced, is called the core of X,
denoted core(X).
Let U be a finite connected graph such that core(U ) = U , let o ∈ V U and let
F = π1 (U, o) be the fundamental group of U at o. Then F is a free group of rank
r(F ) = |EU |/2 − |V U | + 1, where |B| is the cardinality of a finite set B, and the
elements of F can be thought of as reduced closed paths in U starting at o.
Following Stallings [22], see also [2], [16], with every (finitely generated) subgroup
H of FU = π1 (U, o), we can associate a (resp. finite) graph Y = Y (H) and a map
β : Y → U of graphs so that H is isomorphic to π1 (Y, oY ), where oY ∈ V Y ,
β(oY ) = o, and a reduced path p ∈ π1 (U, o) belongs to H if and only if there is a
reduced path pH ∈ π1 (Y, oY ) such that β(pH ) = p. In addition, we may assume
that β is a locally injective map of graphs, i.e., the restriction of β on a regular
neighborhood of every vertex of Y is injective. We call a locally injective map of
graphs an immersion. Since β is an immersion, it follows that every reduced path
in H ⊆ π1 (U, o) has a unique preimage in Y .
Consider two finitely generated subgroups H1 and H2 of the free group FU =
π1 (U, o). Pick a set S(H1 , H2 ) of representatives of those double cosets H1 gH2 ,
g ∈ FU , for which the intersection H1 ∩ gH2 g −1 is nontrivial.
Let Y1 , Y2 be Stallings graphs of the subgroups H1 , H2 and let Y1 × Y2 denote
the pullback of the maps βi : Yi → U , i = 1, 2. Recall that

U

V (Y1 × Y2 ) = {(v1 , v2 ) | vi ∈ V Yi , β1 (v1 ) = β2 (v2 )},
U

E(Y1 × Y2 ) = {(e1 , e2 ) | ei ∈ EYi , β1 (e1 ) = β2 (e2 )},
U

and (e1 , e2 )− = ((e1 )− , (e2 )− ), (e1 , e2 )+ = ((e1 )+ , (e2 )+ ).
According to Walter Neumann [19], the set S(H1 , H2 ) is finite and the nontrivial
intersections H1 ∩ sH2 s−1 , where s ∈ S(H1 , H2 ), are in bijective correspondence

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

5

with the connected components Ws of the core W := core(Y1 × Y2 ). Moreover, for
U

every s ∈ S(H1 , H2 ), we have
r̄(H1 ∩ sH2 s−1 ) = r̄(Ws ) = |EWs |/2 − |V Ws |.
Hence,

X

r̄(H1 ∩ sH2 s−1 ) = r̄(W ) = |EW |/2 − |V W |.

s∈S(H1 ,H2 )

Let

α′i

denote the projection map Y1 × Y2 → Yi , i = 1, 2, i.e., α′i ((e1 , e2 )) = ei and
U

α′i ((v1 , v2 )) = vi . Restricting α′i on W ⊆ Y1 × Y2 , we obtain the map αi : W → Yi ,
U

i = 1, 2. In this notation, we have a commutative diagram depicted in Figure 1.
α1

W

✠
Y1

α2
❅
❘
❅
Y2

β
β❅
1
❘ ✠ 2
❅
U
Figure 1
In particular, if X ∈ {Y1 , Y2 , W, U }, then there is a canonical immersion
ϕ : X → U,
where ϕ = βi if X = Yi , i = 1, 2, ϕ = idU if X = U and ϕ = βi αi if X = W .
More generally, we will say that X is a U -graph if X is equipped with a graph map
ϕ : X → U . A U -graph X is reduced if ϕ is an immersion. For example, Y1 , Y2 , W, U
are reduced U -graphs. If x ∈ V X ∪ EX then ϕ(x) ∈ V U ∪ EU is called the label
of x.
It will be convenient to work with a graph U of a special form which we denote
Um . The graph Um contains two vertices o1 , o2 , V Um := {o1 , o2 }, and the vertices o1 , o2 are connected by m ≥ 3 nonoriented edges so that the oriented edges
a1 , . . . , am ∈ EUm start at o1 and end in o2 , see Figure 2, where the case m = 3 is
depicted.
a1
U3
a2
a3
Figure 2
We will be considering mostly Um -graphs, where m ≥ 3. Since Um is fixed, we
will be writing Y1 × Y2 in place of Y1 × Y2 .
Um

Denote
A := {a1 , . . . , am }.

(2.1)

6

S. V. IVANOV

Let X be a Um -graph. A vertex v ∈ V X is called an i-vertex if ϕ(v) = oi ,
i = 1, 2. Clearly, if e+ is a 2-vertex then ϕ(e) ∈ A and if e+ is a 1-vertex then
−1
ϕ(e) ∈ A−1 = {a−1
1 , . . . , am }.
An edge e ∈ EX is called a b-edge, where b ∈ A, if ϕ(e) = b. The set of all
b-edges of X is denoted Eb X. Clearly,
X
|Eb X| = |EX|/2.
b∈A

3. The system of linear inequalities SLI[Y1 ]
Suppose that Y1 is a finite reduced Um -graph such that Y1 = core(Y1 ) and
r̄(Y1 ) := −χ(Y1 ) = |EY1 |/2 − |V Y1 | > 0,
where χ(Y1 ) is the Euler characteristic of Y1 (since EY1 is the set of oriented edges
of Y1 , we use |EY1 |/2 in χ(Y1 )). This graph Y1 will be held fixed throughout
Sections 3–4.
Let (A1 , . . . , Am ) be an m-tuple of sets Aj such that
Aj ⊆ Eaj Y1 ,

j = 1, . . . , m.

(3.1)

Recall that m = |A| and m ≥ 3, see (2.1).
Sm
Let e, f ∈ j=1 Aj . We say that the edges e, f are i-related, written e ∼i f , if
e− = f− in Y1 when i = 1 or e+ = f+ in Y1 when i = 2. Note that it follows
from (3.1) and from Y1 being a Um -graph that e− , f− are 1-vertices
while e+ , f+
S
are 2-vertices. Clearly, ∼i is an equivalence relation on the set m
j=1 Aj .
Sm
Let [e]∼i denote the equivalence class of an edge e ∈ j=1 Aj relative to this
equivalence relation ∼i and let |[e]∼i | denote the cardinality of [e]∼i .
We will say
that an m-tuple (A1 , . . . , Am ) is i-admissible,
where i = 1, 2 is fixed,
Sm
Sm
if the union j=1 Aj is not empty and, for every e ∈ j=1 Aj , we have |[e]∼i | > 1.
Sm
It is clear that, for every e ∈ j=1 Aj ,
2 ≤ |[e]∼i | ≤ k ≤ m,

(3.2)

where k is the number of nonempty sets Aj in the tuple (A1 , . . . , Am ).
If (A1 , . . . , Am ) is an i-admissible tuple, we define the number Ni (A1 , . . . , Am )
to be the sum
X
(|[e]∼i | − 2)
Sm
over all equivalence classes [e]∼i of the equivalence relation ∼i on j=1 Aj . Hence,
X
(3.3)
(|[e]∼i | − 2).
Ni (A1 , . . . , Am ) :=
[e]∼i

We note that
r̄(Y1 ) = |EY1 |/2 − |V Y1 | =

1
2

X

(deg u − 2),

u∈V Y1

where deg u is the degree of a vertex u ∈ V Y1 , i.e., deg u is the number of edges
e ∈ EY1 such that e+ = v.
Let Vi Y1 denote the set of all i-vertices of Y1 , i = 1, 2. Define
X
r̄i (Y1 ) := 12
(deg u − 2).
u∈Vi Y1

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

Observe that r̄(Y1 ) = r̄1 (Y1 ) + r̄2 (Y1 ) and that
X
(|[e]∼i | − 2)
Ni (A1 , . . . , Am ) :=
[e]∼i

≤

X

7

(3.4)

(deg u − 2) = 2r̄i (Y1 ) ≤ 2r̄(Y1 ).

u∈Vi Y1

For every nonempty set B ⊆ Eaj Y1 , we consider a variable xj,B . We also introduce a special variable xs . Note that, for given j, the set of all variables xj,B is
finite and its cardinality is equal to 2|Eaj Y1 | − 1.
Now we will define a system of inequalities in these variables xj,B , xs so that
each inequality is determined by means of an i-admissible tuple (A1 , . . . , Am ).
For an i-admissible tuple (A1 , . . . , Am ), let Aj1 , . . . , Ajk denote all nonempty sets
in (A1 , . . . , Am ).
If i = 1 then the inequality, corresponding to the 1-admissible tuple (A1 , . . . , Am ),
is defined as follows
− xj1 ,Aj1 − xj2 ,Aj2 − . . . − xjk ,Ajk − (k − 2)xs ≤ −N1 (A1 , . . . , Am ).

(3.5)

If i = 2 then the inequality, corresponding to the 2-admissible tuple (A1 , . . . , Am ),
is defined as follows
xj1 ,Aj1 + xj2 ,Aj2 + . . . + xjk ,Ajk − (k − 2)xs ≤ −N2 (A1 , . . . , Am ).

(3.6)

Let
SLI[Y1 ]

(3.7)

denote the system of all linear inequalities (3.5)–(3.6) constructed for all i-admissible
tuples (A1 , . . . , Am ), i = 1, 2. Clearly, SLI[Y1 ] is finite.
Assume that the map
α2 : core(Y1 × Y2 ) → Y2
is surjective, i.e., α2 (core(Y1 × Y2 )) = Y2 .
For every i-vertex u ∈ V Y2 , consider all the edges e1 , . . . , ek ∈ EY2 such that
(e1 )− = · · · = (ek )− = u if i = 1 or (e1 )+ = · · · = (ek )+ = u if i = 2, so
ϕ(e1 ), . . . , ϕ(ek ) ∈ A, see (2.1), and the edges e1 , . . . , ek start or finish at u. Denote
ϕ(eℓ ) = ajℓ for ℓ = 1, . . . , k.
If j 6∈ {j1 , . . . , jk }, we set Aj (u) := ∅. Otherwise, j = jℓ for some ℓ = 1, . . . , k,
and we set
Ajℓ (u) := α1 α−1
(3.8)
2 (eℓ ) ⊆ Ejℓ Y1 ,
where α−1
2 (eℓ ) is the full preimage of the edge eℓ in core(Y1 × Y2 ). It is immediate
from the definitions that the tuple (A1 (u), . . . , Am (u)) is i-admissible. Recall that
the graphs Y1 and Y2 coincide with their cores and have no vertices of degree less
than 2.
Since every i-admissible tuple (A1 , . . . , Am ) gives rise to an inequality (3.5) if
i = 1 or to an inequality (3.6) if i = 2 and every i-vertex u ∈ V Y2 defines, as
indicated above, an i-admissible tuple (A1 (u), . . . , Am (u)), it follows that every
vertex u ∈ V Y2 is mapped to a certain inequality of the system SLI[Y1 ], denoted
inqV (u). Thus we obtain a function
inqV : V Y2 → SLI[Y1 ]

8

S. V. IVANOV

from the set V Y2 of vertices of a graph Y2 , with the property that the map
α2 : core(Y1 × Y2 ) → Y2
is surjective, to the set of inequalities of the system SLI[Y1 ].
If q is an inequality of the system SLI[Y1 ], written q ∈ SLI[Y1 ], we let q L denote
the left hand side of q, let q R denote the number of the right hand side of the
inequality q, and let k(q) ≥ 2 denote the parameter k for q, see the definition of
inequalities (3.5)–(3.6).
Lemma 3.1. Suppose Y2 is a finite reduced Um -graph with the property that the
map α2 : core(Y1 × Y2 ) → Y2 is surjective. Then
X
X
inqV (u)L = −2r̄(Y2 )xs and
inqV (u)R = −2r̄(core(Y1 × Y2 )).
u∈V Y2

u∈V Y2

Proof. Suppose e ∈ EY2 , ϕ(e) = aj , and e− = u1 , e+ = u2 . Clearly, ui is an i-vertex
of Y2 , i = 1, 2. Denote B := α1 α2−1 (e) ⊆ Eaj Y1 . Then the variables −xj,B and xj,B
P
of inqV (u1 )L and inqV (u2 )L , resp., will cancel out in the sum u∈V Y2 inqV (u)L .
It is easy to see that all occurrences
P of the variable ±xj,B , where j = 1, . . . , m,
B ⊆ Eaj Y1 , |B| > 0, in the sum u∈V Y2 inqV (u)L can be paired down by using
edges of Y2 as indicated above.
Now we observe that every vertex
P u ∈ V Y2 of degree d ≥ 2 contributes −(d − 2)
to the coefficient of xs in the sum u∈V Y2 inqV (u)L and that
X
(deg u − 2).
−χ(Y2 ) = r̄(Y2 ) = 21
u∈V Y2

Therefore, we may conclude that
X
inqV (u)L = −2r̄(Y2 )xs ,
u∈V Y2

as required.
The second equality of the Lemma’s statement follows from the analogous equality
X
(deg u − 2)
−χ(W ) = r̄(W ) = 12
u∈V W

for W = core(Y1 × Y2 ) and from the definition (3.3) of the numbers Ni (A1 , . . . , Am )
that are used in the right hand sides of inequalities (3.5)–(3.6). Indeed, for every
v ∈ V Y2 , the term inqV (v)R of the sum
X
inqV (u)R
u∈V Y2

is −N (A1 (v), . . . , Am (v)), here the sets Aj (v) are defined as in (3.8), which in turn
is equal to
X
(deg w − 2),
−
α2 (w)=v

where the summation runs over all vertices w ∈ W = core(Y1 × Y2 ) with α2 (w) = v.
Since the map α2 is surjective, we obtain
X
inqV (u)R = −2r̄(core(Y1 × Y2 )),
u∈V Y2

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

as required.

9



Let A be a finite set. A combination with repetitions B of A, denoted
B = [[b1 , . . . , bℓ ]] ⊑ A,
is a finite unordered collection of multiple copies of elements of A. Hence, bi ∈ A
and bi = bj is possible when i 6= j. If B = [[b1 , . . . , bℓ ]] is a combination with
repetitions then the cardinality |B| of B is |B| := ℓ.
Observe that the graph Y2 of Lemma 3.1 can be used to construct a combination
with repetitions, denoted
inq(V Y2 ),
of the system SLI[Y1 ], whose elements are individual inequalities, so that every
inequality q = inqV (u) of SLI[Y1 ] occurs in inq(V Y2 ) a number of times equal to
the number of preimages of q in V Y2 under the map inqV . It follows from Lemma 3.1
that if
inq(V Y2 ) = [[q1 , . . . , qℓ ]] ⊑ SLI[Y1 ]
then
X

q L :=

ℓ
X

qiL = −Cxs ,

i=1

q∈inq(V Y2 )

where C ≥ 0 is an integer, C = 2r̄(Y2 ).
For convenience of references, we introduce the following property of a graph Y2
(which need not be connected).
(B) Y2 is a finite reduced Um -graph such that the map α2 : core(Y1 × Y2 ) → Y2
is surjective, core(Y2 ) = Y2 , and r̄(Y2 ) = −χ(Y2 ) > 0.
Note that the equality core(Y2 ) = Y2 could be dropped as it follows from the
surjectivity of the map α2 : core(Y1 × Y2 ) → Y2 .
Lemma 3.2. Suppose Q is a nonempty combination with repetitions of SLI[Y1 ] and
X

q L = −C(Q)xs ,

(3.9)

q∈Q

where C(Q) > 0 is an integer. Then there exists a finite reduced Um -graph Y2,Q
e := inq(V Y2,Q ), one has |Q|
e = |Q| and
with property (B) such that, letting Q
X

qL =

X

qR ≥

q∈Q

q∈Q

X

q L = −2r̄(Y2,Q )xs ,

(3.10)

X

q R = −2r̄(core(Y1 × Y2,Q )).

(3.11)

e
q∈Q

e
q∈Q

Proof. We will construct a graph Y2,Q whose vertices u1 , . . . , u|Q| are in bijective
correspondence
ui 7→ qi ,

i = 1, . . . , |Q|,

with elements of the combination Q = [[q1 , . . . , q|Q| ]] ⊑ SLI[Y1 ].

10

S. V. IVANOV

Recall that every inequality qi in Q has one of the form (3.5)–(3.6). It follows
from the assumption (3.9) that all terms ±xj,D in the sum
|Q|
X

qiL

(3.12)

i=1

will cancel out. Hence, there exists an involution ι on the set of all terms ±xj,D of
the formal sum (3.12) such that ι takes every term ±xj,D of qiL1 to a term ∓xj,D of
qiL2 , where i2 6= i1 , and ι2 = id.
If ι takes the term −xj,D of qiL1 to the term xj,D of qiL2 , then we connect the vertex
ui1 to ui2 by an oriented edge in Y2,Q whose label is aj , aj ∈ A. This definition
determines the local structure of the graph Y2,Q and, in particular, means that if
qi ∈ Q has type (3.5), then ui is a 1-vertex. On the other hand, if qi ∈ Q has
type (3.6), then ui is a 2-vertex. Furthermore, it follows from this definition that
the degree of every vertex ui of Y2,Q is k(qi ) ≥ 2. Recall that k(qi ) denotes the
parameter k for qi , see the definitions (3.5)–(3.6).
Looking at the coefficients of −xs in (3.12), we can see from (3.9) and (3.5)–(3.6)
that
|Q|
X
(k(qi ) − 2) > 0.
C(Q) =
i=1

Hence, the graph Y2,Q has a vertex of degree at least 3.
Therefore, Y2,Q is a finite reduced Um -graph such that core(Y2,Q ) = Y2,Q and
r̄(Y2,Q ) > 0. Note that Y2,Q is not uniquely determined by Q (as there are many
choices to define the involution ι, i.e., to do cancellations in the left hand side of
(3.9)).
Consider the graph core(Y1 × Y2,Q ) and the associated graph maps
α1 : core(Y1 × Y2,Q ) → Y1 ,

α2 : core(Y1 × Y2,Q ) → Y2,Q .

It is clear from the definitions that α2 is surjective, hence, Y2,Q has property (B).
Let ui be a vertex of Y2,Q and let the inequality qi ∈ Q, corresponding to ui , is
constructed by means of an αi -admissible tuple (A1,i , . . . , Am,i ) so that
qiL = (−1)αi xj1,i ,Aj1,i ,i + · · · + (−1)αi xjk(qi ),i ,Ajk(q

i ),i

− (k(qi ) − 2)xs ,

qiR = −Nαi (A1,i , . . . , Am,i ).
It follows from the definitions that, for every possible term ±xj,Aj,i of qiL , where
Aj,i 6= ∅, the set Aj (ui ), as defined in (3.8), contains Aj,i as a subset and, if qiL
has no term ±xj,Aj,i , i.e., Aj,i = ∅, then Aj (ui ) = ∅. These remarks mean that if
e := inq(V Y2,Q ) then |Q|
e = |Q| and Y2,Q = Y e for a suitable involution e
e
Q
ι=e
ι(Q).
2,Q
Hence, if qi has the form (3.5), i.e., αi = 1, then

inqV (ui )L = −xj1,i ,Aj1 (ui ) − . . . − xjk(qi ),i ,Ajk(q

i)

(ui )

− (k(qi ) − 2)xs ,

where Ajt ,i ⊆ Ajt (ui ) for every t = 1, . . . , k(qi ) and
N1 (A1,i , . . . , Am,i ) ≤ N1 (A1 (ui ), . . . , Am (ui )).

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

11

Analogously, if qi has the form (3.6), i.e., αi = 2, then
inqV (ui )L = xj1,i ,Aj1 (ui ) + . . . + xjk(qi ),i ,Ajk(q

i)

(ui )

− (k(qi ) − 2)xs ,

where Ajt ,i ⊆ Ajt (ui ) for every t = 1, . . . , k(qi ) and
N2 (A1,i , . . . , Am,i ) ≤ N2 (A1 (ui ), . . . , Am (ui )).
Therefore,

X

qR =

q∈inq(V Y2,Q )

X

qR ≤

e
q∈Q

X

qR .

q∈Q

Now both the equality (3.10) and inequality (3.11) follow from Lemma 3.1.



We summarize Lemmas 3.1–3.2 as follows.
Lemma 3.3. The function
inq : Y2 7→ inq(V Y2 ) = Q
from the set of finite reduced Um -graphs Y2 with property
P (B) to the set of combinations with repetitions Q of SLI[Y1 ] with the property q∈Q q L = −C(Q)xs , where
C(Q) > 0 is an integer, is such that
X
X
q R = −2r̄(core(Y1 × Y2 )).
q L = −2r̄(Y2 )xs and
q∈inq(V Y2 )

q∈inq(V Y2 )

In addition, for every Q in the codomain of the function inq, there exists a graph
e := inq(V Y2,Q ), one has |Q|
e = |Q|
Y2,Q in the domain of inq such that, letting Q
and
X
X
qL =
q L = −2r̄(Y2,Q )xs ,
q∈Q

X

q∈Q

e
q∈Q

qR ≥

X

q R = −2r̄(core(Y1 × Y2,Q )).

e
q∈Q

Proof. This is straightforward from Lemmas 3.1–3.2.



4. Utilizing the method of linear programming
Let us briefly review relevant results from the theory of linear programming
(LP) over the field Q of rational numbers. Following the notation of Schrijver’s
′
′
′
′
monograph [21], let A ∈ Qm ×n be an m′ × n′ -matrix, let b ∈ Qm ×1 = Qm be
′
a column vector, let c ∈ Q1×n be a row vector, c = (c1 , . . . , cn′ ), and let x be a
column vector consisting of variables x1 , . . . , xn′ , so x = (x1 , . . . , xn′ )⊤ , where M ⊤
means the transpose of a matrix M . The inequality x ≥ 0 means that xi ≥ 0 for
every i.
A typical LP-problem asks about the maximal value of the objective linear function
cx = c1 x1 · · · + cn′ xn′
n′
over all x ∈ Q subject to the system of linear inequalities Ax ≤ b. This value
(and often the LP-problem itself) is denoted
max{cx | Ax ≤ b}.

12

S. V. IVANOV

We write max{cx | Ax ≤ b} = −∞ if the set {cx | Ax ≤ b} is empty. We write
max{cx | Ax ≤ b} = +∞ if the set {cx | Ax ≤ b} is unbounded from above and say
that max{cx | Ax ≤ b} is finite if the set {cx | Ax ≤ b} is nonempty and bounded
from above. The notation and terminology for an LP-problem
min{cx | Ax ≤ b} = − max{−cx | Ax ≤ b}
is analogous with −∞ and +∞ interchanged.
If max{cx | Ax ≤ b} is an LP-problem defined as above, then the problem
min{b⊤ y | A⊤ y = c⊤ , y ≥ 0},
where y = (y1 , . . . , ym′ )⊤ , is called the dual problem of max{cx | Ax ≤ b}.
The (weak) duality theorem of linear programming can now be stated as follows,
see [21, Sections 7.4, 14.3].
Theorem A. Let max{cx | Ax ≤ b} be an LP-problem and let
min{b⊤ y | A⊤ y = c⊤ , y ≥ 0}
′

be its dual LP-problem. Then for every x ∈ Qn such that Ax ≤ b and every
′
y ∈ Qm such that A⊤ y = c⊤ , y ≥ 0, one has that cx = y ⊤ Ax ≤ b⊤ y and
max{cx | Ax ≤ b} = min{b⊤ y | A⊤ y = c⊤ , y ≥ 0}
⊤

(4.1)

⊤

provided both polyhedra {x | Ax ≤ b} and {y | A y = c , y ≥ 0} are not empty. In
addition, the minimum, whenever it is finite, is attained at a vector yV which is a
vertex of the polyhedron {y | A⊤ y = c⊤ , y ≥ 0}.
We now consider the problem of maximizing the objective linear function
cx := −xs
′

over all rational vectors x, x ∈ Qn , for a suitable n′ , subject to the system of
linear inequalities SLI[Y1 ], as an LP-problem max{cx | Ax ≤ b}. Note that, in
this context, m′ = minq and n′ = ninq , where minq is the number of inequalities in
SLI[Y1 ] and ninq is the number of all variables xj,B , xs in SLI[Y1 ].
It is straightforward to verify that the dual problem
min{b⊤ y | A⊤ y = c⊤ , y ≥ 0}
of this LP-problem max{cx | Ax ≤ b} can be equivalently stated as follows
minq

minq

X

yi qiR

→ min

subject to y ≥ 0,

X

yi qiL = −xs .

(4.2)

i=1

i=1

We emphasize that the last equality should be thought of as a formal linear combination on variables xj,B , xs . Note we can write (4.2) in the form

m
minq
inq
X
X
(4.3)
yi qiL = −xs .
yi qiR y ≥ 0,
min
i=1

i=1

In Lemma 3.3, we established the existence of a function
inq : Y2 7→ inq(Y2 ),

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

13

from the set of finite reduced Um -graphs Y2 with property (B) to a certain set of
combinations with repetitions of SLI[Y1 ]. Now we will relate these combinations
with repetitions of SLI[Y1 ] to solutions of the dual LP-problem (4.3).
Consider a combination Q with repetitions of SLI[Y1 ] that has the property that
X
q L = −C(Q)xs ,
(4.4)
q∈Q

where C(Q) > 0 is an integer. As above in (4.2)–(4.3), let all of the inequalities in
SLI[Y1 ] be indexed and
SLI[Y1 ] = {q1 , . . . , qminq }.
Let ηi (Q) ≥ 0 denote the number of times that qi occurs in Q, and let κi be the
coefficient of xs in qi . Then it follows from the definitions and (4.4) that
X

minq

qL =

X

κi ηi (Q)xs = −C(Q)xs .

(4.5)

sol : Q 7→ yQ = (yQ,1 , . . . , yQ,minq )⊤ ,

(4.6)

q∈Q

i=1

Consider the map

ηi (Q)
C(Q)

for i = 1, . . . , minq . It follows from the definitions that yQ is a
where yQ,i :=
rational vector, yQ ≥ 0, and, by (4.5), yQ satisfies the condition that
minq

X

yQ,i qiL = −xs .

i=1

Hence, yQ is a vector in the feasible polyhedron


minq
X
L
yi qi = −xs
y y ≥ 0,

(4.7)

i=1

of the dual LP-problem (4.3).
Note that, in place of (4.6), we could also write
sol : Q 7→ C(Q)−1 η(Q)⊤ ,
−1

where η(Q) = (η1 (Q), . . . , ηminq (Q)), as yQ = C(Q)

(4.8)
⊤

η(Q) .

⊤

Conversely, let z = (z1 , . . . , zminq ) be a vector of the feasible polyhedron (4.7) of
the dual LP-problem (4.3). Let C > 0 be a common multiple of positive denominators of the rational numbers z1 , . . . , zminq . Consider a combination with repetitions
Q(z) of SLI[Y1 ] such that every qi of SLI[Y1 ] occurs in Q(z) exactly Czi = ni many
times. Then it follows from the definitions that
minq
minq
minq
X
X
X
X
zi qiL = −Cxs .
(4.9)
Czi qiL = C
ni qiL =
qL =
q∈Q(z)

Now we can see from

i=1

i=1

i=1

ηi (Q(z))
Czi
=
= zi ,
(4.10)
C
C
where i = 1, . . . , minq , that the vector yQ(z) = sol(Q(z)), defined by (4.6) for Q(z),
is equal to z.

14

S. V. IVANOV

Lemma 4.1. The map
sol : Q 7→ sol(Q) = yQ ,
defined by (4.6), is a surjective function from
P the set of combinations Q with repetitions of SLI[Y1 ] that satisfy the equation q∈Q q L = −C(Q)xs , where C(Q) > 0
is an integer, to the feasible polyhedron (4.7) of the dual LP-problem (4.3). Furthermore, the composition of the maps inq and sol,
sol ◦ inq : Y2 7→ sol(inq(Y2 )) = yY2 ,
is a function from the set of graphs with property (B) toPthe polyhedron (4.7) of
minq
yY2 ,i qiR of the dual
(4.3). Under this map, the value of the objective function i=1
LP-problem (4.3) at yY2 satisfies the equality
minq

X

yY2 ,i qiR = −

i=1

r̄(core(Y1 × Y2 ))
.
r̄(Y2 )

(4.11)

In addition, for every z in the polyhedron (4.7), there is a vector ze in (4.7) such
that ze = sol(inq(Y2 )) for some graph Y2 with property (B) and
minq

minq

X
i=1

zei qiR ≤

X

zi qiR .

(4.12)

i=1

Proof. As was established above, see computations (4.9)–(4.10), sol is a surjective
function.
Consider a finite irreducible Um -graph Y2 with property (B) and define
Q := inq(Y2 ),
By Lemma 3.3, we have
X
q L = −2r̄(Y2 )xs
q∈Q

and

yY2 := sol(Q).
X

q R = −2r̄(core(Y1 × Y2 )).

(4.13)

q∈Q

It follows from (4.5) and (4.13) that C(Q) = 2r̄(Y2 ). Hence, using the definition
(4.6) and equalities (4.13), we obtain
P
minq
R
X
r̄(core(Y1 × Y2 ))
q∈Q q
yY2 ,i qiR =
=−
,
C(Q)
r̄(Y2 )
i=1
as required in (4.11).
To prove the additional statement, consider a vector z in the polyhedron (4.7).
Since sol is surjective, there is a combination with repetitions Q such that sol(Q) =
e
z. By Lemma 3.3 for this Q, there is a graph Y2,Q such that, letting inq(V Y2,Q ) = Q,
e
we have that |Q| = |Q| and
X
X
e s,
qL =
q L = −2r̄(Y2,Q )xs = −C(Q)xs = −C(Q)x
(4.14)
q∈Q

X

q∈Q

e
q∈Q

qR ≥

X

e
q∈Q

q R = −2r̄(core(Y1 × Y2,Q )).

(4.15)

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

e Then, in view of (4.14)–(4.15), we obtain
Let ze := sol(Q).
P
P
minq
minq
R
R
X
X
eq
q∈Q q
q∈Q
R
zi qiR ,
≤
=
zei qi =
e
C(Q)
C(
Q)
i=1
i=1

as required.

15



We will say that a real nonnegative number σ(Y1 ) is the WN-coefficient for the
graph Y1 if
r̄(core(Y1 × Y2 )) ≤ σ(Y1 )r̄(Y1 )r̄(Y2 )
for every finite reduced Um -graph Y2 and σ(Y1 ) is minimal with this property.
Lemma 4.2. The WN-coefficient σ(Y1 ) for the graph Y1 is equal to


r̄(core(Y1 × Y2 ))
sup
r̄(Y1 )r̄(Y2 )
Y2

(4.16)

over all graphs Y2 with property (B).
Proof. Since r̄(Y1 ) > 0 and core(Y1 ) = Y1 , we may use Y2 = Y1 to see that
σ(Y1 ) = sup
Y2

r̄(core(Y1 × Y2 ))
1
r̄(core(Y1 × Y1 ))
≥
≥
>0
r̄(Y1 )r̄(Y2 )
r̄(Y1 )2
r̄(Y1 )

over all finite reduced Um -graph Y2 such that r̄(Y2 ) > 0. We may also assume that
Y2 has no vertices of degree less than 2, i.e., core(Y2 ) = Y2 .
Suppose that a graph Y2 is such that r̄(Y2 ) > 0, core(Y2 ) = Y2 and Y2 does not
satisfy property (B). This means that the projection
α2 : core(Y1 × Y2 ) → Y2
is not surjective. We delete those edges and vertices in Y2 that have no preimages
in core(Y1 × Y2 ) under α2 . As a result, we obtain a subgraph Y2′ of Y2 such that
core(Y1 × Y2′ ) = core(Y1 × Y2 ) and 0 < r̄(Y2′ ) < r̄(Y2 ). Since
r̄(core(Y1 × Y2 ))
r̄(core(Y1 × Y2′ ))
>
,
r̄(Y1 )r̄(Y2′ )
r̄(Y1 )r̄(Y2 )
it follows that the graphs Y2 that do not satisfy property (B) can be disregarded
when taking the supremum (4.16).

Lemma 4.3. Both optima max{−xs | SLI[Y1 ]} and

m
minq
inq
X
X
L
R
yj qj = −xs
yj qj y ≥ 0,
min
j=1

j=1

are finite and satisfy the following equalities
m
inq
X
yi qiR
max{−xs | SLI[Y1 ]} = min
i=1

minq

y ≥ 0,

X
i=1

yi qiL = −xs



(4.17)

= −σ(Y1 )r̄(Y1 ).
Furthermore, the minimum is attained at a vector yeV of the polyhedron (4.7) of the
dual LP-problem (4.3) such that there is a graph Y2,QV with sol(inq(Y2,QV )) = yeV .
1
In addition, m−2
≤ σ(Y1 ) ≤ 1.

16

S. V. IVANOV

Proof. Setting Y2 := Y1 , we obtain a graph Y2 with property (B). Hence, by
Lemma 4.1, yY2 = sol(inq(Y2 )) is a solution to the system
minq

X

y ≥ 0,

yj qjL = −xs ,

j=1

so the feasible polyhedron (4.7) of the dual LP-problem (4.3) is not empty.
To establish that the polyhedron {x | SLI[Y1 ]} is not empty either, we will show
that the vector x
b, whose components are x
bj,B := 0 for all j = 1, . . . , m and for
bs := 2r̄(Y1 ), is a solution to SLI[Y1 ]. To do this, we need to
all B ⊆ Eaj Y1 , and x
check that every inequality (3.5)–(3.6) of SLI[Y1 ] is satisfied with these values of
variables, that is,
−(k − 2) · 2r̄(Y1 ) ≤ −Ni (A1 , . . . , Am )

(4.18)

for every i-admissible tuple (A1 , . . . , Am ) in which exactly k sets, among A1 , . . . , Am ,
are nonempty.
It follows from the definition (3.3) of Ni (A1 , . . . , Am ) that Ni (A1 , . . . , Am ) = 0
if k = 2. Hence, if k = 2 then the inequality (4.18) is true. Since k ≥ 2, we may
assume that k > 2. Then, according to (3.4), Ni (A1 , . . . , Am ) ≤ 2r̄(Y1 ) and the
inequality (4.18) is true again.
Hence, both polyhedra


minq
X
yi qiL = −xs
{x | SLI[Y1 ]},
y y ≥ 0,
i=1

are not empty, as required.
According to Theorem A, the maximum and minimum in (4.17) are finite and
equal. Referring to Theorem A again, we obtain that the minimum in (4.17) is
attained at a vertex yV of the polyhedron (4.7).
It follows from Lemma 4.1 that, for the vertex yV , there is a vector yeV in the
polyhedron (4.7) such that
minq

minq

X
i=1

yeV,i qiR

≤

X

yV,i qiR

i=1

and yeV = sol(inq(Y2,QV )) for some graph Y2,QV with property (B). Hence, the
minimum in (4.17) is also attained at yeV .
r̄(core(Y1 × Y2 ))
By Lemma 4.1, for every graph Y2 with property (B), the ratio −
r̄(Y2 )
is equal to
minq
X
yY2 ,i qiR ,
i=1

where yY2 = sol(inq(Y2 )).
On the other hand, it follows from Lemma 4.2 that




−r̄(core(Y1 × Y2 ))
r̄(core(Y1 × Y2 ))
= − inf
σ(Y1 )r̄(Y1 ) = sup
Y2
r̄(Y2 )
r̄(Y2 )
Y2
over all graphs Y2 with property (B).

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

Therefore, putting together these facts, we obtain


−r̄(core(Y1 × Y2 ))
−σ(Y1 )r̄(Y1 ) = inf
Y2
r̄(Y2 )

m
minq
inq
X
X
L
R
yi qi = −xs
yi qi y ≥ 0,
= inf
Y2

= min

i=1
minq

i=1

m
inq
X

yi qiR

y ≥ 0,

X

yi qiL = −xs

i=1

i=1

17



minq

=

X
i=1

yeV,i qiR = max{−xs | SLI[Y1 ]},

as desired in (4.17). The equalities (4.17) are proven.
1
It remains to show that m−2
≤ σ(Y1 ) ≤ 1. The inequality σ(Y1 ) ≤ 1 follows
from the fact that the strengthened Hanna Neumann conjecture is true, see [7],
[17], [3], [13].
Let Y2 := Um . Then
r̄(Y2 ) = m − 2 and r̄(core(Y1 × Y2 )) = r̄(Y1 )
because Y1 × Y2 = Y1 . Hence,
σ(Y1 ) ≥

1
r̄(core(Y1 × Y2 ))
=
,
r̄(Y1 )r̄(Y2 )
m−2

as required.



Lemma 4.4. There exists a finite reduced Um -graph Y2,QV such that Y2,QV has
property (B),
r̄(core(Y1 × Y2,QV )) = σ(Y1 )r̄(Y1 )r̄(Y2,QV ),
Y2,QV is connected, and
|EY1 |/2+2 log2 m

|EY2,QV | < 22

.

Proof. According to Lemma 4.3 and to Theorem A, we may assume that the minimum of the dual LP-problem (4.3) is attained at a vertex yV , yV ≥ 0, of the feasible
polyhedron (4.7) of the LP-problem (4.3).
Since yV is a vertex solution of the LP-problem (4.3) and (4.3) is stated in the
form min{b⊤ y | A⊤ y = c⊤ , y ≥ 0}, where Ax ≤ b is a matrix form of the system
(3.7), it follows that the vertex solution yV will satisfy minq equalities among
A⊤ y = c⊤ ,

yi = 0,

i = 1, . . . , minq ,

whose left hand side parts are linearly independent (as formal linear combinations
in variables y1 , . . . , yminq ). We will call these minq inequalities distinguished.
The foregoing observation implies that there are r, r ≤ minq , distinguished
⊤
equalities in the system A⊤ y = c⊤ such that the submatrix A⊤
r of A , consisting of
⊤
the rows of A that correspond to the r distinguished equalities, has the following
⊤
property. The rank of A⊤
r is r and deletion of the columns of Ar , that correspond
to the variables yi that in turn correspond to the distinguished equalities yi = 0,
⊤
produces an r × r matrix A⊤
r×r with det Ar×r 6= 0. Reordering the equalities in the

18

S. V. IVANOV

system A⊤ y = c⊤ and variables yi if necessary, we may assume that A⊤
r consists of
⊤
the first r rows of A⊤ and A⊤
is
an
upper
left
submatrix
of
A
.
r×r
Let
ȳV = (yV,1 , . . . , yV,r )
be the truncated version of yV consisting of the first r components. It follows from
the definitions that ȳV contains all nonzero components of yV and
Pminq

⊤
⊤
A⊤
r×r ȳV = c̄ = (c1 , . . . , cr ) .

Since i=1 yV,i qiL = −xs , it follows that cj = 0 if cj corresponds to a variable
xℓ,B and cj = −1 if cj corresponds to the variable xs . Since yV 6= 0 following from
the definition of the LP-problem (4.3), we conclude that c̄⊤ 6= 0, i.e., one of cj is
−1 and all other entries in c̄⊤ are equal to 0. Since every entry of Ar×r is 0 or
±1 or −(k − 2), where 2 ≤ k ≤ m, and since every row of Ar×r contains at most
m + 1 nonzero entries, at most one of which is different from ±1, see the definitions
(3.5)–(3.6), it follows that the standard Euclidian norm of any row of Ar×r is at
most
(m + (m − 2)2 )1/2 < m
as m ≥ 3. Hence, by the Hadamard’s inequality, we obtain
| det Ar×r | < mr .

(4.19)

Invoking the Cramer’s rule, we further get that
yV,i =

⊤
det A⊤
r×r,i (c̄ )
,
det Ar×r

(4.20)

⊤
⊤
where A⊤
r×r,i (c̄ ) is the matrix obtained from Ar×r by replacing the ith column
⊤
with c̄ , i = 1, . . . , r. Similarly to (4.19), we have that

| det Ar×r,i (c̄⊤ )| < mr .

(4.21)

In view of (4.19)–(4.21), we can see that there is a common denominator C > 0
for the rational numbers yV,1 , . . . , yV,r that satisfies C < mr and that the nonnegative integers CyV,1 , . . . , CyV,r are less than mr .
It follows from the definition (4.6) of the function sol, see also Lemma 4.1 and
(4.9)–(4.10), that if QV is a combination such that yV = sol(QV ) and |QV | is
minimal with this property, i.e., the entries of η(QV ) are coprime, then
|QV | < rmr .

(4.22)

Recall that the cardinality |Q| of a combination Q is defined so that every q ∈ Q is
counted as many times as it occurs in Q.
We now construct a graph Y2,QV from QV as described in the proof of Lemma 3.2.
It follows from the definitions and Lemmas 4.1, 4.3 that if
yeV := sol(inq(V Y2,QV ))

then the minimum of the dual LP-problem (4.3) is also attained at yeV and this
minimum is equal to −σ(Y1 )r̄(Y1 ). Hence,
r̄(core(Y1 × Y2,QV )) = σ(Y1 )r̄(Y1 )r̄(Y2,QV ).

Since |V Y2,QV | = |QV |, we have from (4.22) that
|EY2,QV | ≤ m|V Y2,QV | = m|QV | < rmr+1 .

(4.23)

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

19

Note that r does not exceed the total number ninq of variables xj,B , xs of SLI[Y1 ].
It is clear that |Eaj Y1 | ≤ |EY1 |/2 for every j = 1, . . . , m. Hence, the number of
variables xj,B for a fixed j is at most 2|EY1 |/2 − 1. Therefore,
r ≤ ninq ≤ m(2|EY1 |/2 − 1) + 1 ≤ m · 2|EY1 |/2 − 2.

(4.24)

Finally, we obtain from (4.23)–(4.24) that
|EY1 |/2
−1

|EY2,QV | < rmr+1 ≤ (m · 2|EY1 |/2 − 2)mm·2
|EY1 |/2

< 2|EY1 |/2 mm·2

|EY1 |/2

≤ 2|EY1 |/2+(log2 m)·m·2

|EY1 |/2

< 2(1+m·log2 m)·2
< 2m

2

(4.25)

·2|EY1 |/2

|EY1 |/2+2 log2 m

≤ 22

.

It remains to show that the graph Y2,QV is connected.
Arguing on the contrary, assume that the graph Y2,QV is the disjoint union of
its two subgraphs Y3 and Y4 . First we assume that
r̄(Y3 ) > 0

and r̄(Y4 ) > 0.

(4.26)

Clearly, Y3 and Y4 are graphs with property (B). Recall that the vertices of the
graph Y2,QV bijectively correspond to the inequalities of the combination QV , see
the proof of Lemma 3.2. In particular, we can consider the combinations Q3 and
Q4 , whose inequalities bijectively correspond to the vertices of Y3 and Y4 , resp. It
is clear that QV is the union of combinations Q3 and Q4 and
η(QV ) = η(Q3 ) + η(Q4 ).

(4.27)

We specify that the union B1 ⊔ B2 of two combinations B1 , B2 is the combination
whose elements are all elements of both B1 and B2 , in particular, |B1 ⊔ B2 | =
|B1 | + |B2 |.
Furthermore, the graphs Y3 and Y4 could be constructed from Q3 and Q4 , resp.,
in the same manner as Y2,QV was constructed from QV . In particular, the combinations Q3 and Q4 belong to the domain of the function sol.
Invoking Lemma 4.1, denote yV (j) := sol(Qj ), j = 3, 4. We also denote
X
X
q L = −C(Qj )xs ,
q L = −C(QV )xs ,
q∈Qj

q∈QV

where j = 3, 4.
Since QV = Q3 ⊔ Q4 , it follows that C(QV ) = C(Q3 ) + C(Q4 ). According to the
definition (4.6) of the function sol, we have
yV,i =

ηi (QV )
,
C(QV )

yV,i (j) =

ηi (Qj )
C(Qj )

(4.28)

20

S. V. IVANOV

for all suitable i, j. Hence, in view of (4.27), for every i = 1, . . . , minq , we obtain
ηi (Q3 ) + ηi (Q4 )
ηi (QV )
=
C(QV )
C(QV )
C(Q4 ) ηi (Q4 )
C(Q3 ) ηi (Q3 )
·
+
·
=
C(QV ) C(Q3 ) C(QV ) C(Q4 )
= λ3 yV,i (3) + λ4 yV,i (4),

yV,i =

(4.29)

C(Q3 )
C(Q4 )
where λ3 = C(Q
and λ4 = C(Q
are positive rational numbers that satisfy
V)
V)
λ3 + λ4 = 1.
The equalities (4.29) imply that

yV = λ3 yV (3) + λ4 yV (4).

(4.30)

Since yV is a vertex of the polyhedron (4.7), yV (3) and yV (4) are vectors in (4.7),
and 0 < λ3 , λ4 < 1, λ3 + λ4 = 1, it follows from (4.30) that
yV (3) = yV (4) = yV .
Hence, in view of (4.28), the tuples η(QV ), η(Q3 ), η(Q4 ) that have integer entries
are rational multiples of each other. Referring to (4.27), we conclude that the
entries of η(QV ) are not coprime, contrary to the definition of the combination QV .
This contradiction completes the case (4.26).
Assume that the graph Y2,QV is the disjoint union of its two subgraphs Y3 and
Y4 such that
r̄(Y3 ) > 0 and r̄(Y4 ) = 0.
(4.31)
Let 2QV denote the combination such that η(2QV ) = 2η(QV ), i.e., to get 2QV
from QV we double the number of occurrences of each inequality in QV . Using
this combination 2QV , we can construct, as in the proof of Lemma 3.2, a graph
Y2,2QV which consists of two disjoint copies of Y2,QV , denoted Ȳ2,QV and Yb2,QV .
Since Y2,QV = Y3 ∪ Y4 , we can represent the graph Y2,2QV in the form
Y2,2QV = Y5 ∪ Y6 ,
where Y5 := Ȳ3 ∪ Ȳ4 ∪ Yb4 and Y6 := Yb3
Clearly, r̄(Y5 ) > 0, r̄(Y6 ) > 0, and both Y5 , Y6 have property (B). As above,
we remark that the vertices of Y2,2QV are in bijective correspondence with the
inequalities of 2QV . Hence, the combination 2QV is the union of the combinations
Q5 and Q6 that consist of those inequalities that correspond to the vertices of Y5
and Y6 , resp., and that can be used to construct the graphs Y5 and Y6 in the same
manner as Y2,QV was constructed from QV .
As above, we can write
η(2QV ) = η(Q5 ) + η(Q6 ).

(4.32)

Note that the combinations Q5 and Q6 belong to the domain of the function sol.
Using Lemma 4.1, denote yV (j) := sol(Qj ), j = 5, 6. As above, denote
X
X
q L = −C(2QV )xs ,
q L = −C(Qj )xs ,
q∈2QV

where j = 5, 6.

q∈Qj

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

21

Since 2QV = Q5 ⊔ Q6 , it follows that C(2QV ) = C(Q5 ) + C(Q6 ). According to
the definition (4.6) of the function sol, we have
yV,i =

ηi (QV )
ηi (2QV )
=
,
C(QV )
C(2QV )

yV,i (j) =

ηi (Qj )
C(Qj )

(4.33)

for all suitable i, j. Hence, in view of (4.32), for every i = 1, . . . , minq , we obtain
ηi (Q5 ) + ηi (Q6 )
ηi (2QV )
=
C(2QV )
C(2QV )
C(Q6 ) ηi (Q6 )
C(Q5 ) ηi (Q5 )
·
+
·
=
C(2QV ) C(Q5 ) C(2QV ) C(Q6 )
= λ5 yV,i (5) + λ6 yV,i (6),

yV,i =

(4.34)

C(Q5 )
C(Q6 )
where λ5 = C(2Q
and λ6 = C(2Q
are positive rational numbers that satisfy
V)
V)
λ5 + λ6 = 1.
The equalities (4.34) imply that

yV = λ5 yV (5) + λ6 yV (6).

(4.35)

Since yV is a vertex of the polyhedron (4.7), yV (5) and yV (6) are vectors in (4.7),
and 0 < λ5 , λ6 < 1, λ5 + λ6 = 1, it follows from (4.35) that
yV (5) = yV (6) = yV .
Hence, in view of (4.33), the tuples η(2QV ), η(Q5 ), η(Q6 ) that have integer entries
are rational multiples of each other. Referring to (4.32) and keeping in mind that
the entries of η(QV ) are coprime, we conclude that
η(QV ) = η(Q5 ) = η(Q6 ),

(4.36)

i.e., QV = Q5 = Q6 . However, Y6 = Yb3 and Yb3 is a subgraph of Yb2,QV that consists
of several connected components of Yb2,QV and Y3 6= Y2,QV . Hence, Q5 6= QV . This
contradiction to (4.36) completes the second case (4.31). Thus the graph Y2,QV is
connected and Lemma 4.4 is proven.

5. Proofs of Theorems 1.1 and 1.2
Proof of Theorem 1.1. (a) Suppose that H1 is a finitely generated noncyclic subgroup of the free group FUm = π1 (Um , o1 ) of rank m − 1 ≥ 2. Conjugating H1 if
necessary, we may assume that the reduced Um -graph of H1 , denoted as above by
Y1 , coincides with its core, core(Y1 ) = Y1 .
As in Section 3, see (3.7), consider a system of linear inequalities SLI[Y1 ] with
integer coefficients associated with the graph Y1 = Y1 (H1 ) and the LP-problem
max{−xs | SLI[Y1 ]}.

(5.1)

According to Theorem A and Lemma 4.3, the maximum of the LP-problem (5.1)
is equal to −σ(Y1 )r̄(Y1 ), as required.
(b) This part follows from the definitions and Lemmas 4.2–4.4 applied to the
graph Y1 of H1 .
(c) It follows from the definitions of Section 3 that we can algorithmically write
down the system SLI[Y1 ] and this can be done in exponential time in the size of Y1 .
Note that the size of the graph Y1 is polynomial in the size of the input (which is a
generating set for H1 or the graph Y1 itself). It follows from the bound (4.24) and

22

S. V. IVANOV

from the definitions that the number ninq of variables of SLI[Y1 ] and the number
minq of inequalities of SLI[Y1 ] satisfy
ninq ≤ m(2|EY1 |/2 − 1) + 1 < m2|EY1 |/2 ,
minq < 2 · 2|Ea1 Y1 |+···+|Eam Y1 | = 2|EY1 |/2+1 .
Furthermore, every number in SLI[Y1 ] is an integer whose absolute value is
bounded by max(m−2, 2r̄(Y1 )), see (3.4). Hence, the size of the primal LP-problem
max{−xs | SLI[Y1 ]} as well as the size of the dual problem (4.3) are exponential
in the size of the input. By Lemma 4.3, the optimal solution to the dual problem
(4.3) is equal to
−σ(Y1 )r̄(Y1 ) = −σ(H1 )r̄(H1 ).
Since an LP-problem max{cx | Ax ≤ b} can be solved in deterministic polynomial
time in the size of the problem, see [21], and since the reduced rank r̄(Y1 ) = r̄(H1 )
can be computed in polynomial time in the size of the input, it follows that the
WN-coefficient σ(H1 ) of H1 can be computed in exponential time (in the size of
the input).
We recall again that the size of the dual LP-problem (4.3), similarly to the size of
the primal LP-problem max{−xs | SLI[Y1 ]}, is exponential . Next, a vertex solution
yV to the LP-problem (4.3) can be computed in polynomial time in the size of (4.3),
see [21]. Note that here and below we use the notation of the proof of Lemma 4.4.
Hence, a vertex solution yV to (4.3) can be computed in exponential time in the
size of Y1 . Using the function sol, we can compute a combination with repetitions
QV , such that sol(QV ) = yV and entries of QV are coprime, in polynomial time
in the size of yV . The size of the vertex yV , as was established in the proof of
Lemma 4.4, see (4.19)–(4.21), (4.24), is exponential. Hence, the combination QV
can also be computed in exponential time.
In view of inequalities (4.22) and (4.25), we obtain that
|EY1 |/2+2 log2 m

|QV | < rmr < 22

.

(5.2)

This bound, in particular, means that every inequality q ∈ SLI[Y1 ] occurs in QV
|EY1 |/2+2 log2 m
at most 22
times, hence, the number nQV (q) of occurrences of q in QV
can be written by using at most 2|EY1 |/2+2 log2 m bits.
As in the proofs of Lemmas 3.2, 4.4, we construct a graph Y2,QV whose vertices
are in bijective correspondence with inequalities of QV and whose edges are defined
by means of an involution ιV on the set of terms ±xj,D of left hand sides q L of the
inequalities q ∈ QV .
Lemma 5.1. The graph Y2,QV can be constructed in deterministic exponential time
in the size of Y1 .
Proof. We need to explain how to compute the involution ιV as above in exponential
time (in the size of Y1 ). To do this, for each variable xj,D of the system SLI[Y1 ],
see (3.7), we consider a graph Λj,D whose set of vertices is the subset
RV := {q | q ∈ QV }
of SLI[Y1 ] formed with the inequalities of QV . If q1 , q2 ∈ RV are distinct, q1L
contains a term ±xj,D and q2L contains a term ∓xj,D , resp., then we draw an edge
e in Λj,D that connects q1 and q2 . In other words, if there is a potential cancellation

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

23

between terms ±xj,D in the sum q1L + q2L then Λj,D contains an edge that connects
q1 and q2 .
It is clear that Λj,D is a bipartite graph so that every edge connects a vertex of
type (3.5) and a vertex of type (3.6).
Consider a weight function
ωj,D : EΛj,D → Z,

(5.3)

where Z is the set of integers, such that ωj,D (e−1 ) = ωj,D (e) ≥ 0 and
X
ωj,D (e) = nQV (q),
e− =q

where nQV (q) is the number of occurrences of q in QV .
Our nearest goal is to show that such a weight function ωj,D can be computed
in exponential time for every pair of indices j, D. Note that nQV (q) = ηi (QV ) if
q = qi in the notation of (4.8).
Let the edge set
−1
−1
EΛj,D = {e1 , e−1
1 , e2 , e2 , . . . , e|EΛj,D |/2 , e|EΛj,D |/2 }

of the graph Λj,D be indexed as indicated and let (ei )− be a vertex of type (3.5)
for every i.
We will define the numbers ωj,D (ei ) by induction for i = 1, 2, . . . , |EΛj,D |/2 by
the following procedure which also assigns intermediate weights ωj,D (q) to vertices
q ∈ RV of Λj,D .
Originally, we set
ωj,D (q) := nQV (q)
for every q ∈ RV . For each i ≥ 1, if the edge ei goes from q1 to q2 then we set
ωj,D (ei ) := min(ωj,D (q1 ), ωj,D (q2 ))
and redefine the weights of q1 and q2 by setting
′
ωj,D
(q1 ) := ωj,D (q1 ) − min(ωj,D (q1 ), ωj,D (q2 )),
′
ωj,D
(q2 ) := ωj,D (q2 ) − min(ωj,D (q1 ), ωj,D (q2 )),
′
where ωj,D
(q1 ) denotes the new weight.
Note that the assignment of a nonnegative weight ωj,D (ei ) to the edge ei , connecting q1 and q2 , can be interpreted as making ωj,D (ei ) cancellations between
terms ±xj,D of the subsums

q1L + · · · + q1L
{z
}
|
nQV (q1 ) times

and

q2L + · · · + q2L
{z
}
|
nQV (q2 ) times

of the sum in the left hand side of the equality
X
q L = −2r̄(Y1 )xs .

(5.4)

q∈QV

Analogously, the intermediate weight ωj,D (q1 ) of a vertex q1 ∈ V Λj,D can be
interpreted as the number of terms ±xj,D of the subsum
q1L + · · · + q1L
{z
}
|
nQV (q1 ) times

24

S. V. IVANOV

which are still uncancelled in the left hand side of (5.4).
Therefore, in view of the equality (5.4), in the end of this process, we will obtain
that the weights ωj,D (q) of all vertices q ∈ RV are zeros, i.e., cancellations of the
terms ±xj,D are complete, and the weights ωj,D (ei ) of all edges ei have desired
properties.
It is clear that the foregoing inductive procedure makes it possible to compute
such a weight function ωj,D in polynomial time in the size of the graph Λj,D and
in the size of numbers nQV (q), q ∈ RV , written in binary. Hence, we can compute
weight functions ωj,D for all pairs j, D in exponential time in the size of Y1 .
Now we will define the involution ιV based on the weight functions ωj,D .
Let elements of the set RV = {q1 , . . . , q|RV | } be indexed as indicated and let
elements of the combination
QV = [[q1,1 , q1,2 , . . . , q1,nQV (q1 ) ,
q2,1 , q2,2 , . . . , q2,nQV (q2 ) ,
...,

(5.5)

q|RV |,1 , q|RV |,2 , . . . , q|RV |,nQV (q|RV | ) ]],
where qi,ℓ = qi ∈ RV for all possible i, ℓ, be double indexed as indicated according
to the indices introduced on elements of RV .
Since the vertices of the graph Y2,QV are in bijective correspondence with elements of QV , see the proof of Lemma 3.2, we can also write
V Y2,QV = {ui,ℓ | 1 ≤ i ≤ |RV |, 1 ≤ ℓ ≤ nQV (qi )},
where
ui,ℓ 7→ qi,ℓ

(5.6)

under this correspondence.
Let qi ∈ RV be fixed and let
qm1 (i) , . . . , qmti (i)
be all the vertices of Λj,D , where m1 (i) < · · · < mti (i), that are connected to qi by
edges f1 , . . . , fti , resp., in Λj,D with positive weights ωj,D (f1 ), . . . , ωj,D (fti ), resp.
We assume that qi is the terminal vertex of the edges f1 , . . . , fti .
Recall that qiL contains a single term ±xj,D , where the sign is a minus if qi has
type (3.5) and the sign is a plus if qi has type (3.6).
According to the weights ωj,D (f1 ), . . . , ωj,D (fti ), we will define (j, D, i, t)-blocks
of consecutive elements of QV , see (5.5), in the following manner. The (j, D, i, 1)block consists of the first ωj,D (f1 ) elements of the sequence
qi,1 , qi,2 , . . . , qi,nQV (qi ) .

(5.7)

The (j, D, i, 2)-block consists of the next ωj,D (f2 ) elements of the sequence (5.7) and
so on. The (j, D, i, ti )-block consists of the last ωj,D (fti ) elements of the sequence
(5.7). Since
ti
X
ωj,D (ft ) = nQV (qi ),
t=1

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

25

and ωj,D (ft ) > 0 for every t, it follows that these (j, D, i, t)-blocks, where t =
1, . . . , ti and j, D, i are fixed, will form a partition of the sequence (5.7) into ti
subsequences.
We emphasize that every (j, D, i, t)-block is associated with a vertex qi ∈ V Λj,D =
RV and with an edge ft of Λj,D so that ft ends in qi and ωj,D (ft ) > 0. In particular,
for every (j, D, i, t)-block, associated with a vertex qi ∈ RV and with an edge ft
of Λj,D , we have another (j, D, i′ , t′ )-block, associated with a vertex qi′ ∈ RV and
with an edge ft′′ of Λj,D , so that qi′ 6= qi and ft′′ = ft−1 . Here f1′ , . . . , ft′′ ′ are the
i
edges of Λj,D defined for qi′ in the same fashion as the edges f1 , . . . , fti of Λj,D
were defined for qi . Note that i′′ = i and ft′′′′ = ft in this notation.
We define the involution ιV so that all the terms ±xj,D of the inequalities of
the (j, D, i, t)-block are mapped by ιV to the terms ∓xj,D of the inequalities of the
(j, D, i′ , t′ )-block in the natural increasing order of elements in the block.
Equivalently, we can say that the vertices
ui,ωj,D (f1 )+···+ωj,D (ft−1 )+1 ,
ui,ωj,D (f1 )+···+ωj,D (ft−1 )+2 ,

...,

ui,ωj,D (f1 )+···+ωj,D (ft ) ,
that correspond to ωj,D (ft ) inequalities of the (j, D, i, t)-block, see (5.6), are connected in Y2,QV to the vertices
ui′ ,ωj,D (f1′ )+···+ωj,D (f ′′

)+1 ,

ui′ ,ωj,D (f1′ )+···+ωj,D (f ′′

)+2 ,

t −1
t −1

...,

ui′ ,ωj,D (f1′ )+···+ωj,D (f ′′ ) ,
t

resp., that correspond to ωj,D (ft′′ ) inequalities of the (j, D, i′ , t′ )-block, by edges
whose labels are aj if qi has type (3.5) or by edges whose labels are a−1
if qi has
j
type (3.6) (here we assume that the edges start at ui,ℓ vertices). It is clear that
the foregoing construction of the involution ιV can be done in exponential time.
Therefore, the graph Y2,QV can also be constructed in exponential time, as required.
Lemma 5.1 is proved.

Since the graph Y2,QV can be constructed in exponential time, it follows from
Lemma 4.4 that we can output Y2,QV as the Stallings graph of the desired subgroup
H2∗ of part (b) of Theorem 1.1. The proof of Theorem 1.1 is now complete.

It is worthwhile to mention that our construction of the graph Y2,QV is somewhat
succinct (cf. the definition of succinct representations of graphs in [21]) in the sense
that, despite the fact that the size of Y2,QV could be doubly exponential, we are able
to give a description of Y2,QV in exponential time (in the size of Y1 ). In particular,
the vertices of Y2,QV are represented by exponentially long bit strings and the
edges of Y2,QV are drawn in blocks. As a result, we can find out in exponential
time whether two given vertices of Y2,QV are connected by an edge labelled by given
letter a±1
j , aj ∈ A.
Proof of Theorem 1.2. (a) This is immediate from part (c) of Theorem 1.1.
(b) Suppose that a finitely generated subgroup H of the free group F = π1 (Um , o1 )
is not compressed and K is a subgroup of F such that K contains H and K has

26

S. V. IVANOV

a minimal reduced rank r̄(K) such that r̄(K) < r̄(H). Let Y and Z be reduced
Um -graphs of H and K, resp.
Since K contains H, it follows that there is a locally injective map
µ : Y → Z.

(5.8)

Suppose that µ is not surjective. Then there is a subgroup K ′ of F , whose graph
is µ(Y ), such that K ′ contains H, K ′ is a free factor of K and r̄(K ′ ) < r̄(K). This
inequality, however, contradicts the minimality of r̄(K). Hence, the map µ must be
surjective. This means that the graph Z with
r̄(Z) = r̄(K) < r̄(H) = r̄(Y )
can be obtained from the graph Y by a finite sequence of operations each of which
is identification of two edges whose images are equal in Z, i.e., the map (5.8) can
be factored into a product of maps that go through a finite sequence of graphs (not
necessarily reduced) each of which is obtained from the previous one by identification of a pair of edges with the same ϕ-label. Note that the edges of such pairs
need not have the same initial or terminal vertices.
Therefore, our nondeterministic polynomial time algorithm that verifies whether
H is not compressed in F can be run as follows. Starting with the reduced graph Y
of H, we nondeterministically perform a finite sequence of identification of pairs of
edges in Y with the same ϕ-label and, if the resulting Um -graph Z is reduced and
satisfies r̄(Z) < r̄(Y ), we accept and conclude that H is not compressed. Since each
single edge identification decreases the number of edges, it follows that the algorithm
runs in nondeterministic linear time in the size of Y , as required. Theorem 1.2 is
proven.

In conclusion, we mention that it would be of interest tonextend our
o techniques
r̄(H∩K)
to be able to compute the Hanna Heumann coefficient supK r̄(H)r̄(K) of a finitely
generated noncyclic subgroup H of a free group F and to algorithmically decide
whether H is inert. However, it is not clear at all how to replace in our arguments the core of the pullback by its single connected component or, alternatively,
guarantee, at least in certain situations, that the entire pullback is connected.
Acknowledgements. The author is grateful to the referee for making many helpful
remarks and suggestions.
References
[1]
[2]
[3]
[4]
[5]
[6]

S. Arora and B. Barak, Computational complexity – a modern approach, Cambridge Univ.
Press, 2009.
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 and E. Ventura, The group fixed by a family of injective endomorphisms of a free
group, Contemp. Math. 195(1996), 1–81.
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.

INTERSECTING SUBGROUPS IN FREE GROUPS AND LINEAR PROGRAMMING

[7]

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

27

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. Haken, Theorie der Normalflächen, Acta Math. 105(1961), 245–375.
J. Hass, J. C. Lagarias and N. Pippenger, The computational complexity of knot and link
problems, J. Assoc. Comput. Mach. 46(1999), 185–211.
G. Hemion, The classification of knots and 3-dimensional spaces, Oxford Univ. Press, 1993.
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, The computational complexity of basic decision problems in 3-dimensional
topology, Geom. Dedicata 131(2008), 1–26.
S. V. Ivanov, Intersecting free subgroups in free products of left ordered groups, preprint,
arXiv:1607.03010 [].
S. V. Ivanov, Linear programming and the intersection of free subgroups in free products of
groups, preprint, arXiv:1607.03052 [].
W. H. Jaco and J. L. Tollefson, Algorithms for the complete decomposition of a closed
3-manifold, Illinois J. Math. 39(1995), 358–406.
I. Kapovich and A. G. Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra
248(2002), 608–668.
I. Mineyev, Submultiplicativity and the Hanna Neumann conjecture, Ann. Math. 175(2012),
393–414.
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.
C. H. Papadimitriou, Computational complexity, Addison-Wesley Publ., 1994.
A. Schrijver, Theory of linear and integer programming, John Wiley & Sons, 1986.
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

