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
DOI: https://doi.org/10.1090/tran/7166
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?)


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
Email: g.r.grimmett@statslab.cam.ac.uk

Zhongyang Li
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06260
Email: zhongyang.li@uconn.edu

DOI: https://doi.org/10.1090/tran/7166
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