High-girth near-Ramanujan graphs with localized eigenvectors

08/10/2019
by   Noga Alon, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro