On the genericity of Whitehead minimality

DOI10.1515/JGTH-2015-0030zbMATH Open1402.20041arXiv1312.4510OpenAlexW1488336908MaRDI QIDQ905405FDOQ905405

Authors: Frédérique Bassino, Cyril Nicaud, Pascal Weil 

Publication date: 19 January 2016

Published in: Journal of Group Theory (Search for Journal in Brave)

Abstract: We show that a finitely generated subgroup of a free group, chosen uniformly at random, is strictly Whitehead minimal with overwhelming probability. Whitehead minimality is one of the key elements of the solution of the orbit problem in free groups. The proofs strongly rely on combinatorial tools, notably those of analytic combinatorics. The result we prove actually depends implicitly on the choice of a distribution on finitely generated subgroups, and we establish it for the two distributions which appear in the literature on random subgroups.

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

Recommendations

• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Average-case complexity of the Whitehead problem for free groups
• Heuristics for the Whitehead Minimization Problem
• Generic properties of random subgroups of a free group for general distributions.

zbMATH Keywords

free groupgenericityWhitehead minimality

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Automorphisms of infinite groups (20E36) Generators, relations, and presentations of groups (20F05) Subgroup theorems; subgroup growth (20E07) Probabilistic methods in group theory (20P05)

Cited In (10)

• A list of applications of Stallings automata
• Counting words of minimum length in an automorphic orbit.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• A hybrid search algorithm for the Whitehead minimization problem.
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• Heuristics for the Whitehead Minimization Problem
• Generic properties of subgroups of free groups and finite presentations
• Growing words in the free group on two generators.
• Artificial Intelligence and Symbolic Computation
• Title not available (Why is that?)

This page was built for publication: On the genericity of Whitehead minimality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905405)