Limiting distributions and critical-window behavior of the Lin–Lu–Yau Ricci curvature of Erdős–Rényi random graphs

The Lin–Lu–Yau Ricci curvature $\kappa(x,y)$ of a graph is the limit, as the idleness parameter $\alpha$ tends to $1$, of Ollivier's coarse curvature $\kappa_\alpha(x,y)$ normalized by $(1-\alpha)$. Lin, Lu and Yau (2011) proved that on the Erdős–Rényi random graph $G(n,p)$, conditioned on an edge being present, $\kappa(x,y)$ is known to leading order almost surely: it equals $(1+o(1))p$ in the dense regime, satisfies $\kappa(x,y)=O((\ln n)/(np^2))$ in an intermediate window, and tends to $-1$ and $-2$ in the two sparse regimes, with crossovers at the scales $p\asymp n^{-1/3}$, $p\asymp n^{-1/2}$ and $p\asymp n^{-2/3}$ (up to logarithmic corrections). What remains unknown is the fine structure: fluctuation scales, limiting distributions, finite-size corrections, the behavior exactly at the crossover scales, and the locally tree-like window $np\to\lambda$. For Ollivier's idleness-$0$ curvature the analogous theory is known — constant limits in all regimes and convergence in distribution to the curvature of the Poisson Galton–Watson limiting tree (Bhattacharya–Mukherjee, 2015) — but the two curvature notions genuinely differ, and the corresponding picture for the Lin–Lu–Yau curvature is open.

Background

On a Riemannian manifold, Ricci curvature controls how volumes and distances between geodesics deform, and positive lower bounds on it imply comparison theorems such as Bonnet–Myers (diameter bounds) and Lichnerowicz (eigenvalue bounds). Ollivier (2009) transferred this idea to Markov chains on arbitrary metric spaces, in particular graphs. For a locally finite graph $G$ with graph distance $d(\cdot,\cdot)$ and vertex degrees $d_x$, let $m_x^\alpha$ be the $\alpha$-lazy random-walk probability measure at $x$, placing mass $\alpha$ at $x$ and $(1-\alpha)/d_x$ at each neighbor. The $L^1$-transportation distance $W(m_x^\alpha,m_y^\alpha)$ is the infimum of $\mathbb{E}\,d(U,V)$ over all couplings $(U,V)$ of the two measures, and Ollivier's coarse curvature is $\kappa_\alpha(x,y)=1-W(m_x^\alpha,m_y^\alpha)/d(x,y)$. Lin, Lu and Yau (2011) introduced the modification now called the Lin–Lu–Yau curvature,

$$\kappa(x,y)=\lim_{\alpha\to 1^-}\frac{\kappa_\alpha(x,y)}{1-\alpha},$$

which exists because $\alpha\mapsto\kappa_\alpha(x,y)$ is concave and $\kappa_\alpha(x,y)\le 2(1-\alpha)/d(x,y)$. This limit linearizes the transport deficit of the almost-non-moving walk and differs from Ollivier's idleness-$0$ value $\kappa_0$ (the case $\alpha=0$, in which the walk always moves): for instance, hypercubes $Q_n$ and complete bipartite graphs $K_{n,n}$ have strictly positive Lin–Lu–Yau curvature while $\kappa_0$ vanishes on every edge (Bourne–Cushing–Liu–Münch–Peyerimhoff 2018; Hehl 2024; Liu–Yang 2026 characterize exact relations between the two notions). On finite graphs, Lin–Lu–Yau proved a discrete Bonnet–Myers theorem ($\operatorname{diam}(G)\le 2/\kappa$ when every edge satisfies $\kappa(x,y)\ge\kappa>0$), a discrete Lichnerowicz bound ($\lambda_1\ge\kappa$ for the first nonzero eigenvalue of the normalized graph Laplacian, the operator $I-D^{-1/2}AD^{-1/2}$ with $A$ the adjacency matrix and $D$ the degree matrix), a vertex-count bound $n\le 1+\sum_{k=1}^{\lfloor 2/\kappa\rfloor}\Delta^k\prod_{i=1}^{k-1}(1-i\kappa/2)$ in the maximum degree $\Delta$, and an exact Cartesian-product formula for regular factors — the comparison-geometry toolkit that motivated studying this curvature on random graphs.

