Camí autoevitante

Un camí auto-evitat, o self-avoiding walk (SAW), és un camí que unix dos punts en un grafo pla en la condició de que no passa pel mateix punt més d'una volta. En particular, es poden considerar camins sobre la reixeta quadrada 2-dimensional ${\mathbb{Z}}^2$ formada pels punts en ${ℝ}^2$ les components dels quals són sanceres. Un SAW és per lo tant un camí de llongitut $n$ que recorre les arestes de la reixeta sense interceptar-se en si mateixa.

$(\genfrac{}{}{0ex}{}{m+n}{m,n})$

En l'estudi d'estos camins sorgixen dos preguntes fonamentals:

1. ¿Quànts SAWs de llongitut $n$ es poden construir sobre determinada reixeta?
2. ¿Quin és el comportament asintòtic d'un SAW de llongitut $n$, quan $n$ tendix a infinit?

Archiu:Latticee.gif

SAW sobre la reixeta quadrada

Archiu:Натурализация гамильтоновых циклов.jpg

Tres eixemples en un gràfic de celosía quadrada 8x8

Definició

Archiu:Cubo3.gif

SAW sobre la reixeta tridimensional 1x1x1

Sean $x$ i $y$ punts en ${\mathbb{Z}}^d$. Un SAW sobre ${\mathbb{Z}}^d$ és una funció $w:\{0,1,\mathrm{...},n\}⟶{\mathbb{Z}}^d$ que satisfà les següents condicions:

1. $w(0)=x$ i $w(n)=y$
2. $||w(i+1)-w(i)||=1$ para tot $i\in \{0,1,\mathrm{...},n-1\}$
3. $w(i)\ne w(j)$ sempre que $i\ne j$

En esta definició la condició 2. establix que el camí transita solament per les arestes de la reixeta (passos de llongitut 1) i no permet passos en direcció diagonal; i la condició 3. garantisa que en efecte el camí no passa per un punt que ya havia recorregut.

Història

Un model derivat dels camins aleatoris simples és el dels camins auto-evitats, que han segut estudiats durant casi mig sigle i va ser desenrollat inicialment en química física en l'intenció d'analisar el comportament de cadenes de polímeros quan es coloquen en un bon dissolvent (puix els polímero tenen la característica de que cap cadena es pot creuar en cap punt). La resposta al problema presentat per químics i físics va ser tractar de trobar un model simplificat que capturara la propietat essencial dels polímero, inicialment el millor d'ells es va basar en els camins aleatoris i va ser propost fa 60 anys pel químic alemà Kuhn. Una nova resposta va ser descoberta pel nobel Paul Flory en térmens de camins aleatoris auto-evitats i des de llavors els físics han tractat de verificar les seues prediccions i els matemàtics d'establir el seu rigurosidad.

En l'invenció dels computadors, un nou progrés va ser conseguit per mig de la modelació de camins aleatoris auto-evitats en reixetes quadrades i cúbiques. En 1954 Wall, Hiller i Wheeler, i en 1955 Rosenbluth varen tractar de programar simulacions de SAWs pero la provabilitat d'alcançar la llongitut $n$ abans del seu auto-intersecció va ser mínima. En 1982, el físic Nienhuis va trobar una solució exacta per a un model de dos dimensions, llavors el resultat presentat per Flory era correcte, pero esta hipòtesis mai va ser provada en la rigurosidad matemàtica necessària. Finalment, en la década de 1980, Hara, Slade, Lawler, Schramm, Werner i atres matemàtics en un intent per establir resultats rigorosos varen conseguir alvanços significatius.