Connectivity of the Product Replacement Graph of simple groups of bounded Lie rank

Nir Avni*, Shelly Garion

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 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 [M.J. Larsen, R. Pink, Finite subgroups of algebraic groups, preprint, 1998] and does not rely on the classification of finite simple groups.

Original languageEnglish (US)
Pages (from-to)945-960
Number of pages16
JournalJournal of Algebra
Volume320
Issue number2
DOIs
StatePublished - Jul 15 2008

Keywords

  • Product Replacement Algorithm
  • T-systems

ASJC Scopus subject areas

  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Connectivity of the Product Replacement Graph of simple groups of bounded Lie rank'. Together they form a unique fingerprint.

Cite this