Logarithmic girth expander graphs of $S{L}_n({\mathbb{F}}_p)$

Abstract

We provide an explicit construction of finite 4-regular graphs $({\Gamma }_k{)}_{k\in \mathbb{N}}$ with $girth{\Gamma }_k\to \infty$ as $k\to \infty$ and $\frac{diam{\Gamma }_k}{girth{\Gamma }_k}⩽D$ for some $D>0$ and all $k\in \mathbb{N}$. For each fixed dimension $n⩾2,$ we find a pair of matrices in $S{L}_n(\mathbb{Z})$ such that (i) they generate a free subgroup, (ii)~their reductions $\mathrm{mod}p$ generate $S{L}_n({\mathbb{F}}_p)$ for all sufficiently large primes $p$, (iii) the corresponding Cayley graphs of $S{L}_n({\mathbb{F}}_p)$ have girth at least $c_n\log 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(\log p)$. This gives infinite sequences of finite $4$-regular Cayley graphs of $S{L}_n({\mathbb{F}}_p)$ as $p\to \infty$ 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.

Title and content updated to reflect published version. Previous title: "Large girth graphs with bounded diameter-by-girth ratio"

References in corpus (1)

• On sofic approximations of Property (T) groups