Logarithmic girth expander graphs of SLn(Fp)

Goulnara Arzhantseva, Arindam BiswasJournal of Algebraic Combinatorics 2025 · OpenReview

Abstract

We provide an explicit construction of finite 4-regular graphs $(\Gamma_k)_{k \in \mathbb{N}}$ with girth $\text{girth}(\Gamma_k) \to \infty$ as $k \to \infty$ and $$ \frac{\text{diam}(\Gamma_k)}{\text{girth}(\Gamma_k)} \leq D $$ for some $D > 0$ and all $k \in \mathbb{N}$. For each fixed dimension $n \geq 2$, we find a pair of matrices in $\text{SL}_n(\mathbb{Z})$ such that: 1. They generate a free subgroup. 2. Their reductions modulo $p$ generate $\text{SL}_n(\mathbb{F}_p)$ for all sufficiently large primes $p$. 3. The corresponding Cayley graphs of $\text{SL}_n(\mathbb{F}_p)$ have girth at least $c_n \log p$ for some $c_n > 0$. \end{itemize} Relying on growth results (with no reliance on expansion properties of the involved graphs), we observe that the diameter of these Cayley graphs is at most $O(\log p)$. This construction yields infinite sequences of finite 4-regular Cayley graphs of $\text{SL}_n(\mathbb{F}_p)$ as $p \to \infty$, characterized by large girth and a bounded diameter-to-girth ratio. These constructions represent the first explicit examples in all dimensions $n \geq 2$ (with all prior examples confined to $n = 2$). Moreover, they inherently exhibit expander graph properties. Together with the classical constructions of Margulis and Lubotzky–Phillips–Sarnak, these new graphs constitute the only known explicit logarithmic girth Cayley graph expanders.
BibTeX
@article{arzhantseva2025logarithmic,
  author = {Goulnara Arzhantseva and Arindam Biswas},
  title = {{Logarithmic girth expander graphs of SLn(Fp)}},
  journal = {Journal of Algebraic Combinatorics},
  year = {2025},
  url = {https://openreview.net/forum?id=aeWheR6MET},
}

Loading related content...

Figure