Curvature notions on graphs

Abstract

We survey some geometric and analytic results under the assumptions of combinatorial curvature bounds for planar/semiplanar graphs and curvature dimension conditions for general graphs.

Keywords

Planar graphs / combinatorial curvature / curvature dimension conditions / harmonic functions

References

[1] Bauer F, Horn P, Lin Y, Lippner G, Mangoubi D, Yau S-T. Li-Yau inequality on graphs. J Differential Geom, 2015, 99(3): 359–405

[2] Bauer F, Hua B, Jost J, Liu S. Generalized Ricci curvature and the geometry of graphs. In: Najman L, Romon P, eds. Discrete Curvature: Theory and Applications. Luminy: Cedram, 2014, 69–78

[3] Bauer F, Hua B, Jost J, Liu S, Wang G. The geometric meaning of curvature. Local and nonlocal aspects of Ricci curvature. In: Najman L, Romon P, eds. Modern Approaches to Discrete Curvature (to appear)

[4] Bauer F, Hua B, Yau S-T. Davies–Gaffney–Grigor’yan Lemma on graphs. Comm Anal Geom, 2015, 23(5): 1031–1068

[5] Burago D, Burago Yu, Ivanov S. A Course in Metric Geometry. Grad Stud Math, Vol 33. Providence: Amer Math Soc, 2001

[6] Chen B. The Gauss-Bonnet formula of polytopal manifolds and the characterization of embedded graphs with nonnegative curvature. Proc Amer Math Soc, 2008, 137(5): 1601–1611

[7] Chen B, Chen G. Gauss-Bonnet formula, finiteness condition, and characterizations of graphs embedded in surfaces. Graphs Combin, 2008, 24(3): 159–183

[8] Colding T H, Minicozzi II W P. Harmonic functions with polynomial growth. J Differential Geom, 1997, 46(1): 1–77

[9] Colding T H, Minicozzi II W P. Harmonic functions on manifolds. Ann of Math, 1997, 146(3): 725–747

[10] Colding T H, Minicozzi II W P. Liouville theorems for harmonic sections and applications. Comm Pure Appl Math, 1998, 51(2): 113–138

[11] Colding T H, Minicozzi II W P. Weyl type bounds for harmonic functions. Invent Math, 1998, 131(2): 257–298

[12] Coulhon T, Saloff-Coste L. Variétés riemanniennes isométriques à l’infini. Rev Mat Iberoam, 1995, 11(3): 687–726

[13] Delmotte T. Ingalit de Harnack elliptique sur les graphes. Colloq Math, 1997, 72(1): 19–37

[14] Delmotte T. Parabolic Harnack inequality and estimates of Markov chains on graphs. Rev Mat Iberoam, 1999, 15: 181–232

[15] DeVos M, Mohar B. An analogue of the Descartes-Euler formula for infinite graphs and Higuchi’s conjecture. Trans Amer Math Soc, 2007, 359(7): 3287–3301

[16] Erbar M, Maas J. Ricci curvature of finite Markov chains via convexity of the entropy. Arch Ration Mech Anal, 2012, 206(3): 997–1038

[17] Grigor’yan A, Huang X, Masamune J. On stochastic completeness of jump processes. Math Z, 2012, 271(3-4): 1211–1239

[18] Gromov M. Hyperbolic groups. In: Gersten S M, ed. Essays in Group Theory. Math Sci Res Inst Publ, Vol 8. Berlin: Springer, 1987, 75–263

[19] Häggström O, Jonasson J, Lyons R. Explicit isoperimetric constants and phase transitions in the Random-Cluster model. Ann Probab, 2002, 30(1): 443–473

[20] Higuchi Y. Combinatorial curvature for planar graphs. J Graph Theory, 2001, 38(4): 220–229

[21] Higuchi Y, Shirai T. Isoperimetric constants of (d, f)-regular planar graphs. Interdiscip Inform Sci, 2003, 9(2): 221–228

[22] Horn P, Lin Y, Liu S, Yau S-T. Volume doubling, Poincaré inequality and Guassian heat kernel estimate for nonnegative curvature graphs. 2014, arXiv: 1411.5087

[23] Hua B. Generalized Liouville theorem in nonnegatively curved Alexandrov spaces. Chin Ann Math Ser B, 2009, 30(2): 111–128

[24] Hua B, Jost J. Geometric analysis aspects of infinite semiplanar graphs with nonnegative curvature II. Trans Amer Math Soc, 2015, 367: 2509–2526

[25] Hua B, Jost J, Liu S. Geometric analysis aspects of infinite semiplanar graphs with nonnegative curvature. J Reine Angew Math, 2015, 700: 1–36

