Metric uniformization and spectral bounds for graphs

DOI10.1007/S00039-011-0132-9zbMATH Open1229.05094arXiv1008.3594OpenAlexW2963487913WikidataQ125324258 ScholiaQ125324258MaRDI QIDQ659931FDOQ659931

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)

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.

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

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

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)

Cites Work

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

Cited In (15)

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

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)