The graph curvature calculator and the curvatures of cubic graphs

DOI10.1080/10586458.2019.1660740zbMATH Open1494.05028arXiv1712.03033OpenAlexW2972766977WikidataQ125925090 ScholiaQ125925090MaRDI QIDQ5094491FDOQ5094491

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)

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.

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

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

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)

Cites Work

• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• Optimal Transport
• Spectra of graphs
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of finite Markov chains via convexity of the entropy
• Expander graphs in pure and applied mathematics
• Ricci curvature of graphs
• Ramanujan graphs
• Title not available (Why is that?)
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Random Cayley graphs and expanders
• The Geometric Meaning of Curvature: Local and Nonlocal Aspects of Ricci Curvature
• A survey of Ricci curvature for metric spaces and Markov chains
• Bochner's method for cell complexes and combinatorial Ricci curvature
• Ricci curvature on polyhedral surfaces via optimal transportation
• Curvature aspects of graphs
• Discrete curvature and abelian groups
• Modern approaches to discrete curvature
• Forman curvature for complex networks
• Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian
• Bakry–Émery Curvature Functions on Graphs
• Ollivier--Ricci Idleness Functions of Graphs
• Combinatorial quantum gravity: geometry from random bits
• Bakry-Émery curvature and diameter bounds on graphs
• Eigenvalue Ratios of Non-Negatively Curved Graphs
• Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds

Cited In (9)

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

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)