Train track map

In the mathematical subject of geometric group theory, a train track map is a continuous map ''f'' from a finite connected graph to itself which is a homotopy equivalence and which has particularly nice cancellation properties with respect to iterations. This map sends vertices to vertices and edges to nontrivial edge-paths with the property that for every edge ''e'' of the graph and for every positive integer ''n'' the path ''fⁿ''(''e'') is ''immersed'', that is ''fⁿ''(''e'') is locally injective on ''e''. Train-track maps are a key tool in analyzing the dynamics of automorphisms of finitely generated free groups and in the study of the Culler–Vogtmann Outer space.

History

Train track maps for free group automorphisms were introduced in a 1992 paper of Bestvina and Handel.Mladen Bestvina, and Michael Handel
''Train tracks and automorphisms of free groups.''
Annals of Mathematics (2), vol. 135 (1992), no. 1, pp. 1–51 The notion was motivated by Thurston's train tracks on surfaces, but the free group case is substantially different and more complicated. In their 1992 paper Bestvina and Handel proved that every irreducible automorphism of ''F_n'' has a train-track representative. In the same paper they introduced the notion of a ''relative train track'' and applied train track methods to solve the ''Scott conjecture'' which says that for every automorphism ''α'' of a finitely generated free group ''F_n'' the fixed subgroup of ''α'' is free of rank at most ''n''. In a subsequent paperMladen Bestvina and Michael Handel
''Train-tracks for surface homeomorphisms.''
Topology, vol. 34 (1995), no. 1, pp. 109–140. Bestvina and Handel applied the train track techniques to obtain an effective proof of Thurston's classification of homeomorphisms of compact surfaces (with or without boundary) which says that every such homeomorphism is, up to isotopy, either reducible, of finite order or pseudo-anosov.

Since then train tracks became a standard tool in the study of algebraic, geometric and dynamical properties of automorphisms of free groups and of subgroups of Out(''F_n''). Train tracks are particularly useful since they allow to understand long-term growth (in terms of length) and cancellation behavior for large iterates of an automorphism of ''F_n'' applied to a particular conjugacy class in ''F_n''. This information is especially helpful when studying the dynamics of the action of elements of Out(''F_n'') on the Culler–Vogtmann Outer space and its boundary and when studying ''F_n'' actions of on real trees.Gilbert Levitt and Martin Lustig, ''Irreducible automorphisms of F_n have north-south dynamics on compactified outer space.'' Journal of the Institute of Mathematics of Jussieu, vol. 2 (2003), no. 1, 59–72 Examples of applications of train tracks include: a theorem of BrinkmannP. Brinkmann
''Hyperbolic automorphisms of free groups.''
Geometric and Functional Analysis, vol. 10 (2000), no. 5, pp. 1071–1089 proving that for an automorphism ''α'' of ''F_n'' the mapping torus group of ''α'' is word-hyperbolic if and only if ''α'' has no periodic conjugacy classes; a theorem of Bridson and GrovesMartin R. Bridson and Daniel Groves
''The quadratic isoperimetric inequality for mapping tori of free-group automorphisms.''
Memoirs of the American Mathematical Society, to appear. that for every automorphism ''α'' of ''F_n'' the mapping torus group of ''α'' satisfies a quadratic isoperimetric inequality; a proof of algorithmic solvability of the conjugacy problem for free-by-cyclic groups;O. Bogopolski, A. Martino, O. Maslakova, E. Ventura
''The conjugacy problem is solvable in free-by-cyclic groups.''
Bulletin of the London Mathematical Society, vol. 38 (2006), no. 5, pp. 787–794 and others.

Train tracks were a key tool in the proof by Bestvina, Feighn and Handel that the group Out(''F_n'') satisfies the Tits alternative.Mladen Bestvina, Mark Feighn, and Michael Handel
''The Tits alternative for Out(F_n). I. Dynamics of exponentially-growing automorphisms.''
Annals of Mathematics (2), vol. 151 (2000), no. 2, pp. 517–623Mladen Bestvina, Mark Feighn, and Michael Handel.
''The Tits alternative for Out(F_n). II. A Kolchin type theorem.''
Annals of Mathematics (2), vol. 161 (2005), no. 1, pp. 1–59

The machinery of train tracks for injective endomorphisms of free groups was later developed by Dicks and Ventura.Warren Dicks, and Enric Ventura
''The group fixed by a family of injective endomorphisms of a free group.''
Contemporary Mathematics, 195. American Mathematical Society, Providence, RI, 1996.

Formal definition

Combinatorial map

