Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Connective constants and height functions for Cayley graphs

Authors: Geoffrey R. Grimmett and Zhongyang Li
Journal: Trans. Amer. Math. Soc. 369 (2017), 5961-5980
MSC (2010): Primary 05C30, 20F65, 60K35, 82B20
Published electronically: March 31, 2017
Previous version of record: Original version posted March 31, 2017
Corrected version of record: Current version corrects errors introduced by the publisher in the abstract.
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The connective constant $ \mu (G)$ of an infinite transitive graph $ G$ is the exponential growth rate of the number of self-avoiding walks from a given origin. In earlier work of Grimmett and Li, a locality theorem was proved for connective constants, namely, that the connective constants of two graphs are close in value whenever the graphs agree on a large ball around the origin. A condition of the theorem was that the graphs support so-called ``unimodular graph height functions''. When the graphs are Cayley graphs of infinite, finitely generated groups, there is a special type of unimodular graph height function termed here a ``group height function''. A necessary and sufficient condition for the existence of a group height function is presented, and may be applied in the context of the bridge constant, and of the locality of connective constants for Cayley graphs. Locality may thereby be established for a variety of infinite groups including those with strictly positive deficiency.

It is proved that a large class of Cayley graphs support unimodular graph height functions, that are in addition harmonic on the graph. This implies, for example, the existence of unimodular graph height functions for the Cayley graphs of finitely generated solvable groups. It turns out that graphs with non-unimodular automorphism subgroups also possess graph height functions, but the resulting graph height functions need not be harmonic.

Group height functions, as well as the graph height functions of the previous paragraph, are non-constant harmonic functions with linear growth and an additional property of having periodic differences. The existence of such functions on Cayley graphs is a topic of interest beyond their applications in the theory of self-avoiding walks.

