Train track map
Encyclopedia
In the mathematical subject of geometric group theory
Geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act .Another important...

 a train track map is a continuous map f from a finite connected graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 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 fn(e) is immersed, that is fn(e) is locally injective on e. Train-track maps are a key tool in analyzing the dynamics of automorphism
Automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism...

s of finitely generated free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

s and in the study of the Culler
Marc Culler
Marc Edward Culler is an American mathematician who works in geometric group theory and low-dimensional topology. A native Californian, Culler did his undergraduate work at the University of California at Santa Barbara and his graduate work at Berkeley where he graduated in 1978. He is now at the...

Vogtmann
Karen Vogtmann
Karen Vogtmann is a U.S. mathematician working primarily in the area of geometric group theory. She is known for having introduced, in a 1986 paper with Marc Culler, an object now known as the Culler–Vogtmann Outer space...

 Outer space.

History

Train track maps for free group automorphisms were introduced in a 1992 paper of Bestvina
Mladen Bestvina
Mladen Bestvina is a Croatian American mathematician working in the area of geometric group theory. He is a Distinguished Professor in the Department of Mathematics at the University of Utah.-Biographical info:...

 and Handel. The notion was motivated by Thurston's train track
Train track
In the mathematical area of topology, a train track is a family of curves embedded on a surface, meeting the following conditions:#The curves meet at a finite set of vertices called switches....

s 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 Fn 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
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 Fn 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 homeomorphism
Homeomorphism
In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...

s of compact surfaces (with or without boundary) which says that every such homeomorphism
Homeomorphism
In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...

 is, up to isotopy, either reducible, of finite order or pseudo-anosov
Pseudo-Anosov map
In mathematics, specifically in topology, a pseudo-Anosov map is a type of a diffeomorphism or homeomorphism of a surface. It is a generalization of a linear Anosov diffeomorphism of the torus...

.

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(Fn). 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 Fn applied to a particular conjugacy class
Conjugacy class
In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...

 in Fn. This information is especially helpful when studying the dynamics of the action of elements of Out(Fn) on the Culler–Vogtmann Outer space and its boundary and when studying Fn actions of on real tree
Real tree
A real tree, or an \mathbb R-tree, is a metric space such thatfor any x, y in M there is a unique arc from x to y and this arc is a geodesic segment. Here by an arc from x to y we mean the image in M of a topological embedding f from an interval [a,b] to M such that f=x and f=y...

s. Examples of applications of train tracks include: a theorem of Brinkmann proving that for an automorphism α of Fn the mapping torus group of α is word-hyperbolic if and only if α has no periodic conjugacy classes; a theorem of Bridson and Groves that for every automorphism α of Fn the mapping torus group of α satisfies a quadratic isoperimetric inequality
Dehn function
In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group in terms of the length of that relation...

; a proof of algorithmic solvability of the conjugacy problem
Conjugacy problem
In abstract algebra, the conjugacy problem for a group G with a given presentation is the decision problem of determining, given two words x and y in G, whether or not they represent conjugate elements of G...

 for free-by-cyclic groups; and others.

Train tracks were a key tool in the proof by Bestvina, Feighn and Handel that the group Out(Fn) satisfies the Tits alternative
Tits alternative
In mathematics, the Tits alternative, named for Jacques Tits, is an important theorem about the structure of finitely generated linear groups. It states that every such group is either virtually solvable In mathematics, the Tits alternative, named for Jacques Tits, is an important theorem about...

.

The machinery of train tracks for injective endomorphism
Endomorphism
In mathematics, an endomorphism is a morphism from a mathematical object to itself. For example, an endomorphism of a vector space V is a linear map ƒ: V → V, and an endomorphism of a group G is a group homomorphism ƒ: G → G. In general, we can talk about...

s of free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

s was later developed by Dicks and Ventura.

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 e1...em 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 ei 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 fn(e) contains no backtracks, that is, it contains no subpaths of the form hh−1 where h is an edge of Γ. In other words, the restriction of fn 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 Fk be a free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 of finite rank k ≥ 2. Fix a free basis A of Fk and an identification of Fk with the fundamental group
Fundamental group
In mathematics, more specifically algebraic topology, the fundamental group is a group associated to any given pointed topological space that provides a way of determining when two paths, starting and ending at a fixed base point, can be continuously deformed into each other...

 of the rose Rk which is a wedge of k circles corresponding to the basis elements of A.

Let φ ∈  Out(Fk) be an outer automorphism of Fk.

A topological representative of φ is a triple (τ, Γ, f) where:
  • Γ is a finite connected graph with the first betti number
    Betti number
    In algebraic topology, a mathematical discipline, the Betti numbers can be used to distinguish topological spaces. Intuitively, the first Betti number of a space counts the maximum number of cuts that can be made without dividing the space into two pieces....

     k (so that the fundamental group
    Fundamental group
    In mathematics, more specifically algebraic topology, the fundamental group is a group associated to any given pointed topological space that provides a way of determining when two paths, starting and ending at a fixed base point, can be continuously deformed into each other...

     of Γ is free of rank k).
  • τ : Rk → Γ 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 σ : Γ → Rk is a homotopy inverse of τ then the composition
