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 journalArticle

2 Citations (Scopus)

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

Fingerprint

Simple group
Replacement
Connectivity
Finite Simple Group
Graph in graph theory
Groups of Lie Type
Random Element
Algebraic Groups
Random walk
Finite Group
Subgroup

Keywords

  • Product Replacement Algorithm
  • T-systems

ASJC Scopus subject areas

  • Algebra and Number Theory

Cite this

@article{ed7aea83b3524512bcfcca148ae013bc,
title = "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 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.",
keywords = "Product Replacement Algorithm, T-systems",
author = "Nir Avni and Shelly Garion",
year = "2008",
month = "7",
day = "15",
doi = "10.1016/j.jalgebra.2008.03.005",
language = "English (US)",
volume = "320",
pages = "945--960",
journal = "Journal of Algebra",
issn = "0021-8693",
publisher = "Academic Press Inc.",
number = "2",

}

Connectivity of the Product Replacement Graph of simple groups of bounded Lie rank. / Avni, Nir; Garion, Shelly.

In: Journal of Algebra, Vol. 320, No. 2, 15.07.2008, p. 945-960.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Avni, Nir

AU - Garion, Shelly

PY - 2008/7/15

Y1 - 2008/7/15

N2 - 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.

AB - 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.

KW - Product Replacement Algorithm

KW - T-systems

UR - http://www.scopus.com/inward/record.url?scp=44649118529&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44649118529&partnerID=8YFLogxK

U2 - 10.1016/j.jalgebra.2008.03.005

DO - 10.1016/j.jalgebra.2008.03.005

M3 - Article

VL - 320

SP - 945

EP - 960

JO - Journal of Algebra

JF - Journal of Algebra

SN - 0021-8693

IS - 2

ER -