self-avoiding walk

{{unsolved|mathematics|Is there a formula or algorithm that can calculate the number of self-avoiding walks in any given lattice?}}

In mathematics, a self-avoiding walk (SAW) is a sequence of moves on a lattice (a lattice path) that does not visit the same point more than once. This is a special case of the graph theoretical notion of a path. A self-avoiding polygon (SAP) is a closed self-avoiding walk on a lattice. Very little is known rigorously about the self-avoiding walk from a mathematical perspective, although physicists have provided numerous conjectures that are believed to be true and are strongly supported by numerical simulations.

In computational physics, a self-avoiding walk is a chain-like path in {{math|R²}} or {{math|R³}} with a certain number of nodes, typically a fixed step length and has the property that it doesn't cross itself or another walk. A system of SAWs satisfies the so-called excluded volume condition. In higher dimensions, the SAW is believed to behave much like the ordinary random walk.

SAWs and SAPs play a central role in the modeling of the topological and knot-theoretic behavior of thread- and loop-like molecules such as proteins. Indeed, SAWs may have first been introduced by the chemist Paul Flory{{cite book|author=P. Flory|author-link=Paul Flory|title=Principles of Polymer Chemistry|year=1953|publisher=Cornell University Press|isbn= 9780801401343|pages=672}}{{Dubious |Wrong usage of pages in citation |reason=Page 672 is last Page! Also the wrong book? |date=September 2016}} in order to model the real-life behavior of chain-like entities such as solvents and polymers, whose physical volume prohibits multiple occupation of the same spatial point.

SAWs are fractals. For example, in {{math|d {{=}} 2}} the fractal dimension is 4/3, for {{math|d {{=}} 3}} it is close to 5/3 while for {{math|d ≥ 4}} the fractal dimension is {{math|2}}. The dimension is called the upper critical dimension above which excluded volume is negligible. A SAW that does not satisfy the excluded volume condition was recently studied to model explicit surface geometry resulting from expansion of a SAW.{{cite journal|author=A. Bucksch|author2=G. Turk|author2-link=Greg Turk|author3=J.S. Weitz|title=The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion|year=2014| journal=PLOS ONE|volume=9|issue=1|pages=e85585| doi=10.1371/journal.pone.0085585|pmid=24465607|pmc=3899046|arxiv=1304.3521|bibcode=2014PLoSO...985585B|doi-access=free}}{{what|reason=This "orphan" sentence is not explained in the article.|date=October 2023}}

The properties of SAWs cannot be calculated analytically, so numerical simulations are employed. The pivot algorithm is a common method for Markov chain Monte Carlo simulations for the uniform measure on {{mvar|n}}-step self-avoiding walks. The pivot algorithm works by taking a self-avoiding walk and randomly choosing a point on this walk, and then applying symmetrical transformations (rotations and reflections) on the walk after the {{mvar|n}}th step to create a new walk.

