Regular graphs of large girth and arbitrary degree

Original · EN

For every integer d > 9, we construct infinite families Gₙₙ of d+1-regular graphs which have a large girth > logd |Gₙ|, and for d large enough > 1,33 logd |Gₙ|. These are Cayley graphs on PGL₂(q) for a special set of d+1 generators whose choice is related to the arithmetic of integral quaternions. These graphs are inspired by the Ramanujan graphs of Lubotzky-Philips-Sarnak and Margulis, with which they coincide when d is prime. When d is not equal to the power of an odd prime, this improves the previous construction of Imrich in 1984 where he obtained infinite families Iₙₙ of d+1-regular graphs, realized as Cayley graphs on SL₂(q), and which are displaying a girth > 0,48 logd |Iₙ|. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families Mₙₙ of 2ᵏ+1-regular graphs were shown to have a girth > 2/3 logd |Mₙ|.