# On the intersections of finitely generated subgroups of free groups: reduced
rank to full rank

Marco Linton  Mathematics institute, Zeeman building, university of Warwick,
Coventry, CV4 7AL<EMAIL_ADDRESS>
###### Abstract.

We show that the number of conjugacy classes of intersections $A\cap B^{g}$,
for fixed finitely generated subgroups $A,B<F$ of a free group, is bounded
above in terms of the ranks of $A$ and $B$; this confirms an intuition of
Walter Neumann. This result was previously known only in the case where $A$ or
$B$ is cyclic by the $w$-cycles theorem of Helfer and Wise and, independently,
Louder and Wilton. In order to prove our main theorem, we introduce new
results regarding the structure of fibre products of finite graphs. We work
with a generalised definition of graph immersions so that our results apply to
the theory of regular languages. For example, we give a new algorithm to
decide non-emptiness of the intersection of two regular languages.

##  1\. Introduction

Given two combinatorial graph maps $\gamma:\Gamma\to\Delta$ and
$\lambda:\Lambda\to\Delta$, we here study their fibre product
$\Gamma\times_{\Delta}\Lambda$. This explicitly constructed graph is the
pullback in the category of combinatorial graphs. There are two main contexts
in which this graph arises: free groups [26] and regular languages [24]. In
the context of free groups, the topological structure of
$\Gamma\times_{\Delta}\Lambda$ was intensely investigated in the lead up to
the resolution of the strengthened Hanna Neuman conjecture (see in particular
[26, 23, 27, 5, 16]). In the context of regular languages, the topological and
combinatorial structure of $\Gamma\times_{\Delta}\Lambda$ has been studied
with applications to free monoids (see [25, 9]) and to the state complexity of
minimal automata (see [1, 10]). Here we give new results on the structure of
the fibre product graph and provide applications in both contexts.

Our first result deals with the simpler case when $\Lambda\cong\sqcup S^{1}$.
A cycle $\lambda:S^{1}\to\Delta$ is _primitive_ if it does not factor properly
through any other cycle $S^{1}\to\Delta$. The _degree_ $\deg(\lambda)$ will be
the largest degree of a covering map $S^{1}\to S^{1}$ that $\lambda$ factors
through. Recall that if $X$ is a topological space, then $\beta_{i}(X)$ is the
_$i^{\text{th}}$ Betti number_ of $X$. In [11] and [19] it was shown that if
$\gamma:\Gamma\to\Lambda$ is an immersion and $\lambda:S^{1}\to\Delta$ is
primitive, then $\operatorname{Core}(\Gamma\times_{\Delta}S^{1})$ consists of
at most $\beta_{1}(\Gamma)$ components. This improved upon other bounds given
in [30] and resolved the $w$-cycles conjecture, first stated in [29]. If we
allow $\lambda$ to be imprimitive, then we would have at most
$\beta_{1}(\Gamma)$ distinct free homotopy classes of cycles instead. Allowing
$\lambda$ to also consist of arbitrarily many cycles, we prove the following
result.

Let $\gamma:\Gamma\to\Delta$ and $\lambda:\mathbb{S}\to\Delta$ be graph
immersions with $\mathbb{S}=\sqcup S^{1}$. If $\lambda|_{S^{1}}$ is primitive
for each $S^{1}\subset\mathbb{S}$, then there are at most $\beta_{1}(\Gamma)$
many components
$S^{1}\subset\operatorname{Core}(\Gamma\times_{\Delta}\mathbb{S})$ such that:

$\deg(p_{\mathbb{S}}|_{S^{1}})\geq 12\cdot\beta_{1}(\Gamma),$

where $p_{\mathbb{S}}:\Gamma\times_{\Delta}\mathbb{S}\to\mathbb{S}$ is the
natural projection map.

From this theorem it follows that there is a unique map
$s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ where $\mathbb{S}_{\Gamma}$ consists
of a disjoint union of at most $\beta_{1}(\Gamma)$ circles, such that, if
$f:S^{1}\to\Gamma$ is a primitive cycle satisfying $\deg(\gamma\circ f)\geq
12\cdot\beta_{1}(\Gamma)$, then $f$ factors through $s_{\Gamma}$. In Theorem
7.2 we give an efficient algorithm to compute the map $s_{\Gamma}$. Theorems
4.20 and 7.2 are the culmination of several results proved in Section 4 on the
full fibre product $\Gamma\times_{\Delta}S^{1}$. For example, we prove bounds
on the number and the sizes of components of $\Gamma\times_{\Delta}S^{1}$,
even when $\gamma$ is not necessarily an immersion.

In Section 5 we allow $\Lambda$ to be an arbitrary finite graph. As pointed
out in [6] there is a precise multiplicative relation between the sizes of the
edge sets of $\Gamma$ and $\Lambda$ and that of their fibre product. If
$\Gamma$ and $\Lambda$ represent regular languages or subgroups of a free
group, by passing to the core of their fibre product, relative to a collection
of _marked vertices_ , the subgroup or regular language in question is not
changed. If $\Gamma,\Lambda$ and $\Delta$ are all isomorphic to $S^{1}$, then
there is still a multiplicative relation, even after passing to the cores. We
show that if we fix the topology of our graphs, this is essentially the only
situation in which this relation can occur. The precise statement is as
follows.

There exists a universal constant $C>0$ such that the following holds. Let
$\gamma:\Gamma\to\Delta$ and $\lambda:\Lambda\to\Delta$ be immersions of
graphs and let
$s:\mathbb{S}=\operatorname{Core}(\mathbb{S}_{\Gamma}\times_{\Delta}\mathbb{S}_{\Lambda})\to\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$
be the natural map. Then

$\left\lvert
E(\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)-s(\mathbb{S}))\right\rvert\leq
C\cdot(\beta_{1}(\Gamma)\cdot\beta_{1}(\Lambda))^{2}\cdot(\left\lvert
E(\Gamma)\right\rvert+\left\lvert E(\Lambda)\right\rvert).$

Finally, we also prove similar bounds to those provided by the $w$-cycles
theorem in [11] and [19] for arbitrary pairs of forwards immersion.

There exists a universal constant $C>0$ such that the following holds. Let
$\gamma:\Gamma\to\Delta$ and $\lambda:\Lambda\to\Delta$ be immersions of
graphs. The natural map
$\theta:\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)\to\Delta$ consists
of a disjoint union of at most:

$C\cdot(\beta_{1}(\Gamma)\cdot\beta_{1}(\Lambda))^{2}$

many free homotopy classes of connected graph maps.

We prove slightly more general versions of these theorems by also taking into
account a set of marked vertices and relaxing the condition on the maps. The
full statements of Theorems 5.7 and 5.12 also contain explicit upper bounds
for their universal constants.

Now that we have stated our main results for the fibre product graph, we begin
with some applications.

###  1.1. Free groups

Since Stallings’ seminal paper [26], using finite graphs and graph maps to
represent free groups and their finitely generated subgroups has been very
fruitful. Therefore, results for graphs and graph maps usually come with
complementary results in the theory of free groups. Many examples of such
results can be found in [13]. We now discuss the consequences of our theorems
in the realm of free groups, starting with the following natural application
of Theorem 4.20.

Let $F$ be a free group and $A<F$ a finitely generated subgroup. Then there
are at most $\operatorname{rk}(A)$ many conjugacy classes of maximal cyclic
subgroups $M<F$ such that

$12\cdot\operatorname{rk}(A)\leq[M:A\cap M]<\infty.$

This has an immediate corollary. In [4], Delgado, Ventura and Zhakarov
introduce the notions of relative order and spectrum. Given a subset $S$ of a
group $G$, the _relative order_ $\mathcal{O}_{S}(g)$ of an element $g\in G$,
with respect to $S$, is the smallest integer $n\geq 1$ such that $g^{n}\in S$.
The _$S$ -spectrum_ of $G$ is the set $\mathcal{O}_{S}(G)=\cup_{g\in
G}\mathcal{O}_{S}(g)$. It was shown in [13] that the relative spectrum of a
finitely generated subgroup of a free group is bounded. In [4], this result is
generalised and the relative spectrum for other classes of groups is also
studied. Using Theorem 6.4, we may recover the result for free groups and also
improve the known bound to one that, in some sense, only depends on the rank
of the subgroup. Moreover, by Theorem 7.2, we may efficiently compute an upper
bound of the $A$-spectrum for finitely generated subgroups $A<F$ of a free
group.

Let $F$ be a free group and $A<F$ a finitely generated subgroup. Then there
exists a set $N\subset\mathbb{N}$ of cardinality bounded above by
$13\cdot\operatorname{rk}(A)$, such that:

$\mathcal{O}_{A}(F)=\bigcup_{n\in N}\bigcup_{d\mid n}d.$

Our last result of this section is an application of Theorem 5.12. It has been
known since the 1950s by work of Howson [12] that the intersection of two
finitely generated subgroups of a free group is again finitely generated. If
$A$ is a free group, recall that
$\bar{\operatorname{rk}}(A)=\min{\\{0,\operatorname{rk}(A)-1\\}}$ is the
_reduced rank_ of $A$. It was conjectured by Hanna Neumann that for any two
finitely generated subgroups $A,B<F$ of a free group, the inequality
$\bar{\operatorname{rk}}(A\cap
B)\leq\bar{\operatorname{rk}}(A)\cdot\bar{\operatorname{rk}}(B)$ held [22]. A
simple graph argument (see [23]) shows that in fact $\sum_{[A\cap
B^{g}]}\bar{\operatorname{rk}}(A\cap B^{g})\leq
2\cdot\bar{\operatorname{rk}}(A)\cdot\bar{\operatorname{rk}}(B)$, where
$[A\cap B^{g}]$ denotes the conjugacy class of the subgroup $A\cap B^{g}$. In
[23], Walter Neumann formulated the strengthened Hanna Neumann conjecture,
asserting that $\sum_{[A\cap B^{g}]}\bar{\operatorname{rk}}(A\cap
B^{g})\leq\bar{\operatorname{rk}}(A)\cdot\bar{\operatorname{rk}}(B)$. In 2011,
this long standing conjecture was settled independently by Mineyev [21] and
Freidmann [8].

In the same article in which the strengthened Hanna Neumann conjecture was
proposed [23], it was also shown that the larger sum $\sum_{[A\cap
B^{g}]}\operatorname{rk}(A\cap B^{g})$ is finite. The bound that one can
derive from the argument depends on the size of generating sets for $A$ and
$B$. This, in turn, depends on a chosen embedding. However, Walter Neumann
goes on to suggest that it may be possible to bound this larger sum solely in
terms of the ranks of $A$ and $B$.

Since then, most of the literature has focused on the strengthened Hanna
Neumann conjecture. However, one improvement to the naive full rank bound in
the case where $B=\langle w\rangle$ is cyclic is offered by the $w$-cycles
theorem (see [11, 19]). Indeed, it is an immediate consequence that the
inequality $\sum_{[A\cap\langle w\rangle^{g}]}\operatorname{rk}(A\cap\langle
w\rangle^{g})\leq\operatorname{rk}(A)$ holds. This result is even referred to
as a rank 1 version of the Hanna Neumann theorem [11]. As a consequence of
Theorem 5.12, we prove a more general result for arbitrary finitely generated
subgroups of a free group, confirming Walter Neumann’s intuition.

There exists a universal constant $C>0$, with the following property. For any
free group $F$ and any finitely generated subgroups $A,B<F$, we have:

$\sum_{[A\cap B^{g}]}\operatorname{rk}(A\cap B^{g})\leq
C\cdot(\operatorname{rk}(A)\cdot\operatorname{rk}(B))^{2}.$

As demonstrated by Example 5.13, a lower bound for a sharp upper bound for
this sum is $\operatorname{rk}(A)\cdot\operatorname{rk}(B)$.

###  1.2. Regular languages

Let $\Delta$ be a rose graph with an edge for each element in some finite set
$\Sigma$. Then to each regular language $L\subset\Sigma^{*}$, there is an
associated unique minimal deterministic finite state automaton
$\gamma:\Gamma\to\Delta$, such that the language $L(\Gamma)$ is precisely $L$.
It is a classical fact that $L(\Gamma\times_{\Delta}\Lambda)=L(\Gamma)\cap
L(\Lambda)$ [24], thus providing an explicit deterministic quadratic time
algorithm to compute the intersection of two regular languages. By considering
finite sheeted covers of graphs we see that there are pairs of regular
languages that require a quadratic number of states to express their
intersection. Hence, this automaton cannot be improved. On the other hand, it
is an open question as to whether the non-emptiness of $L(\Gamma)\cap
L(\Lambda)$ can be decided in subquadratic time [14]. This decision problem,
extending to an input of $k$ DFAs, is known as the $k$-DFA non-emptiness
intersection problem ($k$-DFA-NEI). Restricting to unary alphabets, $2$-DFA-
NEI is known to be solvable in deterministic linear time and $3$-DFA-NEI in
subquadratic time [2].

If the true complexity of DFA-NEI was strictly better than that of the Rabin-
Scott algorithm, then several strong complexity results would be implied. For
example, if $2$-DFA-NEI could be solved in subquadratic time, it would imply
that $\text{NSPACE}[n+o(n)]\subset\text{DTIME}[2^{(1-\epsilon)\cdot n}]$ for
some $\epsilon>0$, SAT would be solvable in subexponential time and the strong
exponential time hypothesis would be contradicted [3]. If $k$-DFA-NEI could be
solved in $O(n^{o(k)})$ time, we would also have
$\text{NSPACE}[n]\subset\text{DTIME}[2^{o(n)}]$ [3] and
$\text{NL}\neq\text{P}$ [28].

We present a different approach to the non-emptiness intersection problem
based on Theorem 5.7. If we fix the topology of the automata, we obtain
complexity bounds that depend linearly on the input size. Define
$\partial\Gamma\subset V(\Gamma)$ to be the vertices with indegree or
outdegree equal to $0$.

For some $q>0$, there is an algorithm that, given as input two DFAs
$\gamma:\Gamma\to\Delta$ and $\lambda:\Gamma\to\Delta$ such that
$\beta_{1}(\Gamma),\beta_{1}(\Lambda),\left\lvert\partial\Gamma\right\rvert,\left\lvert\partial\Lambda\right\rvert\leq
m$ and $\left\lvert E(\Gamma)\right\rvert,\left\lvert
E(\Lambda)\right\rvert\leq n$, decides if $L(\Gamma)\cap L(\Lambda)$ is non-
empty in

$O(m^{q}\cdot n)$

time.

Note that if $\Delta$ contains a single edge, then for every forwards graph
immersion $\gamma:\Gamma\to\Delta$ we have
$\beta_{1}(\Gamma)+\left\lvert\partial\Gamma\right\rvert\leq 2$. Thus, this
can be seen as a direct generalisation of the unary case.

###  1.3. Organisation of the paper

Our main technical tools will come from new results on the combinatorics of
words. In Section 2, we recall some well known definitions and results and
introduce $w$-factorisations and word overlaps. We then show uniqueness of
$w$-factorisations and describe all overlaps for any given pair of words in
terms of arithmetic progressions. The main result of this section is Theorem
2.17, upon which most of Section 4 relies. In Section 3 we recall all the
necessary definitions for graphs and the fibre product graph. Section 4
introduces $w$-graphs and culminates in the proof of Theorem 4.20. In Section
5, we decompose the fibre product into two subgraphs. Using this decomposition
and combining our word overlap and $w$-graph results, we then obtain Theorems
5.7 and 5.12. Since the graphs we work with are not Stallings graphs, in
Section 6, we explain an alternative construction that allows us to convert
our results to statements about free groups. Finally, Section 7 is dedicated
to our algorithmic results.

### Acknowledgments

We would like to thank Saul Schleimer for many helpful discussions and
comments on previous versions of this article.

##  2\. Some combinatorics on words

###  2.1. Words and the free monoid

Let $\Sigma$ be a set. We denote by $\Sigma^{*}$ the free monoid generated by
$\Sigma$ under the concatenation operation and with neutral element the empty
string $\epsilon$. We call elements of $\Sigma$ _letters_ and elements of
$\Sigma^{*}$ _words_.

We call an equality of the form $w=w_{0}\cdot w_{1}\cdot...\cdot
w_{n}\in\Sigma^{*}$ a _factorisation_ of $w$ and each word $w_{i}$ a _subword_
of $w$. Now let $w\in\Sigma^{*}$ and

$w=w_{0}\cdot w_{1}\cdot...\cdot w_{n}$

be the unique factorisation of $w$ with $w_{i}\in\Sigma$. Then we denote by
$\left\lvert w\right\rvert=n+1$ the _length_ of $w$ and by $w[i]=w_{i}$ the
$i+1^{\text{th}}$ letter of $w$. For any $0\leq i<j\leq n+1$, we denote by
$w[i:j]=w_{i}\cdot w_{i+1}\cdot...\cdot w_{j-1}$ the subword of length $j-i$
starting at $w_{i}$. We denote by $w[:i]=w[0:i]$ the _prefix_ of length $i$
and by $w[j:]=w[j:n+1]$ the _suffix_ of length $n-j+1$. We extend this all to
negative indices by defining $w[-j:-i]=w[|w|-j:|w|-i]$. A _cyclic conjugate_
of $w$ is a word of the form $w[-i:]\cdot w[:i]$ for some $i\leq\left\lvert
w\right\rvert$. We say that two words $v,w$ are _cyclically conjugate_ if $v$
is a cyclic conjugate of $w$. A _conjugating word_ of two cyclically conjugate
words $v,w$ is a word $u$ such that $u\cdot v=w\cdot u$.

A word $w$ is _primitive_ if there is no subword $u$ such that $w=u^{n}$ for
some $n>1$, _imprimitive_ otherwise. A _period_ $p$ of a word $w$ is an
integer $p<\left\lvert w\right\rvert$ such that $w[i]=w[i+p]$ for all
$i\leq|w|-p$. Denote by $\operatorname{per}(w)$ the smallest period of $w$.
Let $w[:\operatorname{per}(w)]=u$, then $w=u^{n}\cdot u^{\prime}$ with
$u^{\prime}$ a proper prefix of $u$. We will call $n=\operatorname{ord}(w)$
the _order_ of $w$. Denote by $\operatorname{Arith}(p,q,r)$ the _arithmetic
progression_ $\\{i\cdot q+r|0\leq i\leq p\\}$.

###  2.2. Periodicity and $w$-factorisations

Before introducing $w$-factorisations, we will state some results on periodic
words, starting with the well known Fine and Wilf periodicity theorem [7].

######  Theorem 2.1.

If $w\in\Sigma^{*}$ has periods $p$ and $q$ and $|w|\geq p+q-\gcd(p,q)$, then
$w$ has period $\gcd(p,q)$. $\hfill\qed$

######  Corollary 2.2.

Let $w\in\Sigma^{*}$. If $w^{2}$ has period $p<\left\lvert w\right\rvert$,
then $w$ is imprimitive. $\hfill\qed$

The following are Lemmas 1 and 3 of [20] respectively.

######  Lemma 2.3.

Let $u,v,w\in\Sigma^{*}$ such that $u\cdot w=w\cdot v$. Then $w$ has prefix
$u$ and period $|u|$. $\hfill\qed$

######  Lemma 2.4.

Let $v,w\in\Sigma^{*}$ such that $v\cdot w=w\cdot v$. Then $v$ and $w$ are
powers of a common word. $\hfill\qed$

A key tool in this paper will be the notion of $w$-factorisations:

######  Definition 2.5.

Suppose $w\in\Sigma^{*}$ is a primitive word. A _left $w$-factorisation_ of a
word $x\in\Sigma^{*}$ is a factorisation of the form $x=v\cdot y$ where $v$ is
a subword of $w^{n}$ for some $n\geq 1$. A left $w$-factorisation $x=v\cdot y$
is _maximal_ if there is no other left $w$-factorisation $x=v^{\prime}\cdot
y^{\prime}$ with $\left\lvert v^{\prime}\right\rvert>\left\lvert
v\right\rvert$. A _(maximal) right $w$-factorisation_ is defined analogously.

######  Lemma 2.6.

Suppose $w\in\Sigma^{*}$ is primitive. Then for any word $x\in\Sigma^{*}$, we
have:

  1. (1)

left and right $w$-factorisations of $x$ of length $k\geq|w|$ are unique,

  2. (2)

if $x$ has a maximal left $w$-factorisation of length $k_{1}$ and a maximal
right $w$-factorisation of length $k_{2}$, then either
$k_{1}=k_{2}=\left\lvert w\right\rvert$, or $k_{1}+k_{2}<|x|+|w|$.

###### Proof.

If the first statement does not hold, then up to replacing $w$ by a cyclic
conjugate of itself, we get $x=w\cdot y=v\cdot u\cdot y$ where $v$ is a proper
suffix of $w$ and $u$ is a proper prefix of $w$. But then $w=u\cdot v=v\cdot
u$ so by Lemma 2.4 $w$ is not primitive. The second statement follows from the
same argument. ∎

######  Remark 2.7.

