A new series of dense graphs of high girth

Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J.

doi:10.1090/S0273-0979-1995-00569-0

A new series of dense graphs of high girth
HTML articles powered by AMS MathViewer

by F. Lazebnik, V. A. Ustimenko and A. J. Woldar PDF

Bull. Amer. Math. Soc. 32 (1995), 73-79 Request permission

Abstract:

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

References

Clark T. Benson, Minimal regular graphs of girths eight and twelve, Canadian J. Math. 18 (1966), 1091–1094. MR 197342, DOI 10.4153/CJM-1966-109-8
N. L. Biggs, Graphs with large girth, Ars Combin. 25 (1988), no. C, 73–80. Eleventh British Combinatorial Conference (London, 1987). MR 943379
N. L. Biggs and A. G. Boshier, Note on the girth of Ramanujan graphs, J. Combin. Theory Ser. B 49 (1990), no. 2, 190–194. MR 1064675, DOI 10.1016/0095-8956(90)90026-V
N. L. Biggs and M. J. Hoare, The sextet construction for cubic graphs, Combinatorica 3 (1983), no. 2, 153–165. MR 726453, DOI 10.1007/BF02579289
Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory Ser. B 16 (1974), 97–105. MR 340095, DOI 10.1016/0095-8956(74)90052-5
A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568, DOI 10.1007/978-3-642-74341-2
Fan R. K. Chung, Constructing random-like graphs, Probabilistic combinatorics and its applications (San Francisco, CA, 1991) Proc. Sympos. Appl. Math., vol. 44, Amer. Math. Soc., Providence, RI, 1991, pp. 21–55. MR 1141922, DOI 10.1090/psapm/044/1141922
R. J. Faudree and M. Simonovits, On a class of degenerate extremal graph problems, Combinatorica 3 (1983), no. 1, 83–93. MR 716423, DOI 10.1007/BF02579343

Graphs of prescribed girth and bi-degree

Wilfried Imrich, Explicit construction of regular graphs without small cycles, Combinatorica 4 (1984), no. 1, 53–59. MR 739413, DOI 10.1007/BF02579157
Felix Lazebnik and Vasiliy A. Ustimenko, New examples of graphs without small cycles and of large size, European J. Combin. 14 (1993), no. 5, 445–460. Algebraic combinatorics (Vladimir, 1991). MR 1241911, DOI 10.1006/eujc.1993.1048
Felix Lazebnik and Vasiliy A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. 60 (1995), no. 1-3, 275–284. ARIDAM VI and VII (New Brunswick, NJ, 1991/1992). MR 1339092, DOI 10.1016/0166-218X(94)00058-L
F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, Properties of certain families of $2k$-cycle-free graphs, J. Combin. Theory Ser. B 60 (1994), no. 2, 293–298. MR 1271276, DOI 10.1006/jctb.1994.1020

A new series of dense graphs of large girth

A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), no. 1, 71–78. MR 671147, DOI 10.1007/BF02579283
G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), no. 1, 51–60 (Russian); English transl., Problems Inform. Transmission 24 (1988), no. 1, 39–46. MR 939574
Peter Sarnak, Some applications of modular forms, Cambridge Tracts in Mathematics, vol. 99, Cambridge University Press, Cambridge, 1990. MR 1102679, DOI 10.1017/CBO9780511895593
M. Simonovits, Extremal graph theory, Selected topics in graph theory, 2, Academic Press, London, 1983, pp. 161–200. MR 797252
V. A. Ustimenko, Tits geometries and division algebras, Dokl. Akad. Nauk SSSR 296 (1987), no. 5, 1061–1065 (Russian); English transl., Soviet Math. Dokl. 36 (1988), no. 2, 366–369. MR 915644
V. A. Ustimenko, Linear interpretation of the geometries of flags of Chevalley groups, Ukrain. Mat. Zh. 42 (1990), no. 3, 383–387 (Russian, with Ukrainian summary); English transl., Ukrainian Math. J. 42 (1990), no. 3, 341–344. MR 1054885, DOI 10.1007/BF01057020
V. A. Ustimenko, On embedding of some geometries and flag systems in Lie algebras and superalgebras, Akad. Nauk Ukrain. SSR Inst. Mat. Preprint 8 (1990), 3–17 (English, with Russian summary). MR 1078874

On some properties of geometries of the Chevalley groups and their generalizations

V. A. Ustimenko and A. J. Woldar, An improvement on the Erdős bound for graphs of girth $16$, Second International Conference on Algebra (Barnaul, 1991) Contemp. Math., vol. 184, Amer. Math. Soc., Providence, RI, 1995, pp. 419–425. MR 1332307, DOI 10.1090/conm/184/02136
Alfred Weiss, Girths of bipartite sextet graphs, Combinatorica 4 (1984), no. 2-3, 241–245. MR 771732, DOI 10.1007/BF02579225
R. Wenger, Extremal graphs with no $C^4$’s, $C^6$’s, or $C^{10}$’s, J. Combin. Theory Ser. B 52 (1991), no. 1, 113–116. MR 1109426, DOI 10.1016/0095-8956(91)90097-4
Andrew J. Woldar and Vasiliy A. Ustimenko, An application of group theory to extremal graph theory, Group theory (Granville, OH, 1992) World Sci. Publ., River Edge, NJ, 1993, pp. 293–298. MR 1348910