Connectivity of the Product Replacement Algorithm Graph of PSL(2,q)
arXiv:0712.1357 · doi:10.1515/JGT.2008.048
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.
12 pages. This article was submitted to the Journal of Group Theory on July 2007 and accepted on December 2007