Lemma 2.6 cannot be extended for any left or right factorisations of length
less than $w$ for the simple fact that $w$ can have many repeated subwords.
For example, if $w=u^{n}\cdot u^{\prime}$ for some $n\geq 1$ and $u^{\prime}$
a proper non-trivial prefix of $u$, then $x=u^{n-k}\cdot u^{\prime}$ has at
least $k+1$ different $w$-factorisations.

We conclude this section with a couple of algorithmic results. The following
theorem is the main result in [17].

######  Theorem 2.8.

The set of periods $p$ of a word $w\in\Sigma^{*}$ can be computed in linear
time. $\hfill\qed$

######  Proposition 2.9.

Let $u,v\in\Sigma^{*}$. We can check if $u$ and $v$ are cyclically conjugate
in $O(\left\lvert u\right\rvert+\left\lvert v\right\rvert)$ time. Moreover,
the algorithm returns a conjugating word $w$.

###### Proof.

The words $u$ and $v$ are cyclically conjugate if and only if $\left\lvert
u\right\rvert=\left\lvert v\right\rvert$ and $v$ is a subword of $u^{2}$.
Since checking this can be done in linear time by the Knuth-Morris-Pratt
algorithm [17], checking if $u$ and $v$ are cyclically conjugate can be done
in $O(\left\lvert u\right\rvert+\left\lvert v\right\rvert)$ time. Since the
algorithm also outputs an index $i$ such that $u^{2}[i:i+\left\lvert
v\right\rvert]=v$, we also get the conjugating word $w=u[:i]$. ∎

###  2.3. Overlapping words

In this section we will review the idea of overlaps of two given words
$v,w\in\Sigma^{*}$.

######  Definition 2.10.

Let $v,w\in\Sigma^{*}$ be two words. There are three distinct types of
overlaps: _subword_ , _prefix_ and _suffix_ overlap. These are described in
the table below.

$\displaystyle v[i:j]$ $\displaystyle=w$ Subword overlap $\displaystyle v[:i]$
$\displaystyle=w[-i:]$ Prefix overlap $\displaystyle v[-i:]$
$\displaystyle=w[:i]$ Suffix overlap

We will use the notation $\operatorname{Sub}(v,w)$ to denote the set of
_subword indices of $w$ in $v$_: that is, the set of integers $0\leq
i\leq\left\lvert v\right\rvert-\left\lvert w\right\rvert$ such that
$v[i:i+|w|]=w$. We will write $\operatorname{Pref}(v,w)$ to denote the set of
_prefix indices of $w$ in $v$_: that is, the set of integers
$0<i\leq\min{\\{\left\lvert v\right\rvert,\left\lvert w\right\rvert\\}}$ such
that $v[:i]=w[-i:]$. Finally, we write $\operatorname{Suff}(v,w)$ to denote
the set of _suffix indices of $w$ in $v$_: that is, the set of integers
$\max{\\{0,\left\lvert v\right\rvert-\left\lvert w\right\rvert\\}}\leq
i<\left\lvert v\right\rvert$ such that $v[i:]=w[:\left\lvert
v\right\rvert-i]$.

######  Definition 2.11.

We say $w$ _crosses_ $v$ at $j$ if there is an integer $i$ with $i\leq
j<i+|w|$ such that

$v[i:i+|w|]=w.$

We will call the index $i$ a _crossing index of $w$ in $v$ at $j$_. Denote by
$\operatorname{Sub}(v,w,j)$ the crossing indices of $w$ in $v$ at $j$.

The word $w$ crosses $v$ at $j$ if $w$ appears as a subword of $v$ containing
the letter $v[j]$. Or in other words, $w$ crosses $v$ at $j$ if $v=y\cdot
w\cdot z$ with $i=|y|+1$ a crossing index of $w$ in $v$ at $j$. This
definition and the following lemma have been used extensively in the pattern
matching literature; see [18] and the references therein.

######  Lemma 2.12.

Let $w,v\in\Sigma^{*}$ and let $j\leq|v|$ be an integer. There exists some
triple $p,q,r\leq|v|$ such that:

$\operatorname{Sub}(v,w,j)=\operatorname{Arith}(p,q,r)$

with $q\geq\operatorname{per}(w)$ and $p\leq\operatorname{ord}(w)$.
Furthermore, if $p\geq 2$, then $q=\operatorname{per}(w)$.

###### Proof.

The first part of the statement is Lemma 1 in [18]. If $p\geq 2$, then we must
have $\operatorname{per}(w)|q$ by Theorem 2.1. Set
$d=\frac{q}{\operatorname{per}(w)}$. If we have

$v=y\cdot w[:q]^{p}\cdot w[q:]\cdot z$

then we also have

$v=y\cdot w[:\operatorname{per}(w)]^{p\cdot d}\cdot w[q:]\cdot z.$

Thus $d=1$ as otherwise
$\operatorname{Arith}(p,q,r)\subsetneq\operatorname{Sub}(v,w,j)$. ∎

The following results are direct applications of Lemma 2.12.

######  Lemma 2.13.

Let $v,w\in\Sigma^{*}$. There is a sequence of integers $j_{1},...,j_{k}$ such
that $j_{i+1}-j_{i}\geq\left\lvert w\right\rvert$ for all $i<k$ such that:

$\operatorname{Sub}(v,w)=\bigcup_{i=1}^{k}\operatorname{Sub}(v,w,j_{i}).$

$\hfill\qed$

######  Corollary 2.14.

Let $v,w\in\Sigma^{*}$. The set $\operatorname{Sub}(v,w)$ can be decomposed:

$\operatorname{Sub}(v,w)=\bigcup_{i=1}^{k}\operatorname{Arith}(p_{i},q_{i},r_{i})$

where $k\leq\left\lfloor\frac{|v|}{|w|}\right\rfloor$ and $p_{i}\cdot
q_{i}\leq\left\lvert w\right\rvert$ for all $i\leq k$. $\hfill\qed$

We now move onto classifying prefix and suffix overlaps in a similar way.
Since $\operatorname{Pref}(w,v)=\\{\left\lvert v\right\rvert-i\mid
i\in\operatorname{Suff}(v,w)\\}$, it is only necessary to treat the
$\operatorname{Suff}(v,w)$ case.

######  Lemma 2.15.

Let $v,w\in\Sigma^{*}$. If $i<j\in\operatorname{Suff}(v,w)$, then

$\operatorname{Arith}\left(\left\lfloor\frac{\left\lvert
v\right\rvert-i}{j-i}\right\rfloor,j-i,i\right)\subset\operatorname{Suff}(v,w).$

###### Proof.

If $i<j\in\operatorname{Suff}(v,w)$, then $v[i:]=w[:\left\lvert
v\right\rvert-i]$ and $v[j:]=w[:\left\lvert v\right\rvert-j]$. In particular:

$v[i:j]\cdot w[:\left\lvert v\right\rvert-i]=w[:\left\lvert
v\right\rvert-i]\cdot w[\left\lvert v\right\rvert-j:\left\lvert
v\right\rvert-i].$

By Lemma 2.3, $v[i:]$ and $w[:\left\lvert v\right\rvert-i]$ have period $j-i$
and so $\operatorname{Arith}\left(\left\lfloor\frac{\left\lvert
v\right\rvert-i}{i-j}\right\rfloor,j-i,i\right)\subset\operatorname{Suff}(v,w)$
as claimed. ∎

######  Proposition 2.16.

Let $v,w\in\Sigma^{*}$. The set of suffix indices of $w$ in $v$ can be
decomposed as a union of arithmetic progressions:

$\operatorname{Suff}(v,w)=\bigcup_{i=1}^{k}\operatorname{Arith}(p_{i},q_{i},r_{i})$

such that, for all $n\leq k$:

  1. (1)

if $j\in\operatorname{Suff}(v,w)$ and $j\leq|v|-q_{n}$, then
$j\in\bigcup_{i=1}^{n}\operatorname{Arith}(p_{i},q_{i},r_{i})$,

  2. (2)

$r_{n}\geq|v|-q_{n-1}$,

  3. (3)

$p_{n}\cdot q_{n}+r_{n}\geq|v|-q_{n}$,

  4. (4)

$q_{n}\leq\frac{q_{n-1}}{2}$,

  5. (5)

$v[r_{n}:r_{n}+q_{n}]$ is primitive.

Furthermore,
$k\leq\min{\\{\left\lfloor\log_{2}{|v|}\right\rfloor,\left\lfloor\log_{2}{|w|}\right\rfloor\\}}$

###### Proof.

We will inductively define arithmetic progressions
$\operatorname{Arith}(p_{n},q_{n},r_{n})\subset\operatorname{Suff}(v,w)$
satisfying (1) to (5) in the statement. Once we have done this, (1) will imply
the decomposition and (4) will imply the bound on $k$.

For the base case we will simply set
$r_{1}=\min{\\{\operatorname{Suff}(v,w)\\}}$, $p_{1}=0$ and $q_{1}=\left\lvert
v\right\rvert-r_{1}$. Now suppose $n\geq 2$. Let
$j\in\operatorname{Suff}(v,w)$ be the smallest index not contained in
$\bigcup_{i=1}^{n-1}\operatorname{Arith}(p_{i},q_{i},r_{i})$. Let
$l\in\operatorname{Suff}(v,w)\cup\\{\left\lvert v\right\rvert\\}$ minimise
$\left\lvert l-j\right\rvert$. Inductively by (1), we have $j\geq\left\lvert
v\right\rvert-q_{n-1}$ and by (3) we have $p_{n-1}\cdot
q_{n-1}+r_{n-1}\geq\left\lvert v\right\rvert-q_{n-1}$, hence $\left\lvert
l-j\right\rvert\leq\frac{q_{n-1}}{2}$. So if we set $r_{n}=j$,
$q_{n}=\left\lvert l-j\right\rvert$ and $p_{n}=\left\lfloor\frac{\left\lvert
v\right\rvert-r_{n}}{q_{n}}\right\rfloor$, then
$\operatorname{Arith}(p_{n},q_{n},r_{n})\subset\operatorname{Suff}(v,w)$ by
Lemma 2.15. This verifies the last four properties, so we turn our attention
to (1).

If $l=|v|$, then we are done. Now assume that $l\neq\left\lvert v\right\rvert$
and hence $p_{n}\geq 1$. Suppose there is some index
$m\in\operatorname{Suff}(v,w)$ such that $|v|-q_{n-1}<m\leq|v|-q_{n}$ and
$m\notin\cup_{i=1}^{n}\operatorname{Arith}(p_{i},q_{i},r_{i})$. By our choice
of $j$, we must have $m>j$. Furthermore, $\left\lvert m-j\right\rvert\geq
q_{n}$ and $q_{n}\nmid\left\lvert m-j\right\rvert$. So in particular, there is
some integer $i<p_{n}$ such that $0<m-(i\cdot q_{n}+r_{n})<q_{n}$. We may
assume that $m$ was chosen to minimise $\left\lvert m-i\cdot
p_{n}+r_{n}\right\rvert$ over all valid choices of $i$. Then by Lemma 2.15,
$v[i\cdot q_{n}+r_{n}:]$ has period $m-(i\cdot q_{n}+r_{n})$. Now by Theorem
2.1 we arrive at a contradiction to the minimality of $m$. Hence no such $m$
exists and (1) holds. ∎

We close this section with a result which will play a key role in our analysis
of $w$-graphs in Section 4.

######  Theorem 2.17.

Let $w,x_{1},...,x_{n}\in\Sigma^{*}$ be words with $w$ primitive. There is
some cyclic shift $w_{0}$ of $w$ such that

$|\operatorname{Sub}(w_{0}^{2},x_{i},|w_{0}|-1)|\leq 2$

for all $1\leq i\leq n$.

In other words, Theorem 2.17 tells us that there is some cyclic shift $w_{0}$
of $w$ such that each $x_{i}$ crosses the midpoint of $w_{0}^{2}$ at most
twice.

###### Proof of Theorem 2.17.

Suppose there is some $x_{i}$ such that $\left\lvert
x_{i}\right\rvert\geq\left\lvert w\right\rvert$. By Lemma 2.6, if
$\operatorname{Sub}(w_{0}^{2},x_{i},\left\lvert w\right\rvert-1)\neq\emptyset$
for some cyclic shift $w_{0}$ of $w$, then $x_{i}$ has a unique
$w$-factorisation. Hence,
$\left\lvert\operatorname{Sub}(w_{0}^{2},x_{i},\left\lvert
w\right\rvert-1)\right\rvert\leq 1$ for all cyclic shifts $w_{0}$ of $w$. By
Lemma 2.12, if $\operatorname{ord}(x_{i})\leq 1$, then we also have
$|\operatorname{Sub}(w_{0}^{2},x_{i},|w|-1)|\leq 2$ for all $i$. Hence there
is no loss in generality assuming that $\left\lvert
x_{i}\right\rvert<\left\lvert w\right\rvert$ and
$\operatorname{ord}(x_{i})\geq 2$ for all $i$.

Denote by $w[[j]]=w[j:]\cdot w[:j]$ where $j$ is taken mod $\left\lvert
w\right\rvert$. For each $i$, let
$y_{i},y_{i}^{\prime},y_{i}^{\prime\prime}\in\Sigma^{*}$ and $c_{i}\geq 2$
such that

$\displaystyle y_{i}$ $\displaystyle=x_{i}[:\operatorname{per}(x_{i})]$
$\displaystyle x_{i}$ $\displaystyle=y_{i}^{c_{i}}\cdot y_{i}^{\prime}$
$\displaystyle y_{i}$ $\displaystyle=y_{i}^{\prime}\cdot y_{i}^{\prime\prime}$

We may assume that the $x_{i}$ are ordered so that $|y_{i}|\geq|y_{i+1}|$. To
simplify the argument we will consider an extra word $x_{0}=w$. We will find
by induction a sequence of integers $i_{0},i_{1},...,i_{n}$ such that for all
$k\leq n$ the following is satisfied:

  1. (1)

if $k\geq 1$, then $i_{k-1}-2\cdot\left\lvert y_{k-1}\right\rvert\leq
i_{k}-2\cdot\left\lvert y_{k}\right\rvert$ and $i_{k-1}\leq i_{k}$,

  2. (2)

$\left\lvert\operatorname{Sub}(w^{2}[[i_{k}-l]],x_{k},\left\lvert
w\right\rvert-1)\right\rvert\leq 2$ for all $l\leq 2\cdot\left\lvert
y_{k}\right\rvert$,

  3. (3)

there is some integer $m(k)\leq k$ such that $i_{m(k)}=...=i_{k}$ and
$y_{m(k)}^{2}$ is a suffix of $w[[i_{m(k)}]]$.

Then we will take $w_{0}=w[[i_{n}]]$ and the theorem will be proved by (1) and
(2).

By setting $i_{0}=2\cdot\left\lvert w\right\rvert$ and $m(0)=0$, the base case
holds trivially. So now for the inductive step, let $k\geq 1$. If

$\left\lvert\operatorname{Sub}(w^{2}[[i_{m(k-1)}-l]],x_{k},\left\lvert
w\right\rvert)\right\rvert\leq 2$

for all $l\leq 2\cdot\left\lvert y_{m(k-1)}\right\rvert$, then set
$i_{k}=i_{m(k)}=i_{m(k-1)}$ and $m(k)=m(k-1)$ and all three conditions are
satisfied. So now suppose that:

$|\operatorname{Sub}(w^{2}[[i_{m(k-1)}-l]],x_{k},|w|)|>2$

for some $l\leq 2\cdot|y_{m(k-1)}|$. Then $y_{k}^{2}$ is a subword of
$w[[i_{m(k-1)}]][-2\cdot\left\lvert y_{m(k-1)}\right\rvert:]$ by Lemma 2.12
and $y_{k}\neq y_{m(k-1)}$. So let $i,j$ be integers such that

$i_{m(k-1)}-2\cdot\left\lvert y_{m(k-1)}\right\rvert\leq i<j\leq i_{m(k-1)}$

and $w[[i_{m(k-1)}]][i:j]$ has the largest $y_{k}$-factorisation among all
such choices of integers. If $i=i_{m(k-1)}-2\cdot\left\lvert
y_{m(k-1)}\right\rvert$ and $j=i_{m(k-1)}$, then, either $y_{k}=y_{m(k-1)}$,
or $y_{m(k-1)}$ is imprimitive by Corollary 2.2. But this is a contradiction.

So now suppose first that $i>i_{m(k-1)}-2\cdot\left\lvert
y_{m(k-1)}\right\rvert$. Let $i_{k}>i$ be the smallest integer such that
$y_{k}^{2}$ is a suffix of $w[[i_{k}]]$, but not $y_{k}^{3}$. This exists and
is smaller than $j$ since $j-i\geq 2\cdot\left\lvert y_{k}\right\rvert$. Thus
we have

$\displaystyle i_{m(k-1)}-2\cdot\left\lvert y_{m(k-1)}\right\rvert$
$\displaystyle<i\leq i_{k}-2\cdot\left\lvert y_{k}\right\rvert$ $\displaystyle
i_{k}$ $\displaystyle\leq j\leq i_{m(k-1)}$

hence (1) holds. By setting $m(k)=k$, (3) holds. If
$c\in\operatorname{Sub}(w^{2}[[i_{k}]],x_{k},\left\lvert w\right\rvert-1)$,
then $w[[i_{k}]][c:]$ has a $y_{k}$-factorisation beginning with $y_{k}$. But
then by Lemma 2.6 it follows that either $c=\left\lvert
w\right\rvert-2\cdot\left\lvert y_{k}\right\rvert$ or $c\geq\left\lvert
w\right\rvert-\left\lvert y_{k}\right\rvert$. So by Lemma 2.12, (2) holds.

If $i=i_{m(k-1)}-2\cdot\left\lvert y_{m(k-1)}\right\rvert$, then
$j<i_{m(k-1)}$. So now we let $i_{k}\leq j$ be the largest integer such that
$y_{k}^{2}$ is a suffix of $w[[i_{k}]]$, but $y_{k}$ is not a prefix. As
before, (1) is satisfied. Similarly, setting $m(k)=k$, (3) is also satisfied.
If $c\in\operatorname{Sub}(w^{2}[[i_{k}]],x_{1},\left\lvert w\right\rvert-1)$,
then by Lemma 2.12, $w[[i_{k}]][c:]$ has a $y_{k}$-factorisation. By Lemma
2.6, we must have $c=\left\lvert w\right\rvert-d\cdot\left\lvert
y_{k}\right\rvert$ for some $d\geq 1$ or $c>\left\lvert
w\right\rvert-\left\lvert y_{k}\right\rvert$. Since $w[[i_{k}]]$ does not have
$y_{k}$ as a prefix, $\operatorname{Sub}(w^{2}[[i_{k}]],x_{k},\left\lvert
w\right\rvert-1)$ contains at most one value of the first type. By Lemma 2.12
it contains at most one value of the second type. So (2) holds and the theorem
is proved. ∎

##  3\. Graphs

A directed graph is a tuple $\Gamma=(V,E,o,t)$ where $V$ is the set of
_vertices_ , $E$ is the set of _edges_ and $o,t:E\to V$ are the _origin_ and
_target_ maps respectively. We always assume our graphs are directed and so
will refer to them simply as graphs. If $S\subset V$ or $S\subset E$, then we
denote by $\Gamma-S$ the maximal subgraph of $\Gamma$ that does not contain
any vertices or edges in $S$. Define the _forwards star_ of a vertex $v$ in a
graph $\Gamma$ to be the set $\operatorname{St^{+}}(v,\Gamma)=\\{e\in
E(\Gamma)\mid o(e)=v\\}$. We also define the set
$\operatorname{St^{-}}(v,\Gamma)=\\{e\in E(\Gamma)\mid t(e)=v\\}$ which we
will call the _backwards star_. We then define the _indegree_ of $v$ to be
$\operatorname{deg^{-}}(v)=\left\lvert\operatorname{St^{-}}(v,\Gamma)\right\rvert$,
the _outdegree_ of $v$ to be
$\operatorname{deg^{+}}(v)=\left\lvert\operatorname{St^{+}}(v,\Gamma)\right\rvert$
and the _degree_ of $v$ to be
$\deg(v)=\operatorname{deg^{-}}(v)+\operatorname{deg^{+}}(v)$.

With applications in mind, it is useful to allow an auxiliary subset
$V^{m}(\Gamma)\subset V(\Gamma)$ of _marked vertices_. We further decompose
this set $V^{m}(\Gamma)=V^{i}(\Gamma)\cup V^{f}(\Gamma)$ into _initial_ and
_final vertices_.

######  Definition 3.1.

Denote by $\partial\Gamma\subset V(\Gamma)$ the vertices $v$ such that
$\operatorname{deg^{-}}(v)=0$ or $\operatorname{deg^{+}}(v)=0$.

Note that this is a different definition to the usual boundary of a graph.

######  Definition 3.2.

Denote by $\bar{V}(\Gamma)\subset V(\Gamma)$ the vertices $v$ such that
$\operatorname{deg^{-}}(v)\neq 1$ or $\operatorname{deg^{+}}(v)\neq 1$.

A _graph map_ $\gamma:\Gamma\to\Delta$ consists of a pair of maps
$\gamma_{V}:V(\Gamma)\to V(\Delta)$ and $\gamma_{E}:E(\Gamma)\to E(\Delta)$
such that $\gamma_{V}\circ o=o\circ\gamma_{E}$ and $\gamma_{V}\circ
t=t\circ\gamma_{E}$. If $\gamma:\Gamma\to\Delta$ is a graph map of graphs with
marked vertices, we require that $V^{i}(\Gamma)$ maps to $V^{i}(\Delta)$ and
$V^{f}(\Gamma)$ maps to $V^{f}(\Delta)$. We say a graph map
$\gamma:\Gamma\to\Delta$ is a _forwards immersion_ if the induced map
$\gamma_{v}^{+}:\operatorname{St^{+}}(v,\Gamma)\to\operatorname{St^{+}}(\gamma(v),\Delta)$
is injective for each $v\in V(\Gamma)$. We say $f$ is an _immersion_ if
$\gamma_{v}^{+}$ and $\gamma_{v}^{-}$ are injective for all $v\in V(\Gamma)$.

A _segment_ is a graph consisting of vertices $v_{0},...,v_{k}$ and edges
$e_{0},...,e_{k-1}$ such that $o(e_{i})=v_{i}$, $t(e_{i})=v_{i+1}$ for all
$i<k$. A _path_ is a graph map $f:I\to\Gamma$ where $I$ is a segment. The
_length_ of a path $f$ will be defined as $|f|=|E(I)|=k$. Denote by

$\displaystyle f(i)$ $\displaystyle=v_{i},$ $\displaystyle f[i]$
$\displaystyle=e_{i},$ $\displaystyle o(f)$ $\displaystyle=v_{0},$
$\displaystyle t(f)$ $\displaystyle=v_{k}.$

Paths may also be considered as words over $E(\Gamma)$ and thus we will be
able to apply the same notation and results from Section 2 to paths. If $f$
and $g$ are two paths with $t(f)=o(g)$, then we will write $f*g$ for their
concatenation. A path $f$ is _primitive_ if there is no other path
$w:I\to\Gamma$ such that $f=w^{n}$ for some $n\geq 2$. A path $f$ is _simple_
if $f(i)\neq f(j)$ for all $i,j<\left\lvert f\right\rvert$. A path
$f:I\to\Gamma$ is a _loop_ if $o(f)=t(f)$. We say that a path $f:I\to\Gamma$
is _accepting_ if $o(f)\in V^{i}(\Gamma)$ and $t(f)\in V^{f}(\Gamma)$. A path
$f:I\to\Gamma$ is _admissible_ if it is accepting or if it is a loop.

We say a path $f:I\to\Gamma$ _connects_ $o(f)$ with $t(f)\in V(\Gamma)$.
Connectedness generates a reflexive and transitive binary relation on
$V(\Gamma)$. A graph is _connected_ it has a single equivalence class under
the symmetric closure of this binary relation. The _connected components_ are
the maximal connected subgraphs.

A _circle_ is a graph consisting of vertices $v_{0},...,v_{k-1}$ and edges
$e_{0},...,e_{k-1}$ such that $o(e_{i})=v_{i}$ and $t(e_{i})=v_{i+1}$ for all
$i<k$ and where the indices are taken mod $k$. A _cycle_ is a graph map
$f:S^{1}\to\Gamma$ where $S^{1}$ is a circle. Recall that $\deg(f)$ is the
largest degree of a covering map $S^{1}\to S^{1}$ that $f$ factors through. If
$f:I\to\Gamma$ is a path, we write $\hat{f}:S^{1}\to\Gamma$ for the cycle
obtained from $f$ by identifying the vertices $\partial I$. The union of
images of cycles in $\Gamma$ is _the core_ of $\Gamma$; we denote this by
$\operatorname{Core}(\Gamma)$. The _relative core_
$\operatorname{Core^{rel}}(\Gamma)$ is the union of the images of all
admissible paths.

######  Definition 3.3.

Denote by $\bar{E}(\Gamma)$ the collection of paths $e:I\to\Gamma$ and cycles
$f:S^{1}\to\Gamma$ such that:

  1. (1)

$e_{E}$ and $f_{E}$ are injective,

  2. (2)

$e(I)\cap\bar{V}(\Gamma)=\\{o(e),t(e)\\}$ and
$f(S^{1})\cap\bar{V}(\Gamma)=\emptyset$.

We denote by $\bar{E}_{c}(\Gamma)\subset\bar{E}(\Gamma)$ the subset
corresponding to all the cycles.

See Figure 1 for an example of the elements $\bar{E}(\Gamma)$. Throughout, we
may consider the elements of $\bar{E}(\Gamma)$ as paths or cycles, or as
subgraphs of $\Gamma$.

Figure 1. A graph $\Gamma$ and the segments $\bar{E}(\Gamma)$.

We define an alternative version of our origin and target maps for graphs
$\Gamma$ such that $\bar{E}_{c}(\Gamma)=\emptyset$. If $e\in E(\Gamma)$ and
$\bar{e}\in\bar{E}(\Gamma)$ is the unique element such that
$e\subset\bar{e}(I)$, then we do this as follows:

$\bar{o}:E(\Gamma)\to\bar{E}(\Gamma)\times\mathbb{N},$
$\bar{o}(e)=(\bar{e},i),$

where $o(e)=\bar{e}(i)$. Then the map

$\bar{t}:E(\Gamma)\to\bar{E}(\Gamma)\times\mathbb{N}$

is defined similarly. We also extend these maps to non-trivial paths.

######  Definition 3.4.

Suppose $\gamma:\Gamma\to\Delta$ is a graph map and $w:I\to\Delta$ is a non-
trivial path. Then we will denote by $\operatorname{\mathcal{L}}(\gamma,w)$
the lifts of $w$ to $\Gamma$.

######  Definition 3.5.

Suppose $\gamma:\Gamma\to\Delta$ is a graph map and $w:I\to\Delta$ is a path.
Define
$\operatorname{\mathcal{L}_{\text{sub}}}(\gamma,w)\subset\operatorname{\mathcal{L}}(\gamma,w)$
to be the lifts that do not contain any vertex $v\in\bar{V}(\Gamma)$ in their
image. Define
$\operatorname{\mathcal{L}_{\text{overlap}}}(\gamma,w)\subset\operatorname{\mathcal{L}}(\gamma,w)$
to be the lifts which do contain some $v\in\bar{V}(\Gamma)$ in their image.

In Section 5.1, we characterise these subsets for the fibre product graph.

The following lemma is a rephrasing of a standard fact about graphs using our
notation. We include its proof for completeness.

######  Lemma 3.6.

Let $\Gamma=\operatorname{Core^{rel}}(\Gamma)$ be a graph, then:

$\displaystyle\left\lvert\bar{V}(\Gamma)\right\rvert$ $\displaystyle\leq
2\cdot(\beta_{1}(\Gamma)-\beta_{0}(\Gamma))+2\cdot\sum_{v\in\partial\Gamma}\deg(v),$
$\displaystyle\left\lvert\bar{E}(\Gamma)-\bar{E}_{c}(\Gamma)\right\rvert$
$\displaystyle\leq
3\cdot(\beta_{1}(\Gamma)-\beta_{0}(\Gamma))+2\cdot\sum_{v\in\partial\Gamma}\deg(v).$

###### Proof.

We have:

$\displaystyle\beta_{1}(\Gamma)$
$\displaystyle=\beta_{0}(\Gamma)-\chi(\Gamma)$
$\displaystyle=\beta_{0}(\Gamma)-\left\lvert\bar{V}\right\rvert+\left\lvert\bar{E}-\bar{E}_{c}\right\rvert.$

We also have the following:

$\left\lvert\bar{E}-\bar{E}_{c}\right\rvert=\frac{1}{2}\cdot\sum_{v\in\bar{V}}\deg(v).$

We will prove the bounds by induction on $|\partial\Gamma|$. So if
$|\partial\Gamma|=0$, since $\Gamma$ is core, $\deg(v)\geq 3$ for each
$v\in\bar{V}$. Now by the above formula, we get
$\left\lvert\bar{E}-\bar{E}_{c}\right\rvert\geq\frac{3}{2}\cdot\left\lvert\bar{V}\right\rvert$.
Hence we may derive:

$\left\lvert\bar{V}\right\rvert\leq
2\cdot(\beta_{1}(\Gamma)-\beta_{0}(\Gamma)),$
$\left\lvert\bar{E}-\bar{E}_{c}\right\rvert\leq
3\cdot(\beta_{1}(\Gamma)-\beta_{0}(\Gamma)).$

Now suppose the bounds are true for all graphs with $<k$ boundary points and
suppose that $\left\lvert\partial\Gamma\right\rvert=k$. Let
$v\in\partial\Gamma$. Then let
$\Gamma^{\prime}=\Gamma-(\operatorname{St^{-}}(v,\Gamma)\cup\operatorname{St^{+}}(v,\Gamma))$.
By attaching a segment to $\Gamma^{\prime}$ we add at most two elements to
$\bar{V}$, and possibly two elements to $\bar{E}$ as we may need to divide an
element of $\bar{E}(\Gamma^{\prime})$. Hence, by induction the bounds hold. ∎

###  3.1. The fibre product graph

Let $\gamma:\Gamma\to\Delta$ and $\lambda:\Lambda\to\Delta$ be two graph maps.
Define the _fibre product graph_ of $\Gamma$ and $\Lambda$ as the graph
$\Gamma\times_{\Delta}\Lambda$ with vertex set:

$V(\Gamma\times_{\Delta}\Lambda)=\\{(u,v)\in V(\Gamma)\times
V(\Lambda)\mid\gamma_{V}(u)=\lambda_{V}(v)\\}$

and edge set:

$E(\Gamma\times_{\Delta}\Lambda)=\\{(e,f)\in E(\Gamma)\times
E(\Lambda)\mid\gamma_{E}(e)=\lambda_{E}(f)\\}.$

The origin and target maps $o,t:E(\Gamma\times_{\Delta}\Lambda)\to
V(\Gamma\times_{\Delta}\Lambda)$ will then be given by $o(e,f)=(o(e),o(f))$
and $t(e,f)=(t(e),t(f))$. We will denote by
$p_{\Gamma},p_{\Lambda}:\Gamma\times_{\Delta}\Lambda\to\Gamma,\Lambda$ the
natural projection maps. If our graphs have marked vertices, then we will
define the marked vertices of $\Gamma\times_{\Delta}\Lambda$ to be

$\displaystyle V^{i}(\Gamma\times_{\Delta}\Lambda)$ $\displaystyle=\\{(v,w)\in
V^{i}(\Gamma)\times V^{i}(\Lambda)\mid\gamma(v)=\lambda(w)\\},$ $\displaystyle
V^{f}(\Gamma\times_{\Delta}\Lambda)$ $\displaystyle=\\{(v,w)\in
V^{f}(\Gamma)\times V^{f}(\Lambda)\mid\gamma(v)=\lambda(w)\\}.$

In general, as pointed out in [6], the following is satisfied:

$\left\lvert E(\Gamma\times_{\Delta}\Lambda)\right\rvert=\sum_{e\in
E(\Delta)}\left\lvert\gamma_{E}^{-1}(e)\right\rvert\cdot\left\lvert\lambda_{E}^{-1}(e)\right\rvert.$

If $\gamma$ and $\lambda$ are finite covers, then
$\Gamma\times_{\Delta}\Lambda$ is equal to its core. Hence, a quadratic bound
on the edges and vertices is best possible. The following lemma demonstrates a
similar relationship between $\left\lvert\bar{E}(\Gamma)\right\rvert$,
$\left\lvert\bar{E}(\Lambda)\right\rvert$ and
$\left\lvert\bar{E}(\operatorname{Core^{rel}}(\Gamma\times_{\Delta}\Lambda))\right\rvert$
when $\gamma$ and $\lambda$ are forwards immersions.

######  Lemma 3.7.

Let $\gamma:\Gamma\to\Delta$ and $\lambda:\Lambda\to\Delta$ be forwards
immersions of graphs. If
$\Theta=\operatorname{Core^{rel}}(\Gamma\times_{\Delta}\Lambda)$, then

$\left\lvert\bar{V}(\Theta)\right\rvert,\left\lvert\bar{E}(\Theta)-\bar{E}_{c}(\Theta)\right\rvert\leq
4\cdot\left(\left\lvert V^{i}(\Gamma)\right\rvert\cdot\left\lvert
V^{i}(\Lambda)\right\rvert+\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert\right).$

###### Proof.

Let $V^{\prime}\subset V(\Theta)$ be the vertices with outdegree two or more.
By removing these vertices and taking the closure, we obtain a disjoint union
of graphs $\sqcup_{i=1}^{n}\Theta_{i}$ along with a surjective quotient map
$q:\sqcup_{i=1}^{n}\Theta_{i}\to\Theta$. Each graph $\Theta_{i}$ has the
property that $\operatorname{deg^{+}}(v)\leq 1$ by construction. Furthermore,
$q:\bar{V}(\sqcup_{i=1}^{n}\Theta_{i})\to\bar{V}(\Theta)$ is surjective and
$q:\bar{E}(\sqcup_{i=1}^{n}\Theta_{i})\to\bar{E}(\Theta)$ is bijective. We
have at most

$\left\lvert V^{i}(\Theta)\right\rvert+\sum_{v\in
V^{\prime}}\operatorname{deg^{+}}(v)\leq\left\lvert
V^{i}(\Gamma)\right\rvert\cdot\left\lvert
V^{i}(\Lambda)\right\rvert+\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert$

many leaf vertices in $\sqcup_{i=1}^{n}\Theta_{i}$. Hence

$\sum_{i=1}^{n}\left\lvert\partial\Theta_{i}\right\rvert\leq
2\cdot\left(\left\lvert V^{i}(\Gamma)\right\rvert\cdot\left\lvert
V^{i}(\Lambda)\right\rvert+\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert\right).$

Thus, since $\beta_{1}(\Theta_{i})\leq 1$ for all $i$, the bounds follow by
Lemma 3.6. ∎

##  4\. The structure of $\Gamma\times_{\Delta}S^{1}$

Let us fix a graph map $\gamma:\Gamma\to\Delta$ and a primitive loop
$w:I\to\Delta$. A cycle $f:S^{1}\to\Gamma$ is a _$w$ -cycle_ if $f$ factors
through $\hat{w}$. A path $f:I\to\Gamma$ will be called a _$w$ -path_ if
$\gamma\circ f$ factors surjectively through $\hat{w}$. The projection of the
$w$-path to $\Delta$ can be factorised like a word:

$\gamma\circ f=w^{\prime}*w^{n}*w^{\prime\prime}$

where $w^{\prime}$ and $w^{\prime\prime}$ are a proper suffix and a proper
prefix of $w$ respectively. We call this a _$w$ -factorisation of $f$_. The
following Lemma follows from Lemma 2.6:

######  Lemma 4.1.

If $f:I\to\Gamma$ is a $w$-path, then it has a unique $w$-factorisation.
$\hfill\qed$

The _$w$ -length_ of a $w$-path $f:I\to\Gamma$ is the number $n=|f|_{w}$ such
that $\gamma\circ f=w^{\prime}*w^{n}*w^{\prime\prime}$ is the
$w$-factorisation of $f$. By Lemma 4.1 this is always well defined.

A $w$-path $f^{\prime}$ _right extends_ $f$, or is a _right extension of $f$_,
if $f$ is a proper prefix of $f$. If $f$ is a proper suffix of $f^{\prime}$,
then we say $f^{\prime}$ _left extends_ $f$. A $w$-path is a _simple $w$-path_
if

$f(k+i\cdot|w|)\neq f(k+j\cdot|w|)$

for all integers $i<j$ and $k$, unless $k+j\cdot|w|=|f|$. We refer to $f$ as
_right maximal_ if $f$ is a simple $w$-path and there is no simple $w$-path
$f^{\prime}$ which right extends $f$. We similarly define _left maximal_. We
refer to $f$ as _maximal_ if it is both left and right maximal. We also refer
to $f$ as _right submaximal_ if either $f$ is right maximal, or $f$ is simple
and $t(f)\in\bar{V}(\Gamma)\cup V^{f}(\Gamma)$. Similarly, we say $f$ is _left
submaximal_ if either $f$ is left maximal, or if $f$ is a simple $w$-path and
$o(f)\in\bar{V}(\Gamma)\cup V^{i}(\Gamma)$. Then _submaximal_ $w$-paths are
those that are both left and right submaximal. Denote by
$\operatorname{\mathcal{M}}(\gamma,w)$ the set of maximal $w$-paths in
$\Gamma$ and by $\operatorname{\mathcal{SM}}(\gamma,w)$ the set of submaximal
$w$-paths in $\Gamma$. Defining:

$\displaystyle\operatorname{\mathcal{M}_{\text{sub}}}(\gamma,w)$
$\displaystyle=\operatorname{\mathcal{L}_{\text{sub}}}(\gamma,w)\cap\operatorname{\mathcal{M}}(\gamma,w),$
$\displaystyle\operatorname{\mathcal{M}_{\text{overlap}}}(\gamma,w)$
$\displaystyle=\operatorname{\mathcal{L}_{\text{overlap}}}(\gamma,w)\cap\operatorname{\mathcal{M}}(\gamma,w),$
$\displaystyle\operatorname{\mathcal{SM}_{\text{sub}}}(\gamma,w)$
$\displaystyle=\operatorname{\mathcal{L}_{\text{sub}}}(\gamma,w)\cap\operatorname{\mathcal{SM}}(\gamma,w),$
$\displaystyle\operatorname{\mathcal{SM}_{\text{overlap}}}(\gamma,w)$
$\displaystyle=\operatorname{\mathcal{L}_{\text{overlap}}}(\gamma,w)\cap\operatorname{\mathcal{SM}}(\gamma,w),$

we get decompositions

$\displaystyle\operatorname{\mathcal{M}}(\gamma,w)$
$\displaystyle=\operatorname{\mathcal{M}_{\text{sub}}}(\gamma,w)\sqcup\operatorname{\mathcal{M}_{\text{overlap}}}(\gamma,w),$
$\displaystyle\operatorname{\mathcal{SM}}(\gamma,w)$
$\displaystyle=\operatorname{\mathcal{SM}_{\text{sub}}}(\gamma,w)\sqcup\operatorname{\mathcal{SM}_{\text{overlap}}}(\gamma,w).$

######  Remark 4.2.

If $\gamma:\Gamma\to\Delta$ is a forwards immersion, then maximal right
extensions of $w$-paths are unique. However, there may be several left maximal
extensions if $\gamma$ is not an immersion.

The following lemmas follow directly from the definitions, but we record them
for later use.

######  Lemma 4.3.

Let $\gamma:\Gamma\to\Delta$ be a forwards immersion and $w:I\to\Delta$ a
primitive loop. Every $w$-path $f:I\to\Gamma$ has a unique decomposition:

$f=f_{s}*f_{c}^{n}*f_{c}^{\prime}$

for some $n\geq 0$ and where

  1. (1)

$f_{s}*f_{c}$ is a simple $w$-path,

  2. (2)

$f_{c}$ is a simple $w$-cycle,

  3. (3)

$f_{c}^{\prime}$ is a proper prefix of $f_{c}$.

Furthermore, $f$ is simple if and only if $n\leq 1$ and
$f_{c}^{\prime}=\epsilon$. $\hfill\qed$

######  Lemma 4.4.

Let $\gamma:\Gamma\to\Delta$ be a graph map and $w:I\to\Delta$ a primitive
loop. Let $f:I\to\Gamma$ be an admissible path with a factorisation

$f=f_{1}*f_{w}*f_{2}$

with $f_{w}$ a maximal $w$-path in $I$. Then if
$f_{w}=f_{s}*f_{c}^{n}*f_{c}^{\prime}$ is the factorisation from Lemma 4.3,
$f_{s}*f_{c}$ is submaximal and $f_{c}^{\prime}$ is a submaximal prefix of
$f_{c}$. $\hfill\qed$

Extending our definition of $w$-paths to graphs, we say a graph map
$W\to\Delta$ is a _$w$ -graph map_ if it factors surjectively through the map
$\hat{w}:S^{1}\to\Delta$. The graph $W$ will then be called a _$w$ -graph_.

######  Lemma 4.5.

Let $W$ be a connected graph and $W\to S^{1}$ a forwards immersion. Then $W$
is one of the following:

  1. (1)

A rooted tree,

  2. (2)

a cycle with rooted trees attached along their root vertices.$\hfill\qed$

Every $w$-path factors through $\Gamma\times_{\Delta}S^{1}$, but this is not
quite a $w$-graph as it contains components that don’t surject onto $S^{1}$.
So denote by $\Omega_{\gamma,w}\subset\Gamma\times_{\Delta}S^{1}$ the subgraph
consisting of the $w$-graph components. Call this _the $w$-graph of $\Gamma$_
and denote by $p_{w}:\Omega_{\gamma,w}\to S^{1}$ the projection map. We will
further define the subgraph $\Omega_{\gamma,w}^{k}\subset\Omega_{\gamma,w}$
consisting of the components which support a $w$-path of $w$-length at least
$k$.

The following Lemma is a graph version of Lemma 2.6.

######  Lemma 4.6.

Let $f:I\to\Gamma$ be a path with $|f|\geq|w|$ and
$p_{\Gamma}:\Omega_{\gamma,w}\to\Gamma$ the projection map, then:

$\left\lvert\operatorname{\mathcal{L}}(p_{\Gamma},f)\right\rvert\leq 1.$

###### Proof.

If $\tilde{f}:I\to\Omega_{\gamma,w}$ is a lift of $f$, then $f$ has a
$w$-factorisation. If $|f|\geq|w|$, by Lemma 2.6, $f$ has a unique
$w$-factorisation and so $o(p_{w}\circ\tilde{f})$ is uniquely determined by
this factorisation. By the construction of the fibre product graph, it follows
that there can be at most one lift of $f$ to $\Omega_{\gamma,w}$. ∎

###  4.1. $w$-paths

In this section we will fix a graph map $\gamma:\Gamma\to\Delta$ and a
primitive loop $w:I\to\Delta$. The aim of this section will be to prove bounds
on the number of $w$-lengths that $w$-paths in $\Gamma$ can have.

First, we define a type of factorisation of paths relative to a subgraph.

######  Definition 4.7.

Let $\Gamma^{\prime}\subset\Gamma$ be a subgraph and $f:I\to\Gamma$ a path. If
$f$ does not factor through $\Gamma-\bar{V}(\Gamma)$, the _$\Gamma^{\prime}$
-factorisation_ of $f$ is the factorisation of the form:

$f=e_{0}[-l:]*w_{1}*e_{1}*...*e_{n-1}*w_{n}*e_{n}[:m],$

where:

  1. (1)

$o(w_{i})$, $t(w_{i})\in\bar{V}(\Gamma)$,

  2. (2)

$w_{i}$ is supported in $\Gamma^{\prime}\cup\bar{V}(\Gamma)$,

  3. (3)

$e_{0}$, $e_{n}\in\bar{E}(\Gamma)$,

  4. (4)

$e_{1},...,e_{n-1}\in\bar{E}(\Gamma)-\bar{E}(\Gamma^{\prime})$,

  5. (5)

$n$ is maximal possible among all such factorisations.

If $f$ does factor through $\Gamma-\bar{V}(\Gamma)$, then by convention the
$\Gamma^{\prime}$-factorisation of $f$ will be $e_{0}[l:m]$ for some
$e_{0}\in\bar{E}(\Gamma)$.

The following lemma follows from the definition.

######  Lemma 4.8.

$\Gamma^{\prime}$-factorisations are unique. $\hfill\qed$

Denote by $\bar{E}_{w}(\Gamma)\subset\bar{E}(\Gamma)$ the elements $e$ such
that $|e|<|w|$. Then denote by

$\Gamma_{w}=\cup_{e\in\bar{E}_{w}(\Gamma)}e$

the subgraph of $\Gamma$ induced by $\bar{E}_{w}(\Gamma)$.

######  Definition 4.9.

We will call a vertex $v\in V(\Gamma)$ a _$w$ -sink_ if there is a $w$-path
$f:I\to\Gamma_{w}$ satisfying the following:

  1. (1)

$o(f)$, $t(f)\in\bar{V}(\Gamma)$,

  2. (2)

$\gamma\circ f=w^{\prime}*w*w^{\prime\prime}$ for some proper suffix
$w^{\prime}$ of $w$ and proper prefix $w^{\prime\prime}$ of $w$,

  3. (3)

$f(|w^{\prime}*w|)=v$.

Denote by $V_{w}(\Gamma)\subset V(\Gamma_{w})$ the set of all $w$-sinks of
$\Gamma$.

The $w$-sinks of a graph can be thought of as a set of vertices any
sufficiently long $w$-path must visit. We now show that there cannot be too
many of such vertices.

######  Lemma 4.10.

There is a cyclic shift $w_{0}$ of $w$ such that:

$\left\lvert V_{w_{0}}(\Gamma)\right\rvert\leq
2\cdot\left\lvert\bar{E}(\Gamma_{w})\right\rvert.$

###### Proof.

Since a cycle doesn’t have any $w$-sinks, we may assume that
$\bar{E}_{c}(\Gamma)=\emptyset$. Now let $w=x*y$ with $x\neq\epsilon$ such
that $w_{0}=y*x$ is the cyclic shift of $w$ from Theorem 2.17 with

$\\{x_{1},...,x_{n}\\}=\\{\gamma\circ e\mid e\in\bar{E}(\Gamma_{w})\\}.$

For each $v\in V_{w_{0}}(\Gamma)$, let $f_{v}:I\to\Gamma_{w}$ be a
$w_{0}$-path such that: $o(f_{v})$, $t(f_{v})\in\bar{V}(\Gamma_{w})$,
$\gamma\circ f_{v}=w_{v}^{\prime}*w_{0}*w_{v}^{\prime\prime}$ and
$f_{v}(|w_{v}^{\prime}*w_{0}|)=v$. Denote by

$\bar{t}\left(f_{v}\left[:\left\lvert
w_{v}^{\prime}*w_{0}\right\rvert\right]\right)=(e_{v},i_{v})\in\bar{E}(\Gamma_{w})\times\mathbb{N}$

Now by Theorem 2.17, we have:

$\left\lvert\\{(e_{v},i_{v})\\}_{v\in
V_{w_{0}}(\Gamma)}\cap\\{e\\}\times\mathbb{N}\right\rvert\leq 2,$

for all $e\in\bar{E}(\Gamma_{w})$, thus obtaining the desired inequality. ∎

######  Lemma 4.11.

If $\gamma:\Gamma\to\Delta$ is a forwards immersion, then:

$\left\lvert V_{w}(\Gamma)\right\rvert\leq
2\cdot\left\lvert\bar{E}(\Gamma_{w})\right\rvert.$

###### Proof.

Since a cycle doesn’t have any $w$-sinks, we may assume that
$\bar{E}_{c}(\Gamma)=\emptyset$. Now let $w=x*y$ with $x\neq\epsilon$ such
that $y*x$ is the cyclic shift of $w$ from Theorem 2.17 with

$\\{x_{1},...,x_{n}\\}=\\{\gamma\circ e\mid e\in\bar{E}(\Gamma_{w})\\}.$

For each $v\in V_{w}$, let $f_{v}:I\to\Gamma_{w}$ be a $w$-path such that:
$o(f_{v})$, $t(f_{v})\in\bar{V}(\Gamma)$, $\gamma\circ
f_{v}=w_{v}^{\prime}*w*w_{v}^{\prime\prime}$ and
$f_{v}(|w_{v}^{\prime}*w|)=v$. Denote by

$\bar{t}(f_{v}[:\left\lvert
w_{v}^{\prime}*x\right\rvert])=(e_{v},i_{v})\in\bar{E}(\Gamma_{w})\times\mathbb{N}$

This is well defined since $x\neq\epsilon$. Since $\gamma$ is a forwards
immersion, $(e_{v},i_{v})=(e_{v^{\prime}},i_{v^{\prime}})$ if and only if
$v=v^{\prime}$. Now by Theorem 2.17, we have:

$\left\lvert\\{(e_{v},i_{v})\\}_{v\in
V_{w}(\Gamma)}\cap\\{e\\}\times\mathbb{N}\right\rvert\leq 2,$

for all $e\in\bar{E}(\Gamma_{w})$, thus obtaining the desired inequality. ∎

Using these bounds on $w$-sinks and $\Gamma_{w}$-factorisations, we prove
something about general $w$-paths.

######  Lemma 4.12.

Let $f:I\to\Gamma$ be a simple $w$-path that does not factor through
$\Gamma-\bar{V}(\Gamma)$. Let

$f=e_{0}[-l:]*w_{1}*e_{1}*...*e_{n-1}*w_{n}*e_{n}[:m],$

be its $\Gamma_{w}$-factorisation. Then:

  1. (1)

$e_{i}=e_{j}$ if and only if $i=j$ for all $1\leq i,j<n$,

  2. (2)

if $l\geq\left\lvert w\right\rvert$ or $m\geq\left\lvert w\right\rvert$, then
$e_{0}\neq e_{i}$ or $e_{m}\neq e_{i}$ for all $1\leq i<n$ respectively,

  3. (3)

$\sum_{i=1}^{n}\left\lvert w_{i}\right\rvert_{w}\leq
4\cdot\left\lvert\bar{E}(\Gamma_{w})\right\rvert$,

  4. (4)

if $\gamma$ is a forwards immersion, then $\sum_{i=1}^{n}\left\lvert
w_{i}\right\rvert_{w}\leq 2\cdot\left\lvert\bar{E}(\Gamma_{w})\right\rvert$

###### Proof.

Since $f$ is a simple $w$-path, it lifts to $\Omega_{\gamma,w}$ as a simple
path. As the lift is simple as a path, it can only traverse each edge in
$\Omega_{\gamma,w}$ at most once. Hence by Lemma 4.6, properties 1 and 2
follow. Property 3 follows from Lemma 4.10, the pigeonhole principle and the
fact that $w^{2}$ contains a copy of each cyclic shift of $w$ as a subword.
More directly, property 4 follows from Lemma 4.11. ∎

A direct consequence of Lemma 4.12 is that if $f:I\to\Gamma$ is a simple
$w$-path, then:

$\left\lvert f\right\rvert_{w}\leq
4\cdot\left\lvert\bar{E}(\Gamma)\right\rvert+\sum_{e\in\bar{E}(\Gamma)}\left\lfloor\frac{\left\lvert
e\right\rvert}{\left\lvert w\right\rvert}\right\rfloor.$

The following theorem is an important ingredient in our main results.

######  Theorem 4.13.

Suppose $\gamma:\Gamma\to\Delta$ is a forwards immersion. There are at most
$10\cdot\left\lvert\bar{E}(\Gamma)\right\rvert+3\cdot\left\lvert
V^{i}(\Gamma)\right\rvert$ integers $n\geq 1$ such that there is a right
maximal $w$-path $f\in\operatorname{\mathcal{SM}_{\text{overlap}}}(\gamma,w)$
with $|f|_{w}=n$.

###### Proof.

We may assume that $\Gamma$ is connected. If
$\left\lvert\bar{E}(\Gamma)\right\rvert=1$, then Lemma 2.6 tells us there can
be at most $2+\left\lvert V^{i}(\Gamma)\right\rvert$ such integers $n$: one
integer for the maximal $w$-prefix of $e\in\bar{E}(\Gamma)$, one integer for
the maximal $w$-suffix of $e$ and one integer for each vertex in
$V^{i}(\Gamma)$ from which a $w$-path may begin. So from now on we assume that
$\left\lvert\bar{E}(\Gamma)\right\rvert\geq 2$. Let $f:I\to\Gamma$ be a right
maximal submaximal $w$-path and let

$f=e_{0}[-l:]*w_{1}*e_{1}*...*w_{n}*e_{n}[:m]$

be its $\Gamma_{w}$-factorisation. If $f$ is a loop, we may assume that
$o(f),t(f)\in\bar{V}(\Gamma)$. Since $f$ is a $w$-path, each subpath $e_{i}$
and $w_{i}$ has a well defined $w$-factorisation. So let:

$\displaystyle\gamma\circ e_{0}[-l:]$
$\displaystyle=w_{e_{0}}^{\prime}*w^{q_{0}}*w_{e_{0}}^{\prime\prime}$
$\displaystyle\gamma\circ e_{i}$
$\displaystyle=w_{e_{i}}^{\prime}*w^{q_{i}}*w_{e_{i}}^{\prime\prime}$
$\displaystyle\gamma\circ e_{n}[:m]$
$\displaystyle=w_{e_{n}}^{\prime}*w^{q_{n}}*w_{e_{n}}^{\prime\prime}$
$\displaystyle\gamma\circ w_{i}$
$\displaystyle=w_{i}^{\prime}*w^{k_{i}}*w_{i}^{\prime\prime}$

be the relevant $w$-factorisations. Denote by $V_{f}\subset V(\Gamma)$ the set
of vertices that fall into one of the following categories:

  1. (1)

$v=e_{i}(\left\lvert w_{e_{i}}^{\prime}\right\rvert)$ for some $1\leq i<n$,
or,

  2. (2)

$v=e_{0}(-l+\left\lvert w_{0}^{\prime}\right\rvert)$ if $l\geq|w|$, or,

  3. (3)

$v=e_{n}(\left\lvert w_{e_{n}}^{\prime}\right\rvert)$ if $q_{n}\geq 1$, or,

  4. (4)

$v=w_{i}(\left\lvert w_{i}^{\prime}*w^{j}\right\rvert)$ for some $i\geq 1$ and
$1\leq j\leq k_{i}$, or,

  5. (5)

$v=w_{1}(\left\lvert w_{1}^{\prime}\right\rvert)$ if $l\geq|w|$, or,

  6. (6)

$v=w_{i}(\left\lvert w_{i}^{\prime}\right\rvert)$ for some $i\geq 2$.

By the definition of $\Gamma_{w}$-factorisations, each vertex of type (1) and
(3) is contained in some element $e\in\bar{E}(\Gamma)-\bar{E}_{w}(\Gamma)$.
Moreover, these are independent of $f$ by Lemma 2.6. Hence there can be at
most $\left\lvert\bar{E}(\Gamma)-\bar{E}_{w}(\Gamma)\right\rvert$ many
vertices $v\in\bigcup_{f}V_{f}$ of type (1) or (3), where the union is over
all right maximal submaximal $w$-paths. Since either $o(e_{0}[-l:])\in
V^{i}(\Gamma)$, or $e_{0}[-l:]$ is a left maximal $w$-path, there can be at
most $\left\lvert\bar{E}(\Gamma)-\bar{E}_{w}(\Gamma)\right\rvert+\left\lvert
V^{i}(\Gamma)\right\rvert$ many vertices of type (2). By Lemma 4.11, there are
at most $2\cdot\left\lvert\bar{E}_{w}(\Gamma)\right\rvert$ vertices of type
(4) in $\bigcup_{f}V_{f}$. Since right extensions of $w$-paths are uniquely
defined for forwards immersions, we get a bound of
$\left\lvert\bar{E}(\Gamma)-\bar{E}_{w}(\Gamma)\right\rvert$ for the vertices
of type (5) and (6).

So putting all of this together we get:

$\left\lvert\bigcup_{f}V_{f}\right\rvert\leq
3\cdot\left\lvert\bar{E}(\Gamma)\right\rvert+\left\lvert
V^{i}(\Gamma)\right\rvert.$

To each vertex $v\in\bigcup_{f}V_{f}$, we may associate an integer $k_{v}$
that is the $w$-length of the right maximal $w$-path starting at $v$ with
$w$-factorisation beginning with $w$.

Now let $g:I\to\Gamma$ be a right maximal submaximal $w$-path and let
$g=w^{\prime}*w^{k}*w^{\prime\prime}$ be its $w$-factorisation. Then by
definition of $V_{g}\subset\bigcup_{f}V_{f}$, either $g(\left\lvert
w^{\prime}\right\rvert)\in V_{g}$, $g(\left\lvert w^{\prime}*w\right\rvert)\in
V_{g}$, $g(\left\lvert w^{\prime}*w^{2}\right\rvert)\in V_{g}$ or $\left\lvert
g\right\rvert_{w}\leq 2$. Hence $|g|_{w}=k_{v}$, $|g|_{w}=k_{v}+1$ or
$|g|_{w}=k_{v}+2$ for some $v\in\bigcup_{f}V_{f}$, or $|g|_{w}\leq 2$. So $k$
can be one of at most
$3\cdot\left(3\cdot\left\lvert\bar{E}(\Gamma)\right\rvert+\left\lvert
V^{i}(\Gamma)\right\rvert\right)+2$ distinct integers. Since we assumed that
$\left\lvert\bar{E}(\Gamma)\right\rvert\geq 2$, we obtain the desired upper
bound. ∎

######  Remark 4.14.

If we wanted to relax the assumptions of Theorem 4.13 to encompass general
graph maps, then the number of integers $n$ needed could be exponential in
$\left\lvert\bar{E}(\Gamma)\right\rvert$.

######  Theorem 4.15.

Suppose that $\gamma:\Gamma\to\Delta$ is a forwards immersion and let
$(u,v)\in V(\Gamma)\times V(S^{1})$. There is a regular language of the form:

$L=(a^{n_{1}}+...+a^{n_{k}})\cdot(a^{n})^{*}\subset(a)^{*}$

such that, for any path $f:I\to\Omega_{\gamma,w}$ where $t(f)=(u,v)$ and
$p_{\Gamma}\circ f$ is a left submaximal $w$-path, we have $a^{|f|_{w}}\in L$.
Furthermore, we have that:

$k\leq 10\cdot\left\lvert\bar{E}(\Gamma)\right\rvert+3\cdot\left\lvert
V^{i}(\Gamma)\right\rvert.$

###### Proof.

The fact that the regular language is of the given form is by Lemma 4.5. If
there is an $f:I\to\Omega_{\gamma,w}$ such that $t(f)=(u,v)$, $p_{\Gamma}\circ
f$ is a left submaximal $w$-path and $p_{\Gamma}\circ f$ does not contain any
vertex in $\bar{V}(\Gamma)$ in its image, then $k=1$ and $n=0$. So, assuming
that no such path exists, the proof of the bound on the number of integers is
identical to that of Theorem 4.13. ∎

######  Remark 4.16.

We have stated Theorems 4.13 and 4.15 for left submaximal $w$-paths, but the
analogous results for right submaximal paths also hold with virtually the same
proof if we replace $V^{i}(\Gamma)$ with $V^{f}(\Gamma)$.

###  4.2. $w$-cycles

The following theorem was conjectured in [30] in connection with coherence of
one-relator groups and became known as the $w$-cycles conjecture. It was then
proved independently in [11] and [19].

######  Theorem 4.17.

Let $\gamma:\Gamma\to\Delta$ be an immersion and $\hat{w}:S^{1}\to\Delta$ a
primitive cycle. Then:

$\beta_{0}(\operatorname{Core}(\Gamma\times_{\Delta}S^{1}))\leq\beta_{1}(\Gamma).$

If we want to allow $\hat{w}$ to be imprimitive, then it follows that the map
$\operatorname{Core}(\Gamma\times_{\Delta}S^{1})\to\Delta$ consists of at most
$\beta_{1}(\Gamma)$ many free homotopy classes of cycles. We here prove
Theorem 4.20 from the introduction, generalising this result in some sense to
arbitrary unions of cycles.

######  Lemma 4.18.

Let $\gamma:\Gamma\to\Delta$ be a graph map and $w:I\to\Delta$ a primitive
loop. Let $f:S^{1}\to\Gamma$ be a primitive cycle with $\deg(\gamma\circ
f)\geq 12\cdot\beta_{1}(\Gamma)$. Then there is some $e\in\bar{E}(\Gamma)$
such that $f$ traverses $e$ and $\left\lvert e\right\rvert\geq
2\cdot\left\lvert w\right\rvert$.

###### Proof.

We may assume that $\Gamma$ is connected and core. If $\Gamma$ is a cycle then
the result is clear, so suppose that it is not. By Lemma 3.6,
$\left\lvert\bar{E}(\Gamma)\right\rvert\leq 3\cdot(\beta_{1}(\Gamma)-1)$. Let
$g:I\to\Gamma$, $w:I\to\Delta$ be loops such that $\hat{g}=f$ and $\gamma\circ
g=w^{\deg(f)}$. Then $\left\lvert
g\right\rvert_{w}>4\cdot\left\lvert\bar{E}(\Gamma)\right\rvert$. Now we simply
apply the pigeonhole principle to Lemma 4.12. ∎

######  Theorem 4.19.

Let $\gamma:\Gamma\to\Delta$ be a forwards immersion of graphs. There is a
unique graph map $s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ where
$\mathbb{S}_{\Gamma}$ is a disjoint union of at most $\beta_{1}(\Gamma)$
circles such that, if $f:S^{1}\to\Gamma$ is a cycle satisfying:

$\frac{\deg(\gamma\circ f)}{\deg(f)}\geq 12\cdot\beta_{1}(\Gamma),$

then $f$ factors through $s_{\Gamma}$.

###### Proof.