[26] Hua B, Lin Y. Stochastic completeness for graphs with curvature dimension conditions. 2015, arXiv: 1504.00080

[27] Ishida M. Pseudo-Curvature of a Graph. Lecture at ‘Workshop on Topological Graph Theory’. Yokohama National University, 1990

[28] Jost J, Liu S. Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs. Discrete Comput Geom, 2014, 51(2): 300–322

[29] Keller M. Curvature, geometry and spectral properties of planar graphs. Discrete Comput Geom, 2011, 46(3): 500–525

[30] Keller M. An overview of curvature bounds and spectral theory of planar tessellations. In: Najman L, Romon P, eds. Discrete Curvature: Theory and Applications. Cedram, 2014, 61–68

[31] Keller M, Lenz D. Unbounded Laplacians on graphs: basic spectral properties and the heat equation. Math Model Nat Phenom, 2010, 5(4): 198–224

[32] Keller M, Lenz D. Dirichlet forms and stochastic completeness of graphs and subgraphs. J Reine Angew Math, 2012, 666: 189–223

[33] Keller M, Peyerimhoff N. Cheeger constants, growth and spectrum of locally tessellating planar graphs. Math Z, 2010, 268(3-4): 871–886

[34] Kuwae K, Machigashira Y, Shioya T. Sobolev spaces, Laplacian, and heat kernel on Alexandrov spaces. Math Z, 2001, 238(2): 269–316

[35] Lawrencenko S, Plummer M D, Zha X. Isoperimetric constants of infinite plane graphs. Discrete Comput Geom, 2002, 28(3): 313–330

[36] Li P. Harmonic sections of polynomial growth. Math Res Lett, 1997, 4(1): 35–44

[37] Li P.Geometric Analysis. Cambridge: Cambridge Univ Press, 2009

[38] Lin Y, Lu L, Yau S T. Ricci curvature of graphs. Tohoku Math J (2), 2011, 63(4): 605–627

[39] Lin Y, Yau S T. Ricci curvature and eigenvalue estimate on locally finite graphs. Math Res Lett, 2010, 17(2): 343–356

[40] Lin Y, Yau S T. A brief review on geometry and spectrum of graphs. 2012, arXiv: 1204.3168

[41] Münch F. Remarks on curvature dimension conditions on graphs. 2015, arXiv: 1501.05839

[42] Nicholson R, Sneddon J. New graphs with thinly spread positive combinatorial curvature. New Zealand J Math, 2011

[43] Ollivier Y. Ricci curvature of Markov chains on metric spaces. J Funct Anal, 2009, 256(3): 810–864

[44] Réti T, Bitay E, Kosztolányi Z. On the polyhedral graphs with positive combinatorial curvature. Acta Polytechnica Hungarica, 2005, 2(2): 19–37

[45] Saloff-Coste L. Analysis on Riemannian co-compact covers. Surv Differ Geom, 2004, 9(1): 351–384

[46] Stone D A. A combinatorial analogue of a theorem of Myers. Illinois J Math, 1976, 20(1): 12–21

[47] Sun L, Yu X. Positively curved cubic plane graphs are finite. J Graph Theory, 2004, 47(4): 241–274

[48] Sunada T. Discrete Geometric Analysis. In: Geometry on Graphs and Its Applications. Proc Sympos Pure Math, Vol 77. Providence: Amer Math Soc, 2008, 51–86

[49] Woess W. A note on tilings and strong isoperimetric inequality. Math Proc Cambridge Philos Soc, 1998, 124(3): 385–393

[50] Woess W. Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Math, Vol 138. Cambridge: Cambridge Univ Press, 2000

[51] Wojciechowski R K. Stochastic Completeness of Graphs. Ph D Thesis, City University of New York, 2008

[52] Wojciechowski R K. Heat kernel and essential spectrum of infinite graphs. Indiana Univ Math J, 2009, 58(3): 1419–1442

[53] Wojciechowski R K. Stochastically incomplete manifolds and graphs. In: Lenz D, Sobieczky F, Woess W, eds. Random Walks, Boundaries and Spectra. Progress in Probability, Vol 64. Berlin: Springer, 2011, 163–179

[54] Zhang L. A result on combinatorial curvature for embedded graphs on a surface. Discrete Math, 2008, 308(24): 6588–6595

[55] Ż uk A. On the norms of the random walks on planar graphs. Ann Inst Fourier (Grenoble), 1997, 47(5): 1463–1490

RIGHTS & PERMISSIONS

2016 Higher Education Press and Springer-Verlag Berlin Heidelberg