Connectivity of the product replacement algorithm graph of PSL(2, q)

DOI10.1515/JGT.2008.048zbMATH Open1162.20047arXiv0712.1357OpenAlexW2143349668MaRDI QIDQ3544293FDOQ3544293

Shelly Garion

Publication date: 5 December 2008

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

Abstract: The product replacement algorithm is a practical algorithm to construct random elements of a finite group G. It can be described as a random walk on a graph whose vertices are the generating k-tuples of G (for a fixed k). We show that if G is PSL(2,q) or PGL(2,q), where q is a prime power, then this graph is connected for any k>=4. This generalizes former results obtained by Gilman and Evans.

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

zbMATH Keywords

finite simple groups of Lie typerandom walksrandom elementsproduct replacement algorithmrandom generators

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Sums of independent random variables; random walks (60G50) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Generators, relations, and presentations of groups (20F05) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Linear algebraic groups over finite fields (20G40) Probabilistic methods in group theory (20P05)

Cites Work

• The product replacement algorithm and Kazhdan's property (T)
• Probabilistic generation of finite simple groups
• On the maximal subgroups of the finite classical groups
• Generating random elements of a finite group
• On the maximal size of independent generating sets of \(\text{PSL}_2(q)\)
• Finite Quotients of the Automorphism Group of a Free Group
• T-systems of certain finite simple groups
• Two-generator groups. I
• On T-systems of groups
• Zwei Klassen charakteristischer Untergruppen und ihre Faktorgruppen
• Expansion of product replacement graphs
• On a question of B. H. Neumann

Cited In (4)

• Application of character estimates to the number of \(\mathrm{T}_2\)-systems of the alternating group
• New Upper Bounds On The Spreads of the Sporadic Simple Groups
• A zero-one law for random subgroups of some totally disconnected groups
• Nonabelian level structures, Nielsen equivalence, and Markoff triples

This page was built for publication: Connectivity of the product replacement algorithm graph of PSL(2, q)

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