THE SYMMETRIES OF OUTER SPACE Martin R. Bridson* and Karen Vogtmann**

ABSTRACT. For n ≥ 3, the natural map Out(F_{n}) → Aut(K_{n}) from the outer automorphism group of the free group of rank n to the group of simplicial automorphisms of the spine of outer space is an isomorphism.

§1. Introduction

If a field F has no non-trivial automorphisms, then the fundamental theorem of projective geometry states that the group of incidence-preserving bijections of the projective space of dimension n over F is precisely P GL(n, F). In the early nineteen seventies Jacques Tits proved a far-reaching generalization of this theorem: under suitable hypotheses, the full group of simplicial automorphisms of the spherical building associated to an algebraic group is equal to the algebraic group — see [T, p.VIII]. Tits’s theorem implies strong rigidity results for lattices in higher-rank — see [M].

There is a well-developed analogy between arithmetic groups on the one hand and mapping class groups and (outer) automorphism groups of free groups on the other. In this analogy, the role played by the symmetric space in the classical setting is played by the Teichmüller space in the case of case of mapping class groups and by Culler and Vogtmann’s outer space in the case of Out(F_{n}). Royden’s Theorem (see [R] and [EK]) states that the full isometry group of the Teichmüller space associated to a compact surface of genus at least two (with the Teichmüller metric) is the mapping class group of the surface. An elegant proof of Royden’s theorem was given recently by N. Ivanov [Iv]. Ivanov’s proof, which illuminates the analogy with rigidity results for lattices, proceeds via the appropriate analogue of Tit’s theorem: for surfaces of genus at least two, the full group of simplicial automorphisms of the complex of curves [H] is the mapping class group.

One may think of the theorems of Ivanov, Royden and Tits, and indeed the fundamental theorem of projective geometry, as saying that the spaces under consideration are accurate geometric models for the groups being studied — the spaces have the correct symmetries and no others. Our purpose in this paper is to show that the standard geometric model for Out(F_{n}) is also accurate in this sense. Thus we shall prove an analogue of Royden’s theorem for the action of Out(F_{n}) on the spine of outer space.

Outer space X_{n} is contractible [CV] and the action of Out(F_{n}) on it is proper but not cocompact. The spine of outer space is an equivariant deformation retract K_{n} ⊂ X_{n} on which Out(F_{n}) acts properly and cocompactly; K_{n} is a simplicial complex and the action of Out(F_{n}) is by simplicial automorphisms. Let Aut(K_{n}) denote the group of simplicial automorphisms of K_{n}.

* Supported by an EPSRC Advanced Fellowship ** Partially supported by NSF grant DMS-9307313 Theorem. For n ≥ 3, the natural map Out(F_{n}) → Aut(K_{n}) is an isomorphism.

The corresponding result is clearly false for n = 2; indeed Aut(K_{2}) is uncountable. Tits’s theorem is a vital ingredient in Mostow’s theorem concerning the finiteness of

outer automorphism groups of lattices in semisimple Lie groups [M], and in the same spirit one can use Ivanov’s theorem to establish the finiteness of outer automorphism groups of mapping class groups. Also in the same spirit, although the above theorem does not lead directly to a proof that Out(Out(F_{n})) is finite, we shall show in a subsequent paper that related ideas can be used to show that in fact this group is trivial (cf. [DF]).

As a direct consequence of our theorem one obtains a fixed point result for actions of lattices on outer space. Let G be a semisimple Lie group with finite centre and no compact factors and suppose the real rank of G is at least two. Let Γ be a non-uniform, irreducible lattice in G. Then every homomorphism from Γ to Out(F_{n}) has finite image — see [BF]. Every finite subgroup of Out(F_{n}) has a fixed point in its action on K_{n} (see [C]). Thus, as a consequence of the above theorem we get:

Corollary 1.1. Let G be a semisimple Lie group with finite centre and no compact factors and suppose the real rank of G is at least two. Let Γ be a non-uniform, irreducible lattice in G. Then every simplicial action of Γ on the spine of outer space has a fixed point.

The analogue of this corollary for actions of lattices on Teichmüller space was proved by Farb and Masur [FM]. In their result one does not need to assume that the lattice is non-uniform; in our setting this assumption is probably just an artifact of the proof.

In the remainder of this introduction we shall outline the proof of the above theorem. It is easy to see that the kernel of Out(F_{n}) → Aut(K_{n}) is trivial; the problem is to show that it is surjective. The complex K_{n} is the geometric realization of a poset of finite marked graphs; the maximal elements in the partial ordering are trivalent and the minimal elements are roses, i.e. graphs with a single vertex. A priori it is not clear that a simplicial automorphism of K_{n} must preserve the partial ordering on the vertices. However the vertices that are neither maximal nor minimal are characterized by the fact that their link can be expressed as a non-trivial join (5.1).

The link of every vertex in K_{n} is homotopic to a wedge of (2n − 4) dimensional spheres. In order to distinguish the maximal vertices (trivalent graphs) from the minimal ones (roses) we calculate the number of spheres in these wedges (sections 3 and 4). As a result of these calculations one can see that any simplicial automorphism f of K_{n} must preserve the poset structure. Further calculation of the Euler characteristic of links then shows that f must preserve the homeomorphism type of marked graphs and from this it follows (after further argument) that if f leaves the star of a rose ρ_{0} invariant then it acts on the star in the same manner as some element of the stabilizer of ρ_{0} in Out(F_{n}). It follows that given any f ∈ Aut(K_{n}), we can compose it with a suitable element of Out(F_{n}) and assume that the composition f′ acts trivially on star(ρ_{0}).

