Logarithmic girth expander graphs of SLn(Fp)
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Logarithmic girth expander graphs of SLn(Fp). / Arzhantseva, Goulnara; Biswas, Arindam.
I: Journal of Algebraic Combinatorics, Bind 56, 2022, s. 691–723 .Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Logarithmic girth expander graphs of SLn(Fp)
AU - Arzhantseva, Goulnara
AU - Biswas, Arindam
N1 - Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - Coarse embedding
KW - Diameter
KW - Expander graphs
KW - Large girth graphs
KW - Special linear group
KW - Thin matrix group
UR - http://www.scopus.com/inward/record.url?scp=85130318443&partnerID=8YFLogxK
U2 - 10.1007/s10801-022-01128-z
DO - 10.1007/s10801-022-01128-z
M3 - Journal article
AN - SCOPUS:85130318443
VL - 56
SP - 691
EP - 723
JO - Journal of Algebraic Combinatorics
JF - Journal of Algebraic Combinatorics
SN - 0925-9899
ER -
ID: 308485475