Connectivity of the Product Replacement Graph of Simple Groups of Bounded Lie Rank

Abstract

The Product Replacement Algorithm is a practical algorithm for generating random elements of a finite group. The algorithm can be described as a random walk on a graph whose vertices are the generating k-tuples of the group (for a fixed integer k). We show that there is a function c(r) such that for any finite simple group of Lie type, with Lie rank r, the product replacement graph of the generating k-tuples is connected for any k > c(r). The proof uses results of Larsen and Pink and does not rely on the classification of finite simple groups.

arXiv commentv2 Minor changes, some explanations added

References in corpus (2)

• Commutator maps, measure preservation, and T-systems
• Connectivity of the Product Replacement Algorithm Graph of PSL(2,q)

Cited by in corpus (2)

• Dynamics of Aut(Fn) Actions on Group Presentations and Representations
• A Zero-One Law for Random Subgroups of some Totally Disconnected Groups