References [Enhancements On Off] (What's this?)

  • [1] László Babai, Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1447-1540. MR 1373683
  • [2] Roland Bauerschmidt, Hugo Duminil-Copin, Jesse Goodman, and Gordon Slade, Lectures on self-avoiding walks, Probability and statistical physics in two and more dimensions, Clay Math. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 2012, pp. 395-467. MR 3025395
  • [3] I. Benjamini, H. Duminil-Copin, G. Kozma, and A. Yadin, Minimal growth harmonic functions on lamplighter groups, preprint (2016), arXiv:1607.00753.
  • [4] I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, Group-invariant percolation on graphs, Geom. Funct. Anal. 9 (1999), no. 1, 29-66. MR 1675890,
  • [5] Itai Benjamini, Asaf Nachmias, and Yuval Peres, Is the critical percolation probability local?, Probab. Theory Related Fields 149 (2011), no. 1-2, 261-269. MR 2773031,
  • [6] K. Conrad, SL $ _2(\mathbb{Z})$, (2012), SL(2,Z).pdf.
  • [7] Geoffrey R. Grimmett, Alexander E. Holroyd, and Yuval Peres, Extendable self-avoiding walks, Ann. Inst. Henri Poincaré D 1 (2014), no. 1, 61-75. MR 3166203,
  • [8] Geoffrey R. Grimmett and Zhongyang Li, Counting self-avoiding walks, preprint (2013), arXiv:1304.7216.
  • [9] Geoffrey Grimmett and Zhongyang Li, Self-avoiding walks and the Fisher transformation, Electron. J. Combin. 20 (2013), no. 3, Paper 47, 14. MR 3118955
  • [10] Geoffrey R. Grimmett and Zhongyang Li, Locality of connective constants, preprint (2014), arXiv:1412.0150.
  • [11] Geoffrey R. Grimmett and Zhongyang Li, Strict inequalities for connective constants of transitive graphs, SIAM J. Discrete Math. 28 (2014), no. 3, 1306-1333. MR 3252803,
  • [12] Geoffrey R. Grimmett and Zhongyang Li, Bounds on connective constants of regular graphs, Combinatorica 35 (2015), no. 3, 279-294. MR 3367126,
  • [13] Geoffrey R. Grimmett and Zhongyang Li, Self-avoiding walks and amenability, preprint (2015), arXiv:1510.08659.
  • [14] G. R. Grimmett and J. M. Marstrand, The supercritical phase of percolation is well behaved, Proc. Roy. Soc. London Ser. A 430 (1990), no. 1879, 439-457. MR 1068308,
  • [15] Geoffrey R. Grimmett and David R. Stirzaker, Probability and random processes, 3rd ed., Oxford University Press, New York, 2001. MR 2059709
  • [16] M. Hamann, Accessibility in transitive graphs, preprint (2014), arXiv:1404.7677.
  • [17] J. M. Hammersley and K. W. Morton, Poor man's Monte Carlo, J. Roy. Statist. Soc. Ser. B. 16 (1954), 23-38; discussion 61-75. MR 0064475
  • [18] J. M. Hammersley and D. J. A. Welsh, Further results on the rate of convergence to the connective constant of the hypercubical lattice, Quart. J. Math. Oxford Ser. (2) 13 (1962), 108-110. MR 0139535,
  • [19] Pierre de la Harpe, Topics in geometric group theory, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 2000. MR 1786869
  • [20] Graham Higman, A finitely generated infinite simple group, J. London Math. Soc. 26 (1951), 61-64. MR 0038348,
  • [21] J. A. Hillman, The algebraic characterization of geometric $ 4$-manifolds, London Mathematical Society Lecture Note Series, vol. 198, Cambridge University Press, Cambridge, 1994. MR 1275829
  • [22] J. A. Hillman, Four-manifolds, geometries and knots, Geometry & Topology Monographs, vol. 5, Geometry & Topology Publications, Coventry, 2002. MR 1943724
  • [23] Bruce Kleiner, A new proof of Gromov's theorem on groups of polynomial growth, J. Amer. Math. Soc. 23 (2010), no. 3, 815-829. MR 2629989,
  • [24] Takashi Kumagai, Random walks on disordered media and their scaling limits, Lecture Notes in Mathematics, vol. 2101, Springer, Cham, 2014. Lecture notes from the 40th Probability Summer School held in Saint-Flour, 2010; École d'Été de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School]. MR 3156983
  • [25] W. Ledermann and A. J. Weir, Introduction to Group Theory, Addison Wesley Longman, Harlow, 1996.
  • [26] James R. Lee and Yuval Peres, Harmonic maps on amenable groups and a diffusive lower bound for random walks, Ann. Probab. 41 (2013), no. 5, 3392-3419. MR 3127886,
  • [27] R. Lyons and Y. Peres, Probability on Trees and Networks, Cambridge University Press, Cambridge, 2016,
  • [28] Neal Madras and Gordon Slade, The self-avoiding walk, Probability and its Applications, Birkhäuser Boston, Inc., Boston, MA, 1993. MR 1197356
  • [29] S. Martineau and V. Tassion, Locality of percolation for abelian Cayley graphs, Ann. Probab.,
  • [30] T. Meyerovitch and A. Yadin, Groups with finite dimensional spaces of harmonic functions, preprint (2014), arXiv:1408.6243.
  • [31] Igor Pak and Tatiana Smirnova-Nagnibeda, On non-uniqueness of percolation on nonamenable Cayley graphs, C. R. Acad. Sci. Paris Sér. I Math. 330 (2000), no. 6, 495-500 (English, with English and French summaries). MR 1756965,
  • [32] Derek J. S. Robinson, A course in the theory of groups, 2nd ed., Graduate Texts in Mathematics, vol. 80, Springer-Verlag, New York, 1996. MR 1357169
  • [33] Yehuda Shalom and Terence Tao, A finitary version of Gromov's polynomial growth theorem, Geom. Funct. Anal. 20 (2010), no. 6, 1502-1547. MR 2739001,
  • [34] Paolo M. Soardi and Wolfgang Woess, Amenability, unimodularity, and the spectral radius of random walks on infinite graphs, Math. Z. 205 (1990), no. 3, 471-486. MR 1082868,
  • [35] Matthew C. H. Tointon, Characterizations of algebraic properties of groups in terms of harmonic functions, Groups Geom. Dyn. 10 (2016), no. 3, 1007-1049. MR 3551188,
  • [36] V. I. Trofimov, Groups of automorphisms of graphs as topological groups, Mat. Zametki 38 (1985), no. 3, 378-385, 476 (Russian). MR 811571

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C30, 20F65, 60K35, 82B20

Retrieve articles in all journals with MSC (2010): 05C30, 20F65, 60K35, 82B20

Additional Information

Geoffrey R. Grimmett
Affiliation: Centre for Mathematical Sciences, Cambridge University, Wilberforce Road, Cambridge, CB3 0WB, United Kingdom

Zhongyang Li
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06260

Keywords: Self-avoiding walk, connective constant, vertex-transitive graph, quasi- transitive graph, bridge decomposition, Cayley graph, Higman group, graph height function, group height function, indicability, harmonic function, solvable group, unimodularity
Received by editor(s): January 22, 2015
Received by editor(s) in revised form: July 27, 2015, and August 22, 2016
Published electronically: March 31, 2017
Additional Notes: The first author was supported in part by EPSRC Grant EP/I03372X/1.
The second author was supported in part by Simons Collaboration Grant #351813 and NSF grant #1608896
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society