\(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators (Q800384)

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