A relation between isoperimetry and total variation decay with applications to graphs of non-negative Ollivier-Ricci curvature

2024/11/07 by Hutchcroft, Tom, Lopez, Isaac M. · 1 citation
#Differential Geometry (math.DG) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2411.04988

Abstract

We prove an inequality relating the isoperimetric profile of a graph to the decay of the random walk total variation distance sup_{x∼ y} ||Pⁿ(x,⋅)-Pⁿ(y,⋅)||_TV. This inequality implies a quantitative version of a theorem of Salez (GAFA 2022) stating that bounded-degree graphs of non-negative Ollivier-Ricci curvature cannot be expanders. Along the way, we prove universal upper-tail estimates for the random walk displacement d(X₀,X_n) and information -log Pⁿ(X₀,X_n), which may be of independent interest.

Cited by

• Bounded-degree graphs of non-negative Ollivier-Ricci curvature have subexponential growth and diffusive random walk

Related

• Bounded-degree graphs of non-negative Ollivier-Ricci curvature have subexponential growth and diffusive random walk
• Ollivier Ricci curvature for general graph Laplacians: Heat equation,\n Laplacian comparison, non-explosion and diameter bounds
• Pointwise subexponential growth and near-diffusive displacement on bounded-degree graphs with non-negative Ollivier--Ricci curvature
• Ollivier curvature, Isoperimetry, concentration, and Log-Sobolev inequalitiy
• Probabilistic and Geometrical Applications to Graph Theory