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/\max(Γ^TΓ), where \max indicates the largest eigenvalue of the specified matrix. However, the best bounds produced by embedding …