Self-avoiding walk
In mathematics, a self-avoiding walk is a sequence of moves on a lattice 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 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 or 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 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 the fractal dimension is 4/3, for it is close to 5/3 while for the fractal dimension is. 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. The average size of a self-avoiding walk increases with respect to its length according to an exponent that is the reciprocal of the fractal dimension. The radius of gyration of a SAW depends on the 3/4 power of length in two dimensions, and approximately the 3/5th power in three dimensions.
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 -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 on the walk after the 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.
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 denote the number of -step self-avoiding walks. Since every -step self avoiding walk can be decomposed into an -step self-avoiding walk and an -step self-avoiding walk, it follows that. Therefore, the sequence is subadditive and we can apply Fekete's lemma to show that the following limit exists:is called the connective constant, since depends on the particular lattice chosen for the walk so does. The exact value of is only known for the hexagonal lattice, found by Stanislav Smirnov and Hugo Duminil-Copin, where it is equal to:
For other lattices, has only been approximated numerically, and is believed not to even be an algebraic number. It is conjectured that
as, where depends on the lattice, but the power law correction does not; in other words, this law is believed to be universal.
Growing self-avoiding walk
The growing self-avoiding walk is a dynamical process in which a walk starts at the origin of a lattice and takes a step to an unoccupied site in a random direction. When there are no empty adjacent sites, the walk is said to be trapped, similar to the ending scenario in the video game Snake. On a square lattice it is known from computer simulations that the average number of steps reached by a growing self-avoiding walk is approximately 71. The shortest walk that leads to trapping on a square lattice is six steps, and can be achieved by starting on an empty lattice and moving up, right, right, down, down, left, and up. The average number of steps to trapping depends on the lattice or network, it is similar for the honeycomb lattice but near 78 for the triangular lattice. The average trapping length is much higher in three dimensions, being close to 4000 for the simple cubic lattice. The statistics of the traditional self-avoiding walk assume that each walk of a given length is equally likely, which is not the case for GSAWs. For example, there are 100 square lattice SAWs of length 4 starting at the origin, and four that are completely straight, such that there is a 0.04 probability of such a SAW being straight. However, a GSAW must make its first step in any direction with probability 1, its second in the same direction with probability 1/3, as with its third and fourth steps. Thus the probability of a GSAW being straight is 1/81≈0.012. For this reason, GSAWs are empirically observed in simulations to have a smaller scaling exponent than the 3/4 predicted by the Flory model, and is observed to be close to 0.68.Knots in self-avoiding polygons
Self-avoiding polygons in three dimensions may form knots.On a simple cubic lattice the shortest knotted self-avoiding polygon is a trefoil knot that occupies 24 vertices.
As self-avoiding polygons of greater length are considered, the probability of finding knots increases. It is proven that as the length of a randomly chosen SAP increases, the probability of finding an unknot decreases exponentially, implying that the probability of a self-avoiding polygon being knotted approaches 100% as its length increases.
The length of a SAP at which the probability of knotting on a face-centered cubic lattice reaches 50% is approximately 100,000, and this may vary in other lattices.
Self-avoiding walks that are not closed into polygons may also form entanglements that are colloquially recognized as knots, but these are not formally considered knots within knot theory unless the two ends of the walk are connected in some way.