A new series of dense graphs of high girth

Abstract

Let $k\ge 1$ be an odd integer, $t=\lfloor \frac{k+2}{4}\rfloor$, and $q$ be a prime power. We construct a bipartite, $q$-regular, edge-transitive graph $CD(k,q)$ of order $v\le 2q^{k-t+1}$ and girth $g\ge k+5$. If $e$ is the the number of edges of $CD(k,q)$, then $e=\Omega (v^{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 $v$ and girth at least $g$, $g\ge 5$, $g\ne 11,12$. For $g\ge 24$, this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for $5\le g\le 23$, $g\ne 11,12$, it improves on or ties existing bounds.

7 pages