Self-avoiding walk on the hypercube

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} ${\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{1}{2}$. We refer to the regime $n\ll 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 ${\mu }_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.

45 pages. Minor changes. Final version. To appear in Random Structures and Algorithms