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 Z. Füredi, F. Lazebnik, Á. Seress, V. A. Ustimenko, and A. J. Woldar, Graphs of prescribed girth and bi-degree, submitted.
- 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, Rutcor Research Report RRR 99-93, December 1993.
- 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, Investigation in Algebraic Theory of Combinatorial Objects (I. A. Faradzev, A. A. Ivanov, M. H. Klin, and A. J. Woldar, eds.) Kluwer, Dordrecht, 1991, pp. 112-121.
- 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
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 32 (1995), 73-79
- MSC: Primary 05C35
- DOI: https://doi.org/10.1090/S0273-0979-1995-00569-0
- MathSciNet review: 1284775