The growing self-avoiding walk (GSAW), introduced in 1984 under this name by Lyklema and Kremer and independently as the kinetic growth walk by Majid, Jan, Coniglio and Stanley, grows on a lattice by stepping to a uniformly chosen unoccupied nearest-neighbor site and becomes trapped when none exists; unlike the canonical self-avoiding walk (SAW), its ensemble is history-dependent. The central question since the model's introduction is whether the GSAW belongs to the SAW universality class — whether its size exponent ν\nu equals the SAW value (exactly 3/4 in two dimensions, written in the source as the Flory form 3/(d+2)3/(d+2)) — after the alternative true-self-avoiding-walk class was conclusively excluded. Padmanabhan (2014) proposed two routes toward the exponent — rigorous analysis of the depth-first-search enumeration algorithm for restricted walks with finite memory, and detailed analysis of a proposed generalization, motivated by condensation polymerization, in which the walker computes its step probabilities by looking a finite number of steps ahead instead of one only — and both routes remain unfinished.

Background

A self-avoiding walk (SAW) on a lattice is a path that never revisits a site; it is the standard lattice model of a polymer chain in good solvent, with every nn-step walk taken as equally likely. The number of nn-step SAWs grows like μn\mu^n (μ\mu the connective constant of the lattice), and the mean-square end-to-end distance grows like ⟨Rn2⟩∼n2ν\langle R_n^2\rangle\sim n^{2\nu} with size exponent ν\nu: ν=3/4\nu=3/4 exactly in two dimensions (Nienhuis's derivation from the O(n) loop model), ν≈0.587597(7)\nu\approx0.587597(7) in three dimensions (Clisby), and ν=1/2\nu=1/2 for d≥4d\ge4. The Flory mean-field estimate of the exponent is 3/(d+2)3/(d+2), exact only at d=2d=2; the source paper writes the SAW universality-class value in this Flory form. The growing self-avoiding walk (GSAW) is an irreversible growth variant of the SAW, introduced in 1984 under this name by Lyklema and Kremer and, independently, as the kinetic growth walk by Majid, Jan, Coniglio and Stanley (the double naming was itself disputed in a 1985 Physical Review Letters exchange between Kremer-Lyklema and Pietronero). Starting at the origin, the walk at each step moves to a uniformly chosen unoccupied nearest-neighbor site and is trapped when no such site exists; the probability of a particular nn-step walk is the product over its steps of the reciprocals of the number of available sites at that step (the local atmosphere), so the ensemble is history-dependent and biased toward more compact configurations relative to the uniform SAW measure. Trapping occurs with probability one (Hemmer and Hemmer), with a mean trapping length of approximately 71 steps on the square lattice — a famous number known only empirically. Because the two-dimensional exponent measured at accessible lengths (about 0.66-0.68, below 3/4) lies near the value 2/(d+1)2/(d+1) of the true self-avoiding walk (a different model of Amit, Parisi and Peliti in which the walker may revisit sites but is repelled by the local occupation time), the founding literature debated whether the GSAW belongs to the true-self-avoiding-walk universality class or to the SAW class. The former option was conclusively excluded; the latter was never established. Lyklema and Kremer argued from Monte Carlo series analysis that the GSAW exponent approaches the SAW value only at walk lengths far beyond simulation reach. On the honeycomb lattice there is an exact physics-level statement: the kinetic growth walk ensemble coincides with the interacting self-avoiding walk (a SAW with an energetic weight per nearest-neighbor contact) at inverse temperature ln 2 (Poole, Coniglio, Jan and Stanley), which lies in the expanded, good-solvent phase and hence in the SAW universality class; no proof of exponent values exists in any dimension, and even ν=3/4\nu=3/4 for the ordinary SAW on the square lattice remains unproved rigorously. Several neighbors must not be confused with the GSAW: the true self-avoiding walk just described; the smart kinetic walk, a never-trapping variant that steps only to sites from which continuation remains possible, exactly related to percolation hulls (Weinrib and Trugman) and analyzed via Schramm-Loewner evolution (SLE, a family of exactly described random planar curves that provably gives the scaling limits of several two-dimensional critical lattice models; Kennedy); and confined ordinary SAWs (Klein), whose strip connective constants happen to agree with those of GSAWs on strips of the same width — a key numerical support for the conjectured common universality class. Padmanabhan's 2014 source paper re-examined the GSAW as a model of addition polymerization (one monomer added at a time), argued it suits only that case, and proposed a GSAW-trees model for condensation (step-growth) polymerization together with a family of generalized walks in which the walker computes its step probabilities by looking a finite number of steps ahead rather than one only, the plain GSAW being the smallest member. The paper reports exact enumerations (mean-square end-to-end distances, survival probabilities) at modest sizes and proposes two routes toward the exponent: rigorous analysis of the depth-first-search (DFS) enumeration algorithms for restricted walks with finite memory, and asymptotic analysis of the generalized family, including inclusion-exclusion recursions and generating functions whose formal conventions appear only in the paywalled full text. The exponent question, and the analysis along both proposed routes, were left open; the source frames the two routes as proposed methods of studying the universality question rather than as independent goals.

Problem Statement

Determine whether the growing self-avoiding walk belongs to the self-avoiding-walk universality class. The GSAW starts at the origin of a regular lattice of dimension dd and at each step moves to a uniformly chosen unoccupied nearest-neighbor site — the probability of a given nn-step walk being the product over its steps of the reciprocals of the number of available sites at that step — and becomes trapped when no unoccupied nearest neighbor exists. Does the size exponent ν\nu governing the mean-square end-to-end distance (equivalently, the radius of gyration) of surviving nn-step walks exist as n→∞n\to\infty, and does it equal the self-avoiding-walk universality-class value — 3/43/4 at d=2d=2, ≈0.587597(7)\approx0.587597(7) at d=3d=3, and 1/21/2 for d≥4d\ge4, the source writing the d=2d=2 value in the Flory form 3/(d+2)3/(d+2) (which agrees with the SAW exponent only at d=2d=2)? Prove or disprove this for every lattice dimension d≥2d\ge2. The source (Padmanabhan 2014) proposes two routes toward this goal — rigorous analysis of the depth-first-search enumeration algorithm for restricted walks with finite memory, and detailed analysis of its proposed generalization in which the walker computes its step probabilities by looking a finite number of steps ahead instead of one only — but these are suggested instruments, not mandatory deliverables: a resolution of the exponent question settles the problem whether or not it proceeds along either proposed route.

References

  1. A. S. Padmanabhan, "Growing self avoiding walk trees", Journal of Mathematical Chemistry 52, 355-367 (2014). DOI: 10.1007/s10910-013-0267-z. https://doi.org/10.1007/s10910-013-0267-z
  2. A. S. Padmanabhan and Susamma Jacob, "Self avoiding walk trees and laces", Journal of Mathematical Chemistry 52, 627-645 (2014). DOI: 10.1007/s10910-013-0283-z. https://doi.org/10.1007/s10910-013-0283-z
  3. Imtiaz Majid, Naeem Jan, Antonio Coniglio and H. Eugene Stanley, "Kinetic Growth Walk: A New Model for Linear Polymers", Physical Review Letters 52, 1257-1260 (1984). DOI: 10.1103/PhysRevLett.52.1257. https://doi.org/10.1103/PhysRevLett.52.1257
  4. J. W. Lyklema and K. Kremer, "The growing self avoiding walk", Journal of Physics A: Mathematical and General 17, L691-L696 (1984). DOI: 10.1088/0305-4470/17/13/003. https://doi.org/10.1088/0305-4470/17/13/003
  5. K. Kremer and J. W. Lyklema, "Indefinitely Growing Self-Avoiding Walk", Physical Review Letters 54, 267-269 (1985). DOI: 10.1103/PhysRevLett.54.267. https://doi.org/10.1103/PhysRevLett.54.267
  6. K. Kremer and J. W. Lyklema, "Monte Carlo series analysis of irreversible self-avoiding walks. I. The indefinitely-growing self-avoiding walk (IGSAW)", Journal of Physics A: Mathematical and General 18, 1515-1531 (1985). DOI: 10.1088/0305-4470/18/9/031. https://doi.org/10.1088/0305-4470/18/9/031
  7. J. W. Lyklema and K. Kremer, "Monte Carlo series analysis of irreversible self-avoiding walks. II. The growing self-avoiding walk", Journal of Physics A: Mathematical and General 19, 279-289 (1986). DOI: 10.1088/0305-4470/19/2/021. https://doi.org/10.1088/0305-4470/19/2/021
  8. L. Pietronero, "Survival Probability for Kinetic Self-Avoiding Walks", Physical Review Letters 55, 2025-2027 (1985). DOI: 10.1103/PhysRevLett.55.2025. https://doi.org/10.1103/PhysRevLett.55.2025
  9. K. Kremer and J. W. Lyklema, "Kinetic Growth Models", Physical Review Letters 55, 2091 (1985). DOI: 10.1103/PhysRevLett.55.2091. https://doi.org/10.1103/PhysRevLett.55.2091
  10. S. Hemmer and P. C. Hemmer, "An average self-avoiding random walk on the square lattice lasts 71 steps", The Journal of Chemical Physics 81, 584-585 (1984). DOI: 10.1063/1.447349. https://doi.org/10.1063/1.447349
  11. P. C. Hemmer and S. Hemmer, "Trapping of genuine self-avoiding walks", Physical Review A 34, 3304-3308 (1986). DOI: 10.1103/PhysRevA.34.3304. https://doi.org/10.1103/PhysRevA.34.3304
  12. Peter H. Poole, Antonio Coniglio, Naeem Jan and H. Eugene Stanley, "Universality classes of the theta and theta' points", Physical Review B 39, 495-504 (1989). DOI: 10.1103/PhysRevB.39.495. https://doi.org/10.1103/PhysRevB.39.495
  13. Bernard Nienhuis, "Exact Critical Point and Critical Exponents of O(n) Models in Two Dimensions", Physical Review Letters 49, 1062-1065 (1982). DOI: 10.1103/PhysRevLett.49.1062. https://doi.org/10.1103/PhysRevLett.49.1062
  14. Nathan Clisby, "Accurate Estimate of the Critical Exponent nu for Self-Avoiding Walks via a Fast Implementation of the Pivot Algorithm", Physical Review Letters 104, 055702 (2010). DOI: 10.1103/PhysRevLett.104.055702. https://doi.org/10.1103/PhysRevLett.104.055702
  15. M. Ponmurugan, S. L. Narasimhan and K. P. N. Murthy, "Is kinetic growth walk equivalent to canonical self-avoiding walk?", Physica A: Statistical Mechanics and its Applications 371, 171-176 (2006). DOI: 10.1016/j.physa.2006.03.058, arXiv:cond-mat/0602370. https://doi.org/10.1016/j.physa.2006.03.058
  16. Wyatt Hooper and Alexander R. Klotz, "Trapping in self-avoiding walks with nearest-neighbor attraction", Physical Review E 102, 032132 (2020). DOI: 10.1103/PhysRevE.102.032132, arXiv:2006.12680. https://doi.org/10.1103/PhysRevE.102.032132
  17. Alexander R. Klotz and Everett Sullivan, "Exactly-Solvable Self-Trapping Lattice Walks. Part I: Trapping in Ladder Graphs", arXiv:2207.00539 (2022); published as "Exactly-solvable self-trapping lattice walks in ladder graphs", Discrete Mathematics (2026). DOI: 10.1016/j.disc.2026.115315. https://arxiv.org/abs/2207.00539
  18. Jay Pantone, Alexander R. Klotz and Everett Sullivan, "Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height", arXiv:2407.18205 (2024); published as "Exactly-solvable self-trapping lattice walks on lattices of arbitrary height", Annales de l'Institut Henri Poincare D, Combinatorics, Physics and their Interactions (2026). DOI: 10.4171/aihpd/226. https://arxiv.org/abs/2407.18205
  19. Christophe Laforge, Hayk Mikayelyan and Patrick Senet, "Trapping statistics in growing self-interacting self-avoiding walks: Square versus honeycomb lattices", Physical Review E 110, 064120 (2024). DOI: 10.1103/PhysRevE.110.064120. https://doi.org/10.1103/PhysRevE.110.064120
  20. Abraham Taniya, Murali Deepthi and Alapat Padmanabhan, "Statistical mechanics of addition polymerisation. Calculations of the expectation and variance of the average atmosphere in growing self avoiding walks", AIP Advances 8, 065205 (2018). DOI: 10.1063/1.5030045. https://doi.org/10.1063/1.5030045
  21. A. Weinrib and S. A. Trugman, "A new kinetic walk and percolation perimeters", Physical Review B 31, 2993-2997 (1985). DOI: 10.1103/PhysRevB.31.2993. https://doi.org/10.1103/PhysRevB.31.2993
  22. Tom Kennedy, "The Smart Kinetic Self-Avoiding Walk and Schramm Loewner Evolution", Journal of Statistical Physics 160, 302-320 (2015). DOI: 10.1007/s10955-015-1271-4, arXiv:1408.6714. https://doi.org/10.1007/s10955-015-1271-4
  23. Douglas J. Klein, "Asymptotic distributions for self-avoiding walks constrained to strips, cylinders, and tubes", Journal of Statistical Physics 23, 561-586 (1980). DOI: 10.1007/BF01011730. https://doi.org/10.1007/BF01011730