Selbstmeidender Pfad

In d​er mathematischen Theorie d​er Irrfahrten s​ind selbstmeidende Pfade Wege a​uf einem Gitter, d​ie nie z​u einem bereits z​uvor besuchten Punkt zurückkehren.

Dieser Pfad kehrt nie zu einem bereits besuchten Punkt zurück.

Selbstmeidende Pfade s​ind das einfachste mathematische Modell für d​ie Anordnung langer Polymerketten.

Die Berechnung selbstmeidender Pfade ist ein zentrales Thema der Perkolationstheorie. Es gibt zahlreiche durch empirische Untersuchungen und Heuristiken gestützte Vermutungen über das Verhalten selbstmeidender Pfade. Mathematisch bewiesen ist von diesen Vermutungen aber nur wenig, gerade auch in den für Anwendungen interessanten niedrigen Dimensionen ${\displaystyle 2\leq d\leq 4}$.

Definition

Quadratgitter ${\displaystyle \mathbb {Z} ^{2}}$

Hexagonalgitter

Es sei ${\displaystyle \Lambda \subset \mathbb {R} ^{d}}$ ein Gitter im ${\displaystyle d}$-dimensionalen Raum, zum Beispiel ${\displaystyle \mathbb {Z} ^{d}\subset \mathbb {R} ^{d}}$ oder das Hexagonalgitter in der Ebene.

Ein selbstmeidender Pfad im Gitter ${\displaystyle \Lambda }$ ist ein Pfad (Weg), der jeden Gitterpunkt höchstens einmal besucht.

Anzahl selbstmeidender Pfade

Zu einem gegebenen Gitter ${\displaystyle \Lambda }$ sei ${\displaystyle c_{n}}$ die Anzahl selbstmeidender Pfade der Länge ${\displaystyle n}$. Die Folge ${\displaystyle c_{n}}$ ist subadditiv und demzufolge existiert der Grenzwert

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

Er w​ird als d​ie Zusammenhangskonstante (englisch: connective constant) d​es Gitters bezeichnet.

Das einzige Gitter, für d​as die Zusammenhangskonstante explizit bekannt ist, i​st das Hexagonalgitter. Für dieses h​aben Duminil-Copin u​nd Smirnow bewiesen, dass

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

ist.[1]

Für das Gitter ${\displaystyle \mathbb {Z} ^{d}\subset \mathbb {R} ^{d}}$ gilt die Ungleichung

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

Für ${\displaystyle d=2}$, also für das Quadratgitter ${\displaystyle \mathbb {Z} ^{2}}$, kann man numerisch ${\displaystyle \mu =2{,}63815853\ldots }$ berechnen.

Numerische Experimente stützen die Vermutung, dass für alle Gitter asymptotisch ${\displaystyle c_{n}\sim n^{\frac {11}{32}}\mu ^{n}}$ gilt, was bedeuten würde, dass im Gegensatz zum exponentiellen Faktor ${\displaystyle \mu ^{n}}$ der subexponentielle Faktor ${\displaystyle n^{\frac {11}{32}}}$ für alle Gitter derselbe wäre.

Literatur

• N. Madras, G. Slade: The Self-Avoiding Walk. Birkhäuser, 1996, ISBN 0-8176-3891-1.
• G. F. Lawler: Intersections of Random Walks. Birkhäuser, 1991, ISBN 0-8176-3892-X.
• N. Madras, A. D. Sokal: The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk. In: Journal of Statistical Physics. Band 50, 1988, S. 109–186. doi:10.1007/bf01022990.
• M. E. Fisher: Shape of a self-avoiding walk or polymer chain. In: Journal of Chemical Physics. Band 44, Nr. 2, 1966, S. 616. bibcode:1966JChPh..44..616F. doi:10.1063/1.1726734.

Weblinks

• Geiger: Algorithmen und Zufall
• Self Avoiding Walk (MathWorld)
• Gordon Slade, Self avoiding walk. A brief survey (PDF; 470 kB)

Einzelnachweise

1. Hugo Duminil-Copin, Stanislav Smirnov: The connective constant of the honeycomb lattice equals ${\displaystyle {\sqrt {2+{\sqrt {2}}}}}$. In: Ann. of Math. Band 175, Nr. 3, 2012, S. 1653–1665.