Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem.

In the 1988 paper "Ramanujan graphs", Lubotzky, Philips, and Sarnak showed that there exist $k$-regular graphs with girth $(4/3) \log_{k-1} n$. The graphs they construct are Cayley graphs on $PSL(2, \mathbb{Z}/q)$ and the proof that the girth is as large as claimed depends on subtle number-theoretic considerations. On the other hand, a simple counting argument shows that the girth can never be more than $2 \log_{k-1} n$.

I am wondering what the best known bounds are, 25 years after this landmark paper, especially for the case of cubic graphs $k=3$. In particular, have either of the constants $4/3$ or $2$ been improved?

(Although there has also been study of this kind of question for small $n$, I am only interested in the asymptotics as $n \to \infty$.)

share|improve this question
From this recent survey, it doesn't appear that much progress has been made:combinatorics.org/ojs/index.php/eljc/article/view/DS16 –  Ian Agol Sep 12 '13 at 4:42
A database of cages is here: school.maths.uwa.edu.au/~gordon/remote/cages –  joro Sep 12 '13 at 7:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.