High-girth near-Ramanujan graphs with localized eigenvectors

08/10/2019

∙

by   Noga Alon, et al.

∙

0

∙

share

We show that for every prime d and α∈ (0,1/6), there is an infinite sequence of (d+1)-regular graphs G=(V,E) with girth at least 2αlog_d(|V|)(1-o_d(1)), second adjacency matrix eigenvalue bounded by (3/√(2))√(d), and many eigenvectors fully localized on small sets of size O(|V|^α). This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the "scarring" phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of Erdős and Sachs for constructing high girth regular graphs.