Metric uniformization and spectral bounds for graphs

DOI10.1007/S00039-011-0132-9MaRDI QIDQ659931zbMATH OpenOpenAlexWikidataFDO

Authors Jonathan Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng

Publication date 24 January 2012

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.3594

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Planar graphs; geometric and topological aspects of graph theory (05C10) Metric geometry (51F99) Circle packings and discrete conformal geometry (52C26) General theory of differentiable manifolds (58A99)

Abstract: We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate "Riemannian" metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the kth smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k=2.

Recommendations

• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs
• A transfer principle and applications to eigenvalue estimates for graphs
• Spectral gap of the largest eigenvalue of the normalized graph Laplacian
• On sums of graph eigenvalues

Cites work

• scientific article; zbMATH DE number 3136785 (Why is no real title available?)
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 3678793 (Why is no real title available?)
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 3698075 (Why is no real title available?)
• scientific article; zbMATH DE number 1303002 (Why is no real title available?)
• scientific article; zbMATH DE number 1303610 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 6297701 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 3356292 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• A separator theorem for graphs of bounded genus
• An r-Dimensional Quadratic Placement Algorithm
• An extremal function for contractions of graphs
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Diameters and Eigenvalues
• Divide-and-conquer approximation algorithms via spreading metrics
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Eigenvalues and expanders
• Eigenvectors of acyclic matrices
• Excluded minors, network decomposition, and multicommodity flow
• Extending Lipschitz functions via random metric partitions
• Finite-Difference Approach to the Hodge Theory of Harmonic Forms
• Geometric Separators for Finite-Element Meshes
• Graph Coloring Using Eigenvalue Decomposition
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Graph minors. XX: Wagner's conjecture
• Kreisausfüllungen der hyperbolischen Ebene
• Lower Bounds for the Partitioning of Graphs
• Measured descent: A new embedding method for finite metrics
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Spectral partitioning works: planar graphs and finite element meshes
• Triangulations and moduli spaces of Riemann surfaces with group actions
• Upper bounds for eigenvalues of conformal metrics
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(14)

• Multi-way dual Cheeger constants and spectral bounds of graphs
• Eigenvalues of the Laplacian on the Goldberg-Coxeter constructions for 3- and 4-valent graphs
• Approximating unique games using low diameter graph decomposition
• Discrete uniformizing metrics on distributional limits of sphere packings
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs
• Separators in region intersection graphs
• Network cluster-robust inference
• Quasimetric embeddings and their applications
• Conformal growth rates and spectral geometry on distributional limits of graphs
• scientific article; zbMATH DE number 915266 (Why is no real title available?)
• A transfer principle and applications to eigenvalue estimates for graphs
• A Schur complement Cheeger inequality
• Sharp bounds on random walk eigenvalues via spectral embedding

Describes a project that uses

Uses Software

• MESHPART

This page was built for publication: Metric uniformization and spectral bounds for graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659931)