Prove that the diameter of a $(n,d,\lambda)$-graph is at most $\lceil \log n / \log (d/\lambda) \rceil$

algebraic-graph-theorygraph theorylinear algebrarandom-graphsspectral-graph-theory

Let $G$ be a $n$-vertex $d$-regular graph. Let $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ be the eigenvalues of the adjacency matrix $A_G$ of $G$ and $\lambda\geq \max\{|\lambda_2|, |\lambda_n|\}$. (I.e., $G$ is a $(n,d,\lambda)$-graph.)

Prove that the diameter of $G$ is at most $\lceil \log n / \log (d/\lambda) \rceil$.

I think this problem is related to the proofof Alon-Boppana bound, but I don't have any idea how to prove.

Best Answer

Have a look at "Chung, F. R. K. (1989). Diameters and Eigenvalues. Journal of the American Mathematical Society, 2(2), 187."

Here is the proof (obviously not my work).

enter image description here

Related Question