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

496 Views Asked by At

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.

1

There are 1 best solutions below

1
On 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