SAWs, trails, kites, patterns
Abstract
A self-avoiding walk (SAW) on a vertex-transitive graph G is a path that visits no vertex more than once; a trail is a path that traverses no edge more than once. The number of n-step self-avoiding walks (respectively, trails) starting at a given vertex has order μ(G)n (respectively, μT(G)n), where μ(G) is called the connective constant and μT(G) is the trail constant. It is immediate that μ=μT if G either has degree $3$ or less, or is a tree. We prove a necessary and sufficient condition for the strict inequality μ< μT if G has degree $4$ or more and is not a tree, and in addition G possesses a so-called height function. This condition is satisfied whenever the height function is transitive. The core of the proof is a pattern theorem for graphs possessing height functions, and this is achieved using an unpublished argument for Bbb Zd by Hammersley, reported by Janse van Rensburg et al. (J. Stat. Phys. 85, 1996, 103--130). Some ancillary results are included concerning SAWs on the line graph of G.
Related
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- On Associative Neural Networks for Sparse Patterns with Large Capacities
- Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotics Aspects and Borges's Theorem
- When arrow patterns meet classical patterns
- An Erdős-Szekeres-Type Result on Permutation Patterns
BibTeX
@misc{grimmett2026saws,
title = {{SAWs, trails, kites, patterns}},
author = {Geoffrey R. Grimmett},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00816},
eprint = {2611.00816},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00816},
}
RIS
TY - UNPB
TI - SAWs, trails, kites, patterns
AU - Geoffrey R. Grimmett
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00816
UR - https://arxiv.org/abs/2611.00816
AB - A self-avoiding walk (SAW) on a vertex-transitive graph G is a path that visits no vertex more than once; a trail is a path that traverses no edge more than once. The number of n-step self-avoiding walks (respectively, trails) starting at a given vertex has order μ(G)^n (respectively, μ_T(G)^n), where μ(G) is called the connective constant and μ_T(G) is the trail constant. It is immediate that μ=μ_T if G either has degree $3$ or less, or is a tree. We prove a necessary and sufficient condition for the strict inequality μ< μ_T if G has degree $4$ or more and is not a tree, and in addition G possesses a so-called height function. This condition is satisfied whenever the height function is transitive. The core of the proof is a pattern theorem for graphs possessing height functions, and this is achieved using an unpublished argument for Bbb Z^d by Hammersley, reported by Janse van Rensburg et al. (J. Stat. Phys. 85, 1996, 103--130). Some ancillary results are included concerning SAWs on the line graph of G.
ER -