Self-avoiding walk on the hypercube

Gordon Slade

Published 2021-08-08Version 1

The counting of self-avoiding walks is a classical problem in enumerative combinatorics which is also of interest in probability theory, statistical physics, and polymer chemistry. We study the number $c_n^{(N)}$ of $n$-step self-avoiding walks on the $N$-dimensional hypercube, and identify an $N$-dependent connective constant $\mu_N$ and amplitude $A_N$ such that $c_n^{(N)}$ is $O(\mu_N^n)$ for all $n$ and $N$, and is asymptotically $A_N \mu_N^n$ as long as $n\le 2^{pN}$ for any fixed $p< \frac 12$. We refer to the regime $n \ll 2^{N/2}$ as the dilute phase and regard it as the regime in which the self-avoiding walk is not yet long enough to "feel" the finite volume of the hypercube. 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; this shares similarities with the much studied percolation phase transition on the hypercube. 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 $\mu_N = N-1-N^{-1}-4N^{-2}-26N^{-3}+O(N^{-4})$. A similar asymptotic expansion holds for $A_N$. The proofs are based on generating function and Tauberian methods implemented via the lace expansion, for which an introductory account is provided. The generating function analysis also leads to results for the asymptotic behaviour of the susceptibility and the expected length for self-avoiding walk on the hypercube. The convergence proof we present for the lace expansion is simpler for self-avoiding walk on the hypercube than it is for other settings and models.