λ1, Isoperimetric inequalities for graphs, and superconcentrators

A general method for obtaining asymptotic isoperimetric inequalities for families of graphs is developed. Some of these inequalities have been applied to functional analysis. This method uses the second smallest eigenvalue of a certain matrix associated with the graph and it is the discrete version of a method used before for Riemannian manifolds. Also some results are obtained on spectra of graphs that show how this eigenvalue is related to the structure of the graph. Combining these results with some known results on group representations many new examples are constructed explicitly of linear sized expanders and superconcentrators.