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. Building on work of Brooks and Lindenstrauss, we show that if any eigenvector of the adjacency matrix of a d-regular graph has an epsilon fraction of its ell_2^2 mass concentrated on k vertices, then the graph must contain a cycle of length at most roughly log_d(k)/epsilon (improving their bound by about 1/epsilon). We complement this with a probabilistic construction showing that our bound is essentially sharp. Altogether these results precisely quantify the interplay between delocalization and girth, in particular showing that arbitrary high girth graphs enjoy considerably weaker delocalization properties than random regular graphs.

Joint work with Shirshendu Ganguly (Berkeley).