### 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 language | English (US) |
---|---|

Pages (from-to) | 945-960 |

Number of pages | 16 |

Journal | Journal of Algebra |

Volume | 320 |

Issue number | 2 |

DOIs | |

State | Published - Jul 15 2008 |

### Fingerprint

### Keywords

- Product Replacement Algorithm
- T-systems

### ASJC Scopus subject areas

- Algebra and Number Theory

### Cite this

*Journal of Algebra*,

*320*(2), 945-960. https://doi.org/10.1016/j.jalgebra.2008.03.005

}

*Journal of Algebra*, vol. 320, no. 2, pp. 945-960. https://doi.org/10.1016/j.jalgebra.2008.03.005

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

Research output: Contribution to journal › Article

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 -