Any two roses in K_{n} can be connected by a sequence of roses that are Nielsen adjacent (see section 2) and we shall prove that because the intersection of the stars of each pair of Nielsen adjacent roses is large, any simplicial automorphism of K_{n} that fixes the star of a rose must also fix the star of all Nielsen adjacent roses (5.7). K_{n} is the union of the stars of roses, therefore we will have shown that f′ is the identity, and hence f ∈ Out(F_{n}).

§2. Background

For the convenience of the reader, we briefly outline here the definition and some properties of the spine K_{n} of outer space.

The spine K_{n} is a simplicial complex. We first describe the vertices of K_{n}, which are called marked graphs of rank n. Fix a standard graph R_{n} with one vertex and n edges. A marked graph of rank n is an equivalence class of pairs (g, Γ), where Γ is a connected graph all of whose vertices are at least trivalent, and g: R_{n} → Γ is a homotopy equivalence; pairs (g, Γ) and (g′, Γ′) are equivalent if there is a homeomorphism h: Γ → Γ′ with h ∘ g ≃ g′. We also assume that Γ has no separating edges.

One may picture (g, Γ) as a labelled graph in the following manner (see Figure 1): fix a basis for F_{n} ≅ π_{1}R_{n}; choose a maximal tree T ⊂ Γ and a base-vertex x ∈ T; each edge e ⊂ Γ − T determines an element ϵ ∈ π_{1}(Γ, x), and one labels e with the reduced word representing g_{∗}^{−1}(ϵ) ∈ F_{n}. One can recover (g, Γ) from this labelled graph, but there are many labelled graphs representing the same marked graph: the labelling depends on the choice of maximal tree and base-vertex as well as the choice of (g, Γ) within its equivalence class.

Figure 1

A set of edges ϕ ⊂ Γ is a forest if the corresponding subgraph of Γ contains no cycles. Given a forest ϕ ⊂ Γ, we define Γ_{ϕ} to be the graph obtained from Γ by collapsing each edge of ϕ to a point. The quotient map q_{ϕ}: Γ → Γ_{ϕ} is called a forest collapse. Marked graphs represented by (g, Γ) and (g′, Γ′) are connected by an edge in K_{n} if there is a forest ϕ ⊂ Γ such that (g′, Γ′) is equivalent to the pair (q_{ϕ} ∘ g, Γ_{ϕ}). Marked graphs γ_{0}, …, γ_{k} span a k-simplex of K_{n} if every pair γ_{i}, γ_{j} is connected by an edge.

A special role is played by roses, which are marked graphs γ = (g, Γ) such that Γ has exactly one vertex, and by Nielsen graphs, which are marked graphs (g, Γ) such that Γ has exactly two vertices, one of which is trivalent with no loops (see Figure 2).

Roses at distance 1 from the same Nielsen graph are called Nielsen adjacent. An edge path in K_{n} passing only through roses and Nielsen graphs is called a Nielsen path.

If we identify F_{n} with π_{1}(R_{n}), an element α ∈ Out(F_{n}) is represented by a unique homotopy class of maps f_{α}: R_{n} → R_{n}. The (right) action of Out(F_{n}) on K_{n} is given by (g, Γ) · α = (g ∘ f_{α}, Γ). (If one portrays (g, Γ) as a labelled graph, then the outer automorphism class of ψ ∈ Aut(F_{n}) sends (g, Γ) to the isomorphic graph in which each label w is replaced by ψ^{−1}(w).) Note that Out(F_{n}) acts transitively on roses.

Figure 2

A Nielsen automorphism of F_{n} is an automorphism given in terms of some basis A = {u_{1}, …, u_{n}} for F_{n} by sending u_{1} ↦ u_{1}u_{2} and fixing all u_{i} with i > 1. This Nielsen automorphism takes the rose whose petals are labelled by the basis A to a Nielsen adjacent rose. Since Nielsen automorphisms together with the stabilizer of a rose generate Out(F_{n}), it follows that any two roses can be joined by a Nielsen path.

Since a simplicial automorphism of K_{n} must take each vertex to another vertex with an isomorphic link, we study the links of vertices with the aim of characterising Out(F_{n})- orbits of vertices by their links. The link of γ = (g, Γ) is the join lk(γ) = lk_{−}(γ) ∗ lk_{+}(γ), where lk_{−}(γ) is the full subcomplex spanned by marked graphs which can be obtained from γ by forest collapse, and lk_{+}(γ) is the full subcomplex spanned by marked graphs which collapse to γ. The complex K_{n} is (2n−3)-dimensional, and it was shown in [V] that K_{n} is Cohen-Macaulay; in particular the link of every vertex is homotopy equivalent to a wedge of spheres of dimension 2n − 4. In the first two sections, we estimate the number of spheres in this wedge if Γ is trivalent (i.e. a maximal element of K_{n}) and if Γ is a rose (a minimal element).

§3. The link of a trivalent marked graph

Let γ = (g, Γ) be a maximal vertex of K_{n}; thus Γ is a connected trivalent graph of rank n (i.e. Euler characteristic 1 − n), with no separating edges. The link of γ in K_{n} can be identified with the geometric realization of the partially ordered set (poset) F (Γ) of all non-empty forests in Γ.

The functions e(Γ), v(Γ), τ(Γ), t(Γ).

For any graph Γ and edge e of Γ, let Γ − e denote the graph obtained from Γ by removing e, and let Γ/e denote the graph obtained by collapsing the edge e to a point. Let v(Γ) denote the number of vertices of Γ, and e(Γ) the number of edges. Following [SV], we define τ(Γ) = ∑_{ϕ}(−1)^{e(ϕ)}, where the sum is over all forests ϕ in Γ, including the empty forest. Thus τ(Γ) = 1 if Γ is a rose, and τ(Γ) = 1 − k if Γ has two vertices with k edges between them. Recall from [SV] the following elementary properties of τ:

(1) For any edge e of Γ which is not a loop, τ(Γ) = τ(Γ − e) − τ(Γ/e).

(2) If Γ is the disjoint union of Γ_{1} and Γ_{2}, then τ(Γ) = τ(Γ_{1})τ(Γ_{2}).

(3) If Γ has a separating edge, then τ(Γ) = 0.

(4) τ(Γ) = χ(|F (Γ)|) − 1, where |F (Γ)| is the geometric realization of F (Γ). Let t(Γ) be the absolute value of τ(Γ). Note that if e is not a loop, then t(Γ) = t(Γ − e) + t(Γ/e).

Definition. A CW-complex is d-spherical if it is d-dimensional and (d−1)-connected. The rank of a d-spherical complex K is the rank of the free abelian group H̃_{d}(K) := H̃_{d}(K; ℤ). Note that if L is a d-spherical subcomplex of a d-spherical complex K, then rank(L) ≤ rank(K).

Lemma 3.1. Let Γ be a finite connected graph. The geometric realization |F (Γ)| of the poset F (Γ) is (v(Γ) − 2)-spherical of rank t(Γ).

Proof. (This is a quantitative version of the proof of Proposition 2.2 in [V].) If e is an edge which is a loop in Γ, then F (Γ) = F (Γ − e), so we may assume Γ has no loops. If Γ has a separating edge e, then ϕ → ϕ ∪ e → {e} is a poset map giving a deformation retraction of |F (Γ)| to the point {e}, so the Lemma is true. In particular, if e(Γ) = v(Γ) − 1, the Lemma is true.

If v(Γ) = 2, then t(Γ) = k −1, where k is the number of edges joining the two vertices, and |F (Γ)| is a discrete set of k points, hence 0-spherical of rank k − 1.

The proof now proceeds by induction on v(Γ) and e(Γ). Fix an edge e of Γ. If e is separating, we are done. If not, the poset map ϕ → ϕ−{e} induces a homotopy equivalence from |F (Γ)−{e}| to |F (Γ−e)|, which is (v(Γ)−2)-spherical of rank t(Γ−e) by induction on e(Γ). The link of {e} in |F (Γ)| is isomorphic to F (Γ/e) via the isomorphism ϕ → ϕ/e, and is therefore (v(Γ) − 3)-spherical of rank t(Γ/e), by induction on v(Γ). The Van Kampen Theorem and Mayer-Vietoris sequence for |F (Γ)| = |F (Γ) − {e}| ∪ st(e) now show that F (Γ) is (v(Γ) − 2)-spherical of rank t(Γ − e) + t(Γ/e) = t(Γ). ⊔ ⊓

We now specialize to the case where Γ is connected and trivalent, and estimate t(Γ) in terms of n. Note that in this case τ(Γ) = χ(|F (Γ)|) − 1 ≤ 0.

Proposition 3.2. Let Γ be a connected trivalent graph of rank n. Then

t(Γ) ≤ 2^{n−1}Π_{i=2}^{n} log_{2}(i).

Proof. The proof is by induction on n. For n = 2 there are two connected trivalent graphs Γ, one with t(Γ) = 0 and one with t(Γ) = 2, so the proposition is true. Now assume that t(Δ) ≤ M_{n−1} := 2^{n−2}Π_{i=2}^{n−1} log_{2}(i) for all connected trivalent graphs Δ of rank n − 1.

Let k = k(Γ) be the length of the shortest edge-cycle in Γ. We will show first that t(Γ) ≤ k · M_{n−1}, and then that k ≤ 2 log_{2}(n), giving the result.

Claim 1. t(Γ) ≤ k · M_{n−1}

Proof. This is shown by induction on k. If k = 1, then Γ has a separating edge, so t(Γ) = 0.

If k = 2, let e be one edge in a cycle of length 2. Then some edge of Γ/e is a loop; after removing this loop and the consequent single bivalent vertex, we obtain a trivalent graph with rank n − 1. Removing a bivalent vertex simply changes the sign of τ, leaving t unchanged. The graph Γ − e has two bivalent vertices; after removing these, this graph too becomes trivalent of rank n − 1. Thus the formula τ(Γ) = τ(Γ − e) − τ(Γ/e) becomes t(Γ) = t(Γ − e) + t(Γ/e) ≤ 2 · M_{n−1}.

Now suppose k ≥ 3. Let e be an edge of a shortest cycle in Γ. The graph Γ/e is equal to Γ′/e′ for a unique graph Γ′ whose shortest edge-cycle has length k − 1 (see Figure 3: collapsing e creates an edge-cycle of length k − 1 in Γ/e; we can then expand Γ/e in exactly one way to a trivalent graph Γ′ without expanding that edge-cycle.)

Note that e′ is separating if and only if removing the closure of e disconnects Γ. If this is the case, replace e by a_{1}. If removing the closure of a_{1} also disconnects Γ, then b is a separating edge of Γ, so that t(Γ) = 0 and the proposition is true. Otherwise, we have that e′ is non-separating in Γ′. The formulas τ(Γ) = τ(Γ − e) − τ(Γ/e) and τ(Γ′) = τ(Γ′ − e′) − τ(Γ′/e′) then combine to give

τ(Γ) = τ(Γ − e) + τ(Γ′) − τ(Γ′ − e′).

After removing the bivalent vertices, Γ′ − e′ is trivalent. Since e′ is non-separating τ(Γ), τ(Γ−e), τ(Γ′) and τ(Γ′ −e′) are all negative, and by induction on k, t(Γ′) ≤ (k−1)·M_{n−1}. Thus the formula above gives