For a finite graph ''Γ'' (which is thought of here as a 1-dimensional cell complex) a ''combinatorial map'' is a continuous map
:''f'' : ''Γ'' → ''Γ''
such that:
* The map ''f'' takes vertices to vertices.
* For every edge ''e'' of ''Γ'' its image ''f''(''e'') is a nontrivial edge-path ''e''₁...''e''_''m'' in ''Γ'' where ''m'' ≥ 1. Moreover, ''e'' can be subdivided into ''m'' intervals such that the interior of the ''i''-th interval is mapped by ''f'' homeomorphically onto the interior of the edge ''e''_''i'' for ''i'' = 1,...,''m''.

Train track map

Let ''Γ'' be a finite connected graph. A combinatorial map ''f'' : ''Γ'' → ''Γ'' is called a ''train track map'' if for every edge ''e'' of ''Γ'' and every integer ''n'' ≥ 1 the edge-path ''f''^''n''(''e'') contains no backtracks, that is, it contains no subpaths of the form ''hh''⁻¹ where ''h'' is an edge of ''Γ''. In other words, the restriction of ''f''^''n'' to ''e'' is locally injective (or an immersion) for every edge ''e'' and every ''n'' ≥ 1.

When applied to the case ''n'' = 1, this definition implies, in particular, that the path ''f''(''e'') has no backtracks.

Topological representative

Let ''F''_''k'' be a free group of finite rank ''k'' ≥ 2. Fix a free basis ''A'' of ''F''_''k'' and an identification of ''F''_''k'' with the fundamental group of the ''rose'' ''R''_''k'' which is a wedge of ''k'' circles corresponding to the basis elements of ''A''.

Let ''φ'' ∈  Out(''F''_''k'') be an outer automorphism of ''F''_''k''.

A ''topological representative'' of ''φ'' is a triple (''τ'', ''Γ'', ''f'') where:
*''Γ'' is a finite connected graph with the first betti number ''k'' (so that the fundamental group of ''Γ'' is free of rank ''k'').
* ''τ'' : ''R_k'' → ''Γ'' is a homotopy equivalence (which, in this case, means that ''τ'' is a continuous map which induces an isomorphism at the level of fundamental groups).
* ''f'' : ''Γ'' → ''Γ'' is a combinatorial map which is also a homotopy equivalence.
* If ''σ'' : ''Γ'' → ''R_k'' is a homotopy inverse of ''τ'' then the composition
: ''σfτ'' : ''R_k'' → ''R_k''
:induces an automorphism of ''F''_''k'' = ''π''₁(''R_k'') whose outer automorphism class is equal to ''φ''.

The map ''τ'' in the above definition is called a ''marking'' and is typically suppressed when topological representatives are discussed. Thus, by abuse of notation, one often says that in the above situation ''f'' : ''Γ'' → ''Γ'' is a topological representative of ''φ''.

Train track representative

Let ''φ'' ∈  Out(''F''_''k'') be an outer automorphism of ''F''_''k''. A train track map which is a topological representative of ''φ'' is called a ''train track representative'' of ''φ''.

Legal and illegal turns

Let ''f'' : ''Γ'' → ''Γ'' be a combinatorial map. A ''turn'' is an unordered pair ''e'', ''h'' of oriented edges of ''Γ'' (not necessarily distinct) having a common initial vertex. A turn ''e'', ''h'' is ''degenerate'' if ''e'' = ''h'' and ''nondegenerate'' otherwise.

A turn ''e'', ''h'' is ''illegal'' if for some ''n'' ≥ 1 the paths ''f''^''n''(''e'') and ''f''^''n''(''h'') have a nontrivial common initial segment (that is, they start with the same edge). A turn is ''legal'' if it not ''illegal''.

An edge-path ''e''₁,..., ''e''_''m'' is said to ''contain'' turns ''e''_''i''⁻¹, ''e''_''i''+1 for ''i'' = 1,...,''m''−1.

A combinatorial map ''f'' : ''Γ'' → ''Γ'' is a train-track map if and only if for every edge ''e'' of ''Γ'' the path ''f''(''e'') contains no illegal turns.

Derivative map

