High-girth near-Ramanujan graphs with localized eigenvectors

Noga Alon, Shirshendu Ganguly, Nikhil Srivastava

Research output: Contribution to journalArticlepeer-review

Abstract

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 high girth Ω(α logd(∣V∣), second adjacency matrix eigenvalue bounded by (3/2)d, and many eigenvectors fully localized on small sets of size O(mα). This strengthens the results of [GS18], 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 [Kah92] 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.

Original languageEnglish (US)
JournalIsrael Journal of Mathematics
DOIs
StateAccepted/In press - 2021

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'High-girth near-Ramanujan graphs with localized eigenvectors'. Together they form a unique fingerprint.

Cite this