arXiv:1512.08539v1 [math.GR] 28 Dec 2015

ALGORITHMIC ASPECTS OF BRANCHED COVERINGS I.
VAN KAMPEN’S THEOREM FOR BISETS
LAURENT BARTHOLDI AND DZMITRY DUDKO

Abstract. We develop a general theory of bisets: sets with two commuting
group actions. They naturally encode topological correspondences.
Just as van Kampen’s theorem decomposes into a graph of groups the
fundamental group of a space given with a cover, we prove analogously that
the biset of a correspondence decomposes into a graph of bisets: a graph with
bisets at its vertices, given with some natural maps. The fundamental biset of
the graph of bisets recovers the original biset.
We apply these results to decompose the biset of a Thurston map (a
branched self-covering of the sphere whose critical points have finite orbits)
into a graph of bisets. This graph closely parallels the theory of Hubbard
trees.
This is the first part of a series of five articles, whose main goal is to prove
algorithmic decidability of combinatorial equivalence of Thurston maps.

1. Introduction
This is the first of a series of five articles, and develops the theory of decompositions of bisets. For an overview of the series, see [1].
1.1. Bisets. Bisets are algebraic objects used to describe continuous maps up to
isotopy. Classically, a map f : pY, :q Ñ pX, ˚q between pointed spaces induces
a homomorphism between the fundamental groups f˚ : π1 pY, :q Ñ π1 pX, ˚q. If,
however, f does not preserve any natural base points, it is much more convenient
to consider a weaker kind of relation between π1 pY, :q and π1 pX, ˚q: this is precisely
a biset, namely a set Bpf q with two commuting group actions, of π1 pY, :q on the left
and of π1 pX, ˚q on the right. Bisets may naturally be multiplied, and the product
of bisets corresponds to composition of the maps.
Another advantage of bisets is that only bijective maps may be inverted, while
every biset B has a contragredient B _ , obtained by dualizing the actions. Thus it
f
i
is almost as easy to handle correspondences Y Ð Z Ñ X as genuine maps Y Ñ X,
see §4: the biset of the correspondence is Bpiq_ b Bpf q.
Van Kampen’s theorem is a cornerstone in algebraic topology: given a space X
covered by (say) open subsets pUα q, the theorem expresses the fundamental group
of a space in terms of the fundamental groups of the pieces Uα and of their intersections. This is best expressed in terms of a graph of groups, namely a simplicial
graph with groups attached to its vertices and edges. The fundamental group of a
graph of groups is algebraically constructed in terms of the graph data, and recovers
the fundamental group of X.
Date: December 28, 2015.
Partially supported by ANR grant ANR-14-ACHN-0018-01 and DFG grant BA4197/6-1.
1

2

LAURENT BARTHOLDI AND DZMITRY DUDKO

The main construction in this article is a graph of bisets expressing the decomposition of a continuous map, or more generally a topological correspondence, between
spaces given with compatible covers, see Definition 3.8. We single out the subclass
of fibrant graphs of bisets. Graphs of bisets can be multiplied, and the product of
fibrant graphs of bisets is again fibrant.
We construct in Definition 3.13 the fundamental biset of a graph of bisets, and
show in Corollary 3.20 how they can be conveniently computed for fibrant graphs
of bisets.
Our central result, Theorem 4.8, is an analogue of van Kampen’s theorem in the
language of bisets. It expresses the biset of a correspondence as the fundamental
biset of a graph of bisets constructed from restrictions of the correspondence to
elements of the cover.
1.2. Applications. We then apply these results, in §5, to complex dynamics. Following Thurston, we consider branched coverings of the sphere, namely self-maps
f : S 2 ý that are locally modeled on z ÞÑ z d in complex charts. The subset of S 2
at which the local model is z d with d ą 1 is called the critical set of f , and the
post-critical set P pf q is the strict forward orbit of the critical set. A Thurston map
is a branched covering of the sphere for which P pf q is finite. Examples are rational
maps such as f pzq “ z 2 ´ 1.
The simplest example of all is the map f pzq “ z d itself, with P pf q “ t0, 8u.
p
p
The map f is a covering on Czt0,
8u, and π1 pCzt0,
8u, 1q “ Z. In this case, we can
give the biset of f quite explicitly: it is Bpf q “ Z, with right and left actions given
by m ¨ b ¨ n “ dm ` b ` n. We call such bisets regular cyclic bisets, and we define a
cyclic biset as a transitive biset over cyclic groups.
The next simplest maps are complex polynomials f pzq with finite post-critical
set. They have been intensively studied, in particular via their Hubbard tree, see [6,
7,14]. This is a dynamically-defined f -invariant tree containing P pf q and embedded
in C. We apply the van Kampen Theorem 4.8 to the Hubbard tree and obtain
in this manner a decomposition of the biset of f as a graph of cyclic bisets, see
Theorem 5.5.
One of the advantages in working with branched coverings rather than rational
maps is that surgery operations are possible. For example, given a Thurston map
f with a fixed point z mapping locally to itself by degree d ą 1, and given a
topological polynomial g of degree d, a small neighbourhood of f may be removed
to be replaced by a sphere, punctured at 8, on which g acts. One calls the resulting
map the tuning of f by g.
This operation has a transparent interpretation in terms of graphs of bisets: it
amounts to replacing a cyclic biset, at a vertex of the graph of bisets of f , with the
biset Bpgq; see Theorem 5.8.
In case f itself also has degree d, one calls the resulting map h the mating
of f and g. The sphere on which h acts is naturally covered by the spheres on
which f , respectively g act, and the “equator” on which they overlap. Thus h is
naturally expressed by a graph of bisets with two vertices corresponding to f and
g respectively, and an edge corresponding to the equator; see Theorem 5.9.
Laminations allow Julia sets of polynomials to be obtained out of the Julia set
of z d , namely a circle, by pinching. Similarly, van Kampen’s Theorem 4.8 applied
to the lamination of f decomposes the biset Bpf q into a graph of bisets made of
trivial bisets and one regular cyclic biset (the biset of z d ). We compute it explicitly

VAN KAMPEN’S THEOREM FOR BISETS

3

for the map f pzq “ z 2 ´ 1, and describe in this manner, in §5.6, the mating of z 2 ´ 1
with an arbitrary quadratic polynomial.
1.3. Notation. We introduce some convenient notations, which we will follow
throughout the series of articles. For a set S, we write S Ó. for its permutation
group. This has the mnemonic advantage that #pS Ó.q “ p#Sq!. We always write
1 for the identity map from a set to itself. The restriction of a map f : Y Ñ X to
a subset Z Ă Y is written f åZ . Self-maps are written f : X ý in preference to
f : X Ñ X.
Paths are continuous maps γ : r0, 1s Ñ X; the path starts at γp0q and ends at
γp1q. We write γ#δ for concatenation of paths, following first γ and then δ; this is
defined only when γp1q “ δp0q. We write γ ´1 for the inverse of a path.
We write « for isotopy of paths, maps etc, „ for conjugacy or combinatorial
equivalence, and – for isomorphism of algebraic objects.
A graphs of groups is a graph X with groups associated with X’s vertices and
edges. We always write Gx for the group associated with x P X; thus if Y is
another graph of groups, we will write Gy for the group associated with y P Y, and
no relationship should be assumed between Gx and Gy . Similarly, in a graph of
bisets B there are bisets Bz associated with z P B, and different graphs of bisets
will all have their bisets written in this manner.
2. Bisets
We show, in this section, how topological data can be conveniently converted
to group theory. We shall extend, along the way, the classical dictionary between
topology and group theory.
Consider a continuous map f : Y Ñ X between path connected topological
spaces, and basepoints : P Y and ˚ P X. Denote by H “ π1 pY, :q and G “ π1 pX, ˚q
their fundamental groups. If f p:q “ ˚, then f induces a homomorphism f˚ : H Ñ G;
however, no such natural map exists if f does not preserve the basepoints.
A solution would be to express f in the fundamental groupoid π1 pXq, whose
objects are X and whose morphisms from x to y consist of all paths from x to y
in X up to homotopy rel their endpoints. However, for computational purposes,
a much more practical solution exists: one chooses basepoints in X and Y , and
expresses f as an H-G-biset.
Definition 2.1 (Bisets). Let H, G be two groups. An H-G-biset is a set B equipped
with a left H-action and a right G-action that commute; namely, a set B and maps
H ˆ B Ñ B and B ˆ G Ñ B, both written ¨, such that
h ¨ h1 ¨ pb ¨ gg 1 q “ hh1 ¨ pb ¨ gg 1 q “ phh1 ¨ bq ¨ gg 1 “ phh1 ¨ bq ¨ g ¨ g 1 ,
so that no parentheses are needed to write any product of h’s, b, and g’s. We will
also omit the ¨, and write the actions as multiplication.
A G-biset is a G-G-biset.
An H-G-set B is left-free if, qua left H-set, it is isomorphic to H ˆ S for a set S
(where, implicitly, the left action of H is by multiplication on the first coördinate);
it is right-free if, qua right G-set, B is isomorphic to T ˆ G. It is left-principal,
respectively right-principal, if furthermore S, respectively T may be chosen a singleton, so that the respective action is simply transitive; more generally, it is left,
respectively right free of rank r if #S “ r, respectively #T “ r.
4

4

LAURENT BARTHOLDI AND DZMITRY DUDKO

Bisets should be thought of as generalizations of homomorphisms. Indeed, if
φ : H Ñ G is a group homomorphism, one associates with it the H-G-set Bφ ,
which, qua right G-set, is plainly G; the left H-action is by
h ¨ b “ hφ b.
All bisets of the form Bφ are right-principal; and they are left-free if and only if φ
is injective. Note that we write the evaluation of maps as ‘f pxq’, unless the map is
a group homomorphism, in which case we write ‘xf ’.
Let us return to our continuous map f : Y Ñ X, but drop the assumption
f p:q “ ˚. The H-G-biset of f is defined as homotopy classes of paths rel their
endpoints:
(1)

