Connective constants and height functions for Cayley graphs

DOI10.1090/TRAN/7166zbMATH Open1362.05059arXiv1501.00476OpenAlexW2964311887MaRDI QIDQ5347287FDOQ5347287

Zhongyang Li, G. R. Grimmett

Publication date: 23 May 2017

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1501.00476

Recommendations

• Self-avoiding walks and connective constants
• Self-avoiding walks and amenability
• Locality of connective constants
• Strict inequalities for connective constants of transitive graphs
• A general bridge theorem for self-avoiding walks

zbMATH Keywords

harmonic functionCayley graphsolvable groupunimodularityself-avoiding walkvertex-transitive graphquasi-transitive graphconnective constantbridge decompositiongraph height functiongroup height functionindicabilityhigman group

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Geometric group theory (20F65)

Cites Work

• Probability and random processes.
• Probability on trees and networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lectures on Self-Avoiding Walks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• FURTHER RESULTS ON THE RATE OF CONVERGENCE TO THE CONNECTIVE CONSTANT OF THE HYPERCUBICAL LATTICE
• Is the critical percolation probability local?
• A new proof of Gromov’s theorem on groups of polynomial growth
• A Finitely Generated Infinite Simple Group
• The supercritical phase of percolation is well behaved
• Characterisations of algebraic properties of groups in terms of harmonic functions
• Title not available (Why is that?)
• A finitary version of Gromov's polynomial growth theorem.
• Title not available (Why is that?)
• Group-invariant percolation on graphs
• Harmonic maps on amenable groups and a diffusive lower bound for random walks
• Amenability, unimodularity, and the spectral radius of random walks on infinite graphs
• Random walks on disordered media and their scaling limits. École d'Été de Probabilités de Saint-Flour XL -- 2010
• Self-avoiding walks and the Fisher transformation
• Bounds on connective constants of regular graphs
• Title not available (Why is that?)
• Automorphism groups of graphs as topological groups
• Minimal growth harmonic functions on lamplighter groups
• Extendable self-avoiding walks
• Strict Inequalities for Connective Constants of Transitive Graphs
• On non-uniqueness of percolation on nonamenable Cayley graphs
• Self-avoiding walks and amenability
• Locality of connective constants
• Locality of percolation for abelian Cayley graphs

Cited In (11)

• Cubic graphs and the golden mean
• Self-avoiding walk on nonunimodular transitive graphs
• A general bridge theorem for self-avoiding walks
• Self-Avoiding Walks and Connective Constants
• The 1-2 model
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• Positive speed self-avoiding walks on graphs with more than one end
• Locally infinite graphs and symmetries
• Self-avoiding walks and amenability
• Weighted self-avoiding walks
• Locality of connective constants

This page was built for publication: Connective constants and height functions for Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347287)