An algorithm to evaluate the spectral expansion

Abstract

Assume that $X$ is a connected $(q+1)$-regular undirected graph of finite order $n$. Let $A$ denote the adjacency matrix of $X$. Let ${\lambda }_1=q+1>{\lambda }_2\ge {\lambda }_3\ge \dots \ge {\lambda }_n$ denote the eigenvalues of $A$. The spectral expansion of $X$ is defined by $$\Delta (X)={\lambda }_1-\underset{2\le i\le n}{\max }|{\lambda }_i|.$$ By the Alon--Boppana theorem, when $n$ is sufficiently large, $\Delta (X)$ is quite high if $$\mu (X)=q^{-\frac{1}{2}}\underset{2\le i\le n}{\max }|{\lambda }_i|$$ is close to $2$. In this paper, with the inputs $A$ and a real number $\epsilon >0$ we design an algorithm to estimate if $\mu (X)\le 2+\epsilon$ in $O(n^{\omega }\log {\log }_{1+\epsilon }n)$ time, where $\omega <2.3729$ is the exponent of matrix multiplication.