Bpf q “ Bpf, :, ˚q “ tγ : r0, 1s Ñ X | γp0q “ f p:q, γp1q “ ˚u{„.

For paths γ, δ : r0, 1s Ñ X with γp1q “ δp0q, we denote by γ#δ their concatenation,
defined by
#
γp2tq
if 0 ď t ď 21 ,
pγ#δqptq “
δp2t ´ 1q if 12 ď t ď 1;
and, for a path γ : r0, 1s Ñ X, its reverse γ ´1 is defined by
γ ´1 ptq “ γp1 ´ tq.
The left action of H on Bpf q is, for a loop λ in Y based at :,
rλs ¨ rγs “ rf ˝ λ#γs,
and the right action of G is, for a loop µ in X based at ˚,
rγs ¨ rµs “ rγ#µs.
It is then clear that Bpf q is a right-principal biset. If f p:q “ ˚, then Bpf q is
naturally isomorphic to Bf˚ .
As we will see in §4, bisets actually encode topological correspondences, as generalizations of continuous maps.
2.1. Morphisms. We consider three different kinds of maps between bisets.
Definition 2.2 (Biset morphisms). Let H BG and H B 1 G be two H-G-bisets. A
morphism between them is a map β : B Ñ B 1 such that
hbβ g “ phbgqβ

for all h P H, b P B, g P G.

The definitions of endomorphism, isomorphism, automorphism, monomorphism,
and epimorphism are standard.
Let now H BG and H 1 B 1 G1 be two bisets. A congruence is a triple pψ, β, φq of
maps, with ψ : H Ñ H 1 and φ : G Ñ G1 group homomorphisms, and β : B Ñ B 1 a
map, such that
hψ bβ g φ “ phbgqβ

for all h P H, b P B, g P G.

The map β itself is called a pψ, φq-congruence; therefore a morphism is the same
thing as a p1, 1q-congruence. A congruence in injective if all ψ, β, φ are injective,
and similarly for surjective etc.

VAN KAMPEN’S THEOREM FOR BISETS

5

Consider finally a G-biset G BG and a G1 -biset G1 B 1 G1 . Apart from morphisms
and congruences, a third (intermediate) notion relates them: a semiconjugacy is a
pair pφ, βq of maps, with φ : G Ñ G1 and β : B Ñ B 1 , such that
hφ bβ g φ “ phbgqβ

for all g, h P G, b P B.

In other words, β is a pφ, φq-congruence. Note that we do not require, as is sometimes customary, that β be surjective. A conjugacy is an invertible semiconjugacy,
i.e. a semiconjugacy in which both φ and β are invertible.
4
Note now the following important, if easy, fact: the isomorphism class of a biset
Bφ remembers precisely the homomorphism φ up to inner automorphisms. More
precisely,
Lemma 2.3. Let φ, ψ : H Ñ G be two homomorphisms. Then the bisets Bφ and
Bψ are congruent if and only if there exists an automorphism η of G such that
ψ “ φη; and they are isomorphic if and only if η is inner.
Proof. We only prove the second assertion (“isomorphic bisets if and only if η is
inner”).
Assume first ψ “ φη, and let η be conjugation by g. Then an isomorphism
between the bisets Bφ and Bψ is given by β : b ÞÑ g ´1 b. Indeed,
ph ¨ bqβ “ phφ bqβ “ g ´1 hφ b “ hφη g ´1 b “ hψ bβ “ h ¨ bβ .
Conversely, if Bφ and Bψ are isomorphic, let β be such an isomorphism, and set
g “ p1β q´1 . Because β commutes with the right G-action, which is principal, the
map β must have the form bβ “ 1β b “ g ´1 b, and the same computation as above
shows that ψ “ φη, with η conjugation by g.

2.2. Products. The product of the H-G-biset B with the G-F -biset C is the HF -biset B bG C, defined as
L
B bG C “ B ˆ C tpb, g ¨ cq “ pb ¨ g, cq for all b P B, g P G, c P Cu;
it is naturally an H-F -biset for the left H-action on B and the right F -action on
C. We have the easy
Lemma 2.4. Let φ : H Ñ G and ψ : G Ñ F be group homomorphisms. Then
Bφψ – Bφ bG Bψ .



Note that we stick to the usual topological convention that g ˝ f is first f , then
g; but we use the algebraic order on composition of homomorphisms and bisets, so
that f g means ‘first f , then g’ for composable algebraic objects f and g. In other
words, we may write g ˝ f “ f g.
The contragredient of the H-G-biset B is the G-H-biset B _ , which is B as a set
(but with elements written b̌), and actions
g ¨ b̌ ¨ h “ ph´1 ¨ b ¨ g ´1 qˇ.
If φ : H Ñ G is invertible, then we have pBφ q_ “ Bφ´1 . In all cases, we have a
canonical isomorphism pB b Cq_ “ C _ b B _ .
Remark 2.5. Answering a question of Adam Epstein, we may define HompB, Cq “
B _ b C, and then note that ‘b’ is the adjoint to this internal Hom functor, namely
HompC b B, Dq “ HompB, HompC, Dqq is natural.

6

LAURENT BARTHOLDI AND DZMITRY DUDKO

Products allow us to write congruences in terms of morphisms:
Lemma 2.6. Let ψ : H Ñ H 1 and φ : G Ñ G1 be homomorphisms, let B be an
H-G-biset, and let B 1 be an H 1 -G1 -biset. Then there is an equivalence between
congruences pψ, β, φq : B Ñ B 1 and morphisms γ : Bψ_ b B b Bφ Ñ B 1 , in the
following sense: there is a natural map θ : B Ñ Bψ_ b B b Bφ defined by b ÞÑ
1_ b b b 1, and the congruence pψ, β, φq factors as pψ, β, φq “ θγ.

1
In particular, the bisets G BG and G1 BG
1 are conjugate if and only if there exists
1
1
_
an isomorphism φ : G Ñ G with B – Bφ b B b Bφ “ Bφ´1 b B b Bφ .

2.3. Transitive bisets. We call an H-G-biset transitive if it consists of a single
H ˆ G-orbit. If desired, transitive bisets may be viewed as quotients of rightprincipal bisets (namely, bisets coming from homomorphisms), as follows:
Lemma 2.7. Let B be a transitive H-G-biset. Then there exist a group K and
homomorphisms φ : K Ñ G, ψ : K Ñ H such that B “ Bψ_ bK Bφ . Furthermore,
there exists a unique minimal such K, in the sense that if pK 1 , φ1 , ψ 1 q also satisfy
B “ Bψ_1 bK 1 Bφ1 then there exists a homomorphism τ : K 1 Ñ K with τ φ “ φ1 and
τ ψ “ ψ1 :
K1
τ
ψ1

K

ψ

H

φ1
φ

G

Proof. Choose a basepoint b P B, and define
K “ tph, gq P H ˆ G | bg “ hbu.
The homomorphisms ψ, φ are given by projection on the first, respectively second
coördinate. To construct an isomorphism β : Bψ_ bBφ Ñ B, set ph_ bgqβ :“ h´1 bg;
note that this is well-defined because h_ b g “ ph1 q_ b g 1 if and only if there exists
ph2 , g 2 q P K with g 1 “ g 2 g and h1 “ h2 h; and then h´1 bg “ ph1 q´1 bg 1 .
To prove the unicity of K, consider a group K 1 with homomorphisms φ1 : K 1 Ñ G
and ψ 1 : K 1 Ñ H, and an isomorphism β : Bψ_1 bK 1 Bφ1 Ñ B. Define then the map
τ : K 1 Ñ K as follows. Write β ´1 pbq “ pb1 , b2 q. For k 1 P K 1 , define h P H, g P G by
βpb1 , k 1 b2 q “ hb “ bg and then τ pk 1 q “ ph, gq.



Note that the product of two bisets, when expressed as groups K, L with homomorphisms as in the lemma, is nothing but the fibre product of the corresponding
groups K, L.
If furthermore B is left-free, then the construction can be made even more explicit: the biset Bψ_ is a subbiset of B, and Bφ is a left- and right-free. We summarize
this in the
Proposition 2.8. Let B be a left-free transitive H-G-biset. Choose b P B. Define
‚ Gb :“ tg P G | bg P Hbu, the right stabilizer of b;

VAN KAMPEN’S THEOREM FOR BISETS

‚ D :“ Gb GG , the natural Gb -G biset;
‚ C _ :“ Hb, an H-Gb subbiset of H BGb .
Then C is a right-principal biset and B – C _ bGb D.

7



2.4. Combinatorial equivalence of bisets. Let G BG be a left-free biset. For
bn
every n ě 0 we have a right G-action on 1 bG BG
, which gives a well defined
action on the set
ğ
bn
T :“
1 bG B G
.
ně0

The G-set T naturally has the structure of a rooted tree, by putting an edge from
1 b b1 b ¨ ¨ ¨ b bn to 1 b b1 b ¨ ¨ ¨ b bn b bn`1 for all bi P B. The action of G on T is
self-similar in an appropriate labeling of T , see [12, Chapter 2].
Set G1 :“ G{ kerpactionq; thus G1 is the quotient of G so that the induced action
on T is faithful. As in [13] we say that G BG is combinatorially equivalent to
1
G1 BG1

:“ G1 bG B bG G1 .

1
(The motivation is dynamical: if G BG is contracting, then so is G1 BG
1 and, more1
over, the limit dynamical systems associated with G BG and G1 BG1 are topologically
conjugate, see e.g. [12, Corollary 3.6.7].)
1
We say that two left-free G BG and H CH are combinatorially equivalent if G1 BG
1
1
and H 1 CH 1 are conjugate.
It is easy to check that any surjective semi-conjugacy pφ, βq : G BG Ñ H CH
1
1
between left-free bisets descents into a semi-conjugacy pφ1 , β 1 q : G1 BG
1 Ñ H 1 CH 1 .
We say that a surjective semi-conjugacy pφ, βq : G BG Ñ H CH between left-free
1
1
bisets respects combinatorics if pφ1 , β 1 q : G1 BG
1 Ñ H 1 CH 1 is a conjugacy (so that
G BG and H CH are combinatorially equivalent).

2.5. Biset presentations. Let B be a left-free H-G-biset. Choose a basis of B,
namely a subset S of B such that B, qua left H-set, is isomorphic to H ˆ S. In
other words, S contains precisely one element from each H-orbit of B.
The structure of the biset is then determined by the right action in that description. For g P G and s P S, there are unique ph, tq P H ˆ S such that sg “ ht. The
choice of basis therefore leads to a map S ˆ G Ñ H ˆ S, or, which is the same, a
map Φ : G Ñ pH ˆ SqS .
Associativity of the biset operations yields, as is easy to see, that Φ is a group
homomorphism G Ñ H o S Ó.. This last group, the wreath product of H with the
symmetric group S Ó. on S, is by definition the semidirect product of H S with S Ó., in
which S Ó. acts by permutations of the coördinates in H S . We call Φ a wreath map
of the biset B.
Wreath products are best thought of in terms of decorated permutations: one
writes permutations of S in the standard arrow diagram notation, but adds a label
belonging to H on each arrow in the permutation. Permutations are multiplied by
concatenating arrow diagrams and multiplying the labels.
A presentation of B is a choice of generating sets Γ, ∆ for G, H respectively, and
for each g P Γ an expression of the form
g “ !h1 , . . . , hd "pi1 , . . . q,
describing Φpgq; the hi are words in ∆, and pi1 , . . . q is a permutation of S –
t1, . . . , du in disjoint cycle format.

8

LAURENT BARTHOLDI AND DZMITRY DUDKO

Lemma 2.9. If Φ, Ψ : G Ñ H o dÓ. are two wreath maps of the same biset
then there exists w P H o dÓ. such that Ψ “ Φ ¨ ph ÞÑ hw q.

H BG ,

Proof. Let S, T be the bases of B in which Φ, Ψ are computed, and identify S, T
with t1, . . . , du by writing S “ ts1 , . . . , sd u and T “ tt1 , . . . , td u. In B, write
tiπ “ wi ¨ si for i “ 1, . . . , d, defining thus w “ !w1 , . . . , wd "π P H o dÓ..
Consider an arbitrary g P G, and write
Φpgq “ !g1 , . . . , gd "σ,

Ψpgq “ !h1 , . . . , hd "τ.

We therefore have si g “ gi siσ and ti g “ hi tiτ for all i. Now
hiπ tiπτ “ tiπ g “ wi´1 si g “ wi´1 gi siσ “ wi´1 gi wiσπ tiσπ ,
so Φpgqw “ Ψpgq.



It may help to introduce an example here. Consider the map f pzq “ z d from the
cylinder X “ Czt0u to itself. Choose ˚ “ : “ 1 as basepoints, and identify π1 pX, ˚q
with Z by choosing as generator the loop τ ptq “ expp2iπtq.
The biset Bpf q is the set of homotopy classes of loops at 1, and so may be
naturally identified with Z. The biset structure is given by n ¨ b ¨ m “ dn ` b ` m
for n, m P Z – π1 pX, ˚q and b P Z – Bpf q. Thus Bpf q is left-free of rank d,
and a basis is a complete set of congruence representatives modulo d, for example
t0, 1, . . . , d ´ 1u. In that basis, the wreath map reads
Φpτ q “ !1, . . . , 1, τ "p1, 2, . . . , dq,
or in diagram notation
τ“

τ

2.6. Conjugacy classes in groups. We will, in later articles, consider conjugacy
classes so as to represent unbased loops in topological spaces. There are various
applications; for example, a fundamental construction by Goldman [8] defines a Lie
bracket structure on the vector space spanned by conjugacy classes in π1 pX, ˚q for
a closed surface X. We consider, here, the general case of groups and bisets.
Let GG denote the set of conjugacy classes of the group G, and consider a leftfree H-G-biset B. Choose a basis S of B, whence a wreath map Φ : G Ñ H o S Ó..
Consider g G P GG , write Φpgq “ !h1 , . . . , hd "π, and let S1 , . . . , S` be the orbits
of π on S. For each j “ 1, . . . , `, let kj be the product of the hi ’s along the orbit
Sj ; namely, if Sj “ ts1 , . . . , sdj u with sπi “ si`1 , indices being computed modulo
dj , then kj “ hs1 hs2 ¨ ¨ ¨ hsdj . The multiset tpdj , kjH q | i “ j, . . . , `u consisting of
degrees and conjugacy classes in H is called the lift of g G .
Lemma 2.10. The lift of g G is independent of all the choices made: of g in its
conjugacy class, of the basis S, and of the cyclic ordering of the orbit Sj .
Proof. Different choices of bases give conjugate wreath maps, by Lemma 2.9.



Let QGG denote the vector space spanned by the conjugacy classes GG , and
consider again a left-free H-G-biset B. Then the lift operation gives rise to a linear

VAN KAMPEN’S THEOREM FOR BISETS

9

map B ˚ : QGG Ñ QH H , defined on the basis by
ÿ

B ˚ pg G q :“

(2)

G
pdi ,hH
i qPlift of g

kjH
,
dj

called the Thurston endomorphism of B.
3. Graphs of bisets
We define here the fundamental notion in this article: viewing groups as fundamental groups of spaces, bisets describe continuous maps between spaces. Graphs of
groups describe decompositions of spaces, and graphs of bisets describe continuous
maps that are compatible with the decompositions.
3.1. Graphs of groups. We begin by precising the notion of graph we will use;
it is close to Serre’s [15], but allows more maps between graphs. In particular, we
allow graph morphisms that send edges to vertices.
Definition 3.1 (Graphs). A graph X is a set X “ V \ E, decomposed in two
subsets called vertices and edges respectively, equipped with two self-maps x ÞÑ x´
and x ÞÑ x, and subject to axioms
(3)

@x P X :

x “ x,

x´ P V,

and x “ x´ ô x “ x ô x P V.

The object x is called the reverse of x. Setting x` “ pxq´ , the vertices x´ , x` are
respectively the origin and terminus of x.
4
We write V pXq and EpXq for the sets of vertices and edges respectively in a graph
´
X. A path is a sequence pe1 , . . . , en q of edges with e`
i “ ei`1 for all i “ 1, . . . , n ´ 1.
A graph is connected if there exists a path joining any two objects. A circuit is a
´
sequence pe1 , . . . , en q of edges with e`
i “ ei`1 for all i, indices taken modulo n. A
tree is a graph with no non-trivial circuits; that is in every circuit pe1 , . . . , en q one
has ei`1 “ ei for some i.
A graph morphism is a map θ : Y Ñ X satisfying θpyq “ θpyq and θpy ´ q “ θpyq´
for all y P Y. Note that θ maps the vertices of Y to those of X. It is simplicial if
furthermore θ maps the edges of Y to those of X.
A graph of groups is a connected graph X “ V \ E, with a group Gx associated
with every x P X, and homomorphisms pq´ : Gx Ñ Gx´ and pq : Gx Ñ Gx for each
x P X, satisfying the same axioms as (3), namely the composition Gx Ñ Gx Ñ
Gx “ Gx is the identity for every x P X, and if x P V then the homomorphisms
Gx Ñ Gx´ and Gx Ñ Gx are the identity. For g P Ge we write g ` “ g ´ . The
graph of groups is still denoted X.
Let X “ V \ E be a graph of groups. For v, w P V , consider the set
(4)
`
´
`
Πv,w “ tpg0 , x1 , g1 , . . . , xn , gn q | xi P X, x´
1 “ v, xi “ xi`1 , xn “ w, gi P Gx` “ Gx´ u,
i

i`1

of (group-decorated) paths from v to w. As a special case, if v “ w then we allow
n “ 0 and g0 P Gv “ Gw . Say that two paths are equivalent, written „, if they
differ by a finite sequence of elementary local transformations of the form pghq Ø
pg, x, 1, x, hq for some x P X and g, h P Gx´ , or of the form pgh´ , x, kq Ø pg, x, h` kq
for some x P X and g P Gx´ , h P Gx , k P Gx` , or of the form pg, x, hq Ø pghq for
some x P V and g, h P Gx .

10

LAURENT BARTHOLDI AND DZMITRY DUDKO

The product of two paths pg0 , x1 , . . . , gm q and ph0 , y1 , . . . , hn q is defined if x`
m “
and equals pg0 , x1 , . . . , gm h0 , y1 , . . . , hn q; this product Πu,v ˆ Πv,w Ñ Πu,w is
compatible with the equivalence relation. The fundamental groupoid π1 pXq of X
is a groupoid with object set V , and with morphisms between v and w the set
π1 pX, v, wq “ Πv,w {„ of equivalence classes of paths from v to w.
In particular, for v P V , the fundamental group π1 pX, vq is Πv,v {„. If X is
connected, then π1 pX, vq is up to isomorphism independent of the choice of v P V .
In fact, the elements xi in a path may be assumed to all belong to E, and if
xi`1 “ xi then the element gi`1 may be assumed not to belong to pGxi`1 q´ . Such
paths are called reduced, and Πv,w {„ may be identified with the set of reduced
paths from v to w.
In a more algebraic language, the fundamental groupoid π1 pXq is the Ů
universal
groupoid with object set V , and whose morphism set is generated by X \ vPV Gv ;
the source and target of x P X are x´ and x` respectively; the source and target
of g P Gv are v; the relations are those of the Gv as well as v “ 1 P Gv for all
v P V , and xx “ 1 P Gx´ and g ´ x “ xg ` for all x P X and g P Gx . The path
pg0 , x1 , . . . , gn q is identified with g0 x1 . . . gn . The following property follows easily
from the definitions:
y1´ ,

Lemma 3.2 (e.g. Serre [15, §5.2]). Let X be a graph of groups. If all morphisms
Gx Ñ Gx´ are injective, then all natural maps Gx Ñ π1 pX, ˚q are injective.

3.2. Decompositions and van Kampen’s theorem. Graphs of groups, and
their fundamental group, generalize decompositions of spaces and their fundamental
group. Here is a useful example of graphs of groups:
Example 3.3. If X be a path connected surface with at least one puncture, consider a graph X drawn on X which contains precisely one puncture in each face.
Then X deformation retracts to X, and the groups π1 pX, ˚q and π1 pX, ˚q are isomorphic. Here we consider X as a graph of groups in which all groups Gx are
trivial.
Definition 3.4 (Finite 1-dimensional covers). Consider a path connected space X,
covered by a finite collection of path connected subspaces pXv qvPV . It is a finite
1-dimensional cover of X if
‚ for every v, w P V and for every path connected component X 1 of Xu X Xv
r 1 Ą X 1 and an Xw Ă X 1 such that
there are an open neighborhood X
1
r is a homotopy equivalence;
Xw ãÑ X
‚ if Xu Ď Xv Ď Xw then u “ v or v “ w.
We order V by writing u ă v if Xu Š Xv .
4
Remark 3.5. In a classical formulation of van Kampen’s theorem it is assumed
that all Xv are open subsets of X. Then every curve γ Ă X is a concatenation of
finitely many curves γi where each γi lies entirely in some Xvpiq .
For our dynamical purposes it is more convenient to allow the Xv to be closed
subsets of X. Thus we add the condition that Xw is homotopy equivalent to an
open neighborhood of Xw . Under this assumption every curve γ Ă X is, up to
homotopy rel endpoints, a concatenation of finitely many curves γi which all lie
entirely in some Xvpiq .
Definition 3.6 (Graphs of groups from covers). Consider a path connected space
X with a 1-dimensional cover pXv qvPV . It has an associated graph of groups X,

VAN KAMPEN’S THEOREM FOR BISETS

11

defined as follows. The vertex set of X is V . For every pair u ă v there are edges e
and ē connecting u “ e´ “ ē` and v “ e` “ ē´ , and we let E be the set of these
edges. Set X “ V \ E.
Choose basepoints ˚v P Xv for all v P V , and set Gv :“ π1 pXv , ˚v q. For every
edge e with e´ ă e` choose a path γe : r0, 1s Ñ Xe` from ˚e´ to ˚e` , set Ge :“ Ge´
and define Ge Ñ Ge´ :“ 1 and Ge Ñ Ge` by γ ÞÑ γe´1 #γ#γe . Finally for edges
e with e´ ą e` set Ge :“ Gē and γē “ γe´1 and define morphisms Ge Ñ Ge´ and
Ge Ñ Ge` as Gē Ñ Gē` and Gē Ñ Gē´ respectively.
4
The graph of groups X depends on the choice of basepoints ˚v and paths γe , but
mildly: we will show in Lemma 4.9 that the congruence class of X is independent
of the choice of ˚v and γe .
Here is a simple example: on the left, the subspaces Xv are the simple loops and
the two triple intersection points; on the right, the corresponding graph of groups,
with trivial or infinite cyclic groups.

Z‚
‚

1

Z
‚

‚Z
1

‚

Z‚

‚Z

Theorem 3.7 (van Kampen’s Theorem). Let X be a path connected space with
finite 1-dimensional cover pXv q and a choice of basepoints ˚v P Xv as well as paths
connecting ˚u and ˚v if Xu Š Xv . Let X be the associated graph of groups.
Then, for every v, the groups π1 pX, ˚v q and π1 pX, vq are isomorphic.
Sketch of proof. The isomorphism θ : π1 pX, vq Ñ π1 pX, ˚v q is defined by
θpg0 , e1 , g1 , . . . , en , gn q “ g0 #γe1 # . . . γen #gn .
Every loop γ : r0, 1s Ñ X with γp0q “ γp1q “ ˚v is homotopic to a concatenation of
the above type, see Remark 3.5; thus θ is surjective. By the classical van Kampen
argument (see [11, Chapter IV]), the path θpgq is homotopic to θpg 1 q in X if and
only if g and g 1 are equivalent in π1 pX, vq; thus θ is injective.

In case X is a tree, π1 pX, ˚q is an iterated free product with amalgamation of the
Gv ’s, amalgamated over the Ge ’s. It may be constructed
explicitly as follows: conŤ
sider the set of finite sequences over the alphabet vPV Gv ; identify two sequences
if they differ on subsequences respectively of the form tp1q, pqu; or tpg, hq, pghqu for
g, h in the same Gv ; or tpgq, pgqu where the first, respectively second, ‘g’ denote the
image of g P Ge in Ge´ , respectively Ge` ; and quotient by the equivalence relation
generated by these identifications.
Note the following three operations on a graph of groups X, which does not
change its fundamental group:
(1) split an edge: choose an edge e P E. Add a new vertex v to V , and
´
´
´
replace e, e by new edges e0 , e0 , e1 , e1 with e`
0 “ e1 “ v and e0 “ e and
`
`
e1 “ e . Define the new groups by Gv “ Ge0 “ Ge1 “ Ge , with the
obvious maps between them;

12

LAURENT BARTHOLDI AND DZMITRY DUDKO

(2) add an edge: choose a vertex v P V , and a subgroup H Ď Gv . Add a
new vertex w to V , and add new edges e, e with e´ “ v and e` “ w. Define
the new groups by Ge “ Gv “ H, with the obvious maps between them;
(3) barycentric subdivision: construct a new graph X1 “ V 1 \ E 1 with
V 1 “ X{tx “ xu and E 1 “ E ˆ t`, ´u; for e P E and ε P t˘1u, set
pe, εqε “ eε and pe, εq´ε “ res and pe, εq “ pe, ´εq. Define finally a graph
of groups structure pG1rxs q on X1 by setting G1rxs to be Gx for all rxs P V 1
(recalling that Gx and Gx̄ are isomorphic), and G1pe,εq “ Ge , with the
obvious maps between these groups.
Recall that graph morphisms may send edges to vertices, but not vertices to
(midpoints of) edges. If such a map between the topological realizations of the
graphs is needed, it may be expressed as a map between their barycentric subdivisions.
If X be a graph of groups, let X1 denote the underlying graph of X, but with
trivial groups. Then, on the one hand, π1 pX1 q is the usual fundamental groupoid of
X1 , and π1 pX1 , vq is a free group; on the other hand, there exists a natural morphism
of groupoids π1 pXq Ñ π1 pX1 q.
If X, Y be graphs of groups, θ : Y Ñ X be a graph morphism, and θy be, for every
y P Y, a homomorphism Gy Ñ Gθpyq such that θy pgq´ “ θy´ pg ´ q and θy pgq “ θy pgq
for all g P Gy , then there is an induced morphism of groupoids π1 pYq Ñ π1 pXq. We
do not give a name to these kinds of maps, because they are too restrictive; see the
discussion in the introduction of [4]. We will give later, in §3.9, more examples of
graphs of groups; we now describe in more detail the precise notion of morphisms
between graphs of groups that we will use.
3.3. Graphs of bisets. Just as bisets generalize appropriately to our setting homomorphisms between groups, so do “graphs of bisets” also generalize the notion of
homomorphisms between graphs of groups. In fact, our notion also extends the definition of morphisms between graphs of groups given in [4], in that a “right-principal
graph of bisets” is the same thing as a morphism between graphs of groups in the
sense of Bass.
Definition 3.8 (Graph of bisets). Let X, Y be two graphs of groups. A graph of
bisets Y BX between them is the following data:
‚ a graph B, not necessarily connected;
‚ graph morphisms λ : B Ñ Y and ρ : B Ñ X;
‚ for every z P B, a Gλpzq -Gρpzq -biset Bz , a congruence pq´ : Bz Ñ Bz´ with
respect to the homomorphisms Gλpzq Ñ Gλpzq´ and Gρpzq Ñ Gρpzq´ , and
a congruence pq : Bz Ñ Bz with respect to the homomorphisms Gλpzq Ñ
Gλpzq and Gρpzq Ñ Gρpzq .
These homomorphisms must satisfy the same axioms as (3), namely: the
composition Bz Ñ Bz Ñ Bz “ Bz is the identity for every z P X, and if
z P V , then the homomorphisms Bz Ñ Bz´ and Bz Ñ Bz are the identity.
´
For b P Bz we write b` “ b .
We call B a Y-X-biset.
4
Example 3.9. A graph morphism θ : Y Ñ X, given with homomorphisms θy : Gy Ñ
Gθpyq for all y P Y such that pq´ ˝ θy “ θy´ ˝ pq´ , naturally gives rise to a Y-X-biset
Bθ . Its underlying graph is B “ Y; the maps are λ “ 1 and ρ “ θ. For every z P B,

VAN KAMPEN’S THEOREM FOR BISETS

13

the biset Bz is Gθpzq with its natural right Gθpzq -action, and its left Gz -action is
g ¨ b “ θz pgqb.
Definition 3.10 (Product of graphs of bisets). Let B be a Y-X-biset, and let C be a
X-W-biset. The product of B and C is the following graph of bisets Y DW “ BbX C:
its underlying graph is the fibre product
D “ tpb, cq P B ˆ C | ρpbq “ λpcqu,
with pb, cq´ “ pb´ , c´ q and pb, cq “ pb, cq. The map λ : D Ñ Y is λpb, cq “ λpbq,
and the map ρ : D Ñ W is ρpb, cq “ ρpcq. The biset Bpb,cq is Bb bGρpbq Bc .
4
Properties of the product will be investigated in §3.7. For now we content ourselves
with some illustrative examples.
Lemma 3.11 (See Example 3.9). Let θ : Y Ñ X and κ : X Ñ W be graph morphisms, given with homomorphisms θy : Gy Ñ Gθpyq and κx : Gx Ñ Gκpxq . Then
their bisets satisfy Bθ bX Bκ “ Bθκ .
Proof. We have natural identifications Gy bGx Gx “ Gy between the bisets of
Bθ bX Bκ and those of Bθκ .

The contragredient B_ of the graph of bisets B is defined by exchanging ρ and
λ, and taking the contragredients of all bisets Bz . If θ : Y Ñ X is bijective and all
θy are isomorphisms, then the contragredient of Bθ is Bθ´1 .
The identity biset for products is the following biset X IX : its underlying graph
is X, with maps λ “ ρ “ 1, and bisets Bz “ Gz .
Example 3.12 (See Lemma 2.7; a partial converse to Example 3.9). Let Y BX be
a graph of bisets such that the graph B is connected and Bz is transitive for every
z P B. Suppose that for every z P B we are given an element bz P Bz such that
bz “ bz and pbz q´ “ bz´ for all z P B. Then there exist a graph of groups Z and
morphisms of graphs of groups λ : Z Ñ Y and ρ : Z Ñ X as in Example 3.9 such
that B is isomorphic to B_
λ b Bρ .
Note, however, that it is not always possible to make coherent choices of basepoints bz P Bz . For example, it may happen that pBe q´ X pBf q´ “ H for two edges
e, f with e´ “ f ´ .
Here is a dynamical situation in which this happens. Let f be a rational map
whose Julia set is a Sierpiński carpet, and assume that its Fatou set has two invariant components U, V, perforce with disjoint closures, on which f acts as z ÞÑ z m , z n
respectively. Remove these components, and attach on each of them a sphere with
a self-map that has an invariant Fatou component mapped to itself by the same
degree. To these data correspond a graph of groups X with three vertices (the
main sphere and the two grafted ones), and a graph of bisets X BX describing the
self-map. The basepoint on the main sphere cannot be chosen to coincide with the
basepoints of the grafted spheres, because the Fatou components of the Sierpiński
map have disjoint closures.
3.4. The fundamental biset.
Definition 3.13 (Fundamental biset of graph of bisets). Let B be a Y-X-biset;
choose ˚ P X and : P Y. Write G “ π1 pX, ˚q and H “ π1 pY, :q. The fundamental

14

LAURENT BARTHOLDI AND DZMITRY DUDKO

biset of B is an H-G-biset B “ π1 pB, :, ˚q, constructed as follows.
Ů
zPV pBq π1 pY, :, λpzqq bGλpzq Bz bGρpzq π1 pX, ρpzq, ˚q
*.
(5)
B“"
q P π1 pY, :, λpzq´ q, b P Bz ,
´
`
qb p “ qλpzqb ρpzqp @
p P π1 pX, ρpzq´ , ˚q, z P EpBq
In other words, elements of B are sequences ph0 , y1 , h1 , . . . , yn , b, x1 , . . . , gm´1 , xn , gn q
subject to the equivalence relations used previously to define π1 pXq, as well as
pyn , hb´ g, x1 q Ø pyn , h, λpzq, b` , ρpzq, g, x1 q for all z P B, b P Bz , h P Gλpzq´ ,
g P Gρpzq´ .
4
In particular, if Y “ X are graphs with one vertex and no edges and associated
groups
Ů H, G respectively, the definition simplifies a little: then B is the quotient
of zPV pBq Bz by the relation identifying b´ with b` , for all edges z P B and all
b P Bz , with respective images b˘ in Bz˘ .
If f : Y Ñ X be a continuous map and the spaces X, Y admit decompositions
giving a splitting of their fundamental group as a graph of groups, as in Theorem 3.7, and if f is compatible with the decompositions of X and Y , then Bpf q
will decompose into a graph of bisets, as we will see in Theorem 4.8.
Let X be a graph of groups. Choose ˚ P X, and consider the graph t˚u with a
single vertex and no edge. We treat it as a graph of groups, with group π1 pX, ˚q
attached to ˚, and denote it by X0 . Consider now the following biset X pX, ˚qX0 :
its underlying graph is X; the maps are λ “ 1 and ρpzq “ ˚ for all z P X; and the
bisets are Bz “ π1 pX, z ´ , ˚q; for vertices, this is just π1 pX, z, ˚q, while for edges this
is a left Gz -set via the embedding Gz Ñ Gz´ . The embedding Bz Ñ Bz´ is the
identity, while the map Bz Ñ Bz is b ÞÑ zb.
Lemma 3.14. Write G “ π1 pX, ˚q. Then we have an isomorphism of G-G-bisets
π1 ppX, ˚q, ˚, ˚q – G GG .



The bisets pX, ˚q and pY, :q enable us, using (5), to write π1 pB, :, ˚q more simply.
We will prove Lemma 3.15 in §3.7:
Lemma 3.15. Let Y BX be a graph of bisets, and choose ˚ P X, : P Y. Then
π1 pB, :, ˚q “ π1 ppY, :q_ b B b pX, ˚q, :, ˚q.
Note, in particular, the expression π1 ppX, :q_ bX pX, ˚qq “ π1 pX, :, ˚q of the set of
paths from : to ˚ in X in terms of graphs of bisets.
3.5. Fibrant and covering bisets. We now define a class of graphs of bisets for
which the fundamental biset admits a convenient description.
Definition 3.16 (Fibrant and covering graph of bisets). Let B be a Y-X-graph
of bisets. Then B is a left-fibrant graph of bisets if ρ : B Ñ X is a simplicial
graph-map, and for every vertex v P B and every edge f P X with f ´ “ ρpvq the
map
ğ
(6)
Gλpvq bGλpeq Be Ñ Bv ,
g b b ÞÑ gb´
ePρ´1 pf q
e´ “v

is a Gλpvq -Gf biset isomorphism, for the action of Gf on Bv given via pq´ : Gf Ñ
Gρpvq .

VAN KAMPEN’S THEOREM FOR BISETS

15

If in addition Bz is a left-free biset for every object z P X, then B is a covering,
or left-free, graph of bisets.
If furthermore Bz is left-principal for every z P B and ρ : B Ñ Y is a graph
isomorphism, then B is left-principal. Right-fibrant, -free, and -principal graphs of
bisets are defined similarly. For example, the biset associated with a morphism of
groups as in Example 3.9 is right-principal.
4
We think about (6) as a unique lifting property: we may always rewrite pbq P
π1 pB, :, ˚q as p1 b1 P π1 p,:, ˚q in an essentially unique way, as we will see in Corollary 3.20. We will show in Lemma 3.28 that for left-principal graphs of bisets (6)
follows automatically.
p y the image of Gy in the fundamental
For every object y P Y let us denote by G
py .
groupoid π1 pYq; we write g ÞÑ gp the associated natural quotient map Gy Ñ G
p x and g Ñ gp similarly for x P X. Finally, for z P B we set
We define G
pz :“ G
p λpzq bG
p ρpzq
B
B z bG
G
λpzq

ρpzq

pz .
and denote by b ÞÑ pb the natural quotient map Bz Ñ B
p be the graph of bisets obtained from B by replacing all Gx , Gy , Bz by
Let B
p :, ˚q are natupx , G
py , B
pz respectively. It is immediate that π1 pB, :, ˚q and π1 pB,
G
rally isomorphic via ybx ÞÑ yppbp
x.
Theorem 3.17. Suppose that B is a left-fibrant biset. Then
p is left-fibrant;
(1) B
pz – G
p λpzq bG
(2) B
Bz via the natural map 1 b b b 1 Ð 1 b b;
λpzq
pe Ñ B
pe´ are monomorphisms for all e P B; and
(3) pq´ : B
p
(4) if B is left-free, respectively left-principal, then so is B.
p λpzq b Bz , viewed as a right Gρpzq -set. For
Proof. For z P B let us write Bz1 :“ G
x P X let us write
ğ
Cx :“
Bz1 ,
zPρ´1 pxq

viewed as a right Gx -set. In particular, if f P X is an edge, then (6) gives a bijection
ğ `
˘
p λpe´ q {G
p λpeq ˆ B 1 Ñ Cf ´
G
(7)
e

ePρ´1 pf q

of right Gf -sets. Finally, for x P X we denote by AutpCx q the set of pure automorphisms of Cx :
p λpzq u.
AutpCx q :“ tφ “ pφz qzPρ´1 pxq | φz P pB 1 qÓ., pgbqφz “ g bφz @b P B 1 , g P G
z

z

The right action of Gx on Cx induces a homomorphism
θx : Gx Ñ AutpCx q.
Lemma 3.18. Suppose B is a left-fibrant biset. Then for every edge f P X there
is a natural embedding
#
AutpCf q ãÑ AutpC
´
” f´q `
ı
˘
(8)
pq :
p λpe´ q {G
p λpeq ˆ B 1 ÞÑ pg, bφe q
pφe qePρ´1 pf q ÞÑ pg, bq P G
e
under the identification of Cf ´ given by (7). Moreover, pq´ embeds θf pGf q into
θf ´ pGf ´ q.

16

LAURENT BARTHOLDI AND DZMITRY DUDKO

Proof. The contents of (7) that we use is that every Gf -set occurring in Cf occurs
as a summand of Cf ´ , with multiplicity ě 1. Therefore pq´ is injective. Since the
map pq´ : Gf Ñ Gf ´ is equivariant with respect to the actions on Cf and Cf ´ , we
get θf ´ pGf ´ q – pθf pGf qq´ ď θf ´ pGf ´ q.


Let X1 be the graph of groups obtained from X by replacing each Gx with θx pGx q,
with maps pq´ given by (8). By Lemma 3.2, every θx pGx q embeds into the fundamental groupoid π1 pX1 q. We also have an epimorphism θ : π1 pXq Ñ π1 pX1 q induced
by the epimorphisms θx : Gx Ñ θx pGx q. Therefore, θx : Gx Ñ θx pGx q descends to
p x Ñ θx pGx q. The action of G
p ρpzq on B
pz therefore lifts to B 1 , and this
a map θpx : G
z
completes the proof of Claim (2).
p λpvq gives then Claim (1) as well as Claim (3).
Multiplying (6) on the left by G
pz , and similarly if
p λpzq bG
Finally, if Bz is left-free then so is G
Bz “ Bz1 – B
λpzq
p
Bz is left-principal then so is Bz ; this finishes the proof of Theorem 3.17.


3.6. Canonical form for fibrant bisets. We now derive a canonical expression
for element in a left-fibrant biset. Let us set

S :“

ğ

pz b p
π1 pY, :, λpzqq bGp λpzq B
Gρpzq π1 pX, ρpzq, ˚q

zPV pBq

ğ
–

π1 pY, :, λpzqq bGλpzq Bz bGρpzq π1 pX, ρpzq, ˚q.

zPV pBq

Then π1 pB, :, ˚q – S{„ , where „ is the equivalence relation from (5). For any path
p P π1 pX, x, ˚q starting at some vertex x P X, we consider the following subset of S:

Sppq :“

ď

pz b p
π1 pY, :, λpzqq bGp λpzq B
Gρpzq p

zPρ´1 pxq

viewed as a left π1 pY, :q-set.
Proposition 3.19. Suppose B is a left-fibrant graph of bisets. Then for every
p1 , p2 P π1 pX, ´, ˚q the relation „ on Spp1 q ˆ Spp2 q is, in fact, a π1 pY, :q-set isomorphism between Spp1 q and Spp2 q.
Proof. If p P π1 pX, x, ˚q then, clearly, Sppq “ Spgpq for every g P Gx . We now show
that for every edge f P X with f ` “ x the equivalence qb´ p “ qλpzqb` ρpzqp in (5)
p ` is isomorphic to B
p´
induces an isomorphism between Spf pq and Sppq. Since B
e
e

VAN KAMPEN’S THEOREM FOR BISETS

17

by Theorem 3.17(3) we have the required isomorphism:
ğ
p :, λpzqq b p
p
Spf pq “
π1 pY,
Gλpzq Bz b f p
zPρ´1 pf ´ q

ˆ
ğ
“
zPρ´1 pf ´ q

ğ
“
ePρ´1 pf q

ğ
–

˙
ğ

p :, λpzqq b p
π1 pY,
Gλpzq

p λpe´ q b B
p´
G
e

b f p using (6)

ePρ´1 pf q
e´ “z

p :, λpe´ qq b p
π1 pY,
G

λpe´ q

p´ b f p
B
e

p :, λpe´ qq b pλpeqB
p ` ρpeqq b f p using qb´ p „ qλpzqb` ρpzqp
π1 pY,
e

ePρ´1 pf q

ğ
“

p :, λpe` qq b B
p ` b p “ Sppq.
π1 pY,
e



ePρ´1 pf q

Corollary 3.20 (Canonical form of π1 pB, :, ˚q). Let Y BX be a left-fibrant graph
of bisets. Then its fundamental graph of bisets has the following description
ğ
(9)
π1 pB, :, ˚q “
π1 pY, :, λpzqq bGλpzq Bz ,
zPρ´1 p˚q

with right action given by lifting of paths in π1 pX, ˚q.
Proof. Follows immediately from Proposition 3.19, since the right-hand side of (9)
is Sp1q.

p :, ˚q, by Theorem 3.17 we may rewrite (9) as
Since π1 pB, :, ˚q – π1 pB,
ğ
p :, λpzqq b p
p
(10)
π1 pB, :, ˚q –
π1 pY,
Gλpzq Bz .
zPρ´1 p˚q

Corollary 3.21. Let Y BX be a left-free
Ů graph of bisets. Then π1 pB, :, ˚q is a
left-free biset of degree equal to that of zPρ´1 p˚q Bz .
Ů
pz is independent on ˚ P B.
In particular, the number of left orbits of zPρ´1 p˚q B
Proof. Follows immediately from (10) and Theorem 3.17 Claim 4.



Lemma 3.22. Suppose B is a left-fibrant graph of bisets. Then π1 pB, :, ˚q is leftp is a left-free graph of bisets.
free if and only if B
rz is
Proof. It follows from (10) that π1 pB, :, ˚q is left-free if and only if every B
left-free.

The following corollary is an adaptation of Lemma 3.2 to the context of bisets:
Corollary 3.23. Let B be a left-fibrant graph of bisets. If for y P Y the maps
pq´ : Gy Ñ Gy´ are injective, then the natural maps
Bz Ñ π1 pB, λpzq, ρpzqq

b ÞÑ 1 b b b 1

are also injective for all vertices z P B.
p y for all y P Y. Therefore, by TheoProof. By Lemma 3.2 we have Gy – G
p
rem 3.17(2) we have Bz – Bz for all z P B. In particular, all Bz Ñ π1 pB, λpzq, ρpzqq
are injections by Corollary 3.20.


18

LAURENT BARTHOLDI AND DZMITRY DUDKO

Consider a graph of bisets Y BX . As for graphs of groups, Y BX has a barycentric
subdivision Y1 B1X1 : all graphs in Y1 B1X1 are the barycentric subdivisions of those in
1
1
1
Y BX , the vertex groups and bisets Gy , Gx , Bz with y P Y , x P X , z P B are the
groups and bisets of the associated objects in Y BX , the edge groups and bisets in
1
Y1 BX1 represent the group morphisms and the biset congruences of Y BX .
Lemma 3.24. Let Y1 B1X1 be the barycentric subdivision of a graph of bisets Y BX .
Then for : P Y and ˚ P X we have a natural isomorphism π1 pB, :, ˚q – π1 pB1 , :, ˚q.
If Y BX is left-fibrant (left-covering, etc.), then so is Y1 B1X1 .
Proof. Write B1:,˚ :“ pY1 , :q_ b B1 b pX1 , ˚q and B:,˚ :“ pY, :q_ b B b pX, ˚q.
By Lemma 3.15, the fundamental bisets of B1:,˚ and B:,˚ are isomorphic to the
fundamental bisets of B1 and B respectively. It is also easy to see that B1:,˚ is
(isomorphic to) to the barycentric subdivision of B:,˚ because π1 pY1 , :q – π1 pY, :q
and π1 pX1 , ˚q – π1 pX, ˚q. This reduces the problem to the case when Y and X are
graphs with one vertex. In this case we have a simple description Ů
of the fundamental
biset B of B, and similarly of B1 , see §3.4: B is the quotient of zPV pBq Bz by the
relation identifying b´ with b` , for all edges z P B and all b P Bz , with respective
images b˘ in Bz˘ . The first claim of the lemma easily follows.
The second part of the lemma is straightforward: the unique lifting property (6)
is respected by passing to the barycentric subdivision and (6) holds for the new
vertices of B1 which are the former edges of B.

3.7. Properties of products.
Lemma 3.25. For every graphs of bisets
phism
(11)

Y BX

and X CW there exists a biset mor-

π1 pB bX C, :, ;q Ñ π1 pB, :, ˚q bπ1 pX,˚q π1 pC, ˚, ;q

defined as follows: consider pv, wq P V pB bX Cq and b b c P Bpv,wq . Consider paths
q P π1 pY, :, λpvqq and r P π1 pW, ρpwq, ;q. Then a typical element of π1 pBbX C, :, ;q
is of the form qpb b cqr, and its image under (11) is defined to be pqbpq b pp´1 crq
for any choice of path p P π1 pX, ρpvq, ˚q “ π1 pX, λpwq, ˚q.
Proof. To show that (11) is well-defined, we must see that it is independent of the
choice of qpb b cqr in its „-equivalence class and of the choice of p. Clearly the
product over X is independent of the choice of p. Changing bbc into bg bg ´1 c is the
same as changing p into gp. For an edge pe, f q in B bX C, changing qpb b cq´ r into
qλpeqpb b cq` ρpf qr is the same as changing p into λpeqp. It is immediate that (11)
is a biset morphism.

In general, the morphism in Lemma 3.25 need not be an isomorphism. For
instance, B bX C is the empty graph of bisets if the images of the graphs B and C
do not intersect in X. However,
Lemma 3.26. Let B be a left-fibrant Y-X-biset, and let C be a X-W-biset. Then (11)
induces an isomorphism
π1 pB, :, ˚q bπ1 pX,˚q π1 pC, ˚, ;q – π1 pB bX C, :, ;q.
Proof. By definition, every element in π1 pB, :, ˚q bπ1 pX,˚q π1 pC, ˚, ;q is of the form
qbpcr for paths q, p, r in Y, X, W respectively. By Corollary 3.20 the subexpression

VAN KAMPEN’S THEOREM FOR BISETS

19

qbp can be rewritten in a unique way as q 1 b1 . This defines a biset morphism
π1 pB, :, ˚q bπ1 pX,˚q π1 pC, ˚, ;q Ñ π1 pB bX C, :, ;q
1

1

by qbpcr ÞÑ q pb b cqr, which is clearly the inverse of (11).



Lemma 3.27. Let Y BX and X CW be left-fibrant (respectively left-free, left-principal)
bisets. Then B bX C is a left-fibrant (respectively left-free, left-principal) graph of
bisets.
Proof. Observe first that ρ : BbX C Ñ W is simplicial. Indeed, if ρpv, wq is a vertex
for pv, wq P B bX C, then w is a vertex of C because ρ : C Ñ W is simplicial, and
λpwq is a vertex of X because morphisms send vertices to vertices, so v P ρ´1 pλpwqq
is a vertex of B because ρ : B Ñ X is simplicial. Similarly, if ρpv, wq is an edge,
then so is w P C because ρ : C Ñ W is simplicial; thus pv, wq is an edge in B bX C.
Consider now a vertex pv, wq P B bX C and an edge f P W with f ´ “ ρpv, wq.
Let us verify (6). Note first that if p`, eq P ρ´1 pf q with p`, eq´ “ pv, wq, then ` “ v
if and only if λp`q “ λpvq, because ρ : B Ñ X is simplicial. We have
ğ
Bpv,wq “ Bv b Bw – Bv b
Gλpwq bGλpeq Be using (6) for Bw
ePρ´1 pf q
e´ “w

ğ

ğ

pBv b Gλpwq q bGλpeq Be “

“
´1

Bv bGλpeq Be

because ρpvq “ λpwq

´1

ePρ pf q
e´ “w

ePρ pf q
e´ “w

˜

¸
ğ

˜

Bv bGλpeq Be

“

¸
ğ

Bv bGλpeq Be

\

´1

´1

ePρ pf q
e´ “w
λpeq“ρpvq

ePρ pf q
e´ “w
λpeq­“ρpvq

¨
˜

¸
ğ

Bpv,eq

–
pv,eqPρ´1 pf q
pv,eq´ “pv,wq

˛

˚
‹
˜
¸
˚ ğ
‹
ğ
˚
‹
\˚
Gλpvq bGλp`q B` bGλpeq Be ‹
˚ ´1
‹
˝ ePρ pf q `Pρ´1 pλpeqq
‚
e´ “w
λpeq­“ρpvq

˜

¸
ğ

Gλpvq b Bpv,eq

–

˜
Gλpvq bGλp`q Bp`,eq

\

pv,eqPρ pf q
pv,eq´ “pv,wq

ğ

¸
ğ

´1

–

`´ “v

Gλpvq bGλp`q Bp`,eq “

p`,eqPρ´1 pf q
p`,eq´ “pv,wq

´1

p`,eqPρ pf q
p`,eq´ “pv,wq
`­“v

ğ

Gλpv,wq bGλp`,eq Bp`,eq .

p`,eqPρ´1 pf q
p`,eq´ “pv,wq

This shows that BbX C is a left-fibrant graph of bisets. If, moreover, Y BX and X CW
are left-free (respectively left-principal), then all Bpv,wq are left-free (respectively
left-principal); thus BbX C is a left-free (respectively left-principal) graph of bisets.

We are now ready to prove Lemma 3.15:
Proof of Lemma 3.15. Both pB, :q and pX, ˚q are left-principal graphs of bisets.
The proof now follows from Lemmas 3.26 and 3.27.


20

LAURENT BARTHOLDI AND DZMITRY DUDKO

3.8. Principal and biprincipal graphs of bisets. Let us now simplify the part
of Definition 3.16 concerning principal graphs of bisets.
Lemma 3.28. A graph of bisets Y BX is left-principal if and only if ρ : B Ñ X is
a graph isomorphism and Bz are left-principal for all z P B.
Proof. We verify that the conditions stated in Lemma 3.28 imply (6).
Since ρ : B Ñ X is a graph isomorphism, (6) takes the following form: for every
z P B the map
(12)

Gλpe´ q bGλpeq Be Ñ Be´ ,

g b b ÞÑ gb´

is a Gλpe´ q -Gρpeq biset isomorphism (for the action of Gρpeq on Be´ given via
pq´ : Gρpeq Ñ Gρpeq´ ). Let us verify (12).
Consider an edge e P B. We claim that pGλpeq q´ pBe q´
Gρpeq is isomorphic to
pGλpeq q´ bGλpeq pBe qGρpeq . Indeed, pGλpeq q´ pBe q´
is
left-free
as a subbiset of a
Gρpeq
´
left-free biset Be´ . Furthermore, pGλpeq q´ pBe qGρpeq has a single orbit under the action of pGλpeq q´ because this property holds for Be . Therefore, pGλpeq q´ pBe q´
Gρpeq is
´
´
left-principal. As a set it is isomorphic to pGλpeq q ; this proves pGλpeq q´ pBe qGρpeq –
pGλpeq q´ bGλpeq pBe qGρpeq . Since Be´ is left-principal we obtain a natural isomorphism of Gλpe´ q -Gρpeq -bisets
Be´ “ Gλpe´ q pBe q´ – Gλpe´ q bGλpeq Be
which is (12).



An example of left-principal graph of bisets is X pX, ˚qX0 defined in §3.4.
A biset H BG is biprincipal if it is left- and right-principal. Clearly, if H BG is
biprincipal, then the groups G and H are isomorphic. Similarly, a graph of bisets
Y IX is biprincipal if it is left- and right-principal. By Lemma 3.28 a graph of bisets
Y IX is biprincipal if and only if
(1) λ : I Ñ Y and ρ : I Ñ X are graph isomorphisms; and
(2) Bz are biprincipal for all objects z P I.
Definition 3.29 (Congruence of graphs of groups and bisets). Two graphs of
groups Y, X are called congruent if there is a biprincipal graph of bisets Y IX .
Isomorphism of graphs of bisets is meant in the strongest possible sense: isomorphism of the underlying graphs, and isomorphisms of the respective bisets.
Two graphs of bisets Y BX and Y1 CX1 are congruent if there are biprincipal graph
of bisets Y IY1 and X LX1 such that Y BX is isomorphic to I b Y1 CX1 b L_ .
Finally, two graph of bisets X BX and X1 CX1 are conjugate if X BX is isomorphic
to I b X1 CX1 b I_ for a biprincipal graph of bisets X IX1 .
4
Let H BG be a biprincipal biset and let H 1 be a subgroup of H. For every b P B
we consider the subgroup pH 1 qb of G defined by
H 1 b “ bpH 1 qb .
It is easy to see that the conjugacy class of pH 1 qb in G is independent of b.
Lemma 3.30. Let Y, X be graphs of groups and let h : Y Ñ X be an isomorphism
of the underlying graphs. Suppose also that a Gy -Ghpyq biprincipal biset By is given
for every object y P Y. Set I to be Y as a graph. Then the data tBz uzPI extends
(via appropriate embeddings of edge bisets into vertex bisets) to a biprincipal graph

VAN KAMPEN’S THEOREM FOR BISETS

21

of bisets Y IX if and only if for every edge e P I the following holds. For any, or
´
b
equivalently for every, b P Be the groups pG´
e q and Ghpeq are conjugate as subgroups
of Ghpe´ q .
´
b
Proof. Follows immediately from the definition: if pG´
e q and Ghpeq are conjugate,
´
b g
´
say ppG´
e q q “ Ghpeq , then we may define pq : Be Ñ Be´ by mapping Be into
´

G´
e pbgqGhpeq . The converse is obvious.

3.9. Examples. We will give more examples and applications in §5. Nevertheless,
we give here an example that illustrates the main features of Definition 3.13. First
let us introduce some conventions simplifying descriptions of the examples.
Let the graph X “ V \ E be a graph as in Definition 3.1. By an undirected
graph we mean X0 :“ X{tz “ z̄u with vertex set V0 “ V and geometric edge set
E0 :“ E{te “ ēu. The undirected graph X0 is endowed with an adjacency relation.
A map θ : X0 Ñ Y0 is a weak morphism if θ sends adjacent objects into adjacent
or equal objects. If X1 and Y1 are the barycentric subdivisions of X and Y as in
§3.2, then θ : X0 Ñ Y0 uniquely determines a graph morphism θ : X1 Ñ Y1 .
Convention. We will often describe a graph of bisets as Y0 B0X0 with
‚ undirected graphs Y0 , B0 , X0 ;
‚ weak graph morphisms λ : B0 Ñ Y0 and ρ : B0 Ñ X0 ;
‚ groups Gy , Gx and Gλpzq -Gρpzq bisets Bz for all y P Y0 , x P X0 and z P B0
respectively;
‚ congruences from Be to Bv and Bw for all edges e P B0 adjacent to vertices
v, w P B0 ; and, similarly, group morphisms from Be to Bv and Bw for all
edges e P Y0 \ X0 adjacent to vertices v, w.
By passing to a barycentric subdivision of Y0 B0X0 we obtain a graph of bisets
1
Y1 B X1 satisfying Definition 3.8. Following Lemma 3.24 we set π1 pY0 B0X0 , :, ˚q :“
π1 pY1 B1 X1 , :, ˚q.
Example 3.31. Consider the biset corresponding to the “Basilica map” f pzq “
z 2 ´ 1, from pC, t´1, 0, 1uq to pC, t0, ´1uq.
On the one hand, choose a basepoint x0 – ´0.6 in Czt0, ´1u, and choose a graph
X with one vertex x0 to which Czt0, ´1u deformation retracts; let Y be the full
preimage of X under f :
y01

y02

f

x0

There, the graphs of groups X and Y have trivial groups, and the biset B corresponding to f is Y as a graph, with λ “ 1 and ρ “ f .
This biset may be encoded differently, by considering rather an orbispace structure on C with non-trivial groups at 0, ˘1; the complex plane deformation retracts
to the intervals r´1, 0s and r´1, 1s respectively:
y01

y1

y02

Z

Z

Z

f

x1

x0

Z

Z

22

LAURENT BARTHOLDI AND DZMITRY DUDKO

The graphs X and Y have the group Z attached to each vertex, and the edge
groups are all trivial. The biset B has Y as underlying graph; the map λ is the
retraction to the segment ry01 , y1 s “ rx1 , x0 s and ρ folds Y around its middle point.
The bisets By01 and By02 are Z ZZ , while By1 “ 2Z ZZ is free of rank 2 on the left.
The edge bisets embed in By1 as two elements of opposite parity.
Note that the underlying graph of B is the “Hubbard tree” of f ; that will be
explained in more details in §5.2.
Proposition 3.32. Let φ : H Ñ G be a group homomorphism, and let X be a
graph of groups with fundamental group G. Then there exists a graph of groups
decomposition of H and a graph of bisets with limit f . Furthermore, there exists
a unique minimal such decomposition for H in the sense that other decompositions
are refinements of it.
r the universal cover of X (also known as the BassProof. Let G act on the tree X,
Serre tree of G, see [15]), with stabilizers the groups Gx of X. Then H acts on
r via φ. We define the graph of groups Y as X{{H,
r
r
X
namely as the quotient of X
by the action of H, remembering the stabilizers in H of vertices and edges in the
quotient.
r
We next define a graph of bisets B as follows. Its underlying graph is X{H.
The
graph morphism λ : B Ñ Y is the identity, and the graph morphism ρ : B Ñ X is
the natural quotient map xH ÞÑ xG. The biset at the vertex or edge xH is GρpxHq ,
on which GρpxHq acts naturally by left multiplication, while HxH acts on the right
via φ.

Remark 3.33. In a manner similar to Lemma 2.7, every graph of bisets Y BX may
be factored as B “ A_ bK C for some graph of groups K and some right-principal
bisets K AY and K CX . Furthermore, there is an essentially unique minimal such K.
Lemma 3.34. Let Y BX and Y CX be graphs of bisets over the same graphs, and
let θ : B Ñ C be a “semiconjugacy of graphs of bisets”, namely a graph morphism
θ : B Ñ C and compatible surjective biset morphisms θz : Bz Ñ Cθpzq . Then θ may
be factored as θ “ κ ˝ ι through semiconjugacies ι : B Ñ C1 and κ : C1 Ñ C, in
such a manner that ι induces an isomorphism between π1 pBq and π1 pC1 q, and the
underlying graph of C1 is the same as that of C.
4. Correspondences
Bisets are well adapted to encode more general objects than continuous maps,
topological correspondences.
Definition 4.1 (Correspondences). Let X, Y be topological spaces. A topological
correspondence from Y to X is a triple pZ, f, iq consisting of a topological space Z
and continuous maps f : Z Ñ X and i : Z Ñ Y . It is often abbreviated pf, iq, and
written Y Ð Z Ñ X.
In the special case that f is a covering, pZ, f, iq is called a covering correspondence. If X “ Y , then pZ, f, iq is called a self-correspondence. If X “ Y and f is a
covering, then pZ, f, iq is called a covering pair, and is also written f, i : Z Ñ X. 4
Ultimately, we will be interested in dynamical systems that are partially defined
topological coverings f : X 99K X, for path connected topological spaces X; the
dashed arrow means that the map is defined on an open subset Y Ď X; these can
naturally be viewed as correspondences pY, f, iq with i the inclusion.

VAN KAMPEN’S THEOREM FOR BISETS

23

4.1. The biset of a correspondence. Let Y Ð Z Ñ X be a correspondence, and
assume that X and Y are path connected. Assume first that Z is path connected,
and fix a basepoint ; P Z. Then we have (1) a π1 pZ, ;q-π1 pX, ˚q-biset Bpf q and a
π1 pZ, ;q-π1 pY, :q-biset Bpiq; we define the biset Bpf, iq to be Bpiq_ bπ1 pZ,;q Bpf q;
this amounts to first “lifting” from Y to Z, and then projecting Z back to X. If Z
is not path connected, then we define Bpf, iq to be the disjoint union of the bisets
Bpiq_ bπ1 pZ,pq Bpf q with one p per path connected component of Z.
The following alternate construction of Bpf, iq avoids an unnecessary reference
to the basepoint and fundamental group of Z:
Lemma 4.2. The biset Bpf, iq may be constructed directly as follows, from the
correspondence:
,
$¨
˛ˇ
.N
& δ : r0, 1s Ñ Y ˇˇ
δp0q
“
:,
δp1q
“
ippq
ˇ
‚
˝
pPZ
„
(13)
Bpf, iq “
ˇ γp0q “ f ppq,
γp1q “ ˚ %
γ : r0, 1s Ñ X ˇ
in which the equivalence relation „ allows p to move in Z as long as δ, γ move
smoothly with it1.
The left action is by pre-composition of δ by loops in Y at :, and the right action
is by post-composition of γ by loops in X at ˚:
rαs ¨ prδs, p, rγsq ¨ rεs “ prα#δs, p, rγ#εsq.

Z

p

i
:
Y

‚

δ

f
γ

‚

˚
X

Ů
Proof. By the definition of products of bisets, Bpf, iq “ z tpδ̌, γqu{„, with δ : r0, 1s Ñ
Y ending at : and γ : r0, 1s Ñ X ending at ˚ and δp0q “ ipzq and γp0q “ f pzq, and
with one z per path connected component of Z. By the homotopy relation, we may
also allow z to move freely, arriving at the formulation of the lemma in which no
condition on z is imposed.

Recall that a continuous map f : Y Ñ X is a fibration, or a fibrant map if it has
the homotopy lifting property with respect to arbitrary spaces: for every space Z,
every homotopy g : Z ˆ r0, 1s Ñ X and every h : Z ˆ t0u Ñ Y with f ˝ h “ g on
Z ˆ t0u there exists an extension of h to Z ˆ r0, 1s with f ˝ h “ g. Clearly, the
composition of fibrations is a fibration. If X is path connected, then in particular
all fibres f ´1 pxq are homotopy equivalent.
Remark 4.3. In fact, we may consider at no cost a larger class of maps: let us
say that a map f is a π1 -fibration if f has the lifting property with respect to
1Note the similarity with Definition 3.13

24

LAURENT BARTHOLDI AND DZMITRY DUDKO

contractible spaces. This is sufficient for our purposes; it implies, for example, that
all f ´1 pxq have isomorphic fundamental groups.
Lemma 4.4. Assume that f : Z Ñ X is a fibration. Then the biset of f has the
following description:
(14)

Bpf q “ tβ : r0, 1s Ñ Z | βp0q “ :, f pβp1qq “ ˚u{„,
1

with β „ β if and only if there is a path ε : r0, 1s Ñ f ´1 p˚q connecting βp1q to β 1 p1q
such that β#ε is homotopic to β 1 .
Assume that pf, iq is a correspondence with f fibrant. Then in (13) we may
assume that γ is constant, and write
(15)

Bpf, iq “ tpδ : r0, 1s Ñ Y, p P Zq | δp0q “ :, δp1q “ ippq, f ppq “ ˚u{„,

with pδ, pq „ pδ 1 , p1 q if and only if there exists a path ε : r0, 1s Ñ f ´1 p˚q Ď Z
connecting p to p1 , such that δ#ipεq is homotopic to δ 1 .
Proof. Recall from (1) that Bpf q is defined as tγ : r0, 1s Ñ X | γp0q “ f p:q, γp1q “
˚u{„. Since f is fibrant, every γ P Bpf q has a lift, say β, with βp0q “ : and
f ˝ β “ γ. We need to show that if γ0 is homotopic to γ1 , say via γt , then their lifts
β0 and β1 have the property that β0 is homotopic to β1 #ε for some ε in f ´1 p˚q.
Consider γt as a map γ : r0, 1s ˆ r0, 1s Ñ X, where t is the first variable and the
second variable parameterizes γt . By construction, γpt, 0q “ f p:q and γpt, 1q “ ˚.
Since f is fibrant, there is a lift  : r0, 1s ˆ r0, 1s Ñ Z of γ such that pt, 0q “ :,
f “ γ, p0, τ q “ β0 pτ q, and p1, τ q “ β1 pτ q. Define εpτ q :“ p1, τ q. Then β0´1 β1 ε is
pBpr0, 1s ˆ r0, 1sqq. Therefore, β0 is homotopic to β1 #ε.
Let us now prove the second statement. Using the first part, the biset Bpf, iq in
the sense of (13) is identified with
tpδ : r0, 1s Ñ Y, β : r0, 1s Ñ Zq | δp0q “ :, δp1q “ ipβp0qq, f pβp1qq “ ˚u{„,
where pδ0 , β0 q „ pδ1 , β1 q if there is a path ε : r0, 1s Ñ f ´1 p˚q such that pδ0 , β0 q is
homotopic to pδ1 , β1 εq. Projecting β1 ε to Y yields the required description.

Example 4.5. Here are some extreme examples of correspondences worth keeping
in mind. If Z “ t;u is a point, then Bpf, iq “ π1 pY, :qˆπ1 pX, ˚q. On the other hand,
if Z “ X “ Y and f and i are the identity, then Bpf, iq – π1 pY, :q – π1 pX, ˚q.
Finally, one may consider Z “ Y ˆ X with i, f the first and second projections
respectively; then Bpf, iq consists of a single element.
If f is a covering, then the biset Bpf, iq is left-free. Indeed, consider (15) as a
description of Bpf, iq. Suppose f ´1 p˚q “ tpi uiPI . For every i choose δi : r0, 1s Ñ Y
with δi p0q “ : and δi p1q “ ippi q. Then pδi , pi qiPI forms a basis of Bpf, iq.
4.2. Van Kampen’s theorem for correspondences. We describe in this section
the decomposition of the biset of a correspondence into a graph of bisets, using a
decomposition of the underlying spaces. We start by the following straightforward
lemma.
Lemma 4.6. Let
‚ f : Y Ñ X be a continuous map;
‚ X 1 and Y 1 be path connected subsets of X and Y with f pY 1 q Ď X 1 ;
‚ :, :1 , ˚, and ˚1 be base points in Y , Y 1 , X, and X 1 ; and
‚ γ˚ Ă X and γ: Ă Y be curves connecting ˚ to ˚1 and : to :1 respectively.

VAN KAMPEN’S THEOREM FOR BISETS

25

We allow X 1 “ X; in this case we suppose that γ˚ is the constant path and ˚1 “ ˚.
Then the maps δ Ñ γ: δγ:´1 , δ Ñ γ˚ δγ˚´1 , and b Ñ f pγ: qbγ˚´1 define a biset
congruence
π1 pY 1 ,:1 q Bpf åY 1 , :

1

, ˚1 qπ1 pX 1 ,˚1 q Ñ

π1 pY,:q Bpf, :, ˚qπ1 pX,˚q .



Let f : Z Ñ X be a continuous map between path connected spaces. Suppose
that pUα q and pWγ q are finite 1-dimensional covers X and Z respectively, as in
Definition 3.4. Choose base points ˚α P Uα and :γ P Wγ as well as connections
between ˚α1 and ˚α if Uα1 Š Uα ; and similarly for pWγ q. Consider the associated
graphs of groups X and Z according to Definition 3.6. We have π1 pX, ˚α q “ π1 pX, αq
and π1 pZ, :γ q “ π1 pZ, γq, by Theorem 3.7. Suppose furthermore that pUα q and pWγ q
are compatible with f in the following sense: for every γ there is an α “: ρpγq with
f pWγ q Ă Uα .
To the above data there is an associated graph of bisets Z Bpf qX is defined as
follows. As a graph, B is Z, with λ : B Ñ Z the identity and ρ : B Ñ X given
above. For every vertex γ P B, the biset Bγ is Bpf : Wγ Ñ Uρpγq , :λpγq , ˚ρpγq q. For
every edge e P B representing the embedding Wγ 1 Š Wγ the biset Be is Bγ 1 . If e is
oriented so that e´ “ γ 1 and e` “ γ, the congruences pq˘ are pq´ “ 1 : Be Ñ Bγ 1
and pq` : Be Ñ Bγ given by Lemma 4.6.
By construction, Z Bpf qX is a right-principal graph of bisets.
Consider now a correspondence pf, iq, with f : Z Ñ X and i : Z Ñ Y , between
path connected spaces X and Y . Suppose pZk q are the path connected components
of Z, and suppose pUα q, pVβ q, and pWγ q are finite 1-dimensional covers of X, Y ,
and Z respectively, compatible with f and i: for every γ there are λpγq and ρpγq
such that f pWγ q Ă Uρpγq and ipWγ q Ă Vλpγq .
Let pUα q, pVβ q, and pWγ q be finite 1-dimensional covers of X, Y , and Z compatible with f and i as above. We then have graphs of bisets Zk Bpf åZk qX and
Zk Bpi åZk qY . We define the graph of bisets of the correspondence pf, iq as
ğ
_
Y Bpf, iqX :“
Y Bpi åZk qZk bZk Zk Bpf åZk qX .
k

The following equivalent description of
tion; see Lemma 4.2

Y BX

follows immediately from the defini-

Lemma 4.7. Let pZ, f, iq be a topological correspondence from Y to X, for path
connected spaces X, Y . Let pUα q, pVβ q, and pWγ q be finite 1-dimensional covers of
X, Y , and Z compatible with f and i as above. Then the graph of bisets Y BX of
pf, iq with respect to the above data is as follows:
‚ the graphs of groups X and Y are constructed as in Definition 3.6 using the
covers pUα q and pVβ q of X, Y respectively. Choices of paths `e , me were
made for edges e in X, Y respectively;
‚ the underlying graph of B is similarly constructed using the cover pWγ q of
Z. Note that neither Z nor the underlying graph of B need be connected;
‚ for every vertex z P B the biset Gλpzq Bz Gρpzq is Bpf åWz , i åWz q;
‚ for every edge e P B representing the embedding Wz1 Š Wz the biset Be
is Bz1 , and if e is oriented so that e´ “ z 1 then the congruences pq˘ are
the maps pq´ “ 1 : Be Ñ Bz1 and pq` : Be Ñ Bz given by pγ ´1 , δq ÞÑ
´1
pm´1
, δ#`ρpeq q in the description of Be as Bpi åWe´ q_ b Bpf åWe´ q,
λpeq #γ
see Lemma 4.6.


26

LAURENT BARTHOLDI AND DZMITRY DUDKO

Theorem 4.8 (Van Kampen’s theorem for correspondences). Let pf, iq be a topological correspondence from a path connected space Y to a path connected space X,
and let Y BX be the graph of bisets subject to compatible finite 1-dimensional covers
of spaces in question.
Then for every v P Y and u P X we have
Bpf, i, :v , ˚u q – π1 pB, v, uq,
where :v and ˚u are basepoints.
Proof. Recall from §3.2 that for all vertices y P Y there are chosen basepoints
:y P Vy identifying the groups Gy with π1 pVy , :y q and for all edges e P Y there
are curves γe connecting :e´ to :e` satisfying γy “ γy´1 and describing pq´ -maps.
Similarly, for objects in X there are basepoints ˚x P Ux and curves γe Ă X.
Then every biset element b “ ph0 , y1 , . . . , b, . . . xn , gn q P π1 pB, :, ˚q defines a certain element θpbq P BppZ, f, iq, :: , ˚˚ q that is the concatenation h0 #γy1 # . . . #b . . . #γxn gn .
We get a biset morphism
θ : π1 pB, :, ˚q Ñ BppZ, f, iq, :: , ˚˚ q.
Clearly θ is surjective, because every element in BppZ, f, iq, :: , ˚˚ q can be presented
as a concatenation h0 #γy1 # . . . #b . . . #γxn gn , see Remark 3.5. To prove that θ is
injective, we show that if θpb1 q is homotopic to θpb2 q, then b1 “ b2 .
By the classical van Kampen argument (see [11, Chapter IV]) a homotopy between θpb1 q and θpb2 q can be expressed as a combination of the following operations: (1) homotopies within Ui and in Vj ; (2) replacement of gk or hk by γz gk γz´1
´1
#b#γρpzq for some z P B.
or γz hk γz´1 for some z, and (3) replacement of b by γλpzq
All the above operations fix the corresponding elements in π1 pB, :, ˚q.

Lemma 4.9. Consider a path connected space X with a 1-dimensional cover pXv qvPV
and the associated graph of groups X as in Definition 3.6.
Then, up to congruence, X and the graph of bisets associated with a topological
correspondence are independent of the choices of basepoints t˚v u and connecting
paths tγe u,
Proof. Let X, X1 be two graphs of groups associated with X and with a fixed
1-dimensional cover pXv qvPV but with different choices of basepoints and connecting paths. Consider a topological correspondence pX, f, iq such that f : X ý and
i : X ý are the identity maps. We may assume that X1 , resp X, is the graph of
groups associated with the range of f , resp i. Let X BX1 be the graph of bisets
associated with pX, f, iq and the cover pXv qvPV . Then B is a biprincipal graph of
bisets because Bpf |Xv , i |Xv q is biprincipal for every v.
The second claim follows from the first.

4.3. Products of correspondences. Correspondences, just as continuous maps,
may be composed; the operation is given by fiber products.
Let pZ1 , f1 , i1 q and pZ2 , f2 , i2 q be two correspondences such that f1 : Z1 Ñ X
and i2 : Z2 Ñ X have the same range X. Their product is the correspondence
pZ, f, iq given by
Z “ tpz1 , z2 q P Z1 ˆ Z2 | f1 pz1 q “ i2 pz2 qu, f pz1 , z2 q “ f2 pz2 q, ipz1 , z2 q “ i1 pz1 q.
We have natural maps ir2 : Z Ñ Z1 and fr1 : Z Ñ Z2 given respectively by
ir2 pz1 , z2 q “ z1 ,
fr1 pz1 , z2 q “ z2 .

VAN KAMPEN’S THEOREM FOR BISETS

27

•
fr1

ir2

•

•
i1
•

f1
i2

f2

•

Figure 1. An example with Bpf, iq fi Bpf1 , i1 q b Bpf2 , i2 q.
It is easy to check that f is a fibration, respectively a covering, if both f1 and f2
are fibrations, respectively coverings.
The biset of a product of two correspondences is, in favourable cases, the product
of the corresponding bisets:
Lemma 4.10. Let pZ, f, iq be the product of two correspondences pZ1 , f1 , i1 q and
pZ2 , f2 , i2 q, with f1 : Z1 Ñ X and i2 : Z2 Ñ X and X path connected. Then there
is a biset morphism
#
Bpf, iq Ñ Bpf1 , i1 q b Bpf2 , i2 q
(16)
pδ, p, γq ÞÑ pδ, ir2 ppq, ε´1 q b pε, fr1 ppq, γq,
for any choice of path ε from the basepoint of X to f1 pir2 ppqq “ i2 pfr1 ppqq.



Example 4.11. In general, the map in the above lemma need not be an isomorphism; for instance, the ranges of i2 and f1 need not intersect, in which case Z “ H
so Bpf, iq “ H, while Bpf1 , i1 q and Bpf2 , i2 q are non-empty so their product is not
empty.
For a less artificial example, consider the correspondence shown on Figure 4.3.
Denote by 1 the trivial group; we also view 1 as a set consisting of one element.
Then Bpi1 , f1 q “ 1 ZZ , Bpi2 , f2 q “ Z 1Z ; thus Bpi1 , f1 q b Bpi2 , f2 q “ 1 1Z . On the
other hand, Bpir2 i1 , fr1 f2 q “ 1 ZZ .
Sufficient conditions on the map (16) being an isomorphism are given by Lemma 4.12,
in analogy with Lemma 3.26.
Lemma 4.12. If in Lemma 4.10 at least one of the maps i2 , f1 is fibrant, then (16)
is an isomorphism of bisets.
Proof. We construct an inverse to the map (16), keeping the notations of Lemma 4.10.
Suppose without loss of generality that i2 is fibrant. Consider b “ pδ1 , p1 , γ1 q b
pδ2 , p2 , γ2 q P Bpf1 , i1 q b Bpf2 , i2 q. Changing the basepoint in X to ˚ “ f1 pp1 q and
denoting by ˚ the constant path in X at ˚, we rewrite b as pδ1 , p1 , ˚qbpγ1 #δ2 , p2 , γ2 q.
Since i2 is fibrant, the curve γ1 #δ2 admits a lift ε to Z2 with εp1q “ p2 . Write
p12 “ εp0q. We then have b “ pδ1 , p1 , ˚q b p˚, p12 , pf2 ˝ εq#γ2 q, see Lemma 4.4. Since
f1 pp1 q “ ˚ “ i2 pp12 q, there is a unique p P Z with ir2 ppq “ p1 and fr1 ppq “ p12 . Then
pδ1 , p, pf2 ˝ εq#γ2 q P Bpf, iq is a preimage of b under (16).


28

LAURENT BARTHOLDI AND DZMITRY DUDKO

4.4. Fibrant maps and covers. Suppose f : Z Ñ X is a fibrant map between
path connected spaces and pUα q is a cover of X consisting of path connected sets
Uα . The pullback pWγ q :“ f ˚ pUα q is the cover of Z consisting of all path connected
components of f ´1 pUα q, for all Uα in the cover. It is easy to see that if pUα q is
a finite cover and f ´1 p˚q consists of finitely many connected components for some
or equivalently any ˚ P X, then pVα q is a finite cover. If, furthermore, pUα q is
1-dimensional, then so is pWγ q. It is also immediate that all f åWk are fibrant
maps.
Proposition 4.13. Suppose Y BX is the graph of bisets of a topological correspondence pZ, f, iq from Y and X subject to finite 1-dimensional covers pUα q, pVβ q, and
pWγ q of X, Y , and Z respectively.
If f : Z Ñ X is fibrant, respectively a covering, and pWγ q “ f ˚ pUα q, then Y BX
is a left-fibrant, respectively a left-free, graph of bisets.
The proof of the above proposition is based on the following property:
Lemma 4.14. Let
‚ f : W Ñ U be a fibrant map between path connected spaces, with biset
Bpf, :, ˚q;
‚ U 1 Ă U be path connected with basepoint ˚1 ;
‚ tWz1 uzPI be the set of connected components of f ´1 pU 1 q;
‚ Bpf åWz1 , :1z , ˚1 q be the biset of f : Wz1 Ñ U 1 ;
‚ pq´ : π1 pWz1 ,:1z q Bpf åWz1 , :1z , ˚1 qπ1 pU 1 ,˚1 q Ñ π1 pW,:q Bpf, :, ˚qπ1 pU,˚q be congruences as in Lemma 4.6.
Then we have a π1 pW, :q-π1 pU 1 , ˚q isomorphism
ğ
(17)
π1 pW, :q bπ1 pWz1 ,:1z q´ Bpf åWz1 , :1z , ˚1 q ÝÑ Bpf åW , :, ˚q,
g b b ÞÑ gb´
zPI

with right action of π1 pU 1 , ˚1 q on Bpf åW , :, ˚q given via pq´ : π1 pU 1 , ˚1 q Ñ π1 pU, ˚q.
Proof. The statement is clearly stable under motion of ˚, thus we may assume that
˚ “ ˚1 and that pq´ : π1 pU 1 , ˚1 q Ñ π1 pU, ˚q is given by taking each γ P π1 pU 1 , ˚1 q
modulo homotopy in U . By Lemma 4.4
Bpf, :, ˚q “ tβ : r0, 1s Ñ W | βp0q “ :, f pβp1qq “ ˚u{„,
with β „ β 1 if and only if there is a path ε : r0, 1s Ñ f ´1 p˚q connecting βp1q to β 1 p1q
such that β#ε is homotopic to β 1 . Therefore, each β : r0, 1s Ñ W in Bpf q ends at a
unique Wz1 independent on the choice representing β. It is now easy to see that the
π1 pW, :q-π1 pU 1 , ˚q subbiset of Bpf, :, ˚q consisting of all b P Bpf, :, ˚q terminating
at Wz1 is exactly π1 pW, :q bπ1 pWz1 ,:1z q´ Bpf åWz1 , :1z , ˚1 q. This implies (17).

Proof of PropositionŮ
4.13. Let pZk q Â
be the path connected components of Z. By
definition, Y BX “ k Y Bpi åZk q_
Zk
Zk Zk Bpf åZk qX . Lemma 4.14 implies that
every Zk Bpf åZk qX is left-fibrant: Equation (17) is exactly (6). Since the product
of left-fibrant bisets is left-fibrant (Lemma 3.27), Y BX is a left-fibrant biset. This
proves the part of Proposition 4.13 concerning fibrant maps. The case of covering
maps observe that all bisets in Bpf åZk q are left-free because f åZk are
Ů coverings
_
while
all
bisets
in
Bpi
å
q
are
left-principal;
hence
all
bisets
in
B
“
Z
X
k
k Y Bpi åZk
Â
q_
Bpf
å
q
are
left-free.

Z
Z
k
Zk
Zk k

VAN KAMPEN’S THEOREM FOR BISETS

29

4.5. Partial self-coverings. We now turn to a restricted class of covering correspondences pZ, f : Z Ñ X, i : Z Ñ Y q, in which the map i is an inclusion, namely
a homeomorphism on its image. We then view Z as a subset of Y , and write the
correspondence as a partial covering f : Y 99K X. Here the dashed arrow means
that the map is defined on the image of i.
In this case, the definition of the biset of a correspondence (see §4.1) can be
simplified as follows:
Lemma 4.15. Let f : X 99K X be a partially defined self-covering. The biset Bpf q
may then be constructed directly as follows:
Bpf q “ tγ : r0, 1s Ñ X | γp0q “ ˚ “ f pγp1qqu{„.
The left action is by pre-composition by loops in X at ˚, and the right action is by
lifting loops through f :
rγs ¨ rαs “ rγ#α̃s

rαs ¨ rγs “ rα#γs,

for the unique f -lift α̃ of α that starts at γp1q.
Proof. Simply remark that, in the notation of Lemma 4.2, the point p is determined
as i´1 pγp1qq, so may be removed from the definition.

Let us consider now a self-correspondence pZ, f : Z Ñ X, i : Z Ñ Xq. It may
arise as follows: f : X ý is a branched covering, Z is the subset of X on which f
is a genuine covering, and i is the inclusion.
Such correspondences may be iterated; however, their iterates are not defined on
the same Z anymore. We set X p1q :“ Z and, more generally,
X pnq “ tpx1 , . . . , xn q P Z n | f pxi q “ ipxi`1 qu.
Define the maps f pnq px1 , . . . , xn q “ f pxn q and ipnq px1 , . . . , xn q “ ipx1 q. Then
the n-th power, in the sense of §4.3, of pf, iq is pf pnq , ipnq q.
If f is fibrant, then so are all f pnq , and naturally (Lemma 4.12), the biset of
pnq pnq
pf , i q is none other than Bpf, iqbn .
If i : X p1q Ñ X is an inclusion, then so are all ipnq : X pnq Ñ X. Then pf, iq is identified with a partially defined map f : X 99K X; and all pf n : X pnq Ñ X, in : X pnq Ñ
Xq are identified with f pnq : X 99K X. If f is fibrant, then the bisets of pf pnq , ipnq q
and of f pnq are naturally isomorphic.
Iteration may also be interpreted purely in the language of homomorphisms,
using Lemma 2.7. Given a G-G-biset B, write G0 “ G, and find a group G1 such
that B decomposes as Bψ_1 bG1 Bφ1 , for homomorphisms φ1 , ψ1 : G1 Ñ G0 . Define
then iteratively Gn`1 as the fibre product of Gn with Gn over Gn´1 :
Gn`1

φn`1

ψn`1

Gn
Then B bn “ pBψn ¨¨¨ψ1 q_ bGn Bφn ¨¨¨φ1 .

Gn
ψn

φn

Gn´1

30

LAURENT BARTHOLDI AND DZMITRY DUDKO

4.6. Generic maps. We can slightly relax the previous setting, in which i : Z Ñ Y
is an inclusion, to “generic” maps in the following sense.
Definition 4.16 (Generic maps). A continuous map f : Y Ñ X is generic if there
exists a continuous map g : X Ñ Y such that f ˝ g is isotopic to the identity on
X.
4
Here is a typical example: Consider a topological space X and an injective
path γ : r0, 1s Ñ X, such that a neighbourhood of the image of γ is contractible
in X. Then the inclusion f : Xztγp0q, γp1qu Ñ Xztγp0qu is a generic map. Indeed contractibility of the image of γ implies the existence of a homeomorphism
g : Xztγp0qu Ñ Xzγpr0, 1sq.
Lemma 4.17. Let f : Y Ñ X be a generic map, and let : P Y be a basepoint.
Write f p:q “ ˚. Then f˚ : π1 pY, :q Ñ π1 pX, ˚q is a split epimorphism.
Therefore, the biset of f is left-invertible and right-principal; namely, it is a
π1 pY, :q-π1 pX, ˚q-biset B such that B _ bπ1 pY,:q B – π1 pX,˚q π1 pX, ˚qπ1 pX,˚q .
Proof. Let g be a homotopy left inverse of f . The first statement follows simply
from g˚ f˚ “ idX . The second one follows from the first.

4.7. Conjugacy classes in bisets. Let G BG be a biset. Its set of conjugacy
classes is
B G :“ G BG {tb “ gbg ´1 | b P B, g P Gu.
Consider a self-correspondence f, i : Z Ñ X. A homotopy pseudo-fixed point [9]
is the data pp, γq such that p P Z and γ : r0, 1s Ñ X with γp0q “ f ppq and γp1q “
ippq. In other words, γ encodes a homotopy difference between f ppq and ippq. If
γ is a constant path, then p is a fixed point of pf, iq. Two homotopy pseudo-fixed
points pp, γq and pq, δq are conjugate if there is a path ` : r0, 1s Ñ Z with `p0q “ p,
`p1q “ q such that f p`q#β#ip`´1 q is homotopic to γ.
The set of fixed points conjugate to a given fixed point p P Z is also known as
the Nielsen class of p. The Nielsen number N pf, iq is the set of fixed points of pf, iq
considered up to conjugacy.
Every pδ ´1 , p, γq P Bpf, iq, in the notation of Lemma 4.2, naturally defines a
homotopy pseudo-fixed point pp, γ#δq. Conversely, if X is path connected, then for
every homotopy pseudo-fixed point pp, γq we may choose a path ` : r0, 1s Ñ X with
`p0q “ ˚ and `p1q “ f ppq and construct an element p`´1 , p, γ#`q P Bpf, iq encoding
pp, γq.
The following proposition is immediate.
Proposition 4.18. Two elements pδ ´1 , p, γq, pδ 1´1 , p1 , γ 1 q P Bpf, iq are conjugate as
elements of the biset Bpf, iq if and only if the homotopy fixed points pp, γ#δq, pp1 , γ 1 #δ 1 q
are conjugate.
As a corollary, if X is path connected, then the Nielsen number N pf, iq is
bounded by the cardinality of B G .
In [3] we will further investigate homotopy pseudo-periodic orbits of a Thurston
map.
5. Dynamical systems
We turn now to applications of the previous sections. They will mainly be to
the theory of iterations of branched self-coverings of surfaces. The main objective

VAN KAMPEN’S THEOREM FOR BISETS

31

is an algorithmic understanding of these maps up to isotopy, and will be developed
in later articles. Here are some more elementary byproducts.
Consider first a polynomial ppzq P Crzs. We recall some basic definitions and
properties; see [6, 7] for details.
Let us denote by Prppq Ă C the forward orbit of p’s critical points:
Prppq :“ tpn pzq | p1 pzq “ 0, n ě 0 z P Cu.
The post-critical set P ppq :“ ppPrppqq is the forward orbit of p’s critical values. The
polynomial p is post-critically finite if P ppq is finite. The Julia set Jppq of p is the
closure of the repelling periodic points of p. Equivalently, Jppq is the boundary of
the filled-in Julia set Kppq:
Kppq :“ tz P C | P ppq is boundedu,

Jc “ BKc .

The Fatou set F ppq is the complement of Jppq.
Let us assume that p is post-critically finite. This assumption is essential to
obtain simple combinatorial descriptions of p. Then each bounded connected component of F ppq is a disk, and p acts on this set of disks. Furthermore, the boundary
of each disk component is a circle in Jppq.
Furthermore, every grand orbit of p : Prppq Ñ Prppq contains a unique periodic
cycle. If a periodic cycle C Ă Prppq contains a critical point of p, then C lies entirely
in the Fatou set, and moreover each element c P C lies in a different disk of F ppq.
On the other hand, if a cycle C contains no critical point of p, then C lies in Jppq. If
no cycle of P ppq contains a critical point of p, then F ppq has no bounded component
and Jppq is a dendrite.
Let T be the smallest tree in Kppq containing Prppq and containing P ppq in its
vertex set such that T intersects F ppq along radial arcs. Since Prppq is forward
invariant we get a self-map p : T ý. For every pair of adjacent edges e1 , e2 there is
the angle ?pe1 , e2 q P Q{Z uniquely specified by the following conditions, see [14]:
‚ ?pe1 , e2 q “ 0 if and only if e1 “ e2 ;
‚ if v is a common vertex of e1 and e2 and degv ppq is the local degree of p at
v, then
?pppe1 q, ppe2 qq “ degv ppq?pe1 , e2 q;
‚ for all edges e1 , e2 , e3 adjacent to a common vertex we have
?pe1 , e3 q “ ?pe1 , e2 q ` ?pe2 , e3 q.
Definition 5.1 (Hubbard trees). The (angled) Hubbard tree of a complex polynomial p is the data consisting of p : T ý, the values degp pvq P N measuring the local
degrees of p at vertices v P p´1 pT q, and the angle structure “?” on T satisfying
the above axioms.
4
In [14] post-critically finite polynomials are classified in terms of their Hubbard
trees.
Remark 5.2. If p has degree 2, then the angled structure of p : T ý is uniquely
determined by how T is topologically embedded into the plane. However, in general,
the planarity of T is insufficient to recover p; one needs to endow p : T ý with extra
information sufficient to recover the embedding of p´1 pT q into the plane.
It may be more convenient to consider a variant, the Hubbard complex, which is
a special case of topological automaton (see [13, §3]):

32

LAURENT BARTHOLDI AND DZMITRY DUDKO

Definition 5.3 (Hubbard complexes). Let p be a complex polynomial. Its Hubbard
complex is the self-correspondence p, i : H 1 Ñ H 0 defined as follows:
‚ H 0 is the smallest 1-dimensional subcomplex of the plane containing P ppqX
Jppq and all BD for D Ď F ppq a Fatou component intersecting P ppq;
‚ H 1 is the smallest 1-dimensional subcomplex of the plane containing P ppqX
Jppq and all BD for D Ď F ppq a Fatou component intersecting p´1 pP ppqq;
‚ p : H 1 Ñ H 0 is the restriction of p to H 1 and is a covering map;
‚ i : H 1 Ñ H 0 retracts H 1 into H 0 .
4
(As for the Hubbard tree, we assume that H 1 , H 0 intersects F ppq along radial lines.
Points in H 0 X P ppq and in H 1 X Prppq are treated as orbifold points.)

Figure 2. The Julia sets of the maps z 2 `i, z 2 ´1 (the “Basilica”)
and z 2 ` c for pc2 ` cq2 ` c “ 0 (the “Rabbit”). The Hubbard
complex is drawn in red, and (if it differs) the Hubbard tree is
drawn in black.

5.1. Thurston maps. We may consider the more general situation of a branched
self-covering of the sphere S 2 , namely a map p : S 2 ý that is locally modelled, in
complex charts, by z ÞÑ z n for some n P N. Those points z P S 2 at which n ě 2 are
critical points, and P ppq is the forward orbit of p’s critical values. If furthermore
there is a point 8 P S 2 with p´1 p8q “ t8u, then p is a topological polynomial. If
P ppq is finite, then p is called a Thurston map.
Unless p expands a metric on S 2 , there is no well-defined notion of Julia set.
There is, however, a convenient encoding of p by a biset. One sets X “ Y “ S 2 zP ppq
and Z “ S 2 zp´1 pP ppqq, with maps i : Z Ñ Y the inclusion and p : Z Ñ X the
restriction of p. Thus p : S 2 ý is given by a covering correspondence p, i : Z Ñ X.
Fix a basepoint ˚ P X, and write G “ π1 pX, ˚q. Let Bppq denote the biset of
the above correspondence associated with p; it is a G-G-biset, left-free of degree
degppq.

VAN KAMPEN’S THEOREM FOR BISETS

33

Let p0 , p1 be Thurston maps. They are called combinatorially equivalent if there
is an isotopy ppt qtPr0,1s from p0 to p1 along which P ppq moves continuously (and, in
particular, has constant cardinality). The biset of a Thurston map is a complete
invariant for combinatorial equivalence:
Theorem 5.4 (Kameyama [10], Nekrashevych [12, Theorem 6.5.2]). Let p0 , p1
be Thurston maps. Then p0 , p1 are Thurston equivalent if and only if the bisets
Bpp0 q, Bpp1 q are conjugate by an isomorphism π1 pS 2 zP pp0 q, ˚0 q Ñ π1 pS 2 zP pp1 q, ˚1 q
induced by a surface homeomorphism.
By definition, p behaves locally as z ÞÑ z degz ppq at a point z P S 2 ; set
ordpvq “ l. c. m.tdegz ppn q | n ě 0, z P p´n pvqu.
Clearly, ordpzq ą 1 if and only if z P P ppq, and ordpvq “ 8 if and only if v is in
a periodic cycle containing a critical point. For example, the degrees at P ppq are
all 8 for the Basilica and the Rabbit maps, and are 2 at i, ´i, i ´ 1 for z 2 ` i.
This order function ord defines an orbispace structure on S 2 : in our simplified
context, a topological space with the extra data of a non-trivial group attached at a
discrete set of points. We will not go into details of orbispaces, but simply note that,
if v is a point with group Gv attached to it, then v has canonical neighbourhoods
with fundamental group isomorphic to Gv . In our situation, the group attached to
v P P ppq is cyclic of order ordpvq. If ordpvq “ 8, then the point v may be treated
as a puncture rather than as a point with Z attached to it.
For each z P P ppq, let γz denote a small loop around z, and identify γz with a representative of a conjugacy class in π1 pS 2 zP ppq, ˚q. It follows that the fundamental
group of the orbispace defined by ord is given as follows:
(18)

Gp “ π1 pS 2 zP ppq, ˚q{xγzordpzq : z P P ppqy.

For every z P S 2 define ord1 pzq :“ ordpppzqq{ degz ppq. Then p : pS 2 , ord1 q Ñ
pS 2 , ordq is a covering between orbispaces while pS 2 , ord1 q ãÑ pS 2 , ordq is an orbispace inclusion. This defines the Gp -biset Bppq. Note that Theorem 5.4 was
stated for bisets over the group π1 pS 2 zP ppqq, not for bisets over the orbispace fundamental group Gp . However, an analogue of Theorem 5.4 is also true in that
context; this will be proven in [2].
Much structure in the space of Thurston maps can be obtained by comparing, or
deriving, maps from the simplest example f pzq “ z d . This map has Jpf q “ t|z| “ 1u
and P pf q “ t0, 8u so that π1 pCzP pf q, ˚q “ xty – Z. We call the corresponding
biset the regular cyclic biset of degree d: as a left xty-set, it is xty ˆ t1, . . . , du; and
the right action on the basis t1, . . . , du is given by
1 ¨ t “ 2,

...,

pd ´ 1q ¨ t “ d,

d ¨ t “ t ¨ 1.

It may also be defined more economically as Bpz d q “ ttj{d : j P Zu, with left and
right actions given by ti ¨ tj{d ¨ tk “ ti`j{d`k{d .
Since topological polynomials of degree d behave as z d in a neighbourhood of 8,
their bisets contain a copy of the regular degree-d cyclic biset. More generally, if p
has a fixed point in a neighbourhood of which it acts as z ÞÑ z n , then p contains a
regular degree-n cyclic subbiset.
The graph of bisets decompositions that we shall consider essentially attempt to
describe bisets of Thurston maps in terms of cyclic bisets.

34

LAURENT BARTHOLDI AND DZMITRY DUDKO

5.2. (Graphs of ) bisets from Hubbard trees. Let us consider the (angled)
Hubbard tree p : T ý of a complex polynomial p. We will now apply Van Kampen’s
theorem to p : T ý to decompose Bppq as a graph of bisets X TX as in Example 3.31.
Let T 1 be the preimage of T under p : C ý. We note that T 1 is easily reconstructable from the data p : T ý and ? and degv ppq for all v P T . The angled
structure of T lifts via p : T 1 Ñ T to an angled structure on T 1 . We denote by
ι : T 1 Ñ T the natural retraction of T 1 into its subtree. We write λpzq “ v if an
object z P T 1 retracts into a vertex v P T and we write λpzq “ e if an object z P T 1
retracts into a subset of an edge e P T but ιpzq is not a vertex of T . This defines
a graph morphism λ : T 1 Ñ T between undirected graphs, see§3.9 such that the
images of adjacent objects are adjacent or equal objects.
Let X be the space obtained from T by blowing up each vertex v P T into a
closed unit disc Dv with BDv – R{Z and by blowing down each edge e, say adjacent
to vertices v and w, into a point De with tDe u “ Dv X Dw such that for every pair
of edges e1 , e2 adjacent to a common vertex v we have
?pe1 , e2 q “ De1 ´ De2 P R{Z – BDv .
For every vertex v P T put an orbifold point of order ordpvq at the center of Dv , so
that the fundamental group of Dv is a cyclic group of order ordpvq.
Similarly, let X 1 be the space obtained from T 1 by blowing up each vertex v P T 1
into a closed disc Dv with orbifold point of order ord1 pvq at the center of Dv and
by blowing down each edge e into a point De satisfying same properties as above.
Then p : T 1 Ñ T naturally induces a covering map p : X 1 Ñ X specified so that
all maps between unit discs are of the form z Ñ z d . Furthermore, we have a natural
retraction ι : X 1 Ñ X satisfying ιpDz q Ă Dλpzq for every object z P T 1 . Applying
Van Kampen’s theorem Theorem 4.8 to the covering pair pX 1 , p, ιq subject to covers
tDz uzPT 1 , tDz uzPT , p, λ : T 1 Ñ T we get the graph of bisets X TX .
This graph of bisets can in fact also directly be described out of the Hubbard
tree data. We present below an algorithm that computes X TX .
We say that a vertex v P T 1 is essential if it is the image of a vertex under
the embedding T ãÑ T 1 . By definition, every vertex v P T has a unique essential
preimage under λ. We say a vertex v P T 1 is critical if ordpvq ą 1. Observe that if
v is a critical but non-essential, then λpvq is an edge.
ρ
p
λ
λ
On the level of graphs, X Ð T Ñ Y is the barycentric subdivision of T Ð T 1 Ñ
T . For convenience let us write ordpeq “ 1 for every edge e P T . For every object
z P T set
Gz :“ Z{ ordpzq.
In particular, Gz is a non-trivial group if and only if z is an essential vertex. This
constructs the graph of groups X. The fundamental group of X is isomorphic to a
free product of Gv over all essential vertices v P T . For every z P T 1 set
˘
`
(19)
Bz :“ deg1 ppq Z { ordpλpvqq
z

as a set with Gλpzq -Gppzq actions given by
#
m ` b ` degn ppq if z is an essential or a critical vertex,
z
(20)
m¨b¨n“
m`b
otherwise.
It remains to specify a congruence from Be into Bv for every edge e P T 1
adjacent to v P T 1 . Suppose first that v is a non-essential non-critical vertex. Then

VAN KAMPEN’S THEOREM FOR BISETS

35

λpeq “ λpvq and we define Be Ñ Bv to be the natural bijection coming from (19);
this is a well defined congruence between bisets because the right actions are trivial.
Let e P T 1 be an edge adjacent to either an essential or a critical vertex v P T 1 .
Then the congruence Be Ñ Bv is given by
b Ñ b ` tDe u
with De treated as an element of R{Z – BDv and tDe u means “round De down to
an element in Bv ”.
Theorem 5.5. The fundamental group of X is isomorphic to Gp (18). The fundamental biset of X TX constructed as above is isomorphic to Bppq. All bisets Bz , z P T
are cyclic.
Proof. By construction, the covering pair ppC, ord1 q, p, 1q is homotopic to the covering pair pX 1 , p, ιq along a homotopy path of covering pairs. Therefore, by Theorem 3.7 the fundamental group of X is isomorphic to Gp ; and by Theorem 4.8 the
fundamental biset of π1 pX TX q is isomorphic to Bppq. Let us verify that the above
algorithm computes X TX .
Let us assume that 0 P R{Z – BDv is the basepoint of π1 pDv q for every vertex
v P T . For every edge e adjacent to v set r0, De s Ă R{Z – BDv to be the path
connecting the basepoint of Dv to the basepoint of De (recall that De is a singleton).
For every vertex v P T 1 there is an av P R{Z such that the map p : BDv Ñ BDppvq
is given by x Ñ degv ppqx ` av in the R{Z-coordinates. Moreover, for every essential
vertex v P T 1 we may choose coordinates BDv – R{Z such that the map ι : BDv Ñ
BDλpvq is the identity in R{Z-coordinates.
Clearly, Gz is isomorphic to Z{ ordpzq for every object z P T .
For every essential vertex v P T 1 the biset Bv is computed by (15) as
Bv “ tb : r0, 1s Ñ R{Z – BDλpvq | bp0q “ 0, degv ppqbp1q ` av “ 0u{„
with Gλpvq actions are given by pre-concatenation and by post-concatenation via
lifting. Writing
„

t
t ´ av
:“ 0,
Ă R{Z – BDλpvq
degv ppq
degv ppq
we see that Bv takes the form given in (19) and (20). The case of non-essential
vertices is immediate because the right action is trivial.
If e P T 1 is an edge adjacent to a non-essential vertex v P T 1 , then the congruence
Be Ñ Bv respects (19). Suppose e P T 1 is an edge adjacent to an essential vertex
v P T 1 . If λpeq is an edge, then Be – tDe u embeds into Bv as r0, De s Ă R{Z – BDv
followed by the lift of rdegv ppqDe ` av , 0s Ă BDppvq under p : BDv Ñ BDppvq starting
at De P BDv . This gives an element tDe u P Bv with Bv viewed in the form (19).
If λpeq is a vertex, then λpeq “ v and the 0-element of Be is r0, De s Ă R{Z – Dv .
Again, this element is mapped to tDe u via the congruence Be Ñ Bv .

5.3. (Graphs of ) bisets from Hubbard complexes. Consider now a Hubbard
complex p, i : H 1 Ñ H 0 . As in the case of Hubbard trees §5.2 we blow up each
vertex v P H 1 \ H 0 into a closed disc Dv with an orbifold point of order ordpvq
at the center of Dv , and we blow down each edge e P H 1 \ H 0 into a point De .
Observe that all Dv have finite fundamental groups. Then p, i : H 1 Ñ H 0 naturally
induces a correspondence p, i : Y 1 Ñ Y 0 normalized so that all maps between unit
discs are of the form z Ñ z d . As in §5.2 we specify a graph morphism λ : H 1 Ñ H 0

36

LAURENT BARTHOLDI AND DZMITRY DUDKO

by ipDz q Ă Dλpzq for every object z P H 1 . Applying Van Kampen’s Theorem 4.8
to the covering pair pY 1 , p, iq subject to covers tDz uzPH 1 , tDz uzPH 0 with maps
p, λ : H 1 Ñ H 0 we get a graph of bisets Y HY . We remark that Y HY could be
explicitly computed out of p, i : H 1 Ñ H 0 in the same way as X TX was computed
out of the Hubbard tree §5.2.
Theorem 5.6. The fundamental group of Y is isomorphic to Gp (18). The fundamental biset of Y HY is isomorphic to Bppq.
All groups Gy , y P Y and all bisets Bz , z P H are finite.
Proof. The proof is the same as of Theorem 5.5. The claim about finiteness of Gy
and Bz is straightforward.

5.4. (Graphs of ) bisets from subdivision rules. Let us now generalize the
setup of §5.2. Suppose that p : S 2 ý is a topological Thurston map. By a subdivision
rule or a “puzzle partition” we mean graphs G0 Ă G1 Ă S 2 such that
‚ G1 “ p´1 pG0 q;
‚ there is a retraction ι : G1 Ñ G0 , with ι åG0 “ 1 such that G1 is homotopic
in S 2 to ιpG1 q rel the post-critical set;
‚ each connected component S 2 zG1 contains at most one post-critical point.
The last condition guarantees that p, ι : G1 Ñ G0 captures all combinatorial information of p : S 2 ý.
Assume, furthermore, that ι can be chosen in such a way that it maps vertices
and edges of G1 into vertices and edges of G1 . We may construct a graph of
bisets Z GZ associated with p, ι : G1 Ñ G0 . As in §5.2 we blow up each vertex
v P G1 \ G0 into a closed disc Dv with orbifold point of order ordpvq at the center
of Dv and we blow down each edge e P G1 \G0 into a point De . Then p, ι : G1 Ñ G0
naturally descents into a correspondence p, ι : Z 1 Ñ Z 0 normalized so that all maps
between unit discs are of the form z Ñ z d . As in §5.2 we specify a graph morphism
λ : G1 Ñ G0 by ιpDz q Ă Dλpzq for every object z P G1 . Applying Van Kampen’s
Theorem 4.8 to the covering pair pZ 1 , p, iq subject to covers tDz uzPG1 , tDz uzPG0
with p, λ : G1 Ñ G0 we get the graph of bisets Z GZ .
Theorem 5.7. There is a natural epimorphism φ : π1 pZ, ˚q Ñ Gp (18) and there
is a natural surjective map β : π1 pZ GZ , ˚q Ñ Bppq such that
pφ, βq : π1 pZ GZ q Ñ Gp BppqGp
is a semi-conjugacy respecting combinatorics (see §2.4).
Proof. The space Z 0 has a natural embedding into S 2 , unique up to homotopy rel
the post-critical set, such that Z 0 separates post-critical points. Therefore, there
is a natural epimorphism φ : π1 pGq Ñ Gp .
The embedding of p, ι : Z 1 Ñ Z 0 into S 2 defines a semi-conjugacy pφ, βq : BpZ 1 , p, ιq Ñ
Bppq. Observe that if a loop γ P π1 pZ 0 q is trivial in Gp , then all lifts of γ via
p : Z 1 Ñ Z 0 are loops. Therefore, γ has trivial monodromy action, so pφ, βq respects combinatorics.

5.5. Tuning and mating. The tuning operation takes as input a topological polynomial p, a periodic cycle z0 , z1 , . . . , zn “ z0 for p, and n topological polynomials
q0 , . . . , qn´1 with degpqi q “ degzi ppq for all i “ 0, . . . , n ´ 1; and produces a topological polynomial of degree degppq.

VAN KAMPEN’S THEOREM FOR BISETS

37

For each i, we give ourselves a set Pi containing the critical values of qi´1 and
such that qi pPi q Ă Pi`1 . In particular, Pi contains the post-critical set of qi´1 ˝
¨ ¨ ¨ ˝ qi`1 ˝ qi .
For simplicity, let us assume that the cycle z0 , z1 , . . . , zn “ z0 has no iterated
critical preimages outside of the cycle. This condition could be lifted, but the
construction would require slight modifications.
Up to isotopy, we may assume that around each zi there is a small closed topological disc Fi such that p restricts to a covering map p : Fi ztzi u Ñ Fi`1 ztzi`1 u and such
that there are homeomorphisms (known as “Böttcher coördinates”) ψi : intpFi q Ñ
C so that ψi`1 ˝ p ˝ ψi´1 is the map z ÞÑ z degzi ppq . Also, up to isotopy, we may
assume that qi pzq “ z degpqi q ` opz degpqi q q so that the extension of qi to the circle
at infinity coincides with the extension of z Ñ z degzi ppq . We consider the following
tuning map tpp, tzi u, tqi uq:
#
´1
ψi`1
pqi pψi pzqqq if z P intpFi q for some i,
tpzq “
ppzq
otherwise.
Note that if qi “ z degzi ppq for all i then t is isotopic to p.
Theorem 5.8. Suppose that tpp, tzi u, tqi uq is the tuning of a complex post-critically
finite polynomial p with polynomials qi : CzPi 99K CzPi`1 as above. Suppose also
ordpzi q “ 8 for all i. Let X TX denote the graph of bisets constructed out of the
Hubbard tree of p, see Theorem 5.5. Set Gi “ π1 pCzPi , ˚i q for a basepoint ˚i " 0,
and let φi : Gzi Ñ Gi be the monomorphism defined by identifying intpFi q with
C via ψi , so that the circle BFi corresponds to the circle at infinity in CzPi . Let
βi : Bzi Ñ Bpqi q be the pφi , φi`1 q-congruence defined by viewing p : BFi Ñ BFi`1 as
a map at infinity of qi : CzPi 99K CzPi`1 .
For all i, replace the cyclic group Gzi at zi P X by Gi :“ π1 pCzPi q, and replace the
regular cyclic biset Bzi at zi P B by the Gi -Gi`1 -biset Bpqi q. Modify accordingly all
non-essential bisets: replace all Bz with z P λ´1 pzi qztzi u by Gi bGzi Bz and declare
for all z P p´1 pzi`1 qztzi u the right Gi`1 -action on Bz to be trivial. Congruences
of edge bisets into Bpqi q are given through the congruence βi : Bzi Ñ Bpqi q. This
defines a new graph of bisets B with same underlying graph as T.
Then Bptq and π1 pBq are isomorphic.
Proof. Let p, ι : X 1 Ñ X be the correspondence from §5.2 associated with the
r1 Ñ X
r be the correspondence obtained by replacing
Hubbard tree of p. Let t, ι : X
each p : intpDzi q Ñ intpDzi`1 q with qi : CzPi 99K CzPi`1 appropriately glued with
r 1 Ñ X,
r the biset of t is isomorphic to the
BDi , BDi`1 . Since t is isotopic to t, ι : X
1
r , t, ιq which by Van Kampen’s Theorem 4.8 is π1 pBq. 
biset of a covering pair pX
This operation may be performed with p a Thurston map, not necessarily a
topological polynomial. As a special case, a topological polynomial has a critical
fixed point 8. The formal mating p \ q of two topological polynomials p, q of same
degree is the tuning tpp, t8u, qq. In other words, p \ q is a topological map on a
two dimensional sphere where p acts on the southern hemisphere while q acts on
the northern hemisphere.
Since the vertex 8 does not belong to the Hubbard tree of p, Theorem 5.8 cannot
apply. We do have a simple description of the mating in terms of graphs of bisets,
though:

38

LAURENT BARTHOLDI AND DZMITRY DUDKO

Theorem 5.9. Let p, q be two topological polynomials of same degree d. Write
Gp “ π1 pCzP ppq, ˚q and Gq “ π1 pCzP pqq, :q with ˚, : close to 8. Consider the
graph of groups X with one edge e and two vertices p, q. The groups at p, q are
Gp , Gq respectively; the group at e is Z, included in Gp and Gq as the loop around
infinity. Consider the graph of bisets B with one edge and two vertices. The graph
maps λ, ρ are the identity, the biset Be on the edge is regular cyclic of degree d, and
the bisets at the vertices are Bppq, Bpqq respectively. The congruences Be ãÑ Bppq
and Be ãÑ Bpqq are defined by viewing z Ñ z d : S 1 ý as a map on the circle at
infinity of p : CzP ppq 99K CzP ppq and q : CzP pqq 99K CzP pqq.
Then π1 pBq is isomorphic to Bpp \ qq.
Proof. Applying Theorem 4.8 to p \ q subject to the cover consisting of the closed
southern hemisphere, the closed northern hemisphere and the equator, we obtain a
graph of bisets isomorphic to the barycentric subdivision of B.

5.6. Laminations. Consider a complex polynomial p of degree d. The Fatou component around 8 admits a Böttcher parameterization φ : F8 Ñ t|z| ă 1u such
that φpppzqq “ φpzqd . Since Jppq “ BF8 , every element of Jppq may be described
as limrÑ1 φ´1 preiθ q for some (non-unique) angle θ; this gives a surjective map
cp : t|z| “ 1u Ñ Jppq encoding the Julia set. In fact, the biset of p may be read
from the base-d expansion of the kernel of cp , namely the equivalence relation
Ξp “ tpz1 , z2 q | cp pz1 q “ cp pz2 qu.
The equivalence relation may be presented by a lamination of the disk t|z| ď 1u:
the disjoint collection of subsets of the closed disk, called leaves, that are convex
hulls (in the hyperbolic metric, say) of equivalence classes of Ξp .

The Julia set Jppq is the quotient of the circle by the relation Ξp , so the filledin Julia set is the quotient of the disk obtained by contracting all leaves of the
lamination to points. The dynamics on the circle is the “multiply the angle by
d” map. The van Kampen theorem 3.7 may therefore be applied to the covering
consisting of the boundary circle and the leaves. In fact, if p is post-critically
finite it suffices to consider a finite collection of leaves. We consider, as a simple
illustration, the Basilica map z 2 ´ 1 obtained from the circle by pinching the above
lamination.

VAN KAMPEN’S THEOREM FOR BISETS

y1

x1

39

x
f

˚2

˚1

:1 :2

˚

:

i
x2

y2

y

Figure 3. The correspondence generating the lamination
of z 2 ´1.
?
Note that the two preimages of x are x1 , x2 “ ˘ x, and similarly
for y.
The space under consideration consists of a circle C and an arc A connecting
the points x “ expp2iπ{3q and y “ expp4iπ{3q, see Figure 5.6. We fix basepoints
˚ “ 1 on C and : “ x on A.
Let us denote by S, T , U the bisets of f, i : C Ñ C, f, i : A Ñ A, and f : ´A Ñ A,
i : ´ A Ñ C respectively. We thus have the following graph of bisets B:
x
y
x
1

T

1

S
x2

π1 pA, :q

U
y2

π1 pC, ˚q
y

in which S “ 2Z ZZ is the regular cyclic biset encoding the doubling map on C and
the other bisets T, U are trivial. The maps ρ, λ are given by
ρpT q “ ρpU q “ λpT q “ π1 pA, :q,

ρpSq “ λpSq “ λpU q “ π1 pC, ˚q.

The structure of B will have been completely given when we fix bases of S, T, U
and describe the edge bisets x1 , y1 , x2 , y2 as maps from T or U into S. Let us write
H “ π1 pC, ˚q “ xty and 1 “ π1 pA, :q. Then
HS

“ H ˆ t1, 2u,

1T

“ 1 ˆ t3u,

HU

“ H ˆ t4u.

Recall that elements of a biset Bpf, i, ˚2 , ˚1 q are written, in their most general
form (13), as pα, p, βq for paths α, β with αp0q “ ˚2 , αp1q “ ippq, βp0q “ f ppq, βp1q “
˚1 . We fix paths p, x, `, y starting at ˚ “ 1, turning counterclockwise on C, and
ending respectively at expp2iπ{6q, x, ˚2 , y. We also write  for any constant path.
In this notation, the bases 1, 2, 3, 4 are respectively
1 “ p, ˚1 , q,

2 “ p`, ˚2 , q,

3 “ p, :1 , q,

4 “ pp, :2 , q.

We may now view y1 , x2 as maps T Ñ S and x1 , y2 as maps U Ñ S. They are
given by
y1 p3q “ px, :1 , y ´1 q “ 1,

x1 p4q “ pp, :2 , x´1 q “ 1,

x2 p3q “ py, :1 , x´1 q “ 2,

y2 p4q “ pp, :2 , y ´1 q “ t´1 2.

40

LAURENT BARTHOLDI AND DZMITRY DUDKO

We are finally ready to compute the fundamental biset B of B. It is a G-G-biset
for the group G “ H ˚ xyx´1 y “ xt, yx´1 y. We may keep the basis t1, 2u of S, so
that G B “ G ˆ t1, 2u, and we have, just as in S,
1 ¨ t “ 2,

2 ¨ t “ t ¨ 1.

We now compute
1 ¨ yx´1 “ y1 p3qyx´1 “ x3x´1 “ xy ´1 x2 p3q “ xy ´1 ¨ 2,
2 ¨ yx´1 “ ty2 p4qyx´1 “ t4x´1 “ tx1 p4q “ t ¨ 1.
In this manner, we formally recover the presentation of the Basilica biset from the
graph of bisets B, using the relations y1 p3qy “ x3 etc. appearing in Definition 3.13.
There is another sort of mating, obtained directly from the Julia sets. The
geometric mating of two polynomials p, q of same degree is the map obtained from
z ÞÑ z 2 : pC Y t8uq ý through the quotient of t|z| ď 1u by the lamination of p and
through the quotient of t|z| ě 1u by the lamination of q embedded into the outer
disc via the map z Ñ z1 . In case both p and q are post-critically finite quadratic
polynomials that are not in the conjugate limbs of the Mandelbrot set, the formal
and geometric matings of p and q are isotopic. See [5] for a discussion on the various
types of mating.
Theorem 5.10. Let p be a post-critically finite quadratic polynomial that lies outside of the Basilica limb. Write H “ π1 pCzP ppq, ˚q. Then the biset of pz 2 ´ 1q \ p
is the fundamental biset of the following graph of bisets:
x
y1
x1
Bppq

T
x2

U
y2

1

H
y

with the same maps ρ, λ and inclusions as above.
Proof. The map pz 2 ´ 1q \ p is homotopic to the map shown on Figure 5.6 with
t|z| ě 1u replaced by the filled-in Julia set of p. The statement becomes a corollary
of Theorem 4.8.

References
[1] Laurent Bartholdi and Dzmitry V. Dudko, Algorithmic aspects of branched coverings, 2015,
preprint.
[2]
, Algorithmic aspects of branched coverings II. Spheres bisets and their decompositions, 2015, preprint.
[3]
, Algorithmic aspects of branched coverings IV. Expanding maps, 2015, in preparation.
[4] Hyman Bass, Covering theory for graphs of groups, J. Pure Appl. Algebra 89 (1993), no. 1-2,
3–47, DOI 10.1016/0022-4049(93)90085-8. MR1239551 (94j:20028)
[5] Arnaud Chéritat, Tan Lei and Shishikura’s example of non-mateable degree 3 polynomials
without a Levy cycle, Ann. Fac. Sci. Toulouse Math. (6) 21 (2012), no. 5, 935–980, DOI
10.5802/afst.1358 (English, with English and French summaries). MR3088263
[6] Adrien Douady and John H. Hubbard, Étude dynamique des polynômes complexes. Partie I, Publications Mathématiques d’Orsay [Mathematical Publications of Orsay], vol. 84,
Université de Paris-Sud, Département de Mathématiques, Orsay, 1984 (French). MR762431
(87f:58072a)
[7]
, Étude dynamique des polynômes complexes. Partie II, Publications Mathématiques
d’Orsay [Mathematical Publications of Orsay], vol. 85, Université de Paris-Sud, Département
de Mathématiques, Orsay, 1985 (French). With the collaboration of P. Lavaurs, Tan Lei and
P. Sentenac. MR812271 (87f:58072b)

VAN KAMPEN’S THEOREM FOR BISETS

41

[8] William M. Goldman, The symplectic nature of fundamental groups of surfaces, Adv. in
Math. 54 (1984), no. 2, 200–225, DOI 10.1016/0001-8708(84)90040-9. MR762512 (86i:32042)
[9] Yutaka Ishii and John Smillie, Homotopy shadowing, Amer. J. Math. 132 (2010), no. 4,
987–1029, DOI 10.1353/ajm.0.0126. MR2663646 (2012d:37055)
[10] Atsushi Kameyama, The Thurston equivalence for postcritically finite branched coverings,
Osaka J. Math. 38 (2001), no. 3, 565–610. MR1860841 (2002h:57004)
[11] William S. Massey, Algebraic topology: an introduction, Harcourt, Brace and World (New
York), 1967.
[12] Volodymyr V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs,
vol. 117, American Mathematical Society, Providence, RI, 2005. MR2162164 (2006e:20047)
[13] Volodymyr Nekrashevych, Combinatorial models of expanding dynamical systems, Ergodic
Theory Dynam. Systems 34 (2014), no. 3, 938–985, DOI 10.1017/etds.2012.163. MR3199801
[14] Alfredo Poirier, Hubbard trees, Fund. Math. 208 (2010), no. 3, 193–248, DOI 10.4064/fm2083-1. MR2650982 (2011j:37083)
[15] Jean-Pierre Serre, Trees, Springer-Verlag, Berlin, 1980. Translated from the French by John
Stillwell. MR82c:20083
E-mail address: laurent.bartholdi@gmail.com
E-mail address: dzmitry.dudko@gmail.com
École Normale Supérieure, Paris and Mathematisches Institut, Georg-August Universität zu Göttingen

