Navigating directed Cayley graphs of small diameter: A potent Solovay–Kitaev procedure
| Autor: | Henry Bradford |
|---|---|
| Přispěvatelé: | Bradford, Henry [0000-0003-2949-8095], Apollo - University of Cambridge Repository |
| Rok vydání: | 2020 |
| Předmět: |
Normal subgroup
Sequence Profinite group Small diameter Cayley graph Group (mathematics) General Mathematics 010102 general mathematics 4904 Pure Mathematics Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 01 natural sciences Combinatorics 4613 Theory Of Computation 46 Information and Computing Sciences 010201 computation theory & mathematics 49 Mathematical Sciences Spectral gap 0101 mathematics Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.17863/cam.50292 |
| Popis: | Let [Formula: see text] be a group and [Formula: see text] be a descending sequence of finite-index normal subgroups. We establish explicit upper bounds on the diameters of the directed Cayley graphs of the [Formula: see text], under some natural hypotheses on the behavior of power and commutator words in [Formula: see text]. The bounds we obtain do not depend on a choice of generating set. Moreover, under reasonable conditions our method provides a fast algorithm for navigating directed Cayley graphs. The proof is closely analogous to the Solovay–Kitaev procedure, which only uses commutator words, but also only constructs small-diameter undirected Cayley graphs. We apply our procedure to give new directed diameter bounds on finite quotients of a large class of regular branch groups, and of [Formula: see text] (for [Formula: see text] even). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|