Edge-Connectivity versus Lin--Lu--Yau Curvature
math.CO, math.DG
Submitted: 2026-09-30
Updated: 2026-11-02
License: http://creativecommons.org/publicdomain/zero/1.0/
The gist: We systematically explore the relationship between edge-connectivity and Lin--Lu--Yau curvature for graphs.
Abstract
We systematically explore the relationship between edge-connectivity and Lin--Lu--Yau curvature for graphs. The intuition is that a connected graph with large Lin--Lu--Yau curvature should also have large edge-connectivity, and vice versa under suitable conditions. We prove that the edge-connectivity of a connected graph is bounded lower by the product of its minimum degree, its Lin--Lu--Yau curvature and the constant 3 over 2. We also provide two lower bounds on the edge-connectivity of a graph that guarantee positive Lin--Lu--Yau curvature, and discuss the sharpness of these bounds.
Sources
- A note on non-regular Bonnet-Myers Sharp Graphs
- A condition for non-negative Lin-Lu-Yau curvature
- Optimal transport and Ricci curvature for metric-measure spaces
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality