On Non-localization of Eigenvectors of High Girth Graphs
share
We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any ε∈ (0,1) and positive integer k, if a (d+1)-regular graph has an eigenvector which supports ε fraction of the ℓ_2^2 mass on a subset of k vertices, then the graph must have a cycle of size Õ(_d(k)/ε^2), suppressing logarithmic terms in 1/ε. In this paper, we improve the upper bound to Õ(_d(k)/ε) and present a construction showing a lower bound of Ω(_d(k)/ε). Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.
READ FULL TEXT