Diameter of Ramanujan Graphs and Random Cayley Graphs

Abstract

We study the diameter of LPS Ramanujan graphs $X_{p,q}$. We show that the diameter of the bipartite Ramanujan graphs is greater than $(4/3){\log }_p(n)+O(1)$ where $n$ is the number of vertices of $X_{p,q}$. We also construct an infinite family of $(p+1)$-regular LPS Ramanujan graphs $X_{p,m}$ such that the diameter of these graphs is greater than or equal to $\lfloor (4/3){\log }_p(n)\rfloor$. On the other hand, for any $k$-regular Ramanujan graph we show that the distance of only a tiny fraction of all pairs of vertices is greater than $(1+\epsilon ){\log }_{k-1}(n)$. We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically $(4/3){\log }_{k-1}(n)$ and ${\log }_{k-1}(n)$, respectively.