t(Γ) ≤ t(Γ − e) + t(Γ′)
≤ M_{n−1} + (k − 1) · M_{n−1}
= k · M_{n−1}.

Claim 2. k ≤ 2 log_{2}(n)

Proof. Since Γ is trivalent and the shortest cycle in Γ has length k, the maximal trivalent tree T_{k−1} of diameter k − 1 embeds in Γ. If k is even, T_{k−1} has 2 · 2^{\frac{k}{2}} − 2 vertices; if k is odd, T_{k−1} has 3 · 2^{\frac{k−1}{2}} − 2 = \frac{3}{\sqrt{2}} · 2^{\frac{k}{2}} − 2 vertices. In either case, Γ has at least 2 · 2^{\frac{k}{2}} − 2 vertices. Since Γ is trivalent, it has 3v(Γ)/2 edges, and since it has Euler characteristic (1 − n) we have hence v(Γ) = (1 − n) + 3v(Γ)/2, so Γ has exactly 2n − 2 vertices. Thus

2n − 2 ≥ 2 · 2^{\frac{k}{2}} − 2,

giving n ≥ 2^{\frac{k}{2}} , or 2 log_{2}(n) ≥ k. ⊔ ⊓

§4. The link of a rose

In this section we shall calculate the homotopy type of the links of roses in K_{n}. The proof will be given in the language of partitions and ideal edges. The reader unfamiliar with K_{n} is unlikely to see the beautiful geometric picture hidden in this description. We therefore suggest that such readers may wish to look at the pictures on pages 422–428 of [B], which show the link of a rose in K_{3} and its symmetries.

The link of a rose ρ can be identified with a certain partially ordered set of partitions of the oriented edges of the rose. For the convenience of the reader, we briefly review this below (for details, see [CV]).

Definition. Let A be a finite set, and α = (X | A−X) a partition of A into two parts (the parts are unordered, so that (X | A − X) = (A − X | X)). The size of α is the minimum of the orders of the subsets X and A − X. The partition α is said to be thick if it has size at least two. Two partitions (X | A − X) and (Y | A − Y) are compatible if one of the following intersections is empty:

X ∩ Y, X ∩ (A − Y), Y ∩ (A − X), (A − X) ∩ (A − Y)

We form a simplicial complex W (A) with vertices the set of thick partitions of A. A set of k + 1 partitions forms a k-simplex if each pair of partitions in the set is compatible.

Proposition 4.1. Let A = {p_{1}, …, p_{k}} be a set with k elements. Then W = W (A) is (k − 4)-spherical of rank (k − 2)!.

Proof. The proof is by induction on k. If k = 4, W consists of three mutually incompatible partitions, so is 0-spherical of rank 2.

Let α be the partition (X | A − X) with X = {p_{1}, p_{2}}, and let W_{1} be the subcomplex of W spanned by thick partitions of A which are compatible with α. Then W_{1} is a cone with cone point α, so is contractible.

If β is not in W_{1}, then β can be written as (X_{β} | A−X_{β}), with p_{1} ∈ X_{β} and p_{2} ∈ A−X_{β}. We add vertices of W to W_{1} in order of decreasing size of the sets X_{β}, as follows:

Let W_{i} be the subcomplex of W spanned by W_{1} and {β | β ∉ W_{1} and |X_{β}| ≥ k − i}. We have W_{1} ⊂ W_{2} ⊂ … ⊂ W_{k−3} ⊂ W_{k−2} = W.

Claim. W_{i−1} is a deformation retract of W_{i} for 1 ≤ i ≤ k − 3.

Proof. If β ∉ W_{1} and |X_{β}| ≥ 3, we can define a new thick partition p(β) = (X_{β} − p_{1} | A − (X_{β} − p_{1})) by “pushing β off p_{1}”. If β ∈ W_{i} − W_{i−1}, the intersection of the link of β with W_{i−1} is a cone on p(β), so is contractible. Since no two vertices of W_{i} − W_{i−1} are compatible, this shows W_{i} collapses onto W_{i−1}.

The only vertices of W not in W_{k−3} are the k−2 partitions β of the form X_{β} = {p_{1}, p_{j}} with j ≥ 3. Since p_{1} and p_{j} are always on the same side of any partition compatible with β, the map that sends p_{1} and p_{j} to a single point p̄ gives a natural isomorphism from the intersection of W_{k−3} with the link of β to the complex W ({p̄, p_{2}, …, p̂_{j}, …, p_{k}}). By induction, this is (k − 1)-spherical of rank (k − 3)!. Since W_{k−3} is contractible, the Van Kampen and Mayer Vietoris theorems apply to give the result. ⊔ ⊓ Ideal edges.

A rose ρ = (g, R) is determined by a basis B = {a_{1}, …, a_{n}} of F_{n}, up to permutation and inversion of the basis elements. We identify the set of oriented edges of R with the set B ∪ B^{−1}, which we denote E(ρ). Recall from [CV] that a thick partition (X | E(ρ) − X) of E(ρ) is called an ideal edge of ρ if the partition separates some a_{i} from its inverse.

The link of ρ can be identified with the barycentric subdivision of the subcomplex of W (E(ρ)) spanned by the ideal edges. To see this, note that a marked graph γ = (g, Γ) is in the link of ρ if and only if there is a maximal tree T in Γ with the oriented edges of Γ−T labeled by the elements of E(ρ). To each edge e of T, we associate a partition of E(ρ): two elements of E(ρ) are in the same subset of the partition if the corresponding oriented edges of Γ terminate in the same component of T − e. The set of partitions obtained from edges of T are pairwise compatible. They are thick since Γ has no univalent or bivalent vertices, and are “ideal” since Γ has no separating edges.

