Graph Embeddings and Laplacian Eigenvalues

Graph embeddings are useful in bounding the smallest nontrivial eigenvalues of Laplacian matrices from below. For an n × 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 Γ; the best possible bound based on this embedding is n/λₘₐₓ (ΓT Γ), where λₘₐₓ 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 log2n 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 Γ, it is possible to find an embedding such that ΓT Γ has eigenvalues that can be put into a one-to-one correspondence with the eigenvalues of the Laplacian. Specifically, if λ is a nonzero eigenvalue of either matrix, then n / λ 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 Γ 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.