Connective constants and height functions for Cayley graphs

Grimmett, Geoffrey; Li, Zhongyang

doi:10.1090/tran/7166

Connective constants and height functions for Cayley graphs
HTML articles powered by AMS MathViewer

by Geoffrey R. Grimmett and Zhongyang Li PDF

Trans. Amer. Math. Soc. 369 (2017), 5961-5980 Request permission

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

László Babai, Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1447–1540. MR 1373683
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
I. Benjamini, H. Duminil-Copin, G. Kozma, and A. Yadin, Minimal growth harmonic functions on lamplighter groups, preprint (2016), arXiv:1607.00753.
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, DOI 10.1007/s000390050080
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, DOI 10.1007/s00440-009-0251-5
K. Conrad, SL₂(ℤ ) , (2012), http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/ SL(2,Z).pdf.
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, DOI 10.4171/AIHPD/3
Geoffrey R. Grimmett and Zhongyang Li, Counting self-avoiding walks, preprint (2013), arXiv:1304.7216.
Geoffrey Grimmett and Zhongyang Li, Self-avoiding walks and the Fisher transformation, Electron. J. Combin. 20 (2013), no. 3, Paper 47, 14. MR 3118955
Geoffrey R. Grimmett and Zhongyang Li, Locality of connective constants, preprint (2014), arXiv:1412.0150.
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, DOI 10.1137/130906052
Geoffrey R. Grimmett and Zhongyang Li, Bounds on connective constants of regular graphs, Combinatorica 35 (2015), no. 3, 279–294. MR 3367126, DOI 10.1007/s00493-014-3044-0
Geoffrey R. Grimmett and Zhongyang Li, Self-avoiding walks and amenability, preprint (2015), arXiv:1510.08659.
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, DOI 10.1098/rspa.1990.0100
Geoffrey R. Grimmett and David R. Stirzaker, Probability and random processes, 3rd ed., Oxford University Press, New York, 2001. MR 2059709
M. Hamann, Accessibility in transitive graphs, preprint (2014), arXiv:1404.7677.
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 64475
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 139535, DOI 10.1093/qmath/13.1.108
Pierre de la Harpe, Topics in geometric group theory, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 2000. MR 1786869
Graham Higman, A finitely generated infinite simple group, J. London Math. Soc. 26 (1951), 61–64. MR 38348, DOI 10.1112/jlms/s1-26.1.61
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, DOI 10.1017/CBO9780511526350
J. A. Hillman, Four-manifolds, geometries and knots, Geometry & Topology Monographs, vol. 5, Geometry & Topology Publications, Coventry, 2002. MR 1943724
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, DOI 10.1090/S0894-0347-09-00658-4
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, DOI 10.1007/978-3-319-03152-1
W. Ledermann and A. J. Weir, Introduction to Group Theory, Addison Wesley Longman, Harlow, 1996.
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, DOI 10.1214/12-AOP779
R. Lyons and Y. Peres, Probability on Trees and Networks, Cambridge University Press, Cambridge, 2016, http://pages.iu.edu/~rdlyons/.
Neal Madras and Gordon Slade, The self-avoiding walk, Probability and its Applications, Birkhäuser Boston, Inc., Boston, MA, 1993. MR 1197356
S. Martineau and V. Tassion, Locality of percolation for abelian Cayley graphs, Ann. Probab., http://arxiv.org/abs/1312.1946.
T. Meyerovitch and A. Yadin, Groups with finite dimensional spaces of harmonic functions, preprint (2014), arXiv:1408.6243.
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, DOI 10.1016/S0764-4442(00)00211-1
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, DOI 10.1007/978-1-4419-8594-1
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, DOI 10.1007/s00039-010-0096-1
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, DOI 10.1007/BF02571256
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, DOI 10.4171/GGD/375
V. I. Trofimov, Groups of automorphisms of graphs as topological groups, Mat. Zametki 38 (1985), no. 3, 378–385, 476 (Russian). MR 811571