Girth, Expansion, and Localization of Graph Eigenfunctions

The extreme eigenvectors of graphs play a central role in spectral graph theory, corresponding to sparse cuts and colorings. We study the combinatorial meaning of the interior eigenvectors. Brooks and Lindenstrauss showed that if any eigenvector of the adjacency matrix of a d-regular graph has a large fraction of its mass on a few coordinates (i.e., is "localized"), then it must contain a short cycle; we sharpen their results, and complement this with a construction showing that our improved bound on the length of the cycle is essentially optimal, thus precisely quantifying the interplay between localization of eigenvectors and girth in regular graphs. We further construct infinite families of high girth expanders with such localized eigenvectors, which may be viewed as a discrete version of the "scarring" phenomenon observed for eigenfunctions of certain manifolds.

Joint work with N. Alon and S. Ganguly.