In the Erdős–Rényi random graph $G(n,p)$, each of the $\binom{n}{2}$ vertex pairs is an edge independently with probability $p=p(n)$. Lin–Lu–Yau's Theorem 5.1 gives, conditioned on a fixed pair $x,y$ being an edge, the following almost-sure statements (probability tending to one as $n\to\infty$): (1) if $p\ge\sqrt[3]{(\ln n)/n}$ then $\kappa(x,y)=p+O(\sqrt{\ln n/(np)})$, and $\kappa(x,y)=(1+o(1))p$ when $p\gg\sqrt[3]{(\ln n)/n}$; (2) if $\sqrt[3]{(\ln n)/n}>p\ge 2\sqrt{(\ln n)/n}$ then $\kappa(x,y)=O((\ln n)/(np^2))$; (3) if $1/\sqrt{n}\gg p\gg\sqrt[3]{(\ln n)/n^2}$ then $\kappa(x,y)=-1+O(np^2)+O((\ln n)/(n^2p^3))$; (4) if $\sqrt[3]{(\ln n)/n^2}\gg p\gg(\ln n)/n$ then $\kappa(x,y)=-2+O(n^2p^3)+O(\sqrt{\ln n/(np)})$. The leading-order value thus jumps between $p$, $-1$ and $-2$ as $p$ decreases, with crossover scales $p\asymp n^{-1/3}$, $p\asymp n^{-1/2}$ and $p\asymp n^{-2/3}$ up to logarithmic factors, while in the intermediate window Theorem 5.1 provides only the upper bound $O((\ln n)/(np^2))$ and does not determine the leading-order value there; below $p\asymp(\ln n)/n$ the graph becomes locally tree-like, in the sense that rooted graph neighborhoods converge locally weakly (Benjamini–Schramm convergence of rooted neighborhoods to a limiting infinite graph) to a Poisson$(\lambda)$ Galton–Watson tree — the family tree of a branching process in which each vertex independently begets a Poisson$(\lambda)$ number of children — when $np\to\lambda$.

For Ollivier's idleness-$0$ curvature the finer theory is known. Jost and Liu proved the sharp bound $\kappa_0(x,y)\ge-2(1-1/d_x-1/d_y)_+$, with equality on trees, and Bhattacharya–Mukherjee (2015) showed that in $G(n,p)$, conditioned on an edge, $\kappa_0$ converges in probability to the appropriate constant ($0$, $-2$, $-1$, $0$, $p$) in every regime, and converges in distribution to $-2\bigl(1-\tfrac{1}{1+X_1}-\tfrac{1}{1+X_2}\bigr)_+$ with $X_1,X_2$ independent Poisson$(\lambda)$ when $np\to\lambda$, i.e., to the curvature of the limiting tree. No analogue of these fine results is known for the Lin–Lu–Yau curvature $\kappa$ itself, whose definition involves the singular limit $\alpha\to1^-$ of transport distances and which genuinely differs from $\kappa_0$.

Problem Statement

Determine the fine asymptotic theory of the Lin–Lu–Yau Ricci curvature $\kappa(x,y)=\lim_{\alpha\to1^-}\kappa_\alpha(x,y)/(1-\alpha)$ — where $\kappa_\alpha(x,y)=1-W(m_x^\alpha,m_y^\alpha)/d(x,y)$ is Ollivier's coarse curvature of the $\alpha$-lazy random walk between the two endpoints of the edge — on edges of the Erdős–Rényi random graph $G(n,p)$, conditioned on the edge being present, completing Lin–Lu–Yau's Theorem 5.1 beyond leading-order almost-sure constants. Concretely:

(1) Fluctuations and limit laws in the principal regimes. In each of the four regimes of Theorem 5.1 — $p\ge\sqrt[3]{(\ln n)/n}$ (where $\kappa(x,y)=p+O(\sqrt{\ln n/(np)})$); $\sqrt[3]{(\ln n)/n}>p\ge 2\sqrt{(\ln n)/n}$ (where $\kappa(x,y)=O((\ln n)/(np^2))$); $1/\sqrt{n}\gg p\gg\sqrt[3]{(\ln n)/n^2}$ (where $\kappa(x,y)=-1+O(np^2)+O((\ln n)/(n^2p^3))$); and $\sqrt[3]{(\ln n)/n^2}\gg p\gg(\ln n)/n$ (where $\kappa(x,y)=-2+O(n^2p^3)+O(\sqrt{\ln n/(np)})$) — determine the fluctuation scale of $\kappa(x,y)$ around its leading-order value and its limiting distribution (after suitable centering and normalization, or the degenerate constant limit if fluctuations vanish), together with sharp finite-size corrections; in the second regime Theorem 5.1 provides only the upper bound $O((\ln n)/(np^2))$, so determining the actual leading-order value there is part of the problem.