Each such cycle factors through a primitive cycle $g:S^{1}\to\Gamma$ such that
$\deg(\gamma\circ g)\geq 12\cdot\beta_{1}(\Gamma)$. Hence, let
$s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ be the union over all such cycles.
Let $f_{1},...,f_{n}:S^{1}\to\Gamma$ be the cycles in $\mathbb{S}_{\Gamma}$.
Let $w_{i}:I\to\Delta$ be a primitive loop such that $f_{i}$ is a
$w_{i}$-cycle. Assume that $\left\lvert w_{i}\right\rvert\geq\left\lvert
w_{i+1}\right\rvert$. By Lemma 4.18, for each $f_{i}$ there is an element
$e_{i}\in\bar{E}(\Gamma)$ such that $e_{i}$ is a $w_{i}$-path with
$\left\lvert e_{i}\right\rvert\geq 2\cdot\left\lvert w_{i}\right\rvert$. If
$f_{j}$ traverses $e_{i}$ for any $i<j$, up to replacing $w_{i}$ with a cyclic
conjugate of itself, $w_{i}^{2}$ has period $\left\lvert
w_{j}\right\rvert\leq\left\lvert w_{i}\right\rvert$. Since $w_{i}$ and $w_{j}$
are primitive, it follows from Corollary 2.2 that $w_{i}$ is a cyclic
conjugate of $w_{j}$. But since $\gamma$ was a forwards immersion, it then
also follows that $f_{i}=f_{j}$. Hence $f_{i}$ is supported in
$\Gamma-\\{e_{1},...,e_{i-1}\\}$. As
$\Gamma-\\{e_{1},...,e_{\beta_{1}(\Gamma)}\\}$ is a forest, we must have
$n\leq\beta_{1}(\Gamma)$. ∎

Equivalently, we may restate Theorem 4.19 as follows.

######  Theorem 4.20.

Let $\gamma:\Gamma\to\Delta$ and $\lambda:\mathbb{S}\to\Delta$ be graph
immersions with $\mathbb{S}=\sqcup S^{1}$. If $\lambda|_{S^{1}}$ is primitive
for each $S^{1}\subset\mathbb{S}$, then there are at most $\beta_{1}(\Gamma)$
many components $S^{1}\subset\mathbb{S}$ such that:

$\deg(p_{\mathbb{S}}|_{S^{1}})\geq 12\cdot\beta_{1}(\Gamma).$

$\hfill\qed$

###  4.3. $w$-graphs

The following results can also be thought of as generalisations of Theorem
4.17 as we do not only consider the core of the fibre product. Furthermore,
the graph maps no longer need to be immersions.

######  Theorem 4.21.

Let $\gamma:\Gamma\to\Delta$ be a forwards immersion and
$\hat{w}:S^{1}\to\Delta$ a primitive cycle. There are at most
$2\cdot\left\lvert\bar{E}(\Gamma)\right\rvert$ components of
$\Omega_{\gamma,w}^{3}$ that do not factor through $\Gamma-\bar{V}(\Gamma)$.

###### Proof.

Let $\\{f_{i}:I\to\Gamma\\}_{i=1}^{k}$ be a collection of $w$-paths containing
at most one of maximal $w$-length for each component of
$\Omega_{\gamma,w}^{3}$ that does not factor through $\Gamma-\bar{V}$.
Consider the $\Gamma_{w}$-factorisations for each

$f_{i}=e_{i,0}[-l_{i}:]*w_{i,1}*e_{i,1}...*w_{i,n_{i}}*e_{i,n_{i}}[:m_{i}].$

Since $f_{i}$ does not factor through $\Gamma-\bar{V}(\Gamma)$, $n_{i}\geq 1$
for all $i$. Since $\left\lvert f_{i}\right\rvert_{w}\geq 3$ for all $i$, we
may divide our set of paths into three types:

  1. (1)

those with $n_{i}>1$,

  2. (2)

those with $n_{i}=1$ and $|w_{i,1}|_{w}\geq 1$,

  3. (3)

those with $n_{i}=1$, $|w_{i,1}|_{w}=0$ and $|e_{i,0}[-l_{i}:]|_{w}\geq 1$ or
$|e_{i,1}[:m_{i}]|_{w}\geq 1$.

By Lemma 4.6, there can be at most
$2\cdot\left\lvert\bar{E}(\Gamma)-\bar{E}_{w}(\Gamma)\right\rvert$ paths
$f_{i}$ in case 1 or 3. By Lemma 4.11 there can be at most
$2\cdot\left\lvert\bar{E}_{w}(\Gamma)\right\rvert$ many paths $f_{i}$ in case
2. ∎

######  Theorem 4.22.

Let $\gamma:\Gamma\to\Delta$ be a graph map and $\hat{w}:S^{1}\to\Delta$ a
primitive cycle. There are at most
$2\cdot\left\lvert\bar{E}(\Gamma)\right\rvert$ components of
$\Omega_{\gamma,w}^{4}$ that don’t factor through $\Gamma-\bar{V}(\Gamma)$.

###### Proof.

Let $w=x*y$ with $x\neq\epsilon$ such that $w_{0}=y*x$ is the cyclic shift of
$w$ from Lemma 4.10. Now if we replace the use of Lemma 4.11 in the proof of
Theorem 4.21 for Lemma 4.10, we get the same bound for
$\Omega^{3}_{\gamma,w_{0}}$. Since each component of $\Omega^{4}_{\gamma,w}$
is a component of $\Omega^{3}_{\gamma,w_{0}}$, we obtain the bound. ∎

Theorems 4.21 and 4.22 are sharp as is demonstrated by Example 4.23. Obtaining
similar statements for $\Omega_{\gamma,w}$ appears harder.

######  Example 4.23.

Let $\Delta$ be the graph with four edges and one vertex. Let
$E(\Delta)=\\{a_{1},a_{2},a_{3},a_{4}\\}$ and
$w_{i}=a_{i}*a_{i+1}*a_{i+2}*a_{i+3}$ where the indices are taken mod $4$. Now
for each integer $n\geq 1$, consider the graph immersion
$\gamma:\Gamma\to\Delta$ with $\left\lvert\bar{V}(\Gamma)\right\rvert=n$
depicted in Figure 2 when $n$ is even and in Figure 3 when $n$ is odd. We have
$\left\lvert\bar{E}(\Gamma)\right\rvert=2\cdot n$ and
$\Omega_{\gamma,w_{1}}^{3}$ has precisely $4\cdot n$ many components, none of
which factor through $\Gamma-\bar{V}(\Gamma)$.

Figure 2. When $n$ is even. Figure 3. When $n$ is odd.

##  5\. The structure of $\Gamma\times_{\Delta}\Lambda$

From now on we will always assume that $\gamma:\Gamma\to\Delta$ and
$\lambda:\Lambda\to\Delta$ are forwards immersions of graphs. For convenience
we also assume that $\Gamma$ and $\Lambda$ are connected and relatively core.
Let $s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ and
$s_{\Lambda}:\mathbb{S}_{\Lambda}\to\Lambda$ be the graphs from Theorem 4.19.
We will refer to $\mathbb{S}_{\Gamma}$ and $\mathbb{S}_{\Lambda}$ as _the long
cycles_ of $\Gamma$ and $\Lambda$ respectively. Then we define:

$\displaystyle\theta:\Theta$
$\displaystyle=\operatorname{Core^{rel}}(\Gamma\times_{\Delta}\Lambda)\to\Delta,$
$\displaystyle s:\mathbb{S}$
$\displaystyle=\operatorname{Core}(\mathbb{S}_{\Gamma}\times_{\Delta}\mathbb{S}_{\Lambda})\to\Theta.$

Define $\Theta^{s}\subset\Theta$ to be the subgraph with edge set

$E(\Theta^{s})=E(\Theta)-E(s(\mathbb{S}))$

and by

$\displaystyle p_{\Gamma}^{s}$ $\displaystyle:\Theta^{s}\to\Gamma$
$\displaystyle p_{\Lambda}^{s}$ $\displaystyle:\Theta^{s}\to\Lambda.$

the restriction maps. Finally, denote by

$\displaystyle C_{\Gamma}$
$\displaystyle=\left\lvert\bar{E}(\Gamma)\right\rvert+\left\lvert
V^{i}(\Gamma)\right\rvert,$ $\displaystyle C_{\Lambda}$
$\displaystyle=\left\lvert\bar{E}(\Lambda)\right\rvert+\left\lvert
V^{i}(\Lambda)\right\rvert.$

###  5.1. Counting lifts

We here apply our $w$-paths results to count certain subsets of lifts to the
fibre product graph. The idea is that we will apply this to elements of
$\bar{E}(\Gamma)$ and $\bar{E}(\Lambda)$ to cover the graph
$\operatorname{Core^{rel}}(\Gamma\times_{\Delta}\Lambda)$. The reader should
have in mind the connection between the following Proposition and the results
in Section 2.3 on word overlaps.

######  Proposition 5.1.

Let $g:I\to\Gamma$ be a simple path,
$e\in\bar{E}(\Lambda)-\bar{E}_{c}(\Lambda)$ and $\operatorname{Arith}(p,q,r)$
an arithmetic progression such that $p\cdot q\leq\left\lvert g\right\rvert$.
Then:

$\left\lvert\\{\tilde{g}\in\operatorname{\mathcal{L}}(p^{s}_{\Gamma},g)\mid\bar{o}(p^{s}_{\Lambda}\circ\tilde{g})\in\\{e\\}\times\operatorname{Arith}(p,q,r)\\}\right\rvert\leq
100\cdot C_{\Gamma}\cdot C_{\Lambda}.$

###### Proof.

Let
$\\{\tilde{g}_{1},...,\tilde{g}_{n}\\}=\\{\tilde{g}\in\operatorname{\mathcal{L}}(p^{s}_{\Gamma},g)\mid\bar{o}(p_{\Lambda}\circ\tilde{g})\in\\{e\\}\times\operatorname{Arith}(p,q,r)\\}$
and let $p_{1},...,p_{n}$ be integers such that
$\bar{o}(p_{\Lambda}\circ\tilde{g}_{i})=(e,p_{i})$. Note that since $\gamma$
and $\lambda$ are forwards immersions, each lift of $g$ is uniquely determined
by its origin. Thus, $p_{i}\neq p_{j}$ for all $i\neq j$. We assume that the
$\tilde{g}_{i}$ are ordered such that $p_{1}<...<p_{n}$. By assumption
$p_{n}-p_{1}\leq\left\lvert g\right\rvert$ and $q\mid p_{j}-p_{i}$ for all
$i<j$. By Lemma 2.3, $e[p_{1}:p_{n}]$ has a period of $p_{j}-p_{i}$ for all
$i<j$. If $n\leq 2$, then we are done so we may assume that $n\geq 3$. It
follows that $e[p_{1}:p_{n}]=w^{l}$ for some $l\geq 2$ and $w$ primitive such
that $\left\lvert w\right\rvert\mid p_{j}-p_{i}$ for all $i<j$. Thus, we may
assume without loss that $p=k$, $q=\left\lvert w\right\rvert$ and $r=p_{1}$.

Let $e(p_{i})=v_{i}$. For each $i$, choose a left maximal $w$-path
$h_{i}:I\to\Theta$ such that $t(h_{i})=(o(g),v_{i})$. Note that
$p_{\Lambda}\circ h_{i}$ and $p_{\Gamma}\circ h_{i}$ are both left submaximal
$w$-paths by Lemma 4.4 for all $i\geq 1$. Let $m_{1},...,m_{\alpha},m$ be the
integers from Theorem 4.15 applied to $(o(g),o)\in V(\Gamma)\times V(S^{1})$,
where $o\in V(S^{1})$ is the vertex from which we read off $w$. Similarly, let
$k_{1},...,k_{\beta},k$ be the integers from Theorem 4.15 when applied to
$(e(r),o)\in V(\Lambda)\times V(S^{1})$. We can see that for all $i\geq 1$, we
must have:

$a^{\left\lvert
h_{i}\right\rvert_{w}}\in((a^{k_{1}}+...+a^{k_{\beta}})\cdot(a^{k})^{*}\cdot(\emptyset+a+...+a^{l}))\cap((a^{m_{1}}+...+a^{m_{\alpha}})\cdot(a^{m})^{*}).$

Since $g$ was a simple path, if $m\neq 0$, we must have $l\leq m$. If $k\neq
0$, then also $l\leq k$. By hypothesis, $\tilde{g}_{i}$ is supported in
$\Theta^{s}$ for each $i$. Hence either $k<12\cdot\beta_{1}(\Lambda)$ or
$m<12\cdot\beta_{1}(\Gamma)$ by construction. So if $k,m\neq 0$, then we are
done. So now assume that $k=0$ or $m=0$. This regular language can consist of
at most $\alpha\cdot\beta$ elements. In particular, there are at most
$\alpha\cdot\beta$ many integers $j$ such that

$((a^{k_{1}}+...+a^{k_{\beta}})\cdot(a^{k})^{*}\cdot
a^{j})\cap((a^{m_{1}}+...+a^{m_{\alpha}})\cdot(a^{m})^{*})\neq\emptyset.$

Thus, we have $n\leq\alpha\cdot\beta$. Finally, by Theorem 4.15:

$n\leq\left(10\cdot\left\lvert\bar{E}(\Gamma)\right\rvert+3\cdot\left\lvert
V^{i}(\Gamma)\right\rvert\right)\cdot\left(10\cdot\left\lvert\bar{E}(\Lambda)\right\rvert+3\cdot\left\lvert
V^{i}(\Lambda)\right\rvert\right)\leq 100\cdot C_{\Gamma}\cdot C_{\Lambda}.$

∎

###  5.2. A decomposition of $E(\Theta)$

Let $e\in\bar{E}(\Gamma)$ and $f\in\bar{E}(\Lambda)$. Denote by:

$\Theta(e,f)=p_{\Gamma}^{-1}(e)\cap p_{\Lambda}^{-1}(f)\subset\Theta.$

Then we have a decomposition of $E(\Theta)$ into disjoint sets of edges coming
from each subgraph $\Theta(e,f)$:

$E(\Theta)=\bigsqcup_{e\in\bar{E}(\Gamma)}\bigsqcup_{f\in\bar{E}(\Lambda)}E(\Theta(e,f)).$

######  Lemma 5.2.

Each component of $\Theta(e,f)$ is a segment.

###### Proof.

Each component of $\Theta(e,f)$ projects into $e$ and $f$. Hence, apart from
the boundary vertices, each vertex must have indegree and outdegree precisely
one. ∎

By Lemma 5.2 we may consider each component $g\subset\Theta(e,f)$ as a
directed path $g:I\to\Theta$. Just as in Section 2.3, we define subsets
$\Theta_{\operatorname{Sub}}(e,f),\Theta_{\operatorname{Sup}}(e,f),\Theta_{\operatorname{Pref}}(e,f),\Theta_{\operatorname{Suff}}(e,f),\Theta_{\partial}(e,f)\subset\Theta(e,f)$
in the following way. Let $g\subset\Theta(e,g)$ be a component, then:

$\displaystyle g$ $\displaystyle\subset\Theta_{\operatorname{Sub}}(e,f)$
$\displaystyle\text{if }o(p_{\Lambda}\circ g)=o(f)\text{ and
}t(p_{\Lambda}\circ g)=t(f)$ $\displaystyle g$
$\displaystyle\subset\Theta_{\operatorname{Sup}}(e,f)$ $\displaystyle\text{if
}o(p_{\Gamma}\circ g)=o(e)\text{ and }t(p_{\Gamma}\circ g)=t(e)$
$\displaystyle g$ $\displaystyle\subset\Theta_{\operatorname{Pref}}(e,f)$
$\displaystyle\text{if }o(p_{\Gamma}\circ g)=o(e)\text{ and
}t(p_{\Lambda}\circ g)=t(f)$ $\displaystyle g$
$\displaystyle\subset\Theta_{\operatorname{Suff}}(e,f)$ $\displaystyle\text{if
}o(p_{\Lambda}\circ g)=o(f)\text{ and }t(p_{\Gamma}\circ g)=t(e)$
$\displaystyle g$ $\displaystyle\subset\Theta_{\partial}(e,f)$
$\displaystyle\text{if }o(g)\in\partial\Theta\text{ or }t(g)\in\partial\Theta$

These subsets provide us with a further decomposition:

$E(\Theta(e,f))=E(\Theta_{\operatorname{Sub}}(e,f))\cup
E(\Theta_{\operatorname{Sup}}(e,f))\cup
E(\Theta_{\operatorname{Pref}}(e,f))\cup
E(\Theta_{\operatorname{Suff}}(e,f))\cup E(\Theta_{\partial}(e,f)).$

As we will treat the subgraph $\Theta^{s}$ separately, we will mostly be
interested in the following subgraphs:

$\displaystyle\Theta^{s}(e,f)$ $\displaystyle=\Theta(e,f)\cap\Theta^{s},$
$\displaystyle\Theta_{\operatorname{Sub}}^{s}(e,f)$
$\displaystyle=\Theta_{\operatorname{Sub}}(e,f)\cap\Theta^{s},$
$\displaystyle\Theta_{\operatorname{Sup}}^{s}(e,f)$
$\displaystyle=\Theta_{\operatorname{Sup}}(e,f)\cap\Theta^{s},$
$\displaystyle\Theta_{\operatorname{Pref}}^{s}(e,f)$
$\displaystyle=\Theta_{\operatorname{Pref}}(e,f)\cap\Theta^{s},$
$\displaystyle\Theta_{\operatorname{Suff}}^{s}(e,f)$
$\displaystyle=\Theta_{\operatorname{Suff}}(e,f)\cap\Theta^{s}.$

Thus, we get a decomposition of $E(\Theta)$.

######  Lemma 5.3.

$\displaystyle
E(\Theta)=E(s(\mathbb{S}))\sqcup\bigsqcup_{e\in\bar{E}(\Gamma)}\bigsqcup_{f\in\bar{E}(\Lambda)}$
$\displaystyle(E(\Theta^{s}_{\operatorname{Sub}}(e,f))\cup
E(\Theta^{s}_{\operatorname{Sup}}(e,f))\cup$ $\displaystyle\cup
E(\Theta^{s}_{\operatorname{Pref}}(e,f))\cup
E(\Theta^{s}_{\operatorname{Suff}}(e,f))\cup E(\Theta_{\partial}(e,f))).$

$\hfill\qed$

###  5.3. Bounding $|E(\Theta^{s})|$

In this section we will show that each of the sets
$E(\Theta_{\operatorname{Sub}}^{s}(e,f))$,
$E(\Theta^{s}_{\operatorname{Sup}}(e,f))$,
$E(\Theta^{s}_{\operatorname{Pref}}(e,f))$,
$E(\Theta^{s}_{\operatorname{Suff}}(e,f))$ and $E(\Theta_{\partial}(e,f))$
have, up to multiplication by some universal constant, cardinality bounded
above by $C_{\Gamma}\cdot C_{\Lambda}\cdot(\left\lvert
e\right\rvert+\left\lvert f\right\rvert)$ for all $e\in\bar{E}(\Gamma)$ and
$f\in\bar{E}(\Lambda)$. Then, using the decomposition in Lemma 5.3, we can say
something about $\left\lvert E(\Theta^{s})\right\rvert$.

######  Proposition 5.4.

Let $e\in\bar{E}(\Gamma)$ and $f\in\bar{E}(\Lambda)$, then:

$\displaystyle\left\lvert E(\Theta^{s}_{\operatorname{Sub}}(e,f))\right\rvert$
$\displaystyle\leq 100\cdot C_{\Gamma}\cdot C_{\Lambda}\cdot\left\lvert
e\right\rvert,$ $\displaystyle\left\lvert
E(\Theta^{s}_{\operatorname{Sup}}(e,f))\right\rvert$ $\displaystyle\leq
100\cdot C_{\Gamma}\cdot C_{\Lambda}\cdot\left\lvert f\right\rvert.$

###### Proof.

The two inequalities are symmetric so we just prove the first. For each
component $g\subset\Theta^{s}_{\operatorname{Sub}}(e,f)$, there corresponds an
element in $\operatorname{Sub}(e,f)$ in the following way:
$\bar{o}(p_{\Lambda}\circ g)=(e,i)$ where $i\in\operatorname{Sub}(e,f)$. By
Lemma 2.13:

$\operatorname{Sub}(e,f)=\bigcup_{i=1}^{k}\operatorname{Arith}(p_{i},q_{i},r_{i})$

where $k\leq\left\lfloor\frac{\left\lvert e\right\rvert}{\left\lvert
f\right\rvert}\right\rfloor$ and $p_{i}\cdot q_{i}\leq\left\lvert
f\right\rvert$. Moreover, if $p_{i}\geq 2$, then $q=\operatorname{per}(f)$.
But by Proposition 5.1, there can be at most $100\cdot C_{\Gamma}\cdot
C_{\Lambda}$ elements in each arithmetic progression that correspond to
components of $\Theta^{s}_{\operatorname{Sub}}(e,f)$. Hence we get:

$\left\lvert E(\Theta^{s}_{\operatorname{Sub}}(e,f))\right\rvert\leq 100\cdot
C_{\Gamma}\cdot C_{\Lambda}\cdot\left\lfloor\frac{\left\lvert
f\right\rvert}{\left\lvert e\right\rvert}\right\rfloor\cdot\left\lvert
e\right\rvert\leq 100\cdot C_{\Gamma}\cdot C_{\Lambda}\cdot\left\lvert
f\right\rvert.$

∎

######  Proposition 5.5.

Let $e\in\bar{E}(\Gamma)$ and $f\in\bar{E}(\Lambda)$, then:

