Previous button up button Next button

Diameters of Cayley Graphs of Chevalley Groups

Martin Kassabov and Tim Riley

Eur. J. Comb., 28(3), pages 791–800, April 2007

We show that for integers k > 1 and n > 2, the diameter of the Cayley graph of SLn(Z/kZ) with respect to a standard two-element generating set, is at most a constant times n2 ln k. 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.