Self-avoiding walks

This article page is a stub, please help by expanding it.

A self-avoiding walk (SAW) is a lattice path (sequence of moves between adjacent lattice nodes) that does not visit any lattice node more than once.

From Wikipedia:Self-avoiding walk:

SAWs were first 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. 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.

A self-avoiding polygon (SAP) is a self-avoiding cycle (closed self-avoiding walk).

Hamiltonian lattice walks

A Hamiltonian lattice walk is a Hamiltonian path on a lattice that visits each lattice node exactly once.

A Hamiltonian lattice cycle is a Hamiltonian cycle (or Hamiltonian circuit) on a lattice, i.e. a closed Hamiltonian lattice walk.

Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Lattice graphs vs grid graphs

Lattice graphs have their values located at the corners of grid cells. Lattice graph edges join the corners of grid cells.

Grid graphs have their values located at the centers of grid cells. Grid graph edges join the centers of grid cells.

An (m+1) X (n+1) square lattice constitutes the cell corners (coordinates (0,0) to (m,n)) of an m X n square grid.

Self-avoiding walks on a 0-dimensional lattice

Trivial, the point lattice (a single node) has only the null walk (staying put on that single node).

Self-avoiding walks on a 1-dimensional lattice

Trivial, a path lattice of length n has only one walk from nodes (0) to (n-1).

Self-avoiding walks on a 2-dimensional lattice

Self-avoiding walks on a 2-dimensional square lattice

Self-avoiding walks of length n on a 2-dimensional square lattice

Self-avoiding walks of length $\scriptstyle n\,$ on a 2-dimensional square lattice which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.

$\scriptstyle n\,$	Self-avoiding walks of length $\scriptstyle n\,$
1	⦁ ⎪ ⦁ ⎪   ⎪ ⦁ ⎪ ⦁
2	⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁
3	⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

A046170 Number of self-avoiding walks on a 2-D lattice of length $\scriptstyle n,\,n\,\geq \,1,\,$ which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.

{1, 2, 5, 12, 30, 73, 183, 456, 1151, 2900, 7361, 18684, 47652, 121584, 311259, 797311, 2047384, 5260692, 13542718, 34884239, 89991344, 232282110, 600281932, 1552096361, 4017128206, 10401997092, 26957667445, 69892976538, ...}

Self-avoiding walks on an (m+1) X (n+1) square lattice starting from (0,0) and ending at (m,n)

The apex of the triangle ($\scriptstyle m\,=\,n\,=\,0\,$) corresponds to the 0-dimensional lattice with only the null walk.

The first column ($\scriptstyle n\,=\,0\,$) corresponds to 1-dimensional lattices (path lattice of length $\scriptstyle m\,$) with only one walk from nodes (0) to (m).

R(m,n), the number of self-avoiding walks on an (m+1) X (n+1) square lattice starting from (0,0) and ending at (m,n)

$\scriptstyle m\,$ = 0	1
1	1	2
2	1	4	12
3	1	8	38	184
4	1	16	125	976	8512
5	1	32	414	5382	79384	1262816
6	1	64	?	?	?	?	575780564
7	1	128	?	?	?	?	?	789360053252
8	1	256	?	?	?	?	?	?	3266598486981642
9	1	512	?	?	?	?	?	?	?	41044208702632496804
10	1	1024	?	?	?	?	?	?	?	?	1568758030464750013214100
	$\scriptstyle n\,$ = 0	1	2	3	4	5	6	7	8	9	10

Self-avoiding walks on an (n+1) X (n+1) square lattice starting from (0,0) and ending at (n,n)

Self-avoiding walks on an (n+1) X (n+1) square lattice starting from (0,0) and ending at (n,n)

$\scriptstyle n\,$	Self-avoiding walks starting from (0,0) and ending at (n,n)
1	⦁ ⎪ ⦁ ⎪   ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪   ⎪ ⦁ ⎪ ⦁
2	⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪   ⎪   ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

A007764 Number of self-avoiding walks from (0,0) to (n,n), n ≥ 0, of a (n+1) X (n+1) square lattice. Number of nonintersecting (or self-avoiding) rook paths joining opposite corner cells of an n X n grid. (should it be (n+1) X (n+1) grid, since rooks move from center to center of adjacent grid cells? — Daniel Forgues 06:06, 3 January 2012 (UTC))

{1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, ...}

Hamiltonian self-avoiding walks on a 2-dimensional square lattice

Example of a Hamiltonian self-avoiding walk on a 9 X 9 square lattice (corners of cells of an 8 X 8 square grid)

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

⎪

⦁

Example of a Hamiltonian self-avoiding walk on a 15 X 15 square lattice (corners of cells of a 14 X 14 square grid)

Template:Self-avoiding walk

Self-avoiding walks on a 2-dimensional equilateral triangular lattice

Self-avoiding walks of length n on a 2-dimensional equilateral triangular lattice

(...)

Self-avoiding walks on an equilateral triangular lattice starting from (0,0) and ending at (n,0)

(...)

Self-avoiding walks on a 3-dimensional lattice

Self-avoiding walks on a 3-dimensional cubic lattice

(...)

Self-avoiding walks of length n on a 3-dimensional cubic lattice

(...)

Self-avoiding walks on an (l+1) X (m+1) X (n+1) cubic lattice starting from (0,0,0) and ending at (l,m,n)

(...)

Self-avoiding walks on an (n+1) X (n+1) X (n+1) cubic lattice starting from (0,0,0) and ending at (n,n,n)

(...)

Self-avoiding walks on a 4-dimensional lattice

Self-avoiding walks on a 4-dimensional hypercubic lattice

(...)

Self-avoiding walks of length n on a 4-dimensional hypercubic lattice

(...)

Self-avoiding walks on a (k+1) X (l+1) X (m+1) X (n+1) cubic lattice starting from (0,0,0,0) and ending at (k,l,m,n)

(...)

Self-avoiding walks on an (n+1) X (n+1) X (n+1) X (n+1) hypercubic lattice starting from (0,0,0,0) and ending at (n,n,n,n)

(...)

See also

• Template:Tlxb graphic template

External links

• Template:MathWorld
• Template:Wikipedia