Diameters of Cayley graphs of SL_n(Z/kZ)

2005/02/11 by M. Kassabov, Kassabov, M., T. R. Riley +1
Mathematics · #05C35 #20D06 #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #math.CO #math.GR #msc:05C25 #msc:05C35 #msc:20D06 #msc:20F05 #primary 20F05 #secondary 05C25

paper · pdf · doi:10.48550/arxiv.math/0502221

11 pages, no figures

arxiv created 2005/02/11 · arxiv updated 2009/12/01

Abstract

We show that for integers k > 1 and n > 2, the diameter of the Cayley graph of SL_n(Z/kZ) associated to a standard two-element generating set, is at most a constant times n² ln k. This answers a question of A. Lubotzky concerning SL_n(F_p) 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 SL_n(Z/kZ).

Related

• Diameter of Cayley graphs of SL(n,p) with generating sets containing a\n transvection
• Logarithmic bounds for the diameters of some Cayley graphs
• Finite Groups of Uniform Logarithmic Diameter
• A sharp diameter bound for unipotent groups of classical type over Z/pZ
• On the diameter of Cayley graphs of classical groups with generating sets containing a transvection