Diameter of Ramanujan graphs and random Cayley graphs (Q2322509)

Let \(X_{p,q}\) denote a \((p+1)\)-regular bipartite or non-bipartite graph depending on \(p\) being a non-quadratic or quadratic residue modulo \(q\), respectively. \textit{A. Lubotzky} et al. [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)] constructed an explicit family of \((p+1)\)-regular Ramanujan graphs \(X_{p,q}\), where \(p\) and \(q\) are prime numbers and \(q \equiv 1 \pmod4\). The author shows that the diameter of LPS Ramanujan graphs \(X_{p,q}\) is greater than \((4/3) \log_{p}(n)+O(1)\), where \(n\) is the number of vertices of \(X_{p,q}\). He also constructs an infinite family of \((p+1)\)-regular LPS Ramanujan graphs \(X_{p,m}\) with diameter greater than or equal to \(\lfloor(4/3) \log_{p}(n)\rfloor\), and he shows that for any \(k\)-regular Ramanujan graph only a tiny fraction of all pairs of vertices have distance greater than \((1+\varepsilon)\log_{k-1}(n)\). Numerical results indicate that for LPS Ramanujan graphs and random Cayley graphs the diameters are asymptotically \((4/3) \log_{k-1}(n)\) and \(\log_{k-1}(n)\), respectively.