Regular graphs of large girth and arbitrary degree

Abstract

For every integer d > 9, we construct infinite families {G_n}_n of d+1-regular graphs which have a large girth > log_d |G_n|, and for d large enough > 1,33 log_d |G_n|. These are Cayley graphs on PGL_2(q) for a special set of d+1 generators whose choice is related to the arithmetic of integral quaternions. These graphs are inspired by the Ramanujan graphs of Lubotzky-Philips-Sarnak and Margulis, with which they coincide when d is prime. When d is not equal to the power of an odd prime, this improves the previous construction of Imrich in 1984 where he obtained infinite families {I_n}_n of d+1-regular graphs, realized as Cayley graphs on SL_2(q), and which are displaying a girth > 0,48 log_d |I_n|. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {M_n}_n of 2^k+1-regular graphs were shown to have a girth > 2/3 log_d |M_n|.

(15 pages) Accepted at Combinatorica. Title changed following referee's suggestion. Revised version after reviewing process

References in corpus (1)

• Ramanujan graphs of very large girth based on octonions

Cited by in corpus (9)

• Construction of Near-Capacity Protograph LDPC Code Sequences with Block-Error Thresholds
• Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
• An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
• Containment: A Variation of Cops and Robbers
• Constructions of point-line arrangements in the plane with large girth
• A Tight Rate Bound and Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures
• Erasure Codes for Distributed Storage: Tight Bounds and Matching Constructions
• Pseudofiniteness and measurability of the everywhere infinite forest
• On social networks that support learning