Logarithmic girth expander graphs of SLn(Fp)

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

Dokumenter

  • Fulltext

    Accepteret manuskript, 356 KB, PDF-dokument

  • Goulnara Arzhantseva
  • Arindam Biswas

We provide an explicit construction of finite 4-regular graphs (Γk)k∈N with girthΓk→∞ as k→ ∞ and diamΓkgirthΓk⩽D for some D> 0 and all k∈ N. For each fixed dimension n⩾ 2 , we find a pair of matrices in SLn(Z) such that (i) they generate a free subgroup, (ii) their reductions modp generate SLn(Fp) for all sufficiently large primes p, (iii) the corresponding Cayley graphs of SLn(Fp) have girth at least cnlog p for some cn> 0. Relying on growth results (with no use of expansion properties of the involved graphs), we observe that the diameter of those Cayley graphs is at most O(log p). This gives infinite sequences of finite 4-regular Cayley graphs of SLn(Fp) as p→ ∞ with large girth and bounded diameter-by-girth ratio. These are the first explicit examples in all dimensions n⩾ 2 (all prior examples were in n= 2). Moreover, they happen to be expanders. Together with Margulis’ and Lubotzky–Phillips–Sarnak’s classical constructions, these new graphs are the only known explicit logarithmic girth Cayley graph expanders.

OriginalsprogEngelsk
TidsskriftJournal of Algebraic Combinatorics
Vol/bind56
Sider (fra-til)691–723
ISSN0925-9899
DOI
StatusUdgivet - 2022

Bibliografisk note

Funding Information:
This work was financially supported by Young Teacher Training Project in Sun Yat-sen University, China (No.19lgpy274). The experiments results used in this paper are available from the corresponding author on reasonable request.

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

ID: 308485475