Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups
| dc.creator | Kapovich, Ilya | |
| dc.creator | Schupp, Paul | |
| dc.creator | Shpilrain, Vladimir | |
| dc.date | 2003-03-31 | |
| dc.date | 2004-08-27 | |
| dc.date.accessioned | 2026-07-07T04:56:31Z | |
| dc.date.available | 2026-07-07T04:56:31Z | |
| dc.description | 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 \emph{given generating sets} are isometric. Although no nontrivial examples were previously known, we prove that one-relator groups are generically \emph{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 \emph{isomorphism types} of $k$-generator one-relator groups with defining relators of length $n$ satisfies \[ \frac{c_1}{n} (2k-1)^n \le I_k(n)\le \frac{c_2}{n} (2k-1)^n, \] where $c_1=c_1(k)>0, c_2=c_2(k)>0$ are some constants independent of $n$. Thus $I_k(n)$ grows in essentially the same manner as the number of cyclic words of length $n$. | |
| dc.description | final revised version, to appear in Pacific J. Math | |
| dc.identifier | https://arxiv.org/abs/math/0303386 | |
| dc.identifier | http://arxiv.org/abs/math/0303386 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/66947 | |
| dc.subject | Group Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | Geometric Topology | |
| dc.subject | 20F36 | |
| dc.title | Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups | |
| dc.type | text |