Self-avoiding path

This path never returns to a point already visited.

In the mathematical theory of random walks , self-avoiding paths are paths on a grid that never return to a previously visited point.

Self-avoiding paths are the simplest mathematical model for arranging long polymer chains .

The computation of self-avoiding paths is a central topic of percolation theory . There are numerous assumptions about the behavior of self-avoiding paths, supported by empirical research and heuristics. However, little has been mathematically proven of these assumptions, especially in the low dimensions that are interesting for applications . ${\displaystyle 2\leq d\leq 4}$

definition

Square grid ${\displaystyle \mathbb {Z} ^{2}}$

Hexagonal grid

Let it be a lattice in -dimensional space , for example, or the hexagonal lattice in the plane. ${\displaystyle \Lambda \subset \mathbb {R} ^{d}}$ ${\displaystyle d}$ ${\displaystyle \mathbb {Z} ^{d}\subset \mathbb {R} ^{d}}$

A self-avoiding path in the grid is a path that visits each grid point at most once. ${\displaystyle \Lambda }$

Number of self-avoiding paths

For a given grid, let the number of self-avoiding paths be of length . The consequence is subadditive and therefore the limit value exists ${\displaystyle \Lambda }$ ${\displaystyle c_{n}}$ ${\displaystyle n}$ ${\displaystyle c_{n}}$

${\displaystyle \mu =\lim _{n\to \infty }c_{n}^{\frac {1}{n}}}$.

It will serve as the connection constant (English: connective constant ) denotes the grid.

The only lattice for which the connected constant is explicitly known is the hexagonal lattice. For this, Duminil-Copin and Smirnow have proven that

${\displaystyle \mu =2\cos \left({\frac {\pi }{8}}\right)={\sqrt {2+{\sqrt {2}}}}}$

is.

The inequality applies to the grid ${\displaystyle \mathbb {Z} ^{d}\subset \mathbb {R} ^{d}}$

${\displaystyle d\leq \mu \leq 2d-1}$.

For , i.e. for the square grid , one can calculate numerically . ${\displaystyle d=2}$ ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle \mu =2{,}63815853\ldots }$

Numerical experiments support the conjecture that asymptotically holds for all grids , which would mean that, in contrast to the exponential factor, the subexponential factor would be the same for all grids. ${\displaystyle c_{n}\sim n^{\frac {11}{32}}\mu ^{n}}$ ${\displaystyle \mu ^{n}}$ ${\displaystyle n^{\frac {11}{32}}}$

literature

• Madras, N .; Slade, G. (1996). The Self-Avoiding Walk. Birkhäuser. ISBN 978-0-8176-3891-7 .
• Lawler, GF (1991). Intersections of Random Walks. Birkhäuser. ISBN 978-0-8176-3892-4 .
• Madras, N .; Sokal, AD (1988). The pivot algorithm - A highly efficient Monte-Carlo method for the self-avoiding walk . Journal of Statistical Physics 50. doi : 10.1007 / bf01022990 .
• Fisher, ME (1966). Shape of a self-avoiding walk or polymer chain . Journal of Chemical Physics 44 (2): 616. bibcode : 1966JChPh..44..616F . doi : 10.1063 / 1.1726734 .

Web links

• Geiger: Algorithms and chance
• Self Avoiding Walk (MathWorld)
• Gordon Slade, Self avoiding walk. A brief survey (PDF)

Individual evidence

1. ↑ Duminil-Copin, Hugo; Smirnov, Stanislav: The connective constant of the honeycomb lattice equals . ${\displaystyle {\sqrt {2+{\sqrt {2}}}}}$Ann. of Math. (2) 175 (2012), no. 3, 1653-1665.