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 cliq ue embedding into the underlying graph of the Laplacian. An embedding can b e represented by a matrix Gamma; the best possible bound based on this embe dding is n/lambda(max)(Gamma(Gamma)Gamma), where lambda(max) indicates the largest eigenvalue of the specified matrix. However, the best bounds produc ed by embedding techniques are not tight; they can be off by a factor propo rtional to log(2) n for some Laplacians. We show that this gap is a result of the representation of the embedding: B y including edge directions in the embedding matrix representation Gamma, i t is possible to find an embedding such that Gamma(Gamma)Gamma has eigenval ues that can be put into a one-to-one correspondence with the eigenvalues o f 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 produ ces these correspondences has a simple description in electrical terms if t he underlying graph of the Laplacian is viewed as a resistive circuit. We a lso show that a similar technique works for star embeddings when the Laplac ian 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 t he Laplacian. Finally, we connect our results with previous techniques for producing bounds and provide an example.