Logarithmic girth expander graphs of
arXiv:1803.09229 · doi:10.1007/s10801-022-01128-z
Abstract
We provide an explicit construction of finite 4-regular graphs with as and for some and all . For each fixed dimension we find a pair of matrices in such that (i) they generate a free subgroup, (ii)~their reductions generate for all sufficiently large primes , (iii) the corresponding Cayley graphs of have girth at least for some . 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 . This gives infinite sequences of finite -regular Cayley graphs of as with large girth and bounded diameter-by-girth ratio. These are the first explicit examples in all dimensions (all prior examples were in ). 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.
arXiv commentTitle and content updated to reflect published version. Previous title: "Large girth graphs with bounded diameter-by-girth ratio"
References in corpus (8)
- Nonlinear spectral calculus and super-expanders
- Poincaré inequalities, embeddings, and wild groups
- Growth and generation in SL_2(Z/pZ)
- Expansion in perfect groups
- Expansion in SL_d(Z/qZ), q arbitrary
- Expanders with respect to Hadamard spaces and random graphs
- Warped cones and spectral gaps
- On sofic approximations of Property (T) groups