Spectral embedding of graphs uses the top k non-trivial eigenvectors of the random walk matrix to embed the graph into R^k. The primary use of this embedding has been for practical spectral clustering algorithms [SM00,NJW02]. Recently, spectral embedding was studied from a theoretical perspective to prove higher order variants of Cheeger's inequality [LOT12,LRTV12]. We use spectral embedding to provide a unifying framework for bounding all the eigenvalues of graphs. For example, we show that for any finite graph with n vertices and all k >= 2, the k-th largest eigenvalue is at most 1-Omega(k^3 n^3), which extends the only other such result known, which is for k=2 only and is due to [LO81]. This upper bound improves to 1-Omega(k^2 n^2) if the graph is regular. We generalize these results, and we provide sharp bounds on the spectral measure of various classes of graphs, including vertex-transitive graphs and infinite graphs, in terms of specific graph parameters like the volume growth. As a consequence, using the entire spectrum, we provide (improved) upper bounds on the return probabilities and mixing time of random walks with considerably shorter and more direct proofs. Our work introduces spectral embedding as a new tool in analyzing reversible Markov chains. Furthermore, building on [Lyo05], we design a local algorithm to approximate the number of spanning trees of massive graphs.
However, to the best of our knowledge, universal lower bounds were known only for the second smallest eigenvalue of the normalized Laplacian. Namely, Landau and Odlyzko @cite_15 showed that the second eigenvalue of every simple connected graph of size @math is at least @math .
@cite_15
1983122377
Abstract We consider the class of stochastic matrices M generated in the following way from graphs: if G is an undirected connected graph on n vertices with adjacency matrix A , we form M from A by dividing the entries in each row of A by their row sum. Being stochastic, M has the eigenvalue λ=1 and possibly also an eigenvalue λ=-1. We prove that the remaining eigenvalues of M lie in the disk ¦λ¦⩽1– n -3 , and show by examples that the order of magnitude of this estimate is best possible. In these examples, G has a bar-bell structure, in which n 3 of the vertices are arranged along a line, with n 3 vertices fully interconnected at each end. We also obtain better bounds when either the diameter of G or the maximal degree of a vertex is restricted.