Random Walks and Delocalization through Graph Eigenvector Structure

In this thesis we prove the following results.1. We show that the multiplicity of the second normalized adjacency matrix eigenvalueof any connected graph of maximum degree Δ is bounded by nΔ^(7/5)/polylog(n) for any Δ, and n*polylog(d)/polylog(n) for simple d-regular graphs when d is sufficiently large.2. Let G be a random d-regular graph. We prove that for every constant α > 0, withhigh probability every eigenvector of the adjacency matrix of G with eigenvalue less than −2√(d − 2) − α has Ω(n/polylog(n)) nodal domains.3. For every d = p + 1 for prime p and infinitely many n, we exhibit an n-vertexd-regular graph with girth Ω(log_(d−1) n) and vertex expansion of sublinear sized sets upper bounded by (d+1)/2 whose nontrivial eigenvalues are bounded in magnitude by 2√(d − 1) + O(1/log n). This gives a high-girth version of Kahale’s example showing Ramanujan graphs can have poor vertex expansion.4. Anantharaman and Le Masson proved that any family of eigenbases of the adjacencyoperators of a family of graphs is quantum ergodic, assuming the graphs satisfy conditions of expansion and high girth. We show that neither of these two conditions is sufficient by itself to imply quantum ergodicity (which is a form of delocalization).These results although different in nature, all exhibit the utility of the structure of eigenvectors.The main ingredient in the first result is a polynomial (in k) lower bound on the typical support of a closed random walk of length 2k in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix. The second result suggests Gaussian behavior of eigenvectors of random regular graphs conjectured by Elon, a discrete analog of Berry’s conjecture. The third result shows that properties that are sufficient to imply eigenvector delocalization are not strong enough to imply vertex expansion. The theorems and examples in the fourth result show why Anantharaman and Le Masson’s quantum ergodicity result requires expansion both at a global scale (spectral expansion) and a local scale (high girth)