Eigenvalues and Expanders: A Regular Bipartite Graph Is a Strong Expander If and Only If λ(G) Is Bounded Away from 0Research Paper
Expander graphs are sparse graphs in which every set of vertices has many neighbours. Families of them with bounded degree and expansion bounded away from zero are a basic tool of theoretical computer science: they are the main component of the sorting network of Ajtai, Komlós and Szemerédi (AKS 1983), the building block of superconcentrators and other…