(2) Critical windows. At each crossover scale — $p\asymp\sqrt[3]{(\ln n)/n}$, $p\asymp\sqrt{(\ln n)/n}$, $p\asymp\sqrt[3]{(\ln n)/n^2}$, and the scale $p\asymp(\ln n)/n$ at which the fourth regime of Theorem 5.1 ends — where the leading-order constant jumps between $p$, $-1$ and $-2$, determine the typical value of $\kappa(x,y)$, its fluctuations, and its limiting law.

(3) The locally tree-like window. When $np\to\lambda\in(0,\infty)$, determine whether $\kappa(x,y)$ converges in distribution and identify the limit — in particular whether the limit is the Lin–Lu–Yau curvature of an edge in the Poisson$(\lambda)$ Galton–Watson local weak limit, the analogue of Bhattacharya–Mukherjee's convergence of the idleness-$0$ curvature to the Jost–Liu tree value $-2(1-1/(1+X_1)-1/(1+X_2))_+$ with $X_1,X_2$ independent Poisson$(\lambda)$.

Determine the fine asymptotics of $\kappa(x,y)$ for every $p=p(n)$ with $np\to\infty$ — including the band $1/n\ll p\ll(\ln n)/n$, where $np\to\infty$ but $np=o(\ln n)$ and Theorem 5.1 leaves the range uncovered — and the distributional limit in the locally tree-like window $np\to\lambda\in(0,\infty)$.

References

