Strict inequalities for connective constants of transitive graphs

DOI10.1137/130906052zbMATH Open1305.05102arXiv1301.3091OpenAlexW1972283381MaRDI QIDQ2935271FDOQ2935271

Zhongyang Li, G. R. Grimmett

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The connective constant of a graph is the exponential growth rate of the number of self-avoiding walks starting at a given vertex. Strict inequalities are proved for connective constants of vertex-transitive graphs. Firstly, the connective constant decreases strictly when the graph is replaced by a non-trivial quotient graph. Secondly, the connective constant increases strictly when a quasi-transitive family of new edges is added. These results have the following implications for Cayley graphs. The connective constant of a Cayley graph decreases strictly when a new relator is added to the group, and increases strictly when a non-trivial group element is declared to be a generator.

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

Recommendations

• Self-avoiding walks and connective constants
• Bounds on connective constants of regular graphs
• Cubic graphs and the golden mean
• The set of connective constants of Cayley graphs contains a Cantor space
• Connective constants and height functions for Cayley graphs

zbMATH Keywords

Cayley graphregular graphself-avoiding walkvertex-transitive graphquasi-transitive graphconnective constant

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) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cited In (12)

• Cubic graphs and the golden mean
• Self-avoiding walk on nonunimodular transitive graphs
• Bounds on connective constants of regular graphs
• A Note on Schramm’s Locality Conjecture for Random-Cluster Models
• Self-Avoiding Walks and Connective Constants
• Counting self-avoiding walks on free products of graphs
• Strict monotonicity of percolation thresholds under covering maps
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• Connective constants and height functions for Cayley graphs
• Positive speed self-avoiding walks on graphs with more than one end
• Self-avoiding walks and amenability
• Locality of connective constants

This page was built for publication: Strict inequalities for connective constants of transitive graphs

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