$\left\lvert E(\Theta^{s}_{\operatorname{Pref}}(e,f))\right\rvert,\left\lvert
E(\Theta^{s}_{\operatorname{Suff}}(e,f))\right\rvert\leq 200\cdot
C_{\Gamma\leavevmode\nobreak\ }\cdot C_{\Lambda}\cdot\min{\\{\left\lvert
e\right\rvert,\left\lvert f\right\rvert\\}}.$

###### Proof.

The two cases are symmetric so we just prove the inequality for
$\Theta^{s}_{\operatorname{Suff}}(e,f)$. For each component
$g\subset\Theta^{s}_{\operatorname{Suff}}(e,f)$, there corresponds an element
$\operatorname{Suff}(e,f)$ in the following way: $\bar{o}(p_{\Lambda}\circ
g)=(e,i)$ where $i\in\operatorname{Suff}(e,f)$. By Proposition 2.16:

$\operatorname{Suff}(e,f)=\bigcup_{i=1}^{k}\operatorname{Arith}(p_{i},q_{i},r_{i})$

where $k\leq\min{\\{\lfloor\log_{2}(\left\lvert
e\right\rvert)\rfloor,\lfloor\log_{2}(\left\lvert f\right\rvert)\rfloor\\}}$,
$q_{i}\leq\frac{q_{i-1}}{2}$ and $r_{i}\geq\left\lvert f\right\rvert-q_{i-1}$.
By Proposition 5.1, there can be at most $100\cdot C_{\Gamma}\cdot
C_{\Lambda}$ many integers in each arithmetic progression that correspond to
components $g\subset\Theta^{s}_{\operatorname{Suff}}(e,f)$. Since
$q_{i}\leq\frac{q_{i-1}}{2}$ and $r_{i}\geq\left\lvert f\right\rvert-q_{i-1}$,
we get:

$\displaystyle\left\lvert
E(\Theta^{s}_{\operatorname{Suff}}(e,f))\right\rvert$ $\displaystyle\leq
100\cdot C_{\Gamma}\cdot C_{\Lambda}\cdot\left(\min{\\{\left\lvert
e\right\rvert,\left\lvert f\right\rvert\\}}+\frac{\min{\\{\left\lvert
e\right\rvert,\left\lvert f\right\rvert\\}}}{2}+...+\frac{\min{\\{\left\lvert
e\right\rvert,\left\lvert
f\right\rvert\\}}}{2^{\min{\\{\lfloor\log_{2}(\left\lvert
e\right\rvert)\rfloor,\lfloor\log_{2}(\left\lvert
f\right\rvert)\rfloor\\}}}}\right)$ $\displaystyle\leq 200\cdot
C_{\Gamma}\cdot C_{\Lambda}\cdot\min{\\{\left\lvert e\right\rvert,\left\lvert
f\right\rvert\\}}.$

∎

######  Proposition 5.6.

$\sum_{e\in\bar{E}(\Gamma)}\sum_{f\in\bar{E}(\Lambda)}\left\lvert\Theta_{\partial}(e,f)\right\rvert\leq
8\cdot C_{\Gamma}\cdot C_{\Lambda}\cdot\min{\\{\left\lvert
E(\Gamma)\right\rvert,\left\lvert E(\Lambda)\right\rvert\\}}$

###### Proof.

Each element $g\in\Theta_{\partial}(e,f)$ satisfies $\left\lvert
g\right\rvert\leq\min{\\{\left\lvert e\right\rvert,\left\lvert
f\right\rvert\\}}$ by definition. By Lemma 3.7, there are at most $8\cdot
C_{\Gamma}\cdot C_{\Lambda}$ such elements ranging over all pairs
$e\in\bar{E}(\Gamma)$, $f\in\bar{E}(\Lambda)$. ∎

Putting everything from this section together, we may prove on of our main
theorems.

######  Theorem 5.7.

$\left\lvert E(\Theta^{s})\right\rvert\leq 508\cdot C_{\Gamma}\cdot
C_{\Lambda}\cdot\left(\left\lvert\bar{E}(\Lambda)\right\rvert\cdot\left\lvert
E(\Gamma)\right\rvert+\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert
E(\Lambda)\right\rvert\right).$

###### Proof.

By Propositions 5.4 and 5.5:

$\left\lvert E(\Theta^{s}(e,f))-E(\Theta_{\partial}(e,f))\right\rvert\leq
500\cdot C_{\Gamma}\cdot C_{\Lambda}\cdot(\left\lvert
e\right\rvert+\left\lvert f\right\rvert).$

Combining this with Proposition 5.6, Lemma 5.3 and the following:

$\displaystyle\sum_{e\in\bar{E}(\Gamma)}\sum_{f\in\bar{E}(\Lambda)}(\left\lvert
e\right\rvert+\left\lvert f\right\rvert)$
$\displaystyle=\sum_{e\in\bar{E}(\Gamma)}\left(\left\lvert\bar{E}(\Lambda)\right\rvert\cdot\left\lvert
e\right\rvert+\left\lvert E(\Lambda)\right\rvert\right)$
$\displaystyle=\left\lvert\bar{E}(\Lambda)\right\rvert\cdot\left\lvert
E(\Gamma)\right\rvert+\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert
E(\Lambda)\right\rvert,$

the result is proven. ∎

###  5.4. Bounding the number of cycles

Topological methods have been used for a long time to study fibre products of
immersions of undirected graphs (see [26, 23, 27, 5, 16, 21]). By the Hanna
Neumann Theorem, if $\gamma$ and $\lambda$ are immersions of undirected
graphs, then $\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$ has at most
$\chi(\Gamma)\cdot\chi(\Lambda)$ many non cyclic components. However, handling
the cyclic components requires a different approach. Let us first consider the
simplest case when $\Gamma,\Lambda,\Delta\cong S^{1}$. Suppose
$\deg(\gamma)=n\cdot p$ and $\deg(\lambda)=n\cdot q$ for integers $n,p,q\geq
1$ with $\gcd(p,q)=1$. Then $\Theta=\Gamma\times_{\Delta}\Lambda$ has
precisely $n$ components. So the number of components in general of the fibre
product cannot depend on the topology of the graphs as $n$ was arbitrary.
However, if $S_{1},S_{2}\subset\Theta$ are any two distinct components, then

$[\gamma\circ p_{\Gamma}|_{S_{1}}]=[\gamma\circ p_{\Gamma}|_{S_{2}}].$

Hence, all of the components in $\Theta$ represent the same conjugacy class of
subgroup in $\pi_{1}(\Delta)$. We record a slight extension of this
observation with the following Lemma.

######  Lemma 5.8.

If $\Gamma\cong\Lambda\cong S^{1}$, then the canonical map
$\theta:\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)\to\Delta$ is the
disjoint union of at most $\gcd(\deg(\gamma),\deg(\lambda))$ many copies of a
single free homotopy class of map $S^{1}\to\Delta$. $\hfill\qed$

This simpler case suggests that the better quantity to count is the number of
distinct homotopy classes of maps (of connected graphs) that $\theta$
decomposes into. Indeed this line of approach is suggested in [23] in the
context of free groups. The aim of this section is to provide general bounds
for this quantity. The main non-trivial step is to bound the number of cycles
in $\Theta^{s}$. The key observation needed is the following: each element of
$\bar{E}_{c}(\Theta^{s})$ must support some lift in
$\operatorname{\mathcal{L}}(p_{\Gamma}^{s},e)$ for some $e\in\bar{E}(\Gamma)$
such that
$p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
e)$.

######  Proposition 5.9.

Let $e\in\bar{E}(\Gamma)$, then

$\left\lvert\\{\tilde{e}\in\operatorname{\mathcal{L}}(p_{\Gamma}^{s},e)\mid
p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
e)\\}\right\rvert\leq 500\cdot C_{\Gamma}\cdot
C_{\Lambda}\cdot\left\lvert\bar{E}(\Lambda)\right\rvert.$

###### Proof.

If $\tilde{e}\in\operatorname{\mathcal{L}}(p^{s}_{\Gamma},e)$ such that
$p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
e)$, then

$E(\tilde{e})\subset\bigcup_{f\in\bar{E}(\Lambda)}(E(\Theta^{s}_{\operatorname{Sub}}(e,f))\cup
E(\Theta^{s}_{\operatorname{Pref}}(e,f))\cup
E(\Theta^{s}_{\operatorname{Suff}}(e,f))).$

By Propositions 5.4 and 5.5:

$\left\lvert E(\Theta^{s}_{\operatorname{Sub}}(e,f))\cup
E(\Theta^{s}_{\operatorname{Pref}}(e,f))\cup
E(\Theta^{s}_{\operatorname{Suff}}(e,f))\right\rvert\leq 500\cdot
C_{\Gamma\leavevmode\nobreak\ }\cdot C_{\Lambda}\cdot\left\lvert
e\right\rvert,$

and so:

$\displaystyle\bigcup_{\tilde{e}}E(\tilde{e})$ $\displaystyle\leq
500\cdot\sum_{f\in\bar{E}(\Lambda)}500\cdot C_{\Gamma}\cdot
C_{\Lambda}\cdot\left\lvert e\right\rvert$ $\displaystyle\leq 500\cdot
C_{\Gamma}\cdot
C_{\Lambda}\cdot\left\lvert\bar{E}(\Lambda)\right\rvert\cdot\left\lvert
e\right\rvert.$

where $\tilde{e}$ ranges over the elements in the set
$\\{\tilde{e}\in\operatorname{\mathcal{L}}(p_{\Gamma}^{s},e)\mid
p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
e)\\}$. But now since $E(\tilde{e}_{1})\cap E(\tilde{e}_{2})=\emptyset$ for
every pair of distinct lifts
$\tilde{e}_{1},\tilde{e}_{2}\in\operatorname{\mathcal{L}}(p_{\Gamma}^{s},e)$,
the claimed bound follows. ∎

######  Theorem 5.10.

There is a collection of paths $\\{g_{i}:I\to\Theta^{s}\\}_{i=1}^{n}$ such
that

  1. (1)

$\cup_{i=1}^{n}g_{i}(I)=\Theta^{s}$,

  2. (2)

either $p_{\Gamma}\circ g_{i}$ factors through some $e\in\bar{E}(\Gamma)$ or
$p_{\Lambda}\circ g_{i}$ factors through some $f\in\bar{E}(\Lambda)$,

  3. (3)

$n\leq 1008\cdot C_{\Gamma}\cdot
C_{\Lambda}\cdot\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert$.

###### Proof.

Let $e\in E(\Theta^{s})$ be any edge. Let $g_{e},h_{e}:I\to\Theta$ be the
largest paths containing $e$ and such that $p^{s}_{\Gamma}\circ g_{e}$ factors
through some element in $\bar{E}(\Gamma)$ and $p^{s}_{\Lambda}\circ h_{e}$
factors through some element in $\bar{E}(\Lambda)$. It is not hard to see that
if $p^{s}_{\Gamma}\circ g_{e}$ is not equal to an element in
$\bar{E}(\Gamma)$, then $g$ has an end point on the boundary of $\Theta$.
Similarly for $h_{e}$. So let us decompose $E(\Theta^{s})=E_{1}\sqcup E_{2}$
where $E_{1}$ contains all the edges $e$ such that either $g_{e}$ or $h_{e}$
has an endpoint on the boundary. By Lemma 3.7, we can cover all edges in
$E_{1}$ by at most $8\cdot C_{\Gamma}\cdot C_{\Lambda}$ of the required paths.

Now for every $e\in E_{2}$, we have that $p^{s}_{\Gamma}\circ
g_{e}\in\bar{E}(\Gamma)$ and $p^{s}_{\Lambda}\circ h_{e}\in\bar{E}(\Lambda)$.
So if $\left\lvert g_{e}\right\rvert\geq\left\lvert h_{e}\right\rvert$, then
the projection of $g_{e}$ to $\Lambda$ must traverse a vertex in
$\bar{V}(\Lambda)$. In other words:

$g_{e}\in\\{\tilde{e}\in\operatorname{\mathcal{L}}(p_{\Gamma}^{s},p^{s}_{\Gamma}\circ
g_{e})\mid
p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
p^{s}_{\Gamma}\circ g_{e})\\}.$

If $\left\lvert g_{e}\right\rvert\leq\left\lvert h_{e}\right\rvert$ we have:

$h_{e}\in\\{\tilde{e}\in\operatorname{\mathcal{L}}(p_{\Lambda}^{s},p^{s}_{\Lambda}\circ
h_{e})\mid
p_{\Gamma}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\gamma,\lambda\circ
p^{s}_{\Lambda}\circ h_{e})\\}.$

We may bound the sets on the right by Proposition 5.9. Now we take the set
$\\{g_{i}:I\to\Theta\\}_{i=1}^{n}$ to consist of all distinct paths in the
following set:

$\bigcup_{e\in\Theta^{s}}\left(\left(\bigcup_{\left\lvert
g_{e}\right\rvert\geq\left\lvert
h_{e}\right\rvert}g_{e}\right)\cup\left(\bigcup_{\left\lvert
g_{e}\right\rvert<\left\lvert h_{e}\right\rvert}h_{e}\right)\right).$

Summing over elements of $\bar{E}(\Gamma)$ and $\bar{E}(\Lambda)$ we get:

$\displaystyle n\leq$
$\displaystyle\sum_{e\in\bar{E}(\Gamma)}\left\lvert\\{\tilde{e}\in\operatorname{\mathcal{L}}(p_{\Gamma}^{s},e)\mid
p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
e)\\}\right\rvert$
$\displaystyle+\sum_{f\in\bar{E}(\Lambda)}\left\lvert\\{\tilde{f}\in\operatorname{\mathcal{L}}(p_{\Lambda}^{s},f)\mid
p_{\Gamma}^{s}\circ\tilde{f}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\gamma,\lambda\circ
f)\\}\right\rvert+8\cdot C_{\Gamma}\cdot C_{\Lambda}$ $\displaystyle\leq
1008\cdot C_{\Gamma}\cdot
C_{\Lambda}\cdot\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert.$

∎

A simplified version of the proof of Theorem 5.10 yields the following bound
on the number of cycles in $\Theta^{s}$.

######  Theorem 5.11.

$\left\lvert\bar{E}_{c}(\Theta^{s})\right\rvert\leq
500\cdot\left(\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert\right)^{2}.$

###### Proof.

Without loss, we may assume that $V^{m}(\Gamma),V^{m}(\Lambda)=\emptyset$,
thus we have $C_{\Gamma}=\left\lvert\bar{E}(\Gamma)\right\rvert$ and
$C_{\Lambda}=\left\lvert\bar{E}(\Lambda)\right\rvert$. Each element
$g\in\bar{E}_{c}(\Theta^{s})$ must support some element in
$\\{\tilde{e}\in\operatorname{\mathcal{L}}(p_{\Gamma}^{s},e)\mid
p_{\Lambda}^{s}\circ\tilde{e}\in\operatorname{\mathcal{L}_{\text{overlap}}}(\lambda,\gamma\circ
e)\\}$ for some $e\in\bar{E}(\Gamma)$. Hence, just as in the proof of Theorem
5.10, we sum over elements of $\bar{E}(\Gamma)$ to complete the proof. ∎

######  Theorem 5.12.

The natural map $\theta:\Theta\to\Delta$ contains at most

$40538\cdot(\beta_{1}(\Gamma)\cdot\beta_{1}(\Lambda))^{2}$

many free homotopy classes of maps of connected graphs.

###### Proof.

Contractible components all lie in the same free homotopy class, so we add one
to our count and assume that $V^{m}(\Gamma),V^{m}(\Lambda)=\emptyset$. By
Lemma 3.6, we have $\left\lvert\bar{E}(\Gamma)\right\rvert\leq
3\cdot\beta_{1}(\Gamma)$ and $\left\lvert\bar{E}(\Lambda)\right\rvert\leq
3\cdot\beta_{1}(\Lambda)$. By Lemma 3.7, we have
$\left\lvert\bar{E}(\Theta)-\bar{E}_{c}(\Theta)\right\rvert\leq
36\cdot\beta_{1}(\Gamma)\cdot\beta_{1}(\Lambda)$. So now we simply need to
bound the free homotopy classes of maps corresponding to the cycles
$\bar{E}_{c}(\Theta)$. By Lemma 5.8, and Theorem 4.19, the set $\\{\gamma\circ
p_{\Gamma}\circ f\mid f\in\bar{E}_{c}(\Theta)\\}$ contains at most
$\beta_{1}(\Gamma)\cdot\beta_{1}(\Lambda)$ many free homotopy classes of
cycles that factor through $s(\mathbb{S})$. Now applying Theorem 5.11 finishes
the proof. ∎

We conclude this section with an example demonstrating a lower bound for a
sharp upper bound of the free homotopy classes of cycles in
$\theta:\Theta\to\Delta$.

######  Example 5.13.

Let $k,m\geq 1$ be a pair of integers. Let $\Delta$ be the connected graph
with a single vertex and $k+m$ edges. We may label these loops by
$x_{1},...,x_{k},y_{1},...,y_{m}$. Consider the paths:

$\displaystyle w$ $\displaystyle=x_{1}*...*x_{k}*y_{1}*...*y_{m}$
$\displaystyle w_{i}$ $\displaystyle=w[i:]*w[:i].$

Let $p_{1},...,p_{k+m}$ be a collection of distinct primes. Consider the
connected graph $\Gamma$ with $\bar{V}(\Gamma)=\\{v_{\Gamma}\\}$ and
$\bar{E}(\Gamma)=\\{w_{1}^{p_{1}},...,w_{k}^{p_{k}}\\}$. Consider also the
connected graph $\Lambda$ with $\bar{V}(\Lambda)=\\{v_{\Lambda}\\}$ and
$\bar{E}(\Lambda)=\\{w_{k+1}^{p_{k+1}},...,w_{k+m}^{p_{k+m}}\\}$. Then
$\operatorname{Core^{rel}}(\Gamma\times_{\Sigma}\Lambda)$ has precisely

$k\cdot m=\beta_{1}(\Gamma)\cdot\beta_{1}(\Lambda)$

components. By choosing an appropriate basepoint for each component of
$\operatorname{Core^{rel}}(\Gamma\times_{\Delta}\Lambda)$, the labels of each
cycle are $w^{p_{i}\cdot p_{j}}$ as $i$ ranges from $1$ to $k$ and $j$ ranges
from $k+1$ to $k+m$. Hence, the induced maps to $\Delta$ restricted to each
component are in distinct free homotopy classes. Furthermore, each component
represents conjugates $\pi_{1}(\Gamma)\cap\pi_{1}(\Lambda)^{g}$, none of which
are conjugate into each other. On the other hand, they are all conjugate into
the cyclic group $\langle w\rangle$.

##  6\. Free groups

Now that we have proved all of our results in the context of graphs, we can
discuss applications of these results to free groups. We begin by making the
connection with free groups explicit. A _Stallings graph_ $\Gamma$ is a graph,
together with an involution ${}^{-1}:E(\Gamma)\to E(\Gamma)$ such that
$o(e)=t(e^{-1})$ and $e^{-1}\neq e$ for all $e\in E(\Gamma)$. A Stallings
graph map $\gamma:\Gamma\to\Delta$ must also satisfy

$\gamma(e^{-1})=\gamma(e)^{-1}$

for all $e\in E(\Gamma)$.

A path $f:I\to\Gamma$ is _reduced_ if there is no subsequent pair of edges
$e_{1},e_{2}\in E(I)$ such that $f(e_{1})=f(e_{2})^{-1}$. The core of a
Stallings graph is instead defined as the union of all the reduced cycles. The
relative core is defined similarly. The set of (endpoint preserving homotopy
classes of) reduced paths forms a groupoid, the fundamental groupoid
$\pi_{1}(\Gamma)$. If we choose a basepoint $x\in V(\Gamma)$, then the set of
(basepoint preserving homotopy classes of) reduced paths actually form a
group, the fundamental group $\pi_{1}(\Gamma,x)$. By Stallings construction
[26], there is a bijection:

$\\{\gamma:(\Gamma,x)\to(\Delta,y)\mid\gamma\text{ based immersion of
relatively core Stallings graphs}\\}\to\\{A<\pi_{1}(\Delta,y)\\}$

given by the $\pi_{1}$ functor. And so, as elucidated in detail in [13],
results for Stallings graphs correspond directly to results for subgroups of
free groups.

Since the graphs we have worked with were not Stallings graphs, we will
instead consider a slight modification of the classic construction. So let
$\Gamma$ be a graph equipped with an involution on its edges
${}^{-1}:E(\Gamma)\to E(\Gamma)$ and its vertices ${}^{-1}:V(\Gamma)\to
V(\Gamma)$ such that

  1. (1)

for every $e\in E(\Gamma)$, we have $o(e)=t(e^{-1})^{-1}$,

  2. (2)

for all $e\in E(\Gamma)$, $(e^{-1})^{-1}=e$ and $e^{-1}\neq e$,

  3. (3)

for every $v\in V(\Gamma)$, $(v^{-1})^{-1}=v$.

We will call this a _graph with involution_. Note that by property 1, the
involution -1 can be extended to the set of paths: if $f:I\to\Gamma$ is a
path, then $f^{-1}$ is also a path and $o(f)=t(f^{-1})$.