1. Yong Lin, Linyuan Lu, Shing-Tung Yau, 'Ricci curvature of graphs', Tohoku Mathematical Journal (2) 63(4) (2011) 605–627, DOI 10.2748/tmj/1325886283, https://doi.org/10.2748/tmj/1325886283.
2. Yann Ollivier, 'Ricci curvature of Markov chains on metric spaces', Journal of Functional Analysis 256(3) (2009) 810–864, DOI 10.1016/j.jfa.2008.11.001, https://doi.org/10.1016/j.jfa.2008.11.001.
3. Bhaswar B. Bhattacharya, Sumit Mukherjee, 'Exact and asymptotic results on coarse Ricci curvature of graphs', Discrete Mathematics 338(1) (2015) 23–42, DOI 10.1016/j.disc.2014.08.012, arXiv:1306.6741, https://arxiv.org/abs/1306.6741.
4. Jürgen Jost, Shiping Liu, 'Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs', arXiv:1103.4037 (2011), https://arxiv.org/abs/1103.4037.
5. David Bourne, David Cushing, Shiping Liu, Florentin Münch, Norbert Peyerimhoff, 'Ollivier-Ricci idleness functions of graphs', SIAM Journal on Discrete Mathematics 32(2) (2018) 1408–1424, arXiv:1704.04398, https://arxiv.org/abs/1704.04398.
6. Moritz Hehl, 'Ollivier-Ricci curvature of regular graphs', arXiv:2407.08854 (2024), https://arxiv.org/abs/2407.08854.
7. Moritz Hehl, 'Graphs with Lin-Lu-Yau curvature at least one and regular bone-idle graphs', Calculus of Variations and Partial Differential Equations (2025), DOI 10.1007/s00526-025-03052-z, arXiv:2411.12772, https://arxiv.org/abs/2411.12772.
8. Shiping Liu, Yunyan Yang, 'Equivalence of Lin–Lu–Yau curvature and 1/2-Ollivier curvature on weighted graphs', arXiv:2608.05939 (2026), https://arxiv.org/abs/2608.05939.
9. David Cushing, Supanat Kamtue, Riikka Kangaslampi, Shiping Liu, Norbert Peyerimhoff, 'Curvatures, graph products and Ricci flatness', Journal of Graph Theory 96(4) (2021) 522–553, DOI 10.1002/jgt.22630, arXiv:1909.11565, https://arxiv.org/abs/1909.11565.
10. Guiqiang Mou, 'Ricci Curvature of Strong Product Graphs', arXiv:2506.13269 (2025), https://arxiv.org/abs/2506.13269.
11. Jaewoo Jung, Young Soo Kwon, Seungjae Lee, Jihye Park, 'A combinatorial Approach to $\alpha$-Ricci and Lin-Lu-Yau Ricci curvatures on Graphs', arXiv:2606.24261 (2026), https://arxiv.org/abs/2606.24261.
12. David Cushing, Supanat Kamtue, Jack Koolen, Shiping Liu, Florentin Münch, Norbert Peyerimhoff, 'Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature', Advances in Mathematics 369 (2020) 107188, DOI 10.1016/j.aim.2020.107188, arXiv:1807.02384, https://arxiv.org/abs/1807.02384.
13. Yupei Li, Linyuan Lu, 'Ricci Curvature Formula: Applications to Bonnet-Myers Sharp Irregular Graphs', arXiv:2409.15667 (2024), https://arxiv.org/abs/2409.15667.
14. Linyuan Lu, Zhiyu Wang, 'On the size of planar graphs with positive Lin-Lu-Yau Ricci curvature', European Journal of Combinatorics (2026), DOI 10.1016/j.ejc.2026.104355, arXiv:2010.03716, https://arxiv.org/abs/2010.03716.
15. Xiaonan Liu, Linyuan Lu, Zhiyu Wang, 'On the size of outerplanar graphs with positive Lin-Lu-Yau Ricci curvature', arXiv:2409.13666 (2024), https://arxiv.org/abs/2409.13666.
16. Kaizhe Chen, Shiping Liu, Zhe You, 'An extremal theorem for positive curvature of graphs', arXiv:2607.02297 (2026), https://arxiv.org/abs/2607.02297.
17. Frank Bauer, Jürgen Jost, Shiping Liu, 'Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator', arXiv:1105.3803 (2011), https://arxiv.org/abs/1105.3803.
18. Kaizhe Chen, Shiping Liu, Heng Zhang, 'On Lichnerowicz sharp distance-regular graphs', Discrete Mathematics (to appear in a 2027 issue), DOI 10.1016/j.disc.2026.115360, arXiv:2602.10396, https://arxiv.org/abs/2602.10396.
19. Florentin Münch, 'Reflective Graphs, Ollivier curvature, effective diameter, and rigidity', arXiv:2205.15857 (2022), https://arxiv.org/abs/2205.15857.
20. Yanlong Ding, Shiping Liu, Chiyu Zhou, 'Regular Lichnerowicz-sharp graphs are hypercube bundles', arXiv:2606.08006 (2026), https://arxiv.org/abs/2606.08006.
21. Florentin Münch, Radoslaw K. Wojciechowski, 'Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds', Advances in Mathematics 356 (2019) 106759, DOI 10.1016/j.aim.2019.106759, arXiv:1712.00875, https://arxiv.org/abs/1712.00875.
22. Mark Kempton, Gabor Lippner, Florentin Münch, 'Large scale Ricci curvature on graphs', arXiv:1906.06222 (2019), https://arxiv.org/abs/1906.06222.
23. Camillo Brena, Tom Hutchcroft, Florentin Münch, 'Transitive graphs of non-negative Ollivier-Ricci curvature have polynomial growth', arXiv:2512.03968 (2025), https://arxiv.org/abs/2512.03968.
24. Huiqiu Lin, Zhe You, Da Zhao, 'Bipartite graphs, random graphs, and Lin–Lu–Yau curvature', arXiv:2607.22420 (2026), https://arxiv.org/abs/2607.22420.
25. Varun Kotharkar, 'LLY Ricci Reweighting in Stochastic Block Models: Uniform Curvature Concentration and Finite-Horizon Tracking', arXiv:2603.11060 (2026), https://arxiv.org/abs/2603.11060.
26. Pim van der Hoorn, Gabor Lippner, Carlo Trugenberger, Dmitri Krioukov, 'Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds', Discrete & Computational Geometry 70(3) (2023) 671–712, DOI 10.1007/s00454-023-00507-y, arXiv:2009.04306, https://arxiv.org/abs/2009.04306.
27. Justin Salez, 'Sparse expanders have negative curvature', arXiv:2101.08242 (2021), https://arxiv.org/abs/2101.08242.