The marked graph (g, Γ) can be reconstructed from the associated set of ideal edges of E(ρ). For example, the ideal edge α = (X | E(ρ)−X) corresponds to the graph Γ(α) which has two vertices joined by an unlabelled edge, has oriented edges labelled by elements of X terminating at one vertex, and oriented edges labelled by elements of E(ρ)−X terminating at the other vertex (see Figure 4). An ideal edge α has size 2 if and only if the graph Γ(α) is a Nielsen graph in the link of ρ.

Figure 4

Let Γ(α_{1}, …, α_{k}) denote the marked graph in the link of ρ determined by a set {α_{1}, …, α_{k}} of pairwise compatible ideal edges of ρ. If α_{i} = (X_{i} | E(ρ) − X_{i}), it will be sometimes convenient to replace the notation Γ(α_{1}, …, α_{k}) by Γ_{ρ}(X_{1}, …, X_{k}). If α and β are compatible ideal edges, note that Γ(α) and Γ(β) have distance 2 in the link of ρ, since they are joined by the path Γ(α) → Γ(α, β) → Γ(β) (i.e. they have distance 1 in the complex W (E(ρ)).)

Motivated by the above description of the link of a rose, we now consider finite sets A where some of the elements are paired. Define a thick partitition α = (X | A − X) to be ideal if neither X nor A−X is a union of pairs, and let W_{π}(A) be the subcomplex of W (A) spanned by ideal partitions. By Theorem 3.1 of [V], W_{π}(A) is always (|A| − 4)-spherical. Since lk(ρ) can be identified with the barycentric subdivision of W_{π}(E(ρ)), where each edge in E(ρ) is paired with its inverse, we are particularly interested in sets of the form A_{2k} = {p_{1}, p_{1}^{−1}, …, p_{k}, p_{k}^{−1}}, where all elements are paired. To help with the induction, we also consider sets A_{2k−1} = {p_{1}, p_{2}, p_{2}^{−1}, …, p_{k}, p_{k}^{−1}}, where all but one of the elements are paired.

Proposition 4.2. For n = 2k or n = 2k − 1, W_{π}(A_{n}) is (n − 4)-spherical of rank at least (2k − 3) · rank(W_{π}(A_{n−1})).

Proof. The fact that W_{π}(A_{n}) is (n − 4)- spherical is proved in [V]. It remains to prove the rank statement.

Let α = (X | A_{n} − X), with X = {p_{1}, p_{2}}. Exactly as in the proof of Proposition 4.1, we see that the subcomplex W_{n−3} of W_{π}(A) spanned by ideal partitions β which are either compatible with α or “pushable” off p_{1} is contractible.

Ideal partitions of the form β = (X_{β}, A_{n} − X_{β}) with X_{β} = {p_{1}, p_{2}^{−1}} or X_{β} = {p_{1}, p_{i}^{±1}}, i ≥ 3 are not in W_{n−3}. The intersection of the link of any such β with W_{n−3} is (n−5)-spherical by [V], and contains W_{π}(A_{n−1}) as an (n−5)-spherical subcomplex. Therefore, for both n = 2k and n = 2k − 1 the subcomplex V of W_{π}(A_{n}) spanned by W_{n−3} and these 2n−3 vertices β is (n−4)-spherical of rank at least (2k −3)·rank(W_{π}(A_{n−1})). Since W_{π}(A_{n}) is itself (n − 4)-spherical, we have rank(W_{π}(A_{n})) ≥ (2k − 3) · rank(W_{π}(A_{n−1})).⊔ ⊓

Corollary 4.3. For n ≥ 2, the link of a rose is (2n − 4)-spherical of rank at least Π_{k=1}^{n−1}(2k − 1)^{2}. The inequality is strict for n ≥ 3.

Proof. The link of a rose is the barycentric subdivision of W_{π}(E(ρ)) with the natural pairing of each edge with its inverse. If n = 2, W_{π}(E(ρ)) consists of exactly two points, so has rank 1. The corollary is now immediate from Proposition 4.2. ⊔ ⊓

§5. Simplicial automorphisms of K_{n}

The following proposition shows that a simplicial automorphism cannot take a rose or trivalent graph to a vertex of K_{n} of any other type.

We emphasize that in the following discussion, as elsewhere, distance (hence diameter etc.) is combinatorial distance in the 1-skeleton of the complex under consideration.

Proposition 5.1. Let γ = (g, Γ) be a vertex of K_{n}. If Γ is not a rose or a trivalent graph, then lk(γ) has diameter 2. If Γ is a rose or a trivalent graph, lk(γ) has diameter > 2.

Proof. In general, lk(γ) is the join of the “lower link” lk_{−}(γ), consisting of marked graphs which can be obtained from γ by a forest collapse, and the “upper link” lk_{+}(γ), consisting of marked graphs which collapse to γ. If Γ is neither trivalent nor a rose, then both lk_{−}(γ) and lk_{+}(γ) are non-empty, so the join lk_{−}(γ) ∗ lk_{+}(γ) has diameter 2.

If Γ is a rose we have seen that lk(γ) = lk_{+}(γ) can be identified with the geometric realization of the poset of sets of pairwise-compatible ideal edges in γ. If α is an ideal edge of γ, the graphs at distance 1 from Γ(α) are all of the form Γ(α_{1}, …, α_{k}), with α_{1} = α and α_{i} compatible with α for i > 1. Therefore, if α and β are ideal edges of γ which are not compatible, the graphs Γ(α) and Γ(β) have distance greater than 2 in the link.

