Logarithmic girth expander graphs of SL_n(\mathbb F_p)

DOI10.1007/S10801-022-01128-ZarXiv1803.09229MaRDI QIDQ6299529FDOQ6299529

Authors: Goulnara N. Arzhantseva, Arindam Biswas

Publication date: 25 March 2018

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.

Mathematics Subject Classification ID

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)

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)