A new series of dense graphs of high girth

Felix Lazebnik, Vasiliy A. Ustimenko, Andrew J. Woldar

Published 1995-01-01Version 1

Let $k\ge 1$ be an odd integer, $t=\lfloor {{k+2}\over 4}\rfloor$, and $q$ be a prime power. We construct a bipartite, $q$-regular, edge-transitive graph $C\!D(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 $C\!D(k,q)$, then $e =\Omega(v^{1+ {1\over {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 \not= 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\not= 11,12$, it improves on or ties existing bounds.