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

Abstract

We prove an inequality relating the isoperimetric profile of a graph to the decay of the random walk total variation distance ${\sup }_{x\sim y}||P^n(x,\cdot )-P^n(y,\cdot )|{|}_{\mathrm{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_0,X_n)$ and information $-\log P^n(X_0,X_n)$, which may be of independent interest.

12 pages