MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
From this recent survey, it doesn't appear that much progress has been – Ian Agol Sep 12 '13 at 4:42
A database of cages is here: – 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.