Let ''f'' : ''Γ'' → ''Γ'' be a combinatorial map and let ''E'' be the set of oriented edges of ''Γ''. Then ''f'' determines its ''derivative map'' ''Df'' : ''E'' → ''E'' where for every edge ''e'' ''Df''(''e'') is the initial edge of the path ''f''(''e''). The map ''Df'' naturally extends to the map ''Df'' : ''T'' → ''T'' where ''T'' is the set of all turns in ''Γ''. For a turn ''t'' given by an edge-pair ''e'', ''h'', its image ''Df''(''t'') is the turn ''Df''(''e''), ''Df''(''h''). A turn ''t'' is legal if and only if for every ''n'' ≥ 1 the turn (''Df'')^''n''(''t'') is nondegenerate. Since the set ''T'' of turns is finite, this fact allows one to algorithmically determine if a given turn is legal or not and hence to algorithmically decide, given ''f'', whether or not ''f'' is a train-track map.

Examples

Let ''φ'' be the automorphism of ''F''(''a'',''b'') given by ''φ''(''a'') = ''b'', ''φ''(''b'') = ''ab''. Let ''Γ'' be the wedge of two loop-edges ''E''_''a'' and ''E''_''b'' corresponding to the free basis elements ''a'' and ''b'', wedged at the vertex ''v''. Let ''f'' : ''Γ'' → ''Γ'' be the map which fixes ''v'' and sends the edge ''E''_''a'' to ''E''_''b'' and that sends the edge ''E''_''b'' to the edge-path ''E''_''a''''E''_''b''.
Then ''f'' is a train track representative of ''φ''.

Main result for irreducible automorphisms

Irreducible automorphisms

An outer automorphism ''φ'' of ''F''_''k'' is said to be ''reducible'' if there exists a free product decomposition
:$F_k=H_1\ast\dots H_m\ast U$
where all ''H''_''i'' are nontrivial, where ''m'' ≥ 1 and where ''φ'' permutes the conjugacy classes of ''H''₁,...,''H''_''m'' in ''F''_''k''. An outer automorphism ''φ'' of ''F''_''k'' is said to be ''irreducible'' if it is not reducible.

It is known that ''φ'' ∈  Out(''F''_''k'') be irreducible if and only if for every topological representative
''f'' : ''Γ'' → ''Γ'' of ''φ'', where ''Γ'' is finite, connected and without degree-one vertices, any proper ''f''-invariant subgraph of ''Γ'' is a forest.

Bestvina–Handel theorem for irreducible automorphisms

The following result was obtained by Bestvina and Handel in their 1992 paper where train track maps were originally introduced:

Let ''φ'' ∈  Out(''F''_''k'') be irreducible. Then there exists a train track representative of ''φ''.

Sketch of the proof

For a topological representative ''f'':''Γ''→''Γ'' of an automorphism ''φ'' of ''F''_''k'' the ''transition matrix'' ''M''(''f'') is an ''r''x''r'' matrix (where ''r'' is the number of topological edges of ''Γ'') where the entry ''m''_''ij'' is the number of times the path ''f''(''e''_''j'') passes through the edge ''e''_''i'' (in either direction). If ''φ'' is irreducible, the transition matrix ''M''(''f'') is ''irreducible'' in the sense of the Perron–Frobenius theorem and it has a unique Perron–Frobenius eigenvalue ''λ''(''f'') ≥ 1 which is equal to the spectral radius of ''M''(''f'').

One then defines a number of different ''moves'' on topological representatives of ''φ'' that are all seen to either decrease or preserve the Perron–Frobenius eigenvalue of the transition matrix. These moves include: subdividing an edge; valence-one homotopy (getting rid of a degree-one vertex); valence-two homotopy (getting rid of a degree-two vertex); collapsing an invariant forest; and folding. Of these moves the valence-one homotopy always reduced the Perron–Frobenius eigenvalue.

Starting with some topological representative ''f'' of an irreducible automorphism ''φ'' one then algorithmically constructs a sequence of topological representatives
:''f'' = ''f''₁, ''f''₂, ''f''₃,...
of ''φ'' where ''f''_''n'' is obtained from ''f''_''n''−1 by several moves, specifically chosen. In this sequence, if ''f''_''n'' is not a train track map, then the moves producing ''f''_''n''+1 from ''f''_''n'' necessarily involve a sequence of folds followed by a valence-one homotopy, so that the Perron–Frobenius eigenvalue of ''f''_''n''+1 is strictly smaller than that of ''f''_''n''. The process is arranged in such a way that Perron–Frobenius eigenvalues of the maps ''f''_''n'' take values in a discrete substet of $\mathbb R$. This guarantees that the process terminates in a finite number of steps and the last term ''f''_''N'' of the sequence is a train track representative of ''φ''.

Applications to growth

A consequence (requiring additional arguments) of the above theorem is the following:
*If ''φ'' ∈ Out(''F''_''k'') is irreducible then the Perron–Frobenius eigenvalue ''λ''(''f'') does not depend on the choice of a train track representative ''f'' of ''φ'' but is uniquely determined by ''φ'' itself and is denoted by ''λ''(''φ''). The number ''λ''(''φ'') is called the ''growth rate'' of ''φ''.
*If ''φ'' ∈ Out(''F''_''k'') is irreducible and of infinite order then ''λ''(''φ'') > 1. Moreover, in this case for every free basis ''X'' of ''F''_''k'' and for most nontrivial values of ''w'' ∈ ''F''_''k'' there exists ''C'' ≥ 1 such that for all ''n'' ≥ 1
:$\frac\lambda^n(\phi) \le , , \phi^n(w), , _X\le C \lambda^n(\phi),$
:where , , ''u'', , _''X'' is the cyclically reduced length of an element ''u'' of ''F''_''k'' with respect to ''X''. The only exceptions occur when ''F''_''k'' corresponds to the fundamental group of a compact surface with boundary ''S'', and ''φ'' corresponds to a pseudo-Anosov homeomorphism of ''S'', and ''w'' corresponds to a path going around a component of the boundary of ''S''.

Unlike for elements of mapping class groups, for an irreducible ''φ'' ∈ Out(''F''_''k'') it is often the case
Michael Handel, and Lee Mosher, ''The expansion factors of an outer automorphism and its inverse.''
Transactions of the American Mathematical Society, vol. 359 (2007), no. 7, 3185 3208 that
:''λ''(''φ'') ≠ ''λ''(''φ''⁻¹).

Relative train tracks

Applications and generalizations

*The first major application of train tracks was given in the original 1992 paper of Bestvina and Handel where train tracks were introduced. The paper gave a proof of the ''Scott conjecture'' which says that for every automorphism ''α'' of a finitely generated free group ''F_n'' the fixed subgroup of ''α'' is free of rank at most ''n''.
*In a subsequent paper Bestvina and Handel applied the train track techniques to obtain an effective proof of Thurston's classification of homeomorphisms of compact surfaces (with or without boundary) which says that every such homeomorphism is, up to isotopy, is either reducible, of finite order or pseudo-anosov.
*Train tracks are the main tool in Los' algorithm for deciding whether or not two irreducible elements of Out(''F_n'') are conjugate in Out(''F_n'').
*A theorem of Brinkmann proving that for an automorphism ''α'' of ''F_n'' the mapping torus group of ''α'' is word-hyperbolic if and only if ''α'' has no periodic conjugacy classes.
*A theorem of Levitt and Lustig showing that a fully irreducible automorphism of a ''F''_''n'' has "north-south" dynamics when acting on the Thurston-type compactification of the Culler–Vogtmann Outer space.
*A theorem of Bridson and Groves that for every automorphism ''α'' of ''F_n'' the mapping torus group of ''α'' satisfies a quadratic isoperimetric inequality.
*The proof by Bestvina, Feighn and Handel that the group Out(''F_n'') satisfies the Tits alternative.
*An algorithm that, given an automorphism ''α'' of ''F''_''n'', decides whether or not the fixed subgroup of ''α'' is trivial and finds a finite generating set for that fixed subgroup.O. S. Maslakova. ''The fixed point group of a free group automorphism''. (Russian). Algebra Logika, vol. 42 (2003), no. 4, pp. 422–472; translation in
Algebra and Logic, vol. 42 (2003), no. 4, pp. 237–265
*The proof of algorithmic solvability of the conjugacy problem for free-by-cyclic groups by Bogopolski, Martino, Maslakova, and Ventura.
*The machinery of train tracks for injective endomorphisms of free groups, generalizing the case of automorphisms, was developed in a 1996 book of Dicks and Ventura.

See also

*Geometric group theory
*Real tree
*Mapping class group
*Free group
* Out(''F''_''n'')

Basic references

*
*Warren Dicks, and Enric Ventura
''The group fixed by a family of injective endomorphisms of a free group.''
Contemporary Mathematics, 195. American Mathematical Society, Providence, RI, 1996.
*Oleg Bogopolski
''Introduction to group theory''.
EMS Textbooks in Mathematics. European Mathematical Society, Zürich, 2008.

Footnotes

{{reflist

External links

*Peter Brinkmann's minicourse notes on train track

http://www.math.uiuc.edu/~brinkman/research/tex/talk2.pd

http://www.math.uiuc.edu/~brinkman/research/tex/talk5.pdf]

Geometric group theory
Geometric topology
Combinatorics on words