Let $\Gamma$ be a graph with involution. We may also define reduced paths in
$\Gamma$ in the exact same way as we did for Stallings graphs. However, the
fundamental groupoid may not always be defined. If $x\in V(\Gamma)$ such that
$x^{-1}=x$, then by property 1, the fundamental group $\pi_{1}(\Gamma,x)$ is
well defined.

There is a standard formula relating the rank of the fundamental group of a
Stallings graph to its combinatorial data. We record this formula also for
graphs with involution.

######  Lemma 6.1.

Let $\Gamma$ be a connected graph with involution. Then:

$\operatorname{rk}(\Gamma,x)=\frac{\left\lvert\bar{E}(\Gamma)-\bar{E}_{c}(\Gamma)\right\rvert}{2}-\left\lvert\bar{V}(\Gamma)\right\rvert+1.$

$\hfill\qed$

The quotient map $\Gamma\to\Gamma^{\prime}$ which identifies all $v\in
V(\Gamma)$ with $v^{-1}$, induces a functor from the category of graphs with
involution to the category of Stallings graphs. Denote this functor by $ST$.

We say a graph with involution $\Gamma^{\prime}$ is obtained from a graph with
involution $\Gamma$ by _splitting a vertex_ if: there is some vertex $v\in
V(\Gamma)-V^{m}(\Gamma)$ such that
$\operatorname{St^{-}}(v)=\\{e_{1},e_{2}^{-1}\\}$ and
$\operatorname{St^{+}}(v)=\\{e_{1}^{-1},e_{2}\\}$ and $\Gamma^{\prime}$ is
obtained from $\Gamma$ by removing the vertex $v$, removing the edges $e_{1}$
and $e_{2}$, adding two new vertices $v^{\prime}$, $v^{\prime-1}$ and four new
edges $e_{1}^{\prime},e_{1}^{\prime-1},e_{2}^{\prime}$ and $e_{2}^{\prime-1}$
such that:

$\displaystyle o(e_{1}^{\prime})$ $\displaystyle=o(e_{1}),$ $\displaystyle
t(e_{1}^{\prime})$ $\displaystyle=v^{\prime},$ $\displaystyle
o(e_{1}^{\prime-1})$ $\displaystyle=v^{\prime-1},$ $\displaystyle
t(e_{1}^{\prime-1})$ $\displaystyle=t(e_{1}^{-1}),$ $\displaystyle
o(e_{2}^{\prime})$ $\displaystyle=v^{\prime},$ $\displaystyle
t(e_{2}^{\prime})$ $\displaystyle=t(e_{2}),$ $\displaystyle
o(e_{2}^{\prime-1})$ $\displaystyle=o(e_{2}^{-1}),$ $\displaystyle
t(e_{2}^{\prime-1})$ $\displaystyle=v^{\prime-1}.$

This operation is perhaps better understood through a diagram, see Figure 4.
There is an induced quotient map $q:\Gamma^{\prime}\to\Gamma$ where
$v^{\prime}$ and $v^{\prime-1}$ map to $v$,
$e_{1}^{\prime},e_{1}^{\prime-1},e_{2}^{\prime},e_{2}^{\prime-1}$ map to
$e_{1},e_{1}^{-1},e_{2},e_{2}^{-1}$ respectively and everything else maps
where expected. The induced quotient map will be called a _vertex splitting_.
A graph with involution $\Gamma$ is _unsplittable_ if no vertex splitting can
be performed on $\Gamma$.

Figure 4. A vertex splitting

######  Lemma 6.2.

Let $\Gamma$ be a graph with involution. There is a sequence of vertex
splittings:

$\Gamma_{n}\to...\to\Gamma_{1}\to\Gamma.$

such that $\Gamma_{n}$ is unsplittable. Moreover, $\Gamma_{n}$ is uniquely
defined.

###### Proof.

Since each new vertex created in a vertex splitting cannot be split again,
there is a sequence of vertex splittings
$\Gamma_{n}\to...\to\Gamma_{1}\to\Gamma$ such that $\Gamma_{n}$ is
unsplittable and $n\leq\left\lvert V(\Gamma)\right\rvert$. Uniqueness follows
from the fact that any pair of vertex splittings commute. ∎

Figure 5. Applying the functor $SP$

By Lemma 6.2, we will write $SP(\Gamma)$ for the unique unsplittable graph
with involution obtained from a graph with involution $\Gamma$. See Figure 5
for an example of this. This is also a functor and a section for the functor
$ST$. We record this in the following Lemma.

######  Lemma 6.3.

$SP$ and $ST$ are functors, with $SP$ a section for $ST$. $\hfill\qed$

We are now ready to prove our main Theorems for subgroups of free groups from
the introduction.

######  Theorem 6.4.

Let $F$ be a free group and $A<F$ a finitely generated subgroup. Then there
are at most $\operatorname{rk}(A)$ many conjugacy classes of maximal cyclic
subgroups $M<F$ such that

$12\cdot\operatorname{rk}(A)\leq[M:A\cap M]<\infty.$

###### Proof.

Let $\gamma:(\Gamma,y)\to(\Delta,x)$ be the Stallings graph immersion
realising the inclusion $A<F$. Let $[G_{1}],[G_{2}],...$ be conjugacy classes
of maximal cyclic subgroups such that
$12\cdot\operatorname{rk}(A)\leq[G_{i}:A\cap G_{i}]<\infty$. Now let $g_{i}$
be a generator for $G_{i}$. By construction no pair $g_{i}$, $g_{j}$ are
conjugate to each other or to an inverse. Furthermore, $o_{A}(g)\geq
12\cdot\operatorname{rk}(A)$ where $o_{A}(g)$ is the relative order of $g$
defined in the introduction. Let $h_{i}$ be a shortest representative in the
conjugacy class $[g_{i}]$ in $F$. Then there are reduced cycles
$f_{1},...,f_{n}:S^{1}\to SP(\Gamma)$ such that (after choosing an appropriate
basepoint for $S^{1}$) $[f_{i}]=h_{i}$.

Let $w_{i}:I\to SP(\Delta)$ be a primitive loop such that $f_{i}$ is a
$w_{i}$-cycle. Assume that $\left\lvert w_{i}\right\rvert\geq\left\lvert
w_{i+1}\right\rvert$. By Lemma 4.18, for each $f_{i}$ there is an element
$e_{i}\in\bar{E}(SP(\Gamma))$ such that $\left\lvert e_{i}\right\rvert\geq
2\cdot\left\lvert w_{i}\right\rvert$ and $f_{i}$ traverses $e_{i}$. If $f_{j}$
traverses $e_{i}$ for any $i<j$, up to replacing $w_{i}$ with a cyclic
conjugate of itself, $w_{i}^{2}$ has period $\left\lvert
w_{j}\right\rvert\leq\left\lvert w_{i}\right\rvert$. Since $w_{i}$ and $w_{j}$
are primitive, it follows from Corollary 2.2 that $w_{i}$ is a cyclic
conjugate of $w_{j}$. But since $\gamma$ was an immersion, it then also
follows that $f_{i}=f_{j}$. Similarly if $f_{j}$ traverses $e_{i}^{-1}$, but
the contradiction is that $f_{i}=f_{j}^{-1}$. Hence, $f_{i}$ is supported in
$SP(\Gamma)-\\{e_{1},e_{1}^{-1},...,e_{i-1},e_{i-1}^{-1}\\}$. As
$SP(\Gamma)-\\{e_{1},e_{1}^{-1},...,e_{\operatorname{rk}(A)},e_{\operatorname{rk}(A)}^{-1}\\}$
cannot support any reduced non trivial cycles, the result follows. ∎

######  Corollary 6.5.

Let $F$ be a free group and $A<F$ a finitely generated subgroup. Then there
exists a set $N\subset\mathbb{N}$ of cardinality bounded above by
$13\cdot\operatorname{rk}(A)$, such that:

$\mathcal{O}_{A}(F)=\bigcup_{n\in N}\bigcup_{d\mid n}d.$

$\hfill\qed$

######  Theorem 6.6.

There exists a universal constant $C>0$, with the following property. For any
free group $F$ and any finitely generated subgroups $A,B<F$, we have:

$\sum_{[A\cap B^{g}]}\operatorname{rk}(A\cap B^{g})\leq
C\cdot(\operatorname{rk}(A)\cdot\operatorname{rk}(B))^{2}.$

###### Proof.

Let $\Delta$ be a Stallings graph with a single vertex and such that
$\pi_{1}(\Delta,x)\cong F$. Let $\gamma:(\Gamma,y)\to(\Delta,x)$ and
$\lambda:(\Lambda,z)\to(\Delta,x)$ be the Stallings graph immersions realising
the inclusions of the subgroups $A$ and $B<\pi_{1}(\Delta,x)$ respectively. By
Theorem 5.12, the map:

$\theta:\operatorname{Core^{rel}}(SP(\Gamma)\times_{SP(\Delta)}SP(\Lambda))\to
SP(\Delta)$

consists of at most
$C\cdot(\beta_{1}(SP(\Gamma))\cdot\beta_{1}(SP(\Lambda)))^{2}$ many free
homotopy classes of connected graph maps where $C>0$ is a universal constant.
Now by Lemma 6.3, we have that the map:

$\operatorname{Core^{rel}}(\Gamma\times_{\Delta}\Lambda)\to\Delta$

is the same as the map $ST(\theta)$. Hence it must also consist of at most
$C\cdot(\beta_{1}(SP(\Gamma))\cdot\beta_{1}(SP(\Lambda)))^{2}$ many free
homotopy classes of connected graph maps. Thus by Theorem 5.5 in [26] and
Lemma 6.1, the Theorem follows. ∎

Effectively what we have done in this section is convert our statements of our
main fibre product results to hold also for immersions of undirected graphs.
Therefore, we record this in the following Theorem.

######  Theorem 6.7.

Theorems 4.20, 5.7 and 5.12 also hold for graph immersions of undirected
graphs, possibly with larger constants. $\hfill\qed$

##  7\. Algorithmic results

In this section we present our algorithmic results. In what follows, all
algorithms will have as input two forwards graph immersions
$\gamma:\Gamma\to\Delta$ and $\lambda:\Lambda\to\Delta$. We will also use the
same notation given in the beginning of Section 5. The parameters for our
complexity results will be the following two quantities:

$\displaystyle m$
$\displaystyle=(\beta_{1}(\Gamma)+\left\lvert\partial\Gamma\right\rvert)+(\beta_{1}(\Lambda)+\left\lvert\partial\Lambda\right\rvert),$
$\displaystyle n$ $\displaystyle=\left\lvert E(\Gamma)\right\rvert+\left\lvert
E(\Lambda)\right\rvert.$

###  7.1. Accepting paths for $w$-cycles

Let $w:I\to\Delta$ be a primitive loop. Recall that we denote by
$\hat{w}:S^{1}\to\Delta$ the graph map obtained from $w$ by identifying the
vertices in $\partial I$ and a $w$-cycle is a graph map $f:S^{1}\to\Delta$
that factors through $\hat{w}:S^{1}\to\Delta$. An important part of our DFA-
NEI algorithm is the following variation of Theorem 2 in [2].

######  Theorem 7.1.

Let $w:I\to\Delta$ be a primitive loop and $\gamma:\Gamma\to\Delta$ and
$\lambda:\Lambda\to\Delta$ be $w$-cycles. If all the initial states in both
$\Gamma$ and $\Lambda$ are contained in at most $k$ segments of length
$\left\lvert w\right\rvert$, then we may decide in $O(k^{2}\cdot n)$ time if
$\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$ contains an accepting
path.

###### Proof.

We may find shortest loops $w_{\Gamma}:I\to\Gamma$ and
$w_{\Lambda}:I\to\Lambda$ such that $w_{\Gamma}[:\left\lvert
w\right\rvert]=w_{\Lambda}[:\left\lvert w\right\rvert]$ in $O(n)$ time by
Proposition 2.9. We may associate to each vertex $v\in V(\Gamma)$ a pair of
integers $(i,j)$ in the following way: if $0\leq l<\left\lvert
w_{\Gamma}\right\rvert$ is the unique integer such that $w_{\Gamma}(l)=v$,
then let $i=\left\lfloor\frac{l}{\left\lvert w\right\rvert}\right\rfloor$ and
$j=l-i$. Denote by $\eta_{\Gamma}:V(\Gamma)\to\mathbb{N}\times\mathbb{N}$ the
corresponding map. Similarly we have a map
$\eta_{\Lambda}:V(\Lambda)\to\mathbb{N}\times\mathbb{N}$ for $\Lambda$. By
assumption, we have $\left\lvert
p_{1}\circ\eta_{\Gamma}(V^{i}(\Gamma))\right\rvert\leq 2\cdot k$ and
$\left\lvert p_{1}\circ\eta_{\Lambda}(V^{i}(\Lambda))\right\rvert\leq 2\cdot
k$ where $p_{1}:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ is projection to the
first factor. Both the sets $p_{1}\circ\eta_{\Gamma}(V^{i}(\Gamma))$ and
$p_{1}\circ\eta_{\Lambda}(V^{i}(\Lambda))$ may also be computed in $O(n)$
time.

For each pair $a\in p_{1}\circ\eta_{\Gamma}(V^{i}(\Gamma))$, $b\in
p_{1}\circ\eta_{\Lambda}(V^{i}(\Lambda))$, we check if there exists some
$0\leq c<\left\lvert w\right\rvert$ such that
$(a,c)\in\eta_{\Gamma}(V^{i}(\Gamma))$ and
$(b,c)\in\eta_{\Lambda}(V^{i}(\Lambda))$. This may be done in $O(n)$ time for
each choice of $a,b$. If there is no such pair, then
$V^{i}(\operatorname{Core}(\Gamma\times_{\Delta}\Lambda))=\emptyset$ and
$\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$ cannot contain an
accepting path.

Now let $a$, $b$ be a pair of such integers. With some minor modifications, we
now essentially follow the proof of Theorem 2 in [2]. Let $\gamma\circ
w_{\Gamma}=w^{m}$ and $\lambda\circ w_{\Lambda}=w^{n}$ and $q=\gcd(m,n)$. Then
$\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$ contains an accepting path
starting from some vertex in $V(w_{\Gamma}[a\cdot\left\lvert
w\right\rvert:(a+1)\cdot\left\lvert w\right\rvert-1])\times
V(w_{\Lambda}[b\cdot\left\lvert w\right\rvert:(b+1)\cdot\left\lvert
w\right\rvert-1])$ if and only if there is a vertex $(x,y)\in
V^{f}(\Gamma)\times V^{f}(\Lambda)$ and integers $s,t,r,c$ such that:

$\displaystyle\eta_{\Gamma}(x)$ $\displaystyle=(s\cdot q+r-a,c),$
$\displaystyle\eta_{\Lambda}(y)$ $\displaystyle=(t\cdot q+r-b,c).$

Now for each $x\in V^{f}(\Gamma)$, we can compute the unique minimal pair
$(r^{\prime},c^{\prime})$ such that $\eta_{\Gamma}(s^{\prime}\cdot
q+r^{\prime}-a,c^{\prime})$ for some $s^{\prime}$. We may put all these
integers in the set $S_{\Gamma}$. Similarly we compute the set $S_{\Lambda}$.
We may do this in $O(n)$ time. Finally, we decide if $S_{\Gamma}\cap
S_{\Lambda}=\emptyset$ or not. This may also be done in $O(n)$ time.

Thus, by iterating over all pairs $(a,b)\in
p_{1}\circ\eta_{\Gamma}(V^{i}(\Gamma))\times
p_{1}\circ\eta_{\Lambda}(V^{i}(\Lambda))$, we may decide if
$\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$ has any accepting paths in
$O(k^{2}\cdot n)$ time. ∎

###  7.2. Connectivity in $s(\mathbb{S})$

As a product of the proof of Theorem 4.19, we also obtain that the graph
$s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ is computable. The following result
states that we may also compute them efficiently.

######  Theorem 7.2.

There is an algorithm that computes the graph
$s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ from Theorem 4.19 in $O(m^{2}\cdot
n)$ time.

###### Proof.

Since all cycles are supported in $\operatorname{Core}(\Gamma)$, we may assume
that $\Gamma$ is core itself. Let $f:S^{1}\to\Gamma$ be a cycle in
$\mathbb{S}_{\Gamma}$. Then there is some primitive loop $w:I\to\Delta$ and
some map $g:S^{1}\to S^{1}$ such that $\gamma\circ f=\hat{w}\circ g$ and
$\deg(g)\geq 12\cdot\beta_{1}(\Gamma)$. By Lemma 4.18, there is some element
$e\in\bar{E}(\Gamma)$ such that $e$ is a $w$-path and $\left\lvert
e\right\rvert\geq 2\cdot\left\lvert w\right\rvert$. By Theorem 2.1, it follows
that $\operatorname{per}(e)=\left\lvert w\right\rvert$. So in order to find
the cycles in $\mathbb{S}_{\Gamma}$ we may do the following. By Theorem 2.8 we
may compute $\operatorname{per}(e)$ for each $e\in\bar{E}(\Gamma)$ in
$O(\left\lvert E(\Gamma)\right\rvert)$ time. Then let $w_{e}:I\to e$ denote a
subpath of $e$ of length exactly $\operatorname{per}(e)$. By Lemma 4.12, we
may decide in $O\left(\left\lvert
E(\Gamma)\right\rvert+2\cdot\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert
w_{e}\right\rvert\right)$ time if this extends to a $w_{e}$-cycle. Since
$\sum_{e\in\bar{E}(\Gamma)}\left\lvert w_{e}\right\rvert\leq\left\lvert
E(\Gamma)\right\rvert$, we may do this for all $e\in\bar{E}(\Gamma)$ in
$O\left(\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert
E(\Gamma)\right\rvert\right)$ time. Moreover, we may also decide at the same
time if the projections of the computed cycles to $\Delta$ have degree greater
than or equal to $12\cdot\beta_{1}(\Gamma)$. Thus, we may decide if they are
cycles in $\mathbb{S}_{\Gamma}$. Finally, by Proposition 2.9, we may decide in
$O\left(\left\lvert\bar{E}(\Gamma)\right\rvert^{2}\cdot\left\lvert
E(\Gamma)\right\rvert\right)$ time if any of the computed cycles are the same.
Hence overall, the algorithm will require
$O\left(\left\lvert\bar{E}(\Gamma)\right\rvert^{2}\cdot\left\lvert
E(\Gamma)\right\rvert\right)$ time to compute
$s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$. Combined with Lemma 3.6 we obtain
the result. ∎

The subgraph $s(\mathbb{S})\subset\Theta$ in general has more than a linear
number of states and transitions, providing an obstacle to a linear solution
to the DFA non-empty intersection problem. Therefore, in order to get around
this, we may like to learn something about the graph $s(\mathbb{S})$ without
actually computing it. We show that we may answer any question about
connectivity of $s(\mathbb{S})$ efficiently.

######  Proposition 7.3.

There is an integer $q>0$ such that there is a $O(m^{q}\cdot n)$ time
algorithm that, given as input elements $(e,f)\in E(\Gamma)\times E(\Lambda)$
and $(x,y)\in V(\Gamma)\times V(\Lambda)$, decides if there exists a path
$g:I\to\Gamma\times_{\Delta}\Lambda$ with the following properties:

  1. (1)

$g$ lifts to
$s:\operatorname{Core}(\mathbb{S}_{\Gamma}\times_{\Delta}\mathbb{S}_{\Lambda})\to\operatorname{Core}(\Gamma\times_{\Delta}\Lambda)$,

  2. (2)

$g[0]=(e,f)$,

  3. (3)

$t(g)=(x,y)$.

###### Proof.

Without loss we may assume that $\Gamma$ and $\Lambda$ are core graphs. By
Theorem 7.2, we may compute the graphs
$s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ and
$s_{\Lambda}:\mathbb{S}_{\Lambda}\to\Lambda$ in $O(m^{2}\cdot n)$ time. We set

$\displaystyle V^{i}(\mathbb{S}_{\Gamma})$ $\displaystyle=\cup_{e^{\prime}\in
E(s_{\Gamma}^{-1}(e))}o(e^{\prime}),$ $\displaystyle
V^{i}(\mathbb{S}_{\Lambda})$ $\displaystyle=\cup_{f^{\prime}\in
E(s_{\Lambda}^{-1}(f))}o(f^{\prime}),$ $\displaystyle
V^{f}(\mathbb{S}_{\Gamma})$ $\displaystyle=s_{\Gamma}^{-1}(x),$ $\displaystyle
V^{f}(\mathbb{S}_{\Lambda})$ $\displaystyle=s_{\Lambda}^{-1}(y).$

