A new series of dense graphs of high girth

Authors:
  • FLF. Lazebnik
    F. Lazebnik
  • VUV. A. Ustimenko
    V. A. Ustimenko
  • AWA. J. Woldar
    A. J. Woldar

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.

This publication has 18 references indexed in Scilit: