Graph embeddings and Laplacian eigenvalues

Graph embeddings are useful in bounding the smallest nontrivial eigenvalues of Laplacian matrices from below. For an n x n Laplacian, these embedding methods can be characterized as follows: The lower bound is based on a clique embedding into the underlying graph of the Laplacian. An embedding can be represented by a matrix Gamma; the best possible bound based on this embedding is n/lambda(max)(Gamma(Gamma)Gamma), where lambda(max) indicates the largest eigenvalue of the specified matrix. However, the best bounds produced by embedding techniques are not tight; they can be off by a factor proportional to log(2) n for some Laplacians. We show that this gap is a result of the representation of the embedding: By including edge directions in the embedding matrix representation Gamma, it is possible to find an embedding such that Gamma(Gamma)Gamma has eigenvalues that can be put into a one-to-one correspondence with the eigenvalues of the Laplacian. Specifically, if lambda is a nonzero eigenvalue of either matrix, then n/lambda is an eigenvalue of the other. Simple transformations map the corresponding eigenvectors to each other. The embedding that produces these correspondences has a simple description in electrical terms if the underlying graph of the Laplacian is viewed as a resistive circuit. We also show that a similar technique works for star embeddings when the Laplacian has a zero Dirichlet boundary condition, though the related eigenvalues in this case are reciprocals of each other. In the zero Dirichlet boundary case, the embedding matrix Gamma can be used to construct the inverse of the Laplacian. Finally, we connect our results with previous techniques for producing bounds and provide an example.