Self-avoiding walk
A self-avoiding walk (SAW) is a lattice path starting at the origin in \mathbb{Z}^d, consisting of n consecutive steps to nearest-neighbor sites, such that no lattice point is visited more than once.[1] This restriction models the excluded volume constraint, preventing self-intersections, in contrast to unrestricted random walks that allow revisits.[2] Formally, an n-step SAW \omega = (\omega_0, \omega_1, \dots, \omega_n) satisfies \omega_0 = 0, |\omega_i - \omega_{i-1}| = 1 for each i, and \omega_i \neq \omega_j for all $0 \leq i < j \leq n.[1] The model originated in polymer physics, where Nobel laureate Paul J. Flory introduced it in 1949 to analyze the average end-to-end distance of real polymer chains in dilute solutions.[3] Flory argued that polymer molecules, modeled as flexible chains linked by covalent bonds, expand due to repulsive interactions between non-adjacent segments, leading to a scaling R \sim N^\nu where N is the chain length and \nu > 1/2 (unlike the Gaussian chain's \nu = 1/2).[3] Earlier ideas trace to Werner Kuhn in the 1930s, but Flory's mean-field approximation popularized the SAW as a discrete analog for these "hindered" random walks.[2] By the 1950s, computational simulations by Frank Rosenbluth and others began enumerating short SAWs, revealing the model's combinatorial complexity.[2] SAWs serve as a cornerstone in statistical mechanics for studying critical phenomena, phase transitions, and the behavior of linear polymers under good solvent conditions.[1] In polymer science, they approximate the swollen conformations of macromolecules, aiding predictions of viscosity, elasticity, and diffusion.[3] Mathematically, the connective constant \mu = \lim_{n \to \infty} c_n^{1/n} (where c_n is the number of n-step SAWs) governs exponential growth, proven to exist via submultiplicativity.[1] Exact values are known only for specific lattices; for example, on the hexagonal lattice \mu = \sqrt{2} + \sqrt{2}.[1] Despite their simplicity, SAWs pose profound challenges: exact enumeration beyond small n is intractable, and critical exponents like \gamma (susceptibility) and \nu (end-to-end distance) require advanced techniques such as lace expansion or conformal invariance.[2] In high dimensions (d \geq 5), SAWs asymptotically resemble simple random walks, with mean-square displacement \langle |X_n|^2 \rangle \sim n.[2] In four dimensions, logarithmic corrections appear, \langle |X_n|^2 \rangle \sim n (\log n)^{1/2}, while in two dimensions, the scaling limit is believed to be the Schramm–Loewner evolution (SLE) curve with parameter \kappa = 8/3, rigorously proven for specific lattices.[2] These results underscore SAWs' role in bridging combinatorics, probability, and physics, with ongoing research into their universality and extensions like interacting or directed variants.[1]Fundamentals
Definition
A self-avoiding walk (SAW) of length n is formally defined on a lattice, most commonly the d-dimensional integer lattice \mathbb{Z}^d for d \geq 1. It consists of a sequence of n+1 distinct lattice points \omega = (\omega_0, \omega_1, \dots, \omega_n), where \omega_0 is the starting point (often taken as the origin $0 \in \mathbb{Z}^d) and each consecutive pair satisfies \|\omega_{i+1} - \omega_i\|_1 = 1 for i = 0, 1, \dots, n-1, meaning the steps are to nearest-neighbor sites along the lattice edges. The key constraint is the absence of self-intersections: \omega_i \neq \omega_j for all $0 \leq i < j \leq n. This setup ensures the walk traces a path without revisiting any site, modeling non-overlapping configurations in discrete space.[1] The walks are typically undirected in the sense that steps can proceed in any of the $2d possible nearest-neighbor directions from the current site, though the sequence itself imposes a directionality to the path. In some contexts, SAWs may be restricted to directed steps (e.g., only positive coordinates), but the standard formulation allows bidirectional movement while prohibiting loops or overlaps. This no-intersection rule applies strictly to site visits, distinguishing SAWs from lattice animals or other path models that might permit edge crossings without site revisits.[1] For illustration on the square lattice \mathbb{Z}^2 (where d=2 and nearest neighbors differ by \pm e_1 or \pm e_2, with e_1 = (1,0), e_2 = (0,1)), a length-1 SAW is simply (0,0) \to (1,0), a straight step with no opportunity for intersection. A length-2 example without overlap is the bent path (0,0) \to (1,0) \to (1,1), whereas (0,0) \to (1,0) \to (0,0) is invalid due to revisiting the origin. These short paths highlight how the self-avoidance constraint begins to limit configurations even at small scales, unlike simple random walks on the same lattice, which permit arbitrary revisits and thus explore space more freely without intersection prohibitions.[1]Historical development
The concept of the self-avoiding walk (SAW) originated in the context of polymer physics during the mid-20th century, primarily as a model for the conformations of long-chain molecules under the excluded volume effect, where chain segments cannot occupy the same space. In 1947, W.J.C. Orr provided the first exact enumerations of SAWs on lattices, computing the number of walks up to length 6 to study polymer configurations at infinite dilution. This work laid early groundwork for numerical approaches, though limited by computational constraints of the time. Subsequently, in 1949, Paul J. Flory formalized the SAW as a key tool for modeling real polymer chains, deriving approximate scaling relations for their end-to-end distances and emphasizing the role of self-avoidance in preventing unphysical overlaps or knots in chain statistics. The 1950s and 1960s saw the transition of SAWs from a physical model to a rigorous mathematical object, with initial focus on enumeration and bounds. Pioneering computations by Michael E. Fisher and M.F. Sykes in 1959 extended enumerations to walks of length up to 9 on square and cubic lattices, enabling estimates of growth constants. In 1963, Harry Kesten established fundamental upper and lower bounds on the number of n-step SAWs, proving that the connective constant μ (the limit of the nth root of the number of walks) exists and lies between 2^{1/d} and 2d-1 for d-dimensional lattices, where d is the dimension. These results, built on combinatorial arguments, shifted attention toward asymptotic behavior and marked the beginning of SAW as a central problem in probability and statistical mechanics. By the 1970s, SAWs gained prominence in the study of critical phenomena and phase transitions, linking polymer statistics to broader universality classes. Pierre-Gilles de Gennes, in 1972, connected SAWs to the n-vector model in the limit n → 0 using Kenneth Wilson's renormalization group framework, providing a field-theoretic perspective on critical exponents and facilitating predictions for polymer dimensions near criticality. Michael E. Fisher further advanced this by analyzing SAW scaling in relation to Ising model correlations during the same decade, highlighting shared universality with other long-range interacting systems. These developments solidified SAWs as a paradigm for non-Markovian processes in statistical physics. In the 1980s, SAWs were firmly established as a cornerstone model in statistical mechanics, with rigorous proofs of mean-field behavior above the upper critical dimension d=4 by Takao Hara and others, and lace expansion techniques introduced by Gordon Slade confirming Gaussian-like asymptotics in high dimensions. By the 1990s, the model extended to more general settings, including SAWs on arbitrary networks and graphs, as explored in Neal Madras and Gordon Slade's 1996 monograph, which analyzed random walk analogs and connectivity on non-regular structures.[4] Connections to percolation theory also emerged, particularly through the dilute limit where SAWs model incipient infinite clusters, influencing studies of transport and exploration on percolating lattices.Mathematical properties
Enumeration
The number c_n denotes the total number of distinct n-step self-avoiding walks starting from the origin on a given lattice, where each walk is a sequence of adjacent lattice sites without revisiting any site.[1] This count is typically considered up to rotations and reflections only if specified, but standard enumerations fix the starting point and count all possible paths. Examples include the integer lattice \mathbb{Z}^2 (square lattice) and the honeycomb lattice, where the geometry affects the possible configurations.[5] Exact enumeration of c_n relies on recursive algorithms and transfer-matrix methods, which systematically build walks step by step while enforcing the self-avoidance condition. Recursive approaches, such as pruning enumerators, discard invalid partial walks early to reduce computational complexity, achieving growth rates around $1.3^n for practical implementations.[6] Transfer-matrix techniques model the enumeration on finite lattice strips, propagating connectivity states across rows to count walks of increasing length.[7] These methods have yielded exact values for the square lattice up to n = 79, with earlier computations reaching n = 71 and n = 51 using similar algebraic and parallelized strategies.[8][6] No closed-form formula for c_n exists in general, as counting self-avoiding walks of fixed length is #P-complete even on subgraphs of two-dimensional grids.[9] The growth rate of c_n is characterized by the connective constant \mu = \lim_{n \to \infty} c_n^{1/n}, which provides a subexponential measure of branching possibilities. On the square lattice, \mu \approx 2.63815853, while on the honeycomb lattice, \mu = \sqrt{2 + \sqrt{2}} \approx 1.84775907, the only lattice where \mu is known exactly.[10][1] Asymptotically, c_n \sim A \mu^n n^{\gamma - 1}, where A is a critical amplitude and \gamma is a universal critical exponent (detailed in the section on critical exponents). Generating functions, formed as \sum c_n x^n, serve as a tool to analyze these counts through series expansions and singularity analysis.[5] The following table lists exact values of c_n for the square lattice up to n = 20, computed via recursive and transfer-matrix methods; higher values up to n = 79 are available but grow rapidly in magnitude.[8]| n | c_n |
|---|---|
| 1 | 4 |
| 2 | 12 |
| 3 | 36 |
| 4 | 100 |
| 5 | 284 |
| 6 | 780 |
| 7 | 2172 |
| 8 | 5916 |
| 9 | 16268 |
| 10 | 44100 |
| 11 | 120292 |
| 12 | 326120 |
| 13 | 889636 |
| 14 | 2420544 |
| 15 | 6605960 |
| 16 | 17997620 |
| 17 | 49142412 |
| 18 | 134006524 |
| 19 | 365436720 |
| 20 | 997497644 |