Expander graphs (statement)

Definition. A graph is an $(n,d,\lambda)$-expander if it is $d$-regular on $n$ vertices with all nontrivial eigenvalues $\le\lambda$ in absolute value.

Cheeger. The edge expansion $h(G)$ satisfies $\frac{d-\lambda_2}{2}\le h(G)\le\sqrt{2d(d-\lambda_2)}$.

Application. Expanders have logarithmic diameter, good error-correcting codes, derandomization.

Conclusion. Spectral gap controls expansion; expanders are fundamental objects in combinatorics and computer science.