On the diameter of Cayley graphs of classical groups with generating sets containing a transvection
Let \(G\) be a finite group, \(X\) a set of generators of \(G\), and let \(\mathrm{Cay}(G,X)\) be the Cayley graph of \(G\) associated to \(X\). The diameter of \(\mathrm{Cay}(G,X)\) equals the maximum over \(g \in G\) of the length of a shortest expression of \(g\) as a product of generators in \(X\) and their inverses, it is denoted by \(\operatorname{diam} \mathrm{Cay}(G,X)\). The diameter of \(G\) is\N\[\N\operatorname{diam} G= \max \{ \operatorname{diam} \mathrm{Cay}(G,X) \mid X \subseteq G, \langle X \rangle =G \}.\N\]\N\N\textit{L. Babai} and \textit{Á. Seress} [J. Comb. Theory, Ser. A 49, No. 1, 175--179 (1988; Zbl 0649.20002)] proposed the following conjecture: If \(G\) is a non-abelian finite simple group, then \(\operatorname{diam} G \leq ( \log |G| )^{c}\) for some absolute constant \(c\).\N\NThe main result of this paper is Theorem 1.5: Let \(V\) be an \(n\)-dimensional vector space over the finite field \(\mathbb{F}_{q}\) where \(q\) is odd and \(G\) is one of \(\mathrm{SL}(V)\), \(\mathrm{Sp}(V)\) or \(\mathrm{SU}(V)\). Let \(X\) be a generating set for \(G\) containing a transvection. Then \(\operatorname{diam} \mathrm{Cay}(G,X) \leq (n \log q)^{c}\) for some constant \(c\) provided that (a) \(q \not= 9\) if \(G=\mathrm{Sp}(V )\); (b) \(q \not =81\) if \(G=\mathrm{SU}(V)\); (c) \(q \not \in \{9, 81\}\) if \(G=\mathrm{SL}(V)\). So Babai-Seress' bound holds for these cases.
scientific article; zbMATH DE number 7903073
scientific article