Curvature on graphs via equilibrium measures

DOI10.1002/JGT.22925MaRDI QIDQ6074588zbMATH OpenFDO

Authors Stefan Steinerberger

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

Bonnet-Myers theoremcurvatureLichnerowicz theoremvon Neumann Minimax theorem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Discrete potential theory (31C20) Local Riemannian geometry (53B20) Global Riemannian geometry, including pinching (53C20) Applications of game theory (91A80)

Abstract: We introduce a notion of curvature on finite, combinatorial graphs. It can be easily computed by solving a linear system of equations. We show that graphs with curvature bounded below by $K>0$ have diameter bounded by $mboxdiam(G)leq2/K$ (a Bonnet-Myers theorem), that $mboxdiam(G)=2/K$ implies that $G$ has constant curvature (a Cheng theorem) and that there is a spectral gap $lambd{a}_{1}geqK/(2n)$ (a Lichnerowicz theorem). It is computed for several families of graphs and often coincides with Ollivier curvature or Lin-Lu-Yau curvature. The von Neumann minimax theorem features prominently in the proofs.

Recommendations

• Bakry-Émery curvature and diameter bounds on graphs
• Large scale Ricci curvature on graphs
• Distance bounds for graphs with some negative Bakry-Émery curvature
• Volume doubling, Poincaré inequality and Gaussian heat kernel estimate for non-negatively curved graphs
• Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature

Cites work

• A combinatorial analogue of a theorem of Myers
• A curved Brunn-Minkowski inequality on the discrete hypercube, or: what is the Ricci curvature of the discrete hypercube?
• A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points
• A note on tilings and strong isoperimetric inequality
• A survey of Ricci curvature for metric spaces and Markov chains
• Bochner's method for cell complexes and combinatorial Ricci curvature
• Combinatorial curvature for planar graphs
• Curvature aspects of graphs
• Eigenvalue comparison theorems and its geometric applications
• Erratum to: ``Ricci-flat graphs with girth at least five
• Gradient flows of the entropy for finite Markov chains
• scientific article; zbMATH DE number 3156874 (Why is no real title available?)
• scientific article; zbMATH DE number 3894218 (Why is no real title available?)
• scientific article; zbMATH DE number 3205078 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Introduction to analysis on graphs
• Metric measure spaces with Riemannian Ricci curvature bounded from below
• Numerical Geometry-Numbers for Shapes
• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Ollivier-Ricci idleness functions of graphs
• On the geometry of metric measure spaces. II
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Ricci curvature for metric-measure spaces via optimal transport
• Ricci curvature of graphs
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of metric spaces
• Ricci-flat graphs with girth at least five
• Riemannian manifolds with positive mean curvature
• Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature
• The first eigenvector of a distance matrix is nearly constant
• The geometric meaning of curvature: local and nonlocal aspects of Ricci curvature
• The Rendezvous Number of a Symmetric Matrix and a Compact Connected Metric Space
• Volume doubling, Poincaré inequality and Gaussian heat kernel estimate for non-negatively curved graphs

Cited in

(25)

• Total curvature of graphs in Euclidean spaces
• Curvature dimension of trivalent graphs
• A global Poincaré inequality on graphs via a conical curvature-dimension condition
• Bakry-Émery curvature and diameter bounds on graphs
• A homology vanishing theorem for graphs with positive curvature
• Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature
• Large scale Ricci curvature on graphs
• The first eigenvector of a distance matrix is nearly constant
• Discrete curvature and abelian groups
• Curvature calculations for antitrees
• The geometric spectrum of a graph and associated curvatures
• Curvature on a graph via its geometric spectrum
• Sums of distances on graphs and embeddings into Euclidean space
• Cheng's maximal diameter theorem for hypergraphs
• Mean distance on metric graphs
• Graph curvature via resistance distance
• Curvature, diameter and signs of graphs
• Graph curvature and local discrepancy
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• On Steinerberger curvature and graph distance matrices
• Entropy and curvature: beyond the Peres-Tetali conjecture
• A decomposition theorem for balanced measures
• An exploration of graph distances, graph curvature, and applications to network analysis
• On the minimum constant resistance curvature conjecture of graphs
• Cayley-Menger curvature: a geometric approach to discrete curvature on graphs via local simplex embedding

This page was built for publication: Curvature on graphs via equilibrium measures

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