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

DOI10.1515/JGT.2008.048MaRDI QIDQ3544293zbMATH OpenOpenAlexFDO

Authors Shelly Garion

Publication date 5 December 2008

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

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)

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.

Recommendations

• Connectivity of the product replacement graph of simple groups of bounded Lie rank.
• Strong bias of group generators: an obstacle to the “product replacement algorithm”
• What do we know about the product replacement algorithm?
• Expansion of product replacement graphs
• The product replacement algorithm and Kazhdan's property (T)

Cites work

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

Cited in

(5)

• 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
• Connectivity of the product replacement graph of simple groups of bounded Lie rank.
• 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)