The graph curvature calculator and the curvatures of cubic graphs

DOI10.1080/10586458.2019.1660740MaRDI QIDQ5094491zbMATH OpenOpenAlexWikidataFDO

Authors David Cushing, Riikka Kangaslampi, Valtteri Lipiäinen, Shiping Liu, George W. Stagg

Publication date 3 August 2022

Published in Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cubic graphexpander graphdiscrete curvaturegraph curvature calculator

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Planar graphs; geometric and topological aspects of graph theory (05C10) Discrete version of topics in analysis (39A12) Synthetic differential geometry (51K10) Expander graphs (05C48)

Abstract: We classify all cubic graphs with either non-negative Ollivier-Ricci curvature or non-negative Bakry-'Emery curvature everywhere. We show in both curvature notions that the non-negatively curved graphs are the prism graphs and the M"obius ladders. We also highlight an online tool for calculating the curvature of graphs under several variants of these curvature notions that we use in the classification. As a consequence of the classification result we show, that non-negatively curved cubic expanders do not exist.

Recommendations

• Ricci-flat cubic graphs with girth five
• Sparse expanders have negative curvature
• Curvature calculations for antitrees
• Curvatures, graph products and Ricci flatness
• Quartic graphs which are Bakry-Émery curvature sharp

Cites work

• scientific article; zbMATH DE number 1185220 (Why is no real title available?)
• A survey of Ricci curvature for metric spaces and Markov chains
• Bakry-Émery curvature and diameter bounds on graphs
• Bakry-Émery curvature functions on graphs
• Bochner's method for cell complexes and combinatorial Ricci curvature
• Combinatorial quantum gravity: geometry from random bits
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Curvature aspects of graphs
• Discrete curvature and abelian groups
• Eigenvalue ratios of non-negatively curved graphs
• Expander graphs in pure and applied mathematics
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Forman curvature for complex networks
• Modern approaches to discrete curvature
• Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Ollivier-Ricci idleness functions of graphs
• Optimal Transport
• Ramanujan graphs
• Random Cayley graphs and expanders
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of finite Markov chains via convexity of the entropy
• Ricci curvature of graphs
• Ricci curvature on polyhedral surfaces via optimal transportation
• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• Spectra of graphs
• The geometric meaning of curvature: local and nonlocal aspects of Ricci curvature

Cited in

(10)

• Emergence of the circle in a statistical model of random cubic graphs
• Curvature calculations for antitrees
• Bakry-Émery curvature functions on graphs
• Graph curvature and local discrepancy
• Curvature, diameter and signs of graphs
• Bakry-Émery curvature on graphs as an eigenvalue problem
• Sparse expanders have negative curvature
• Curvatures, graph products and Ricci flatness
• Long-scale ollivier Ricci curvature of graphs
• Rigidity properties of the hypercube via Bakry-Émery curvature

Describes a project that uses

Uses Software

• jQuery
• SciPy
• NumPy
• Cytoscape.js

This page was built for publication: The graph curvature calculator and the curvatures of cubic graphs

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