Pure and Applied Mathematics Quarterly

Volume 18 (2022)

Number 6

Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

Concentration inequalities in spaces of random configurations with positive Ricci curvatures

Pages: 2569 – 2598

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a11


Linyuan Lu (University of South Carolina, Columbia, S.C., U.S.A.)

Zhiyu Wang (Georgia Institute of Technology, Atlanta, Ga., U.S.A.)


In this paper, we prove an Azuma–Hoeffding-type inequality in several classical models of random configurations by a Ricci curvature approach. Adapting Ollivier’s work on the Ricci curvature of Markov chains on metric spaces, we prove a cleaner form of the corresponding concentration inequality in graphs. Namely, we show that for any Lipschitz function $f$ on any graph (equipped with an ergodic random walk and thus an invariant distribution $\nu$) with Ricci curvature at least $\kappa \gt 0$, we have\[\nu (\lvert f - E_\nu f \rvert \geq t) \leq 2 \exp \left( - \dfrac{t^2 \kappa}{7} \right) \: \textrm{.}\]


Ricci curvature, concentration inequality, random graphs

2010 Mathematics Subject Classification

Primary 05C81. Secondary 53C44, 60F10.

The first-named author was supported in part by NSF grant DMS-1600811 and NSF DMS-2038080.

Received 27 May 2021

Received revised 3 June 2022

Accepted 10 November 2022

Published 29 March 2023