Calculating the number of self-avoiding walks in any given lattice is a common computational problem. There is currently no known formula, although there are rigorous methods of approximation.{{cite journal|author=Hayes B|date=Jul–Aug 1998|title=How to Avoid Yourself|journal=American Scientist|volume=86|issue=4|page=314|doi=10.1511/1998.31.3301|url=http://bit-player.org/wp-content/extras/bph-publications/AmSci-1998-07-Hayes-self-avoidance.pdf}}{{cite journal |author1=Liśkiewicz M |author2=Ogihara M |author3=Toda S |title=The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes |journal=Theoretical Computer Science |volume=304 |issue=1–3 |pages=129–56 |date=July 2003 | doi=10.1016/S0304-3975(03)00080-X |doi-access=free }}

Universality

One of the phenomena associated with self-avoiding walks and statistical physics models in general is the notion of universality, that is, independence of macroscopic observables from microscopic details, such as the choice of the lattice. One important quantity that appears in conjectures for universal laws is the connective constant, defined as follows. Let {{mvar|c_n}} denote the number of {{mvar|n}}-step self-avoiding walks. Since every {{math|(n + m)}}-step self avoiding walk can be decomposed into an {{mvar|n}}-step self-avoiding walk and an {{mvar|m}}-step self-avoiding walk, it follows that {{math|c_n+m ≤ c_nc_m}}. Therefore, the sequence {{math|{log c_n} }} is subadditive and we can apply Fekete's lemma to show that the following limit exists:

: $\mu = \lim_{n \to \infty} c_n^{\frac{1}{n}}.$

{{mvar|μ}} is called the connective constant, since {{mvar|c_n}} depends on the particular lattice chosen for the walk so does {{mvar|μ}}. The exact value of {{mvar|μ}} is only known for the hexagonal lattice, found by Stanislav Smirnov and Hugo Duminil-Copin, where it is equal to:{{cite journal|last1=Duminil-Copin|first1=Hugo|last2=Smirnov|first2=Stanislav|author2-link=Stanislav Smirnov|title=The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)|journal=Annals of Mathematics|date=1 May 2012|volume=175|issue=3|pages=1653–1665|doi=10.4007/annals.2012.175.3.14|arxiv=1007.0575|s2cid=59164280}}

: $\sqrt{2 + \sqrt{2}}.$

For other lattices, {{mvar|μ}} has only been approximated numerically, and is believed not to even be an algebraic number. It is conjectured that{{cite journal | last1=Lawler | first1=Gregory F. | last2=Schramm | first2=Oded | author2-link = Oded Schramm | last3=Werner | first3=Wendelin | journal=Proceedings of Symposia in Pure Mathematics | pages=339–364 | publisher=American Mathematical Society | title=On the scaling limit of planar self-avoiding walk | date=2004 | volume=72 | issue=2 | doi=10.1090/pspum/072.2/2112127 | isbn=0-8218-3638-2 | arxiv=math/0204277| s2cid=16710180 }}

: $c_n \approx \mu^n n^{\frac{11}{32}}$

as {{math|n → ∞}}, where {{mvar|μ}} depends on the lattice, but the power law correction $n^{\frac{11}{32}}$ does not; in other words, this law is believed to be universal.

On networks

Self-avoiding walks have also been studied in the context of network theory.{{cite journal |author= Carlos P. Herrero|year= 2005|title= Self-avoiding walks on scale-free networks|journal= Phys. Rev. E|volume= 71|issue= 3|pages= 1728 |doi=10.1103/PhysRevE.71.016103|pmid= 15697654|arxiv= cond-mat/0412658|bibcode= 2005PhRvE..71a6103H|s2cid= 2707668}} In this context, it is customary to treat the SAW as a dynamical process, such that in every time-step a walker randomly hops between neighboring nodes of the network. The walk ends when the walker reaches a dead-end state, such that it can no longer progress to newly un-visited nodes. It was recently found that on Erdős–Rényi networks, the distribution of path lengths of such dynamically grown SAWs can be calculated analytically, and follows the Gompertz distribution.{{cite journal|last1=Tishby|first1=I.|last2=Biham|first2=O.|last3=Katzav|first3=E.|title=The distribution of path lengths of self avoiding walks on Erdős–Rényi networks|journal=Journal of Physics A: Mathematical and Theoretical|date=2016|volume=49|issue=28|pages=285002|doi=10.1088/1751-8113/49/28/285002|arxiv=1603.06613|bibcode=2016JPhA...49B5002T|s2cid=119182848}} For arbitrary networks, the distribution of path lengths of the walk, the degree distribution of the non-visited network and the first-hitting-time distribution to a node can be obtained by solving a set of coupled recurrence equations.{{cite journal |last1=Colombani |first1=G. |last2=Bertagnolli |first2=G. |last3=Artime |first3=O. |title=Efficient network exploration by means of resetting self-avoiding random walkers |journal=Journal of Physics: Complexity |date=2023 |volume=4 |issue=4 |pages=04LT01 |doi=10.1088/2632-072X/acff33 |doi-access=free |arxiv=2310.03203 |bibcode=2023JPCom...4dLT01C }}

Limits

Consider the uniform measure on {{mvar|n}}-step self-avoiding walks in the full plane. It is currently unknown whether the limit of the uniform measure as {{math|n → ∞}} induces a measure on infinite full-plane walks. However, Harry Kesten has shown that such a measure exists for self-avoiding walks in the half-plane. One important question involving self-avoiding walks is the existence and conformal invariance of the scaling limit, that is, the limit as the length of the walk goes to infinity and the mesh of the lattice goes to zero. The scaling limit of the self-avoiding walk is conjectured to be described by Schramm–Loewner evolution with parameter {{math|κ {{=}} {{sfrac|8|3}}.}}

References

External links

{{OEIS el|1=A007764|2=Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid}}—the number of self-avoiding paths joining opposite corners of an N × N grid, for N from 0 to 12. Also includes an extended list up to N = 21.
{{MathWorld|urlname=Self-AvoidingWalk|title=Self-Avoiding Walk}}
[http://polymer.bu.edu/java/java/saw/saw.html Java applet of a 2D self-avoiding walk]
[https://github.com/abucksch/FiberWalk Generic python implementation to simulate SAWs and expanding FiberWalks on a square lattices in n-dimensions.]
[http://www.sas.upenn.edu/~vnanda/software.html Norris software] to generate SAWs on the Diamond cubic.

Category:Polygons

Category:Discrete geometry

Category:Computational physics

Category:Computational chemistry

Category:Variants of random walks