ÍâÍøÌìÌÃ

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).