Monotone maps, sphericity and bounded second eigenvalue

For the above bound to be linear, λ2 must be constant. We show that if the second eigenvalue of an n/2-regular graph is bounded by a constant, then the graph is close to being complete bipartite. Namely, its adjacency matrix differs from that of a complete bipartite graph in only o(n2) entries (Theorem 5). Furthermore, for any 0<δ<12, and λ2, there are only finitely many δn-regular graphs with second eigenvalue at most λ2 (Corollary 4).