σfτ : Rk → Rk
induces an automorphism of Fk = π1(Rk) 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(Fk) be an outer automorphism of Fk. 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 fn(e) and fn(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 e1,..., em is said to contain turns ei−1, ei+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 Ea and Eb 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 Ea to Eb and that sends the edge Eb to the edge-path EaEb.
Then f is a train track representative of φ.

Irreducible automorphisms

An outer automorphism φ of Fk is said to be reducible if there exists a free product decomposition
where all Hi are nontrivial, where m ≥ 1 and where φ permutes the conjugacy classes of H1,...,Hm in Fk. An outer automorphism φ of Fk is said to be irreducible if it is not reducible.

It is known that φ ∈  Out(Fk) 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(Fk) be irreducible. Then there exists a train track representative of φ.

Sketch of the proof

For a topological representative f:ΓΓ of an automorphism φ of Fk the transition matrix M(f) is an rxr matrix (where r is the number of topological edges of Γ) where the entry mij is the number of times the path f(ej) passes through the edge ei (in either direction). If φ is irreducible, the transition matrix M(f) is irreducible
Irreducible (mathematics)
In mathematics, the concept of irreducibility is used in several ways.* In abstract algebra, irreducible can be an abbreviation for irreducible element; for example an irreducible polynomial....

 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 eignevalue 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 = f1, f2, f3,...

of φ where fn is obtained from fn−1 by several moves, specifically chosen. In this sequence, if fn is not a train track map, then the moves producing fn+1 from fn necessarily involve a sequence of folds followed by a valence-one homotopy, so that the Perron–Frobenius eignevalue of fn+1 is strictly smaller than that of fn. The process is arranged in such a way that Perron–Frobenius eignevalues of the maps fn take values in a discrete substet of . This guarantees that the process terminates in a finite number of steps and the last term fN 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(Fk) 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(Fk) is irreducible and of infinite order then λ(φ) > 1. Moreover, in this case for every free basis X of Fk and for every w ∈ Fk there exists C ≥ 1 such that for all n ≥ 1
where ||u||X is the cyclically reduced length of an element u of Fk with respect to X.


Unlike for elements of mapping class group
Mapping class group
In mathematics, in the sub-field of geometric topology, the mapping class groupis an important algebraic invariant of a topological space. Briefly, the mapping class group is a discrete group of 'symmetries' of the space.-Motivation:...

s, for an irreducible φ ∈ Out(Fk) it is often the case
that
λ(φ) ≠ λ(φ−1).

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
    Free group
    In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

     Fn 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 homeomorphism
    Homeomorphism
    In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...

    s of compact surfaces (with or without boundary) which says that every such homeomorphism
    Homeomorphism
    In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...

     is, up to isotopy, is either reducible, of finite order or pseudo-anosov
    Pseudo-Anosov map
    In mathematics, specifically in topology, a pseudo-Anosov map is a type of a diffeomorphism or homeomorphism of a surface. It is a generalization of a linear Anosov diffeomorphism of the torus...

    .
  • Train tracks are the main tool in Los' algorithm for deciding whether or not two irreducible elements of Out(Fn) are conjugate
    Conjugacy class
    In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...

     in Out(Fn).
  • A theorem of Brinkmann proving that for an automorphism α of Fn 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 Fn 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 Fn the mapping torus group of α satisfies a quadratic isoperimetric inequality
    Dehn function
    In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group in terms of the length of that relation...

    .
  • The proof by Bestvina, Feighn and Handel that the group Out(Fn) satisfies the Tits alternative
    Tits alternative
    In mathematics, the Tits alternative, named for Jacques Tits, is an important theorem about the structure of finitely generated linear groups. It states that every such group is either virtually solvable In mathematics, the Tits alternative, named for Jacques Tits, is an important theorem about...

    .
  • An algorithm that, given an automorphism α of Fn, decides whether or not the fixed subgroup of α is trivial and finds a finite generating set for that fixed subgroup.
  • The proof of algorithmic solvability of the conjugacy problem
    Conjugacy problem
    In abstract algebra, the conjugacy problem for a group G with a given presentation is the decision problem of determining, given two words x and y in G, whether or not they represent conjugate elements of G...

     for free-by-cyclic groups by Bogopolski, Martino, Maslakova, and Ventura.
  • The machinery of train tracks for injective endomorphism
    Endomorphism
    In mathematics, an endomorphism is a morphism from a mathematical object to itself. For example, an endomorphism of a vector space V is a linear map ƒ: V → V, and an endomorphism of a group G is a group homomorphism ƒ: G → G. In general, we can talk about...

    s of free group
    Free group
    In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

    s, generalizing the case of automorphisms, was developed in a 1996 book of Dicks and Ventura.

See also

  • Geometric group theory
    Geometric group theory
    Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act .Another important...

  • Real tree
    Real tree
    A real tree, or an \mathbb R-tree, is a metric space such thatfor any x, y in M there is a unique arc from x to y and this arc is a geodesic segment. Here by an arc from x to y we mean the image in M of a topological embedding f from an interval [a,b] to M such that f=x and f=y...

  • Mapping class group
    Mapping class group
    In mathematics, in the sub-field of geometric topology, the mapping class groupis an important algebraic invariant of a topological space. Briefly, the mapping class group is a discrete group of 'symmetries' of the space.-Motivation:...

  • Free group
    Free group
    In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

  • Out(Fn)
    Out(Fn)
    In mathematics, Out is the outer automorphism group of a free group on n generators. These groups play an important role in geometric group theory.-Outer space:...


Basic references

  • Mladen Bestvina, and Michael Handel, Train tracks and automorphisms of free groups. Annals of Mathematics
    Annals of Mathematics
    The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study. It ranks amongst the most prestigious mathematics journals in the world by criteria such as impact factor.-History:The journal began as The Analyst in 1874 and was...

     (2), vol. 135 (1992), no. 1, pp. 1–51
  • 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. ISBN 0-8218-0564-9
  • Oleg Bogopolski. Introduction to group theory. EMS Textbooks in Mathematics. European Mathematical Society
    European Mathematical Society
    The European Mathematical Society is a European organization dedicated to the development of mathematics in Europe. Its members are different mathematical societies in Europe, academic institutions and individual mathematicians...

    , Zürich, 2008. ISBN 978-3-03719-041-8

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK