We provide an explicit construction of finite 4-regular graphs (Gamma(k))(k is an element of N) with girth Gamma(k) -> infinity as k -> infinity and diam Gamma(k)/girth Gamma 0 and all k is an element of N. For each fixed dimension n >= 2, we find a pair of matrices in SLn (Z) such that (i) they generate a free subgroup, (ii) their reductions mod p generate SLn (F-p) for all sufficiently large primes p, (iii) the corresponding Cayley graphs of SLn (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 SLn (F-p) as p -> infinity 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.
展开▼