If Γ is trivalent, we have seen that lk(γ) = lk_{−}(γ) can be identified with the geometric realization of the poset of forests in Γ. Let T be a maximal tree in Γ, and e an edge of Γ which is not a loop and is not in T (such an edge exists because Γ has no separating edges). Then d(e, T) > 2, since there is no forest which is both contained in T and contains e.

⊔ ⊓

Corollary 5.2. Every simplicial automorphism of K_{n} takes roses to roses.

Proof. By Proposition 5.1, a rose must be sent either to another rose or to a trivalent graph. By Propositions 3.2 and 4.3, the link of a rose is not homotopy equivalent to the link of any trivalent graph for all n ≥ 4, since (2n − 3)! > 2^{n−1}Π_{k=2}^{n} log_{2}(k). The link of a rose is not isomorphic to the link of any trivalent graph by inspection if n < 4. (For n = 2 this is trivial. For n = 3 one can see, for example, that roses have 72 neighbouring vertices whereas trivalent graphs have at most 16 neighbours.) ⊔ ⊓

Proposition 5.3. Every simplicial automorphism of K_{n} preserves the poset order on the 0-skeleton. In particular, simplicial automorphisms preserve the number of vertices in a marked graph.

Proof. There is one rose in the star of γ = (g, Γ) for each maximal tree in Γ. Suppose γ is obtained from γ′ = (Γ′, g′) by collapsing an edge e. Then the roses in the link of γ correspond to maximal trees of Γ′ which contain e. Since e is not separating, there is a maximal tree of Γ′ which does not contain e; this corresponds to a rose in the link of γ′ that is not in the link of γ. This shows that for any γ < η, the link of η contains more roses than the link of γ; since a simplicial automorphism sends roses to roses by Corollary 5.2, it must therefore preserve the partial ordering. The fact that the number of vertices in Γ is preserved follows since a maximal chain must be sent to a maximal chain, and every marked graph can be put in a maximal chain. ⊔ ⊓

Proposition 5.4. Every simplicial automorphism of K_{n} preserves the homeomorphism type of two-vertex graphs.

Proof. Let γ = (g, Γ) have two vertices v and w with r edges between them, s loops at v and t = n − r − s + 1 loops at w. Then there are r roses in the link of γ, so a simplicial automorphism must take γ to another marked graph with the same value of r. We now fix r and count the number of three-vertex graphs in the link of γ. We do this by choosing a rose ρ in the link of γ and writing γ = Γ(α) for an ideal edge α = (X | E(ρ) − X); we then count the number of ideal edges compatible with α. Any ideal edge compatible with α can be written (Y | E(ρ) − Y), with either Y ⊂ X or Y ⊂ E(ρ) − X. Interchanging X and E(ρ) − X if necessary, we may assume X has 2s + r − 1 elements. We count the number of subsets Y of X which give ideal edges to get

[2^{2s+r−1} − 2 − (2s + r − 1)] − (2^{s} − 1)

ideal edges. Adding the number of allowable subsets Y of E(ρ) − X gives

\begin{aligned}h(r, s, t) & = 2^{2s+r−1} + 2^{2t+r−1} − 2^{s} − 2^{t} − 2r + −2s + −2t − 4 \\ & = 2^{r−1}(2^{2s} + 2^{2t}) − (2^{s} + 2^{t}) − 2n − 2. \end{aligned}

Since r is fixed, s+t = n+1−r is constant, so 2^{n+r−1} = 2^{s}2^{t} = C is constant. Set u = 2^{s}, so 2^{t} = C/u. Writing h as a function of u, we get

h(u) = 2^{r−1}(u^{2} + (C/u)^{2}) − (u + C/u) − 2n − 2.

The function h(u) has a local minimum at u = 2^{\frac{n+r−1}{2}} and no other positive real critical points. Since 2^{s} is positive for all s, this shows that h is monotone decreasing as a function of s, for s ≤ \frac{n+r−1}{2}. In particular, different values of s give different values of h, for s ≤ \frac{n+r−1}{2}, so that non-homeomorphic graphs with a fixed value for r contain different numbers of trivalent graphs in their links. ⊔ ⊓

Stabilizers.

In the proofs that follow we shall need to understand the stabilizers in Out(F_{n}) of certain marked graphs (g, Γ) ∈ K_{n}. In each case the description that we shall give is an easy consequence of the fact that this stabilizer is precisely the full automorphism group of the graph Γ. (This follows easily from [C] and the description of the action that we gave in section 1.)

Lemma 5.5. If a simplicial automorphism f of the link of a rose ρ fixes all Nielsen graphs in the link, then f fixes the entire link.

Proof. Any ideal edge α of ρ is determined by the set of size two ideal edges of ρ with which it is compatible, i.e. the set of Nielsen graphs at distance two from Γ(α) in lk(ρ). If all Nielsen graphs are fixed by f, then Γ(α) must also be fixed by f. An arbitrary graph Γ(α_{1}, …, α_{k}) in the link of ρ is the unique graph at distance 1 from all Γ(α_{i}), so must also be fixed by f. ⊔ ⊓

Proposition 5.6. If a simplicial automorphism f of K_{n} fixes a rose ρ, then the composition of f with some element of stab(ρ) ⊂ Out(F_{n}) fixes the entire star of ρ.

Proof. Let G_{0} be the stabilizer of ρ under the action of Out(F_{n}), and let E(ρ) = {a_{1}, a_{1}^{−1}, …, a_{n}, a_{n}^{−1}}. Then G_{0} ≅ (ℤ/2)^{n}⋊S_{n} is a wreath product: (ℤ/2)^{n} is generated by the n “flips” interchanging a_{i} and a_{i}^{−1}, and the symmetric group S_{n} permutes these flips.

