4
$\begingroup$

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$.)

$\endgroup$
2

0

You must log in to answer this question.

Browse other questions tagged .