Given finite sets of cyclic words {u(1), ..., u(k)} and {nu (1), ..., nu (k)} in a finitely generated free group F and two finite groups A and B of outer automorphisms of F, we produce an algorithm to decide whether t...
详细信息
Given finite sets of cyclic words {u(1), ..., u(k)} and {nu (1), ..., nu (k)} in a finitely generated free group F and two finite groups A and B of outer automorphisms of F, we produce an algorithm to decide whether there is an automorphism which conjugates A to B and takes u(i) to nu (i) for each i. If 4 and B are trivial, this is the classic algorithm due to whitehead. We use this algorithm together with Cohen and Lustig's solution to the conjugacy problem for Dehn twist automorphisms of F to serve the conjugacy problem for outer automorphisms which have a power which is a Dehn twist. This settles the conjugacy problem for all automorphisms of F which have linear growth.
For G the fundamental group of a closed surface, we produce an algorithm which decides whether there is an element of the automorphism group of G which takes one specified finite set of elements to another. The algori...
详细信息
For G the fundamental group of a closed surface, we produce an algorithm which decides whether there is an element of the automorphism group of G which takes one specified finite set of elements to another. The algorithm finds such an automorphism if it exists. The methods are geometric and also apply to surfaces with boundary. (C) 2000 Elsevier Science Ltd. All rights reserved.
We prove that whitehead's algorithm for solving the automorphism problem in a fixed free group F-k has strongly linear time generic-case complexity. This is done by showing that the "hard" part of the al...
详细信息
We prove that whitehead's algorithm for solving the automorphism problem in a fixed free group F-k has strongly linear time generic-case complexity. This is done by showing that the "hard" part of the algorithm terminates in linear time on an exponentially generic set of input pairs. We then apply these results to one-relator groups. We obtain a Mostow-type isomorphism rigidity result for random one-relator groups: If two such groups are isomorphic then their Cayley graphs on the given generating sets are isometric. Although no nontrivial examples were previously known, we prove that one-relator groups are generically complete groups, that is, they have trivial center and trivial outer automorphism group. We also prove that the stabilizers of generic elements of F-k in Aut(F-k) are cyclic groups generated by inner automorphisms and that Aut(F-k)-orbits are uniformly small in the sense of their growth entropy. We further prove that the number I-k(n) of isomorphism types of k-generator one-relator groups with defining relators of length n satisfies c(1)/n (2k - 1)(n) <= I-k(n) <= c(2)/n(2k- 1)(n), where c(1), c(2) are positive constants depending on k but not on n. Thus I-k(n) grows in essentially the same manner as the number of cyclic words of length n.
We prove a new version of the classical peak reduction theorem for automorphisms of free groups in the setting of right-angled Artin groups. We use this peak reduction theorem to prove two important corollaries about ...
详细信息
We prove a new version of the classical peak reduction theorem for automorphisms of free groups in the setting of right-angled Artin groups. We use this peak reduction theorem to prove two important corollaries about the action of the automorphism group of a right-angled Artin group A(Gamma) on the set of k-tuples of conjugacy classes from A(Gamma): orbit membership is decidable, and stabilizers are finitely presentable. Further, we explain procedures for checking orbit membership and building presentations of stabilizers. This improves on a previous result of the author. We overcome a technical difficulty from the previous work by considering infinite generating sets for the automorphism groups. The method also involves a variation on the Hermite normal form for matrices.
Let H be a torsion-free delta-hyperbolic group with respect to a finite generating set S. From the main result in the paper, Theorem 1.2, we deduce the following two corollaries. First, we show that there exists a com...
详细信息
Let H be a torsion-free delta-hyperbolic group with respect to a finite generating set S. From the main result in the paper, Theorem 1.2, we deduce the following two corollaries. First, we show that there exists a computable constant C = C(delta, #S) such that, for any endomorphism phi of H, if phi(h) is conjugate to h for every element h is an element of H of length up to C, then phi is an inner automorphism. Second, we show a mixed (conjugate/non-conjugate) version of the classical whitehead problem for tuples is solvable in torsion-free hyperbolic groups.
暂无评论