Now by construction, the path $g$ exists if and only if there exists some
admissible path in the graph
$\mathbb{S}=\operatorname{Core}(\mathbb{S}_{\Gamma}\times_{\Delta}\mathbb{S}_{\Lambda})$
with $V^{i}(\mathbb{S})=V^{i}(\mathbb{S}_{\Gamma})\times
V^{i}(\mathbb{S}_{\Lambda})$ and
$V^{f}(\mathbb{S})=V^{f}(\mathbb{S}_{\Gamma})\times
V^{f}(\mathbb{S}_{\Lambda})$. We may decide which pairs of components of
$\mathbb{S}_{\Gamma}$ and $\mathbb{S}_{\Lambda}$ factor through the same cycle
in $O(m^{2}\cdot n)$ time using the algorithms from Theorem 2.8 and
Proposition 2.9. By Theorem 4.15, if $S_{\Gamma}\subset\mathbb{S}_{\Gamma}$
and $S_{\Lambda}\subset\mathbb{S}_{\Lambda}$ are both $w$-cycles for some
primitive loop $w:I\to\Delta$, there exist at most
$10\cdot\left(\left\lvert\bar{E}(\Gamma)\right\rvert+\left\lvert\bar{E}(\Lambda)\right\rvert\right)\in
O(m)$ many segments of length $\left\lvert w\right\rvert$ that cover
$V^{i}(S_{\Gamma})$ and $V^{i}(S_{\Lambda})$. Now the problem may be solved
with the required complexity bounds by Theorem 7.1. ∎

######  Proposition 7.4.

There is an integer $q>0$ such that there is a $O(m^{q}\cdot n)$ time
algorithm that computes subsets
$V_{\mathbb{S}}\subset\bar{V}(\Gamma)\times\bar{V}(\Lambda)$ and
$E_{\mathbb{S}}\subset E(\Gamma)\times E(\Lambda)$ along with partitions
$V_{\mathbb{S}}=V_{1}\sqcup...\sqcup V_{c}$ and
$E_{\mathbb{S}}=E_{1}\sqcup...\sqcup E_{c}$ so that for every component
$S\subset s(\mathbb{S})$ there is an $i$ such that:

  1. (1)

$V_{i}=S\cap(\bar{V}(\Gamma)\times\bar{V}(\Lambda))$,

  2. (2)

$E_{i}=S\cap(\bigcup_{v\in\bar{V}(\Gamma)\times\bar{V}(\Lambda)}\operatorname{St^{+}}(v,\Gamma\times_{\Delta}\Lambda))$.

###### Proof.

We may simply iterate the algorithm from Proposition 7.3 for every pair of
elements $u,v\in\bar{V}(\Gamma)\times\bar{V}(\Lambda)$ and every edge in
$\operatorname{St^{+}}(u,\Gamma\times_{\Delta}\Lambda)$. ∎

###  7.3. Regular languages

Let $\Sigma$ be a finite set. A _finite state automaton over $\Sigma$_ is a
graph $\Gamma$ together with an initial vertex $V^{i}(\Gamma)=\\{x\\}$, a
collection of final vertices $V^{f}(\Gamma)$ and a labelling of its edges by
elements of $\Sigma$. If $\Delta$ is a graph with a single vertex and an edge
for each element in $\Sigma$, then labellings of edges of $\Gamma$ by elements
of $\Sigma$ are in a one-to-one correspondence with graph maps
$\gamma:\Gamma\to\Delta$. Thus, for our purposes, a finite state automaton
will be a quadruple $(\Gamma,\gamma,x,V^{f})$, where $\gamma:\Gamma\to\Delta$
is a graph map with $\Delta$ a connected graph with a single vertex. A
_deterministic finite state automaton_ (or _DFA_) is an automaton
$(\Gamma,\gamma,x,V^{f})$ such that $\gamma$ is a forwards immersion. The
_language_ of the automaton $(\Gamma,\gamma,x,V^{f})$ is the following
collection of paths:

$L(\Gamma)=\\{\gamma\circ g\mid g:I\to\Gamma\text{ an accepting path}\\}.$

It is a classical result of Rabin-Scott [24] that, given two automata
$(\Gamma,\gamma:\Gamma\to\Delta,x,V^{f}(\Gamma))$,
$(\Lambda,\lambda:\Lambda\to\Delta,y,V^{f}(\Lambda))$, we have:

$L(\Gamma)\cap L(\Lambda)=L(\Gamma\times_{\Delta}\Lambda).$

If $\gamma$ and $\lambda$ are finite sheeted covers, then
$\Gamma\times_{\Delta}\Lambda$ is a core graph and
$V(\Gamma\times_{\Delta}\Lambda)=V(\Gamma)\cdot V(\Lambda)$. So the optimal
complexity bound for computing the automaton representing $L(\Gamma)\cap
L(\Lambda)$ is $O(n^{2})$.

On the other hand, it is an open problem if deciding if $L(\Gamma)\cap
L(\Lambda)\neq\emptyset$ can be done in subquadratic time. See [14, 15, 28, 2,
3] for results on this problem and its variations. Currently, the only known
positive result for two DFAs is a linear time solution for automata over a
unary alphabet, or rather, automata $\gamma:\Gamma\to\Delta$ where $\Delta$
has only a single edge. This constraint on the edges of $\Delta$ immediately
puts constraints on the topology of $\Gamma$. Indeed, there are at most four
distinct forms that $\Gamma$ can take: a point, a segment, a circle or a
circle with a segment attached. Thus, the $m$ parameter is forced to be
bounded above by $4$. Generalising the unary case, we show that for any fixed
$m$, the DFA-NEI problem can be solved in linear time.

######  Theorem 7.5.

There is an integer $q>0$ such that there is a $O(m^{q}\cdot n)$ time
algorithm that, given as input two deterministic finite state automata
$\gamma:\Gamma\to\Delta$ and $\lambda:\Lambda\to\Delta$, decides if
$L(\Gamma)\cap L(\Lambda)\neq\emptyset$.

###### Proof.

Let us first fix some notation. As $\Gamma$ and $\Lambda$ are automata, they
both only have one initial vertex. So let $V^{i}(\Gamma)=\\{x\\}$ and
$V^{i}(\Lambda)=\\{y\\}$ and denote by
$V^{\prime}=(x,y)\cup\bar{V}(\Gamma)\times\bar{V}(\Lambda)$. Let $C$ be the
constant from Theorem 5.7 such that

$\left\lvert E(\Theta^{s})\right\rvert\leq C\cdot m^{2}\cdot n.$

Let $s_{\Gamma}:\mathbb{S}_{\Gamma}\to\Gamma$ and
$s_{\Lambda}:\mathbb{S}_{\Lambda}\to\Lambda$ be the graphs from Theorem 4.19.
By Theorem 7.2 we may assume that we have precomputed these graphs. We may
also assume that we have computed the subsets $V_{\mathbb{S}}$ and
$E_{\mathbb{S}}$ from Proposition 7.4 along with the partitions
$V_{\mathbb{S}}=V_{1}\sqcup...\sqcup V_{c}$ and
$E_{\mathbb{S}}=E_{1}\sqcup...\sqcup E_{c}$.

Denote by $A\subset L(\Theta)$ the set of paths $g:I\to\Theta$ such that
$t(g)\in V^{f}(\Theta^{s})$ and by $B\subset L(\Theta)$ the set of paths
$g:I\to\Theta$ such that $t(g)\in V^{f}(s(\mathbb{S}))$. Then, by definition
of $\Theta^{s}$, we have $L(\Theta)=A\cup B$. Thus, determining if
$L(\Theta)\neq\emptyset$ is equivalent to determining if $A\neq\emptyset$ or
$B\neq\emptyset$.

The logical structure of the proof is as follows. Let
$\Theta^{\circ}\subset\Gamma\times_{\Delta}\Lambda$ be the connected component
containing the vertex $(x,y)$. We will first compute a graph
$\Theta_{k}\subset\Gamma\times_{\Delta}\Lambda$ such that $\Theta_{k}$
contains the subgraph $\Theta^{s}\cap\Theta^{\circ}$ and satisfies
$\left\lvert E(\Theta_{k})\right\rvert\in O(m^{q}\cdot n)$ for some $q\geq 0$.
It will also be shown that $V(\Theta_{k})\cap(V^{f}(\Gamma)\times
V^{f}(\Lambda))\neq\emptyset$ if and only if $A\neq\emptyset$. Thus we will be
able to decide if $A\neq\emptyset$ in $O(m^{q}\cdot n)$ time for some $q\geq
0$. Then, we will show that using this graph and Theorem 7.1 we may also
decide if $B\neq\emptyset$ in $O(m^{q}\cdot n)$ time for some $q\geq 0$.

Before showing how to compute $\Theta_{k}$ we will need a useful procedure. We
will call the following algorithm the _bounded forced path procedure_. Given
as input a pair $(e,f)\in E(\Gamma)\times E(\Lambda)$ with
$\gamma(e)=\lambda(f)$ and an integer $l$, do the following. Denote by
$g:I\to\Gamma\times_{\Delta}\Lambda$ the path traversing only $(e,f)$. If
$t(e,f)\in\bar{V}(\Gamma)\times\bar{V}(\Lambda)$ or $l=1$, then we terminate
and return the path $g$. If not, then $l\geq 2$ and
$\operatorname{deg^{+}}(e)=1$ or $\operatorname{deg^{+}}(f)=1$. Since $\gamma$
and $\lambda$ are forwards immersions, there is at most one element
$(e^{\prime},f^{\prime})\in\operatorname{St^{+}}((t(e),t(f)),\Gamma\times_{\Delta}\Lambda)$.
If no such element exists, then we also terminate and return the path $g$. If
instead there is such a pair $(e^{\prime},f^{\prime})$, then let
$g^{\prime}:I\to\Gamma\times_{\Delta}\Lambda$ be the output of the bounded
forced path procedure with input $(e^{\prime},f^{\prime})$ and $l-1$. Return
the path $g*g^{\prime}$.

The following complexity bound follows from the fact that for all $u,v\in
V(\Gamma)\times V(\Lambda)$, the set
$\operatorname{St^{+}}((u,v),\Gamma\times_{\Delta}\Lambda)$ can be computed in
$O(m)$ time.

######  Lemma 7.6.

The bounded forced path procedure runs in $O(m\cdot l)$ time. $\hfill\qed$

We are now ready to compute the graph $\Theta_{k}$ as promised. We will in
fact do more than this, we will compute the following finite sequences:

  1. (1)

graphs $\Theta_{0},\Theta_{1},...,\Theta_{k}$ with
$\Theta_{i}\subset\Gamma\times_{\Delta}\Lambda$ for all $i\geq 0$

  2. (2)

sets of edges
$\operatorname{\mathsf{ndir}}_{0},\operatorname{\mathsf{ndir}}_{1},...,\operatorname{\mathsf{ndir}}_{k}$,
$\operatorname{\mathsf{odir}}_{0},\operatorname{\mathsf{odir}}_{1},...,\operatorname{\mathsf{odir}}_{k}$
with

$\operatorname{\mathsf{ndir}}_{i},\operatorname{\mathsf{odir}}_{i}\subset\cup_{v\in
V^{\prime}}\operatorname{St^{+}}(v,\Gamma\times_{\Delta}\Lambda),$

such that
$\operatorname{\mathsf{ndir}}_{i}\cap\operatorname{\mathsf{odir}}_{i}=\emptyset$
and
$\left\lvert\operatorname{\mathsf{odir}}_{i}\right\rvert<\left\lvert\operatorname{\mathsf{odir}}_{i+1}\right\rvert$
for all $i\geq 0$.

By definition, we have
$k\leq\left\lvert\bar{E}(\Gamma)\right\rvert\cdot\left\lvert\bar{E}(\Lambda)\right\rvert$
and so $k\in O(m^{2})$.

We begin the computation by letting
$\text{ndir}_{0}=\operatorname{St^{+}}((x,y),\Gamma\times_{\Delta}\Lambda)$,
$\text{odir}_{0}=\emptyset$ and $\Theta_{0}=\emptyset$. The set
$\operatorname{\mathsf{ndir}}_{i}$ will contain the new directions that we
need to explore at step $i+1$, meanwhile, the set
$\operatorname{\mathsf{odir}}_{i}$ will contain the old directions that we
have already explored before step $i+1$. So suppose now that we have computed
$\Theta_{i-1}$, $\operatorname{\mathsf{ndir}}_{i-1}$ and
$\operatorname{\mathsf{odir}}_{i-1}$. If
$\operatorname{\mathsf{ndir}}_{i-1}=\emptyset$, then we are done and $k=i-1$.
If not, choose some element $(e,f)\in\operatorname{\mathsf{ndir}}_{i-1}$. We
have precomputed $G$, so we first check if

$(e,f)\in d(E(G))\subset\cup_{v\in
V^{\prime}}\operatorname{St^{+}}(v,\Gamma\times_{\Delta}\Lambda).$

We now have two cases to consider.

Case 1: $(e,f)\in E_{\mathbb{S}}$.

If $(e,f)\in E_{\mathbb{S}}$, then $(e,f)\notin E(\Theta^{s})$ by definition.
Now let $j$ be the integer such that $(e,f)\in E_{j}$. By Proposition 7.4, the
vertices $V_{j}$ are precisely the vertices in
$\bar{V}(\Gamma)\times\bar{V}(\Lambda)$ that can be reached by a path starting
with $(e,f)$ in $s(\mathbb{S})$. So let:

$\displaystyle\operatorname{\mathsf{odir}}_{i}$
$\displaystyle=\operatorname{\mathsf{odir}}_{i-1}\cup(e,f)$
$\displaystyle\operatorname{\mathsf{ndir}}_{i}$
$\displaystyle=(\operatorname{\mathsf{ndir}}_{i-1}-(e,f))\cup\bigcup_{v\in
V_{j}}(\operatorname{St^{+}}(v,\Gamma\times_{\Delta}\Lambda)-(\operatorname{St^{+}}(v,\Gamma\times_{\Delta}\Lambda)\cap\operatorname{\mathsf{odir}}_{i}))$
$\displaystyle\Theta_{i}$ $\displaystyle=\Theta_{i-1}.$

Case 2: $(e,f)\notin E_{\mathbb{S}}$.

Let $g$ be the output of the bounded forced path procedure with input the pair
$(e,f)$ and the integer $C\cdot m^{2}\cdot n$. By Lemma 7.6 this may be done
in $O(m^{3}\cdot n)$ number of steps. Then we are left with two subcases.

Subcase 2.1: $t(g)\in\bar{V}(\Gamma)\times\bar{V}(\Lambda)$.

If this is the case, then we set:

$\displaystyle\operatorname{\mathsf{odir}}_{i}$
$\displaystyle=\operatorname{\mathsf{odir}}_{i-1}\cup(e,f)$
$\displaystyle\operatorname{\mathsf{ndir}}_{i}$
$\displaystyle=(\operatorname{\mathsf{ndir}}_{i-1}-(e,f))\cup(\operatorname{St^{+}}(t(g),\Gamma\times_{\Delta}\Lambda)-(\operatorname{St^{+}}(t(g),\Gamma\times_{\Delta}\Lambda)\cap\operatorname{\mathsf{odir}}_{i}))$
$\displaystyle\Theta_{i}$ $\displaystyle=\Theta_{i-1}\cup g.$

Subcase 2.2: $t(g)\notin\bar{V}(\Gamma)\times\bar{V}(\Lambda)$.

Then let $j$ be the largest index such that $g(j)\in V^{f}(\Gamma)\times
V^{f}(\Lambda)$. If no such integer exists, then set $j=0$. We update our sets
as follows:

$\displaystyle\operatorname{\mathsf{odir}}_{i}$
$\displaystyle=\operatorname{\mathsf{odir}}_{i-1}\cup(e,f)$
$\displaystyle\operatorname{\mathsf{ndir}}_{i}$
$\displaystyle=\operatorname{\mathsf{ndir}}_{i-1}-(e,f)$
$\displaystyle\Theta_{i}$ $\displaystyle=\Theta_{i-1}\cup g[:j].$

We have the following properties of $\Theta_{k}$ and
$\operatorname{\mathsf{odir}}_{k}$ that follow from the construction:

  1. (1)

$\Theta^{s}\cap\Theta^{\circ}\subset\Theta_{k}$,

  2. (2)

$E(s(\mathbb{S}))\cap E(\Theta_{k})=\emptyset$,

  3. (3)

for each $v\in\bar{V}(\Gamma)\times\bar{V}(\Lambda)$, there exists an
accepting path $g:I\to\Theta$ traversing $v$ if and only if
$v\in\bigcup_{(e,f)\in\operatorname{\mathsf{odir}}_{k}}o(e,f)$.

By property (1), we have $(V^{f}(\Gamma)\times V^{f}(\Lambda))\cap
V(\Theta_{k})\neq\emptyset$ if and only if $A\neq\emptyset$. Hence, we have
shown that may decide if $A\neq\emptyset$ in $O(m^{q}\cdot n)$ time for some
$q\geq 0$. It remains to show that we can determine if $B\neq\emptyset$ in
$O(m^{q}\cdot n)$ time for some $q\geq 0$.

Suppose that $B\neq\emptyset$. Then there is a pair of paths
$g_{1},g_{2}:I\to\Theta$ such that $o(g_{1})=(x,y)$,
$t(g_{1})=o(g_{2})\in\bar{V}(\Gamma)\times\bar{V}(\Lambda)$, $t(g_{2})\in
V^{f}(\Theta)$ and $g_{2}$ lifts to $s:\mathbb{S}\to\Theta$. By construction
of property (3), it suffices to determine if there is a path $g:I\to\Theta$
such that $o(g)\in\bigcup_{(e,f)\in\operatorname{\mathsf{odir}}_{k}}o(e,f)$,
$t(g)\in V^{f}(\Theta)$ and $g$ lifts to $s:\mathbb{S}\to\Theta$. In order to
determine if such a path exists, we essentially repeat the algorithm from
Proposition 7.3. Let
$(u,v)\in\bigcup_{(e,f)\in\operatorname{\mathsf{odir}}_{k}}o(e,f)$ and
$S_{\Gamma}\subset\mathbb{S}_{\Gamma}$,
$S_{\Lambda}\subset\mathbb{S}_{\Lambda}$ a pair of connected components. Set

$\displaystyle V^{i}(S_{\Gamma})$ $\displaystyle=s_{\Gamma}^{-1}(u)\cap
V(S_{\Gamma}),$ $\displaystyle V^{i}(S_{\Lambda})$
$\displaystyle=s_{\Lambda}^{-1}(v)\cap V(S_{\Lambda}),$ $\displaystyle
V^{f}(S_{\Gamma})$ $\displaystyle=s_{\Gamma}^{-1}(V^{f}(\Gamma))\cap
V(S_{\Gamma}),$ $\displaystyle V^{f}(S_{\Lambda})$
$\displaystyle=s_{\Lambda}^{-1}(V^{f}(\Lambda))\cap V(S_{\Lambda}).$

Then $\operatorname{Core}(S_{\Gamma}\times_{\Delta}S_{\Lambda})$ has an
accepting path if and only if there is a path $g:I\to\Theta$ such that
$o(g)=(u,v)$, $t(g)\in V^{f}(\Theta)$ and $g$ lifts to
$s:\operatorname{Core}(S_{\Gamma}\times_{\Delta}S_{\Lambda})\to\Theta$. Thus,
by iterating over all such vertices and pairs of components, we may decide if
$B\neq\emptyset$. Now, just as in the proof of Proposition 7.3, we may use
Theorem 7.1 to obtain the required bounds. ∎

## References

  * [1] J.-C. Birget.  Intersection and union of regular languages and state complexity.  Information Processing Letters, 43(4):185–190, 1992.
  * [2] M. de Oliveira Oliveira and M. Wehar.  Intersection non-emptiness and hardness within polynomial time.  In M. Hoshi and S. Seki, editors, Developments in Language Theory, pages 282–290, Cham, 2018. Springer International Publishing.
  * [3] M. de Oliveira Oliveira and M. Wehar.  On the fine grained complexity of finite automata non-emptiness of intersection.  In N. Jonoska and D. Savchuk, editors, Developments in Language Theory, pages 69–82, Cham, 2020. Springer International Publishing.
  * [4] J. Delgado, E. Ventura, and A. Zakharov.  Relative order and spectrum in free and related groups, 2021.  arXiv:2105.03798.
  * [5] W. Dicks and E. Formanek.  The rank three case of the Hanna Neumann Conjecture.  Journal of Group Theory, 4, 2001.
  * [6] M. Domaratzki and K. Salomaa.  Transition complexity of language operations.  Theoretical Computer Science, 387(2):147–154, 2007.  Descriptional Complexity of Formal Systems.
  * [7] N. J. Fine and H. S. Wilf.  Uniqueness theorems for periodic functions.  Proceedings of the American Mathematical Society, 16(1):109–114, 1965.
  * [8] J. Friedman.  Sheaves on graphs, their homological invariants, and a proof of the Hanna Neumann Conjecture.  Memoirs of the American Mathematical Society, 233(1100), 2015.
  * [9] L. Giambruno.  Automata-theoretic methods in free monoids and free groups.  PhD thesis, Universita degli Studi di Palermo, 2008.
  * [10] Y.-S. Han and K. Salomaa.  State complexity of union and intersection of finite languages.  Int. J. Found. Comput. Sci., 19:581–595, 2008.