Logarithmic girth expander graphs of SL_n(\mathbb F_p)

DOI10.1007/S10801-022-01128-ZMaRDI QIDQ6299529arXivFDO

Authors Goulnara N. Arzhantseva, Arindam Biswas

Publication date 25 March 2018

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Residual properties and generalizations; residually finite groups (20E26) Geometric group theory (20F65) Linear algebraic groups over finite fields (20G40)

Abstract: We provide an explicit construction of finite 4-regular graphs

(G a m m a_{k})_{k i n m a t h b b N}

with

g i r t h G a m m a_{k} o i n f t y

as

k o i n f t y

and

f r a c d i a m G a m m a_{k} g i r t h G a m m a_{k} l e q s l a n t D

for some

D > 0

and all

k i n m a t h b b N

. For each fixed dimension

n g e q s l a n t 2,

we find a pair of matrices in

S L_{n} (m a t h b b Z)

such that (i) they generate a free subgroup, (ii)~their reductions

generate

S L_{n} (m a t h b b F_{p})

for all sufficiently large primes

p

, (iii) the corresponding Cayley graphs of

S L_{n} (m a t h b b F_{p})

have girth at least

c_{n} l o g p

for some

c_{n} > 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 (l o g p)

. This gives infinite sequences of finite

4

-regular Cayley graphs of

S L_{n} (m a t h b b F_{p})

as

p o i n f t y

with large girth and bounded diameter-by-girth ratio. These are the first explicit examples in all dimensions

n g e q s l a n t 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.

This page was built for publication: Logarithmic girth expander graphs of $SL_n(\mathbb F_p)$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6299529)