A new series of dense graphs of high girth

Abstract

Let k ≥ 1 k \geq 1 be an odd integer, t = ⌊ k + 2 4 ⌋ {t = \left \lfloor {\tfrac {{k + 2}}{4}} \right \rfloor } , and q be a prime power. We construct a bipartite, q-regular, edge-transitive graph C D ( k , q ) CD(k,q) of order υ ≤ 2 q k − t + 1 \upsilon \leq 2{q^{k - t + 1}} and girth g ≥ k + 5 g \geq k + 5 . If e is the the number of edges of C D ( k , q ) CD(k,q) , then e = Ω ( υ 1 + 1 k − t + 1 ) e = \Omega ({{\upsilon ^{1 + \frac {1}{{k - t + 1}}}}}) . These graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of order υ \upsilon and girth at least g, g ≥ 5 g \geq 5 , g ≠ 11 g \ne 11 , 12. For g ≥ 24 g \geq 24 , this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for 5 ≤ g ≤ 23 5 \leq g \leq 23 , g ≠ 11 g \ne 11 , 12, it improves on or ties existing bounds.