Self-avoiding walks and connective constants

DOI10.1007/978-981-15-0302-3_8MaRDI QIDQ3297350zbMATH OpenOpenAlexFDO

Authors G. R. Grimmett, Zhongyang Li

Publication date 3 July 2020

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

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

zbMATH Keywords

bridge constantCayley graphconnective constantcubic graphFisher transformationgolden meangraph height functionlocality theoremquasi-transitive graphregular graphself-avoiding walkspeedtransitive graphunimodularity

Mathematics Subject Classification ID

Applications of graph theory (05C90) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: The connective constant $mu(G)$ of a quasi-transitive graph $G$ is the asymptotic growth rate of the number of self-avoiding walks (SAWs) on $G$ from a given starting vertex. We survey several aspects of the relationship between the connective constant and the underlying graph $G$. $$ We present upper and lower bounds for $mu$ in terms of the vertex-degree and girth of a transitive graph. $$ We discuss the question of whether $mugephi$ for transitive cubic graphs (where $phi$ denotes the golden mean), and we introduce the Fisher transformation for SAWs (that is, the replacement of vertices by triangles). $$ We present strict inequalities for the connective constants $mu(G)$ of transitive graphs $G$, as $G$ varies. $$ As a consequence of the last, the connective constant of a Cayley graph of a finitely generated group decreases strictly when a new relator is added, and increases strictly when a non-trivial group element is declared to be a further generator. $$ We describe so-called graph height functions within an account of "bridges" for quasi-transitive graphs, and indicate that the bridge constant equals the connective constant when the graph has a unimodular graph height function. $$ A partial answer is given to the question of the locality of connective constants, based around the existence of unimodular graph height functions. $$ Examples are presented of Cayley graphs of finitely presented groups that possess graph height functions (that are, in addition, harmonic and unimodular), and that do not. $$ The review closes with a brief account of the "speed" of SAW.

Recommendations

• Strict inequalities for connective constants of transitive graphs
• Connective constants and height functions for Cayley graphs
• Cubic graphs and the golden mean
• Locality of connective constants
• Self-avoiding walks and amenability

Cites work

• A conjecture concerning a limit of non-Cayley graphs
• A remark about the spectral radius
• Amenable semigroups
• Bounds on connective constants of regular graphs
• Connective constants and height functions for Cayley graphs
• Counting self-avoiding walks on free products of graphs
• Critical temperature of periodic Ising models
• Cubic graphs and the golden mean
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Existence of a non-averaging regime for the self-avoiding walk on a high-dimensional infinite percolation cluster
• Extendable self-avoiding walks
• Full Banach Mean Values on Countable groups.
• FURTHER RESULTS ON THE RATE OF CONVERGENCE TO THE CONNECTIVE CONSTANT OF THE HYPERCUBICAL LATTICE
• scientific article; zbMATH DE number 3148803 (Why is no real title available?)
• scientific article; zbMATH DE number 2154241 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• scientific article; zbMATH DE number 863496 (Why is no real title available?)
• scientific article; zbMATH DE number 3088537 (Why is no real title available?)
• Improved lower bounds on the connective constants for two-dimensional self-avoiding walks
• Improved upper bounds for self-avoiding walks in Z^d
• Is the critical percolation probability local?
• Isoperimetric inequalities, growth, and the spectrum of graphs
• Lectures on self-avoiding walks
• Local statistics of realizable vertex models
• Locality of connective constants
• Locality of percolation for abelian Cayley graphs
• Logarithmic correction for the susceptibility of the 4-dimensional weakly self-avoiding walk: a renormalisation group analysis
• Multiplicity of phase transitions and mean-field criticality on highly non-amenable graphs.
• Non-amenable Cayley graphs of high girth have \(p_c < p_u\) and mean-field exponents
• Non-coincidence of quenched and annealed connective constants on the supercritical planar percolation cluster
• On non-uniqueness of percolation on nonamenable Cayley graphs
• On the Number of Self-Avoiding Walks
• On the probability that self-avoiding walk ends at a given point
• Percolation
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• Potts models and random-cluster processes with many-body interactions
• Probability on trees and networks
• Random self-avoiding walks on one-dimensional lattices
• Random Walks on Infinite Graphs and Groups
• Recurrence of distributional limits of finite planar graphs
• Self-avoiding walk is sub-ballistic
• Self-avoiding walks and amenability
• Self-avoiding walks and the Fisher transformation
• Self-avoiding walks and trails on the 3.12² lattice
• Self-Avoiding Walks on Hyperbolic Graphs
• Self-avoiding walks, neighbour-avoiding walks and trails on semiregular lattices
• Self-avoiding walks, the language of science, and Fibonacci numbers
• Some relations between analytic and geometric properties of infinite graphs
• Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
• Strict inequalities for connective constants of transitive graphs
• Strict inequality for critical values of Potts models and random-cluster processes
• Symmetric Random Walks on Groups
• The connective constant of the honeycomb lattice equals \(\sqrt{2+\sqrt 2}\)
• The critical Z-invariant Ising model via dimers: Locality property
• The Random-Cluster Model
• The set of connective constants of Cayley graphs contains a Cantor space
• The vertex-transitive TLF-planar graphs
• Three theorems in discrete random geometry
• Vertex-transitive graphs and vertex-transitive maps

Cited in

(26)

• Join-and-Cut algorithm for self-avoiding walks with variable length and free endpoints
• Self-avoiding walks and amenability
• Locality of connective constants
• Self-avoiding walks, the language of science, and Fibonacci numbers
• A general bridge theorem for self-avoiding walks
• Weighted self-avoiding walks
• Cubic graphs and the golden mean
• Self-avoiding walk on nonunimodular transitive graphs
• The fixed irreducible bridge ensemble for self-avoiding walks
• Extendable self-avoiding walks
• Monotonicity of the number of self-avoiding walks
• Strict inequalities for connective constants of transitive graphs
• Knots in self-avoiding walks
• Self-avoiding walks and the Fisher transformation
• The Language of Self-Avoiding Walks
• The set of connective constants of Cayley graphs contains a Cantor space
• Bounds on connective constants of regular graphs
• Connective constants and height functions for Cayley graphs
• Self-avoiding walks and multiple context-free languages
• Self‐avoiding walk on the hypercube
• Selected Problems in Probability Theory
• Note on locality of volume growth rate of graphs
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• Self-avoiding walk is ballistic on graphs with more than one end
• Counting self-avoiding walks on free products of graphs
• Positive speed self-avoiding walks on graphs with more than one end

This page was built for publication: Self-avoiding walks and connective constants

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