A general bridge theorem for self-avoiding walks

DOI10.1016/J.DISC.2020.112092MaRDI QIDQ2005683zbMATH OpenOpenAlexFDO

Authors Christian Lindorfer

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bridgesself-avoiding walksgrandparent graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Infinite graphs (05C63)

Abstract: Let $X$ be an infinite, locally finite, connected, quasi-transitive graph without loops or multiple edges. A graph height function on $X$ is a map adapted to the graph structure, assigning to every vertex an integer, called height. Bridges are self-avoiding walks such that heights of interior vertices are bounded by the heights of the start- and end-vertex. The number of self-avoiding walks and the number of bridges of length $n$ starting at a vertex $o$ of $X$ grow exponentially in $n$ and the bases of these growth rates are called connective constant and bridge constant, respectively. We show that for any graph height function $h$ the connective constant of the graph is equal to the maximum of the two bridge constants given by increasing and decreasing bridges with respect to $h$. As a concrete example, we apply this result to calculate the connective constant of the Grandparent graph.

Recommendations

• The fixed irreducible bridge ensemble for self-avoiding walks
• Self-avoiding walks and connective constants
• Self-avoiding walks on finite graphs of large girth
• Bounds on the self-avoiding-walk connective constant
• Upper Bounds for the Connective Constant of Self-Avoiding Walks
• scientific article; zbMATH DE number 6456216
• Borel-type bounds for the self-avoiding walk connective constant
• Self-avoiding walks and amenability
• Scaling limits of random walk bridges conditioned to avoid a finite set
• Compressed self-avoiding walks, bridges and polygons

Cites work

• scientific article; zbMATH DE number 3148803 (Why is no real title available?)
• Amenability, unimodularity, and the spectral radius of random walks on infinite graphs
• Automorphism groups of graphs as topological groups
• Connective constants and height functions for Cayley graphs
• FURTHER RESULTS ON THE RATE OF CONVERGENCE TO THE CONNECTIVE CONSTANT OF THE HYPERCUBICAL LATTICE
• Lectures on self-avoiding walks
• Locality of connective constants
• Self-avoiding walks and amenability
• The connective constant of the honeycomb lattice equals \(\sqrt{2+\sqrt 2}\)
• The language of self-avoiding walks
• The self-avoiding walk.

Cited in

(5)

• The fixed irreducible bridge ensemble for self-avoiding walks
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• Connective constants and height functions for Cayley graphs
• Weighted self-avoiding walks
• Locality of connective constants

This page was built for publication: A general bridge theorem for self-avoiding walks

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