Discrete Curvature and Abelian Groups
Bo’az Klartaga b, Gady Kozmac, Peter Rallid e, Prasad Tetalid e
- aSchool of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel e-mail:
- bTel Aviv 69978
- cDepartment of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel e-mail:
- dSchool of Mathematics and School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA e-mail:
- e[Georgia Institute of Technology.]
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
Abstract We study a natural discrete Bochner-type inequality on graphs, and explore its merit as a notion of “curvature” in discrete spaces. An appealing feature of this discrete version of the so-called Γ2-calculus (of Bakry-Émery) seems to be that it is fairly straightforward to compute this notion of curvature parameter for several specific graphs of interest, particularly, abelian groups, slices of the hypercube, and the symmetric group under various sets of generators. We further develop this notion by deriving Buser-type inequalities (à la Ledoux), relating functional and isoperimetric constants associated with a graph. Our derivations provide a tight bound on the Cheeger constant (i.e., the edge-isoperimetric constant) in terms of the spectral gap, for graphs with nonnegative curvature, particularly, the class of abelian Cayley graphs, a result of independent interest.