On the diameter of a Cayley graph of a simple group of Lie type based on a conjugacy class (Q1268608): Difference between revisions

The problem of finding the diameter of a given Cayley graph is of a considerable practical importance. It has been conjectured by \textit{L. Babai} and \textit{Á. Seress} [J. Comb. Theory, Ser. A 19, No. 1, 175-179 (1988; Zbl 0649.20002)] that every connected Cayley graph of a finite simple group \(G\) has diameter at most \(O(\log^c| G|)\). The authors prove the conjecture to be true for Cayley graphs of finite simple groups \(G\) of Lie type whose generating set is a non-identity conjugacy class of \(G\). If \(\text{cd}(G)\) denotes the maximum diameter of all such Cayley graphs of a finite simple group \(G\) of Lie type, of untwisted rank \(\ell\), the main result of the paper asserts that \(\text{cd} (G)\leq 8(5\ell+7)\). The methods used are group-theoretical and include among others the Bruhat decomposition for writing elements of \(G\) as products of long root elements and the use of character tables.