Self‐avoiding walk on the hypercube

DOI10.1002/RSA.21117MaRDI QIDQ6074881zbMATH OpenOpenAlexFDO

Authors Gordon Slade

Publication date 19 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

hypercubelace expansionphase transitionself-avoiding walk

Mathematics Subject Classification ID

Hypergraphs (05C65) Random walks on graphs (05C81) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study the number $c_n^{(N)}$ of $n$-step self-avoiding walks on the $N$-dimensional hypercube, and identify an $N$-dependent emph{connective constant} $m{u}_N$ and amplitude $A_N$ such that $c_n^{(N)}$ is $O(m{u}_N^n)$ for all $n$ and $N$, and is asymptotically $A_{N}m{u}_N^n$ as long as $nle{2}^{pN}$ for any fixed $p<frac12$. We refer to the regime $nll{2}^{N/2}$ as the emph{dilute phase}. We discuss conjectures concerning different behaviours of $c_n^{(N)}$ when $n$ reaches and exceeds $2^{N/2}$, corresponding to a critical window and a dense phase. In addition, we prove that the connective constant has an asymptotic expansion to all orders in $N^{-1}$, with integer coefficients, and we compute the first five coefficients $m{u}_N=N-1-N^{-1}-4N^{-2}-26N^{-3}+O(N^{-4})$. The proofs are based on generating function and Tauberian methods implemented via the lace expansion, for which an introductory account is provided.

Recommendations

• Upper bounds for the connective constant in \(\mathbb Z^d\)
• Self-avoiding walk in five or more dimensions. I: The critical behaviour
• Scaling of self-avoiding walks in high dimensions.
• Improved upper bounds for self-avoiding walks in Z^d
• scientific article; zbMATH DE number 201032

Cites work

• A simple convergence proof for the lace expansion
• An improvement of Watson’s theorem on Borel summability
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Asymptotic expansions inn−1 for percolation critical values on then-Cube and ℤn
• Borel-type bounds for the self-avoiding walk connective constant
• Critical properties of ^4-theories
• Expansion in ${\boldsymbol{n^{-1}}}$ for Percolation Critical Values on the $n$-cube and ${\boldsymbol{{\mathbb Z}^n}}$: the First Three Terms
• Expansion in high dimension for the growth constants of lattice trees and lattice animals
• scientific article; zbMATH DE number 742629 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• scientific article; zbMATH DE number 3195308 (Why is no real title available?)
• Hypercube percolation
• Largest random component of a k-cube
• Marriage of exact enumeration and \(1/d\) expansion methods: lattice model of dilute polymers
• Progress in high-dimensional percolation and random graphs
• Random self-avoiding walks on one-dimensional lattices
• Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
• Random subgraphs of finite graphs. III: The phase transition for the n-cube
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Self-avoiding walk enumeration via the lace expansion
• Self-avoiding walk in 5 or more dimensions
• Self-avoiding walk in five or more dimensions. I: The critical behaviour
• Self-avoiding walk on nonunimodular transitive graphs
• Self-avoiding walk on the complete graph
• Self-avoiding walks and connective constants
• Self-avoiding walks crossing a square
• Self-avoiding walks on finite graphs of large girth
• Self-Avoiding Walks on Hyperbolic Graphs
• Singularity Analysis of Generating Functions
• Slightly subcritical hypercube percolation
• Supercritical self-avoiding walks are space-filling
• The broken supersymmetry phase of a self-avoiding random walk
• The connective constant of the honeycomb lattice equals \(\sqrt{2+\sqrt 2}\)
• The Evolution of Random Subgraphs of the Cube
• The lace expansion and its application. École d'Été de Probabilités de Saint-Flour XXXIV -- 2004.
• The length of self-avoiding walks on the complete graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The scaling limit of lattice trees in high dimensions
• The Self-Avoiding-Walk and Percolation Critical Points in High Dimensions
• Tree graph inequalities and critical behavior in percolation models

Cited in

(8)

• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• Supercritical self-avoiding walks are space-filling
• Non-coincidence of quenched and annealed connective constants on the supercritical planar percolation cluster
• The critical pulling force for self-avoiding walks
• Self-avoiding walks contained within a square
• Weakly self-avoiding walk on a high-dimensional torus
• Two-point functions of random-length random walk on high-dimensional boxes
• Positive speed self-avoiding walks on graphs with more than one end

This page was built for publication: Self‐avoiding walk on the hypercube

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