1995/01/01 by Felix Lazebnik, Vasiliy A. Ustimenko, Andrew J. Woldar · 1 citation
Mathematics · #math.CO
published as Bull. Amer. Math. Soc. (N.S.) 32 (1995) 73-79 · 7 pages
arxiv created 1995/01/01 · arxiv updated 2016/09/06
Let k≥ 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 ≤ 2qk-t+1 and girth g ≥ k+5. If e is the the number of edges of C D(k,q), then e =Ω(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≥ 5, g \not= 11,12. For g≥ 24, this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for 5≤ g≤ 23, g\not= 11,12, it improves on or ties existing bounds.