Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.

DOI10.2140/PJM.2006.223.113zbMath1149.20028arXivmath/0303386OpenAlexW2054631814MaRDI QIDQ868743

Ilya Kapovich, Vladimir Shpilrain, Paul E. Schupp

Publication date: 26 February 2007

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0303386

zbMATH Keywords

one-relator groups Whitehead algorithm generic-case complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Generators, relations, and presentations of groups (20F05) Automorphisms of infinite groups (20E36) Complexity of computation (including implicit computational complexity) (03D15) Fundamental group, presentations, free differential calculus (57M05) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Probabilistic methods in group theory (20P05)

Related Items (38)

Average-case complexity of the Whitehead problem for free groups ⋮ Randomness and complexity in matrix groups ⋮ Random equations in free groups ⋮ Some metric properties of automorphisms of groups. ⋮ A tighter bound for the number of words of minimum length in an automorphic orbit. ⋮ Følner functions and the generic word problem for finitely generated amenable groups ⋮ Primitivity rank for random elements in free groups ⋮ The subadditive ergodic theorem and generic stretching factors for free group automorphisms. ⋮ Virtual geometricity is rare ⋮ Partial word and equality problems and Banach densities ⋮ Primitive and almost primitive elements of Schreier varieties ⋮ On the asymptotics of visible elements and homogeneous equations in surface groups. ⋮ Short, Highly Imprimitive Words Yield Hyperbolic One-Relator Groups ⋮ Counting and boundary limit theorems for representations of Gromov‐hyperbolic groups ⋮ ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM ⋮ Almost all one-relator groups with at least three generators are residually finite. ⋮ Conformal dimension and random groups. ⋮ Random groups arising as graph products. ⋮ On an algorithm to decide whether a free group is a free factor of another ⋮ Random equations in nilpotent groups. ⋮ Subnormal subgroups in free groups, their growth and cogrowth ⋮ The primitivity index function for a free group, and untangling closed curves on hyperbolic surfaces.With the appendix by Khalid Bou–Rabee ⋮ Root extraction in one-relator groups and slenderness ⋮ GENERICITY OF FILLING ELEMENTS ⋮ A hybrid search algorithm for the Whitehead minimization problem. ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ Statistical properties of subgroups of free groups ⋮ Counting words of minimum length in an automorphic orbit. ⋮ On mathematical contributions of Paul E. Schupp ⋮ Sublinear time algorithms in the theory of groups and semigroups. ⋮ Exponentially generic subsets of groups ⋮ Search and witness problems in group theory ⋮ Every group is the outer automorphism group of an HNN-extension of a fixed triangle group ⋮ Non-∀-homogeneity in free groups ⋮ Immersed cycles and the JSJ decomposition ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ Random subgroups, automorphisms, splittings ⋮ Primitivity index bounds in free groups, and the second Chebyshev function

This page was built for publication: Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.