Bounded-degree graphs of non-negative Ollivier-Ricci curvature have subexponential growth and diffusive random walk
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912746732257280 |
|---|---|
| author | Hutchcroft, Tom Münch, Florentin |
| author_facet | Hutchcroft, Tom Münch, Florentin |
| contents | We study the geometric properties of graphs with non-negative Ollivier-Ricci curvature, a discrete analogue of non-negative Ricci curvature in Riemannian geometry. We prove that for each $d<\infty$ there exists a constant $C_d$ such that if $G=(V,E)$ is a finite graph with non-negative Ollivier-Ricci curvature and with degrees bounded by $d$ then the average log-volume growth and random walk displacement satisfy \[
\frac{1}{|V|} \sum_{x\in V} \log \#B(x,r) \leq \exp\left[C_d \sqrt{\log r}\right] = r^{o(1)} \] and \[
\frac{1}{|V|} \sum_{x\in V} \mathbf{E}_x [d(X_0,X_n)^2] \leq n \exp\left[C_d \sqrt{\log n}\right] = n^{1+o(1)} \] for every $n,r\geq 2$. This significantly strengthens a result of Salez (GAFA 2022), who proved that the average displacement of the random walk is $o(n)$ and deduced that non-negatively curved graphs of bounded degree cannot be expanders. Our results also apply to infinite transitive graphs and, more generally, to bounded-degree unimodular random rooted graphs of non-negative Ollivier-Ricci curvature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03968 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounded-degree graphs of non-negative Ollivier-Ricci curvature have subexponential growth and diffusive random walk Hutchcroft, Tom Münch, Florentin Differential Geometry Combinatorics Metric Geometry Probability We study the geometric properties of graphs with non-negative Ollivier-Ricci curvature, a discrete analogue of non-negative Ricci curvature in Riemannian geometry. We prove that for each $d<\infty$ there exists a constant $C_d$ such that if $G=(V,E)$ is a finite graph with non-negative Ollivier-Ricci curvature and with degrees bounded by $d$ then the average log-volume growth and random walk displacement satisfy \[ \frac{1}{|V|} \sum_{x\in V} \log \#B(x,r) \leq \exp\left[C_d \sqrt{\log r}\right] = r^{o(1)} \] and \[ \frac{1}{|V|} \sum_{x\in V} \mathbf{E}_x [d(X_0,X_n)^2] \leq n \exp\left[C_d \sqrt{\log n}\right] = n^{1+o(1)} \] for every $n,r\geq 2$. This significantly strengthens a result of Salez (GAFA 2022), who proved that the average displacement of the random walk is $o(n)$ and deduced that non-negatively curved graphs of bounded degree cannot be expanders. Our results also apply to infinite transitive graphs and, more generally, to bounded-degree unimodular random rooted graphs of non-negative Ollivier-Ricci curvature. |
| title | Bounded-degree graphs of non-negative Ollivier-Ricci curvature have subexponential growth and diffusive random walk |
| topic | Differential Geometry Combinatorics Metric Geometry Probability |
| url | https://arxiv.org/abs/2512.03968 |