The group G_{0} acts transitively on Nielsen graphs in the link of ρ, so we may assume f fixes Γ_{ρ}({a_{1}, a_{2}}). (Here we use the alternate notation Γ_{ρ}({a_{1}, a_{2}}) = Γ(α) for α = ({a_{1}, a_{2}}|{E(ρ) − {a_{1}, a_{2}})).

The graph Γ′ = Γ_{ρ}({a_{1}, a_{2}}, {a_{1}^{−1}, a_{2}^{−1}}) (see Figure 5) is the only 3-vertex graph in the link of ρ which is at distance 1 from Γ_{ρ}({a_{1}, a_{2}}), connects Γ_{ρ}({a_{1}, a_{2}}) to another Nielsen graph in the link of ρ, and has only five roses in its link. (The marked graphs of the form Γ_{ρ}({a_{1}, a_{2}}, {a_{i}^{±1}, a_{2}^{−1}}) or Γ_{ρ}({a_{1}, a_{2}}, {a_{1}^{−1}, a_{j}^{±1}}) have six roses in their link, while those of the form Γ_{ρ}({a_{1}, a_{2}}, {a_{i}^{±1}, a_{j}^{±1}}) have eight.) Therefore Γ′ must be fixed by f, which implies in turn that Γ_{ρ}({a_{1}^{−1}, a_{2}^{−1}}) must be fixed by f, because it is the only Nielsen graph in st(ρ) other than Γ_{ρ}({a_{1}, a_{2}}) that is adjacent to Γ′.

The graphs Γ_{ρ}({a_{1}, a_{2}^{−1}}) and Γ_{ρ}({a_{1}^{−1}, a_{2}}) are the only Nielsen graphs in the link of ρ which are at distance more than 2 from both Γ_{ρ}({a_{1}, a_{2}}) and Γ_{ρ}({a_{1}^{−1}, a_{2}^{−1}}), since distance 2 is equivalent to compatibility of the corresponding ideal edges. The automorphism interchanging a_{1} and a_{2} fixes ρ, Γ_{ρ}({a_{1}, a_{2}}) (and Γ_{ρ}({a_{1}^{−1}, a_{2}^{−1}})), and interchanges Γ_{ρ}({a_{1}, a_{2}^{−1}}) and Γ_{ρ}({a_{1}^{−1}, a_{2}}); so we may assume f fixes both of these last two vertices.

Let G_{1} be the intersection of G_{0} with the stabilizers of Γ_{ρ}({a_{1}, a_{2}}) and Γ_{ρ}({a_{1}, a_{2}^{−1}}). Then G_{1} ≅ (Z_{2})^{n−2}⋊S_{n−2} is a wreath product: (Z_{2})^{n−2} is generated by the (n−2) “flips” interchanging a_{i} and a_{i}^{−1}, where i = 3, …, n, and the symmetric group permutes these flips. Note that G_{1} acts transitively on graphs of the form Γ_{ρ}({a_{2}, a_{j}^{±1}}), with j ≥ 3. Therefore we may assume f fixes Γ_{ρ}({a_{2}, a_{3}}), and hence Γ_{ρ}({a_{2}^{−1}, a_{3}^{−1}}).

The graph Γ_{ρ}({a_{2}, a_{3}^{−1}}) is the only Nielsen graph in the star of ρ which is at distance more than 2 from Γ_{ρ}({a_{1}, a_{2}}), Γ_{ρ}({a_{1}^{−1}, a_{2}}) and Γ_{ρ}({a_{2}^{−1}, a_{3}^{−1}}), so must be fixed by f; consequently, Γ_{ρ}({a_{2}^{−1}, a_{3}}) must also be fixed by f.

Continuing in this manner, we may assume f fixes Γ_{ρ}({a_{i}^{±1}, a_{i+1}^{±1}}) for all 1 ≤ i ≤ n−1. Now for any a = a_{i}^{±1} and b = a_{j}^{±1} with i < j, Γ_{ρ}({a, b}) is the only graph at distance more than 2 from all of Γ_{ρ}({a, a_{i+1}}), Γ_{ρ}({a, a_{i+1}^{−1}}), Γ_{ρ}({a_{j−1}, b}) and Γ_{ρ}({a_{j−1}^{−1}, b}), so must be fixed by f. Thus we may assume that f fixes all Nielsen graphs in the link of ρ. By Lemma 5.5, this implies that f fixes the entire star of ρ. ⊔ ⊓ Proposition 5.7. Let f be a simplicial automorphism of K_{n} which fixes the star of a rose ρ. Then f is the identity on K_{n}.

Proof. Since K_{n} is the union of the stars of roses, and every rose is connected to ρ by a Nielsen path, it suffices to show that f fixes the star of any rose ρ′ which is Nielsen adjacent to ρ.

Let ρ′ be Nielsen adjacent to ρ, and let γ be the Nielsen graph at distance 1 from both ρ and ρ′. The link of γ contains exactly three roses, ρ, ρ′ and ρ′′ , so a simplicial automorphism fixing ρ must either fix ρ′ and ρ′′ or interchange them. If E(ρ) = {a, ā, b, b̄, X}, with γ = Γ_{ρ}({a, b}), then E(ρ′) = {a, ā, ab̄, bā, X} and E(ρ′′) = {b, b̄, ab̄, bā, X} (see Figure 6).

Figure 6

The graph Γ_{1} = Γ_{ρ}({a, b}, {a, ā, b}) in the star of ρ has only two graphs in its link homeomorphic to Γ_{ρ}({a, ā, b}); since Γ_{ρ}({a, ā, b}) is fixed by f, the other one, which is Γ_{2} = Γ_{ρ′}({a, ā, bā}), must also be fixed by f. The graph Γ_{2} is in the link of ρ′ but is not in the link of ρ′′, showing that f cannot interchange ρ′ and ρ′′.

Since f fixes the star of ρ, it must fix st_{+}(γ) = st(ρ) ∩ st(ρ′).

Note that Γ_{ρ}({a, b}) = Γ_{ρ′}({ā, bā}). If an ideal edge β = (X_{β} | E(ρ′) − X_{β}) of E(ρ′) is compatible with ({ā, bā}|E(ρ′)−{ā, bā}), then f fixes ρ′, Γ_{ρ′}({ā, bā}) and Γ_{ρ′}({ā, bā}, X_{β}) ∈ st_{+}(γ), so must fix Γ_{ρ′}(X_{β}), since that is the only other 2-vertex graph in lk(ρ′) adjacent to Γ_{ρ′}({ā, bā}, X_{β}). The graphs Γ_{ρ′}({a, bā}) and Γ_{ρ′}({ā, ab̄}) are the only graphs which are at distance more than 2 in lk(ρ′) from both Γ_{ρ′}({ā, bā}) and Γ_{ρ′}({a, ab̄}), so f must either fix or interchange them. But Γ_{ρ′}({a, bā}) has distance 2 from Γ_{2} = Γ_{ρ′}({a, ā, bā}), which is fixed by f, as we saw above, while Γ_{ρ′}({ā, ab̄}) has distance greater than 2 from Γ_{2}. Therefore Γ_{ρ′}({a, bā}) and Γ_{ρ′}({ā, ab̄}) must both be fixed by f. We now proceed as in the proof of Proposition 5.6 to conclude that every Nielsen graph Γ_{ρ′}(X) is fixed by f, and therefore by Lemma 5.5, the entire star of ρ′ is fixed by f. ⊔ ⊓

Theorem 5.8. Every simplicial automorphism f of K_{n} is given by the action of an element of Out(F_{n}).

Proof. By Corollary 5.2, f sends the standard rose ρ_{0} to another rose ρ. There is an outer automorphism ϕ_{0} of F_{n} taking ρ back to ρ_{0}, so that ϕ_{0} ∘ f fixes ρ_{0}. By Proposition 5.6, we can choose ϕ_{1} in the stabilizer of ρ_{0} so that ϕ_{1} ∘ ϕ_{0} ∘ f fixes st(ρ_{0}). By Proposition 5.7, ϕ_{1} ∘ ϕ_{0} ∘ f is the identity on K_{n}, i.e. f = ϕ_{0}^{−1} ∘ ϕ_{1}^{−1}. ⊔ ⊓

REFERENCES

[B] M.R. Bridson, Geodesics and curvature in metric simplicial complexes, Group Theory From a Geometrical Viewpoint (E. Ghys, A. Haefliger, A. Verjovsky, ed.), World Scientific, Singapore, 1991, 373–463.

[BF] M.R. Bridson and B. Farb, A remark about actions of lattices on free groups, J. Topol. Appl., to appear.

[C] M. Culler, Finite groups of automorphisms of free groups, in Contributions to Group Theory, Contemp. Math., 33 (1984), 197–207. Amer. Math. Soc., Providence RI.

[CV] M. Culler and K. Vogtmann, Moduli of graphs and automorphisms of free groups, Invent. Math. 84 (1986), 91–119

[DF] J. Dyer and E. Formanek, The automorphism group of a free group is complete, J. London Math. Soc. 11 (1975), 181–190.

[EK] C. Earle and I. Kra, On isometries between Teichmüller spaces, Duke Math. J., 41 (1974), 583–591.

[FM] B. Farb and H. Masur, Superrigidity and mapping class groups, Topology, to appear

[H] W.J. Harvey, Geometric structure of surface mapping class groups, in “Homological methods in group theory” (C.T.C. Wall, ed.), LMS Lecture Notes, vol. 36, pp. 255– 269, Camb. Univ. Press, 1979.

[Iv] Ivanov, N. V., Automorphisms of complexes of curves and of Teichmüller spaces, Internat. Math. Res. Notices 1997, no. 14, pp 651–666.

[K] K. Korkmaz, Complexes of curves and mapping class groups, Ph.D. Thesis, Michigan State U., 1996

[M] G.D. Mostow, Strong rigidity of locally symmetric spaces, Annals of math. studies, vol. 78, Princeton Univ. Press, Princeton NJ, 1973.

[R] H.L. Royden, Automorphisms and isometries of Teichmüller spaces, in “Advances in the theory of Riemann surfaces” (L. Ahlfors, L. Bers, H. Farkas, R. Gunning, I. Kra, H. Rauch, eds.), Annals of math. studies, vol. 66, Princeton Univ. Press, Princeton NJ, 1971.

[SV] J. Smillie and K. Vogtmann, A generating function for the Euler characteristic of Out(F_{n}), Proceedings of the Northwestern conference on cohomology of groups (Evanston, Ill., 1985). J. Pure Appl. Algebra 44 (1987), no. 1-3, 329–348.

[T] J. Tits, Buildings of spherical type and finite BN- pairs, Lecture notes in math., vol. 386, Springer-Verlag, Berlin- Heidelberg- New York, 1974.

[V] K. Vogtmann, Local structure of some Out(F_{n})-complexes, Proc. Edinburgh Math. Soc. (2) 33 (1990), no. 3, 367–379.

MRB: Mathematical Institute, 24-29 St Giles’, Oxford OX1 3LB, bridson@maths.ox.ac.uk

KV: Mathematics Department, 555 Malott Hall, Cornell University, Ithaca, NY 14850, vogtmann@math.cornell.edu