Eigenvalues and expanders (Q1112844)

Let \(G=(V,E)\) be a graph. An \((n,d,c)\)-expander is any bipartite graph on the sets of vertices \(I\) (inputs) and \(O\) (outputs), where \(| I| =| O| =n\), the maximal degree of vertices is \(\underline{d}\), and \[ \operatorname{card} \{v\in V\mid vx\in E\text{ for some }x\in X\}\geq [1+c(1- \alpha /n)]\cdot \alpha, \] whenever \(X\subseteq I\) and \(| X| =\alpha \leq n/2\). In this paper it is shown that a regular bipartite graph is an expander if and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph.