Constructing Directed Cayley Graphs of Small Diameter: A Potent Solovay-Kitaev Procedure

2017/10/12 by Henry Bradford, Bradford, Henry
Computer Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1710.04591

openalex publication_date 2017/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let Γ be a group and (Γ_n)_n=1 ^∞ be a descending sequence of finite-index normal subgroups. We establish explicit upper bounds on the diameters of the directed Cayley graphs of the Γ/Γ_n , under some natural hypotheses on the behaviour of power and commutator words in Γ. The bounds we obtain do not depend on a choice of generating set. Moreover under reasonable conditions our method provides a fast algorithm for constructing directed Cayley graphs of diameter satisfying our bounds. The proof is closely analogous to the the Solovay-Kitaev procedure, which only uses commutator words, but also only constructs small-diameter undirected Cayley graphs. As an application we give directed diameter bounds on finite quotients of two very different groups: SL₂ (\mathbbF_q [[t]]) (for q even) and a group of automorphisms of the ternary rooted tree introduced by Fabrykowski and Gupta.

Citations

• On mixing properties of compact group extensions of hyperbolic systems

Related

• Diameter of Cayley graphs of SL(n,p) with generating sets containing a transvection
• On the diameter of permutation groups
• On the diameter of Cayley graphs of classical groups with generating sets containing a transvection
• A sharp diameter bound for unipotent groups of classical type over Z/pZ
• Large Cayley graphs of small diameter