Diameters of Cayley graphs of Chevalley groups

M Kassabov; TR Riley

doi:10.1016/j.ejc.2005.12.005

Diameters of Cayley graphs of Chevalley groups

M Kassabov, TR Riley

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

12 Citations (Scopus)

Abstract

We show that for integers k >= 2 and n >= 3, the diameter of the Cayley graph of SLn (Z/kZ) associated with a standard two-element generating set is at most a constant times 112 Ink. This answers a question of A. Lubotzky concerning SLn(Fp) and is unexpected because these Cayley graphs do not form an expander family. Our proof amounts to a quick algorithm for finding short words representing elements of SLn (Z/kZ). We generalize our results to other Chevalley groups over Z/kZ. (c) 2005 Elsevier Ltd. All rights reserved.

Translated title of the contribution	Diameters of Cayley graphs of Chevalley groups
Original language	English
Pages (from-to)	791 - 800
Number of pages	10
Journal	European Journal of Combinatorics
Volume	28 (3)
DOIs	https://doi.org/10.1016/j.ejc.2005.12.005
Publication status	Published - Apr 2007

Bibliographical note

Publisher: Academic Press Ltd Elsevier Science Ltd

Access to Document

10.1016/j.ejc.2005.12.005

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-4J3WS2H-1&_user=121739&_coverDate=04%2F30%2F2007&_rdoc=13&_fmt=full&_orig=browse&_srch=doc-info(%23toc%236779%232007%23999719996%23638422%23FLA%23display%23Volume)&_cdi=6779&_sort=d&_docanchor=&view=c&_ct=31&_acct=C000010018&_version=1&_urlVersion=0&_userid=121739&md5=62f9023e357323758faa62ae0aeec580

Handle.net

Persistent link

Cite this

@article{14870246c9ff412299ebcb9588bdf217,

title = "Diameters of Cayley graphs of Chevalley groups",

abstract = "We show that for integers k >= 2 and n >= 3, the diameter of the Cayley graph of SLn (Z/kZ) associated with a standard two-element generating set is at most a constant times 112 Ink. This answers a question of A. Lubotzky concerning SLn(Fp) and is unexpected because these Cayley graphs do not form an expander family. Our proof amounts to a quick algorithm for finding short words representing elements of SLn (Z/kZ). We generalize our results to other Chevalley groups over Z/kZ. (c) 2005 Elsevier Ltd. All rights reserved.",

author = "M Kassabov and TR Riley",

note = "Publisher: Academic Press Ltd Elsevier Science Ltd",

year = "2007",

month = apr,

doi = "10.1016/j.ejc.2005.12.005",

language = "English",

volume = "28 (3)",

pages = "791 -- 800",

journal = "European Journal of Combinatorics",

publisher = "Academic Press",

}

TY - JOUR

T1 - Diameters of Cayley graphs of Chevalley groups

AU - Kassabov, M

AU - Riley, TR

N1 - Publisher: Academic Press Ltd Elsevier Science Ltd

PY - 2007/4

Y1 - 2007/4

N2 - We show that for integers k >= 2 and n >= 3, the diameter of the Cayley graph of SLn (Z/kZ) associated with a standard two-element generating set is at most a constant times 112 Ink. This answers a question of A. Lubotzky concerning SLn(Fp) and is unexpected because these Cayley graphs do not form an expander family. Our proof amounts to a quick algorithm for finding short words representing elements of SLn (Z/kZ). We generalize our results to other Chevalley groups over Z/kZ. (c) 2005 Elsevier Ltd. All rights reserved.

AB - We show that for integers k >= 2 and n >= 3, the diameter of the Cayley graph of SLn (Z/kZ) associated with a standard two-element generating set is at most a constant times 112 Ink. This answers a question of A. Lubotzky concerning SLn(Fp) and is unexpected because these Cayley graphs do not form an expander family. Our proof amounts to a quick algorithm for finding short words representing elements of SLn (Z/kZ). We generalize our results to other Chevalley groups over Z/kZ. (c) 2005 Elsevier Ltd. All rights reserved.

U2 - 10.1016/j.ejc.2005.12.005

DO - 10.1016/j.ejc.2005.12.005

M3 - Article (Academic Journal)

VL - 28 (3)

SP - 791

EP - 800

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Diameters of Cayley graphs of Chevalley groups

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this