Camino autoevitante

Un camino auto-evitado, o self-avoiding walk (SAW), es un camino que une dos puntos en un grafo plano con la condición de que no pasa por el mismo punto más de una vez. En particular, se pueden considerar caminos sobre la rejilla^[1]​ cuadrada 2-dimensional ${displaystyle mathbb {Z} ^{2}}$ formada por los puntos en ${displaystyle mathbb {R} ^{2}}$ cuyas componentes son enteras. Un SAW es por lo tanto un camino de longitud ${displaystyle n}$ que recorre las aristas de la rejilla sin interceptarse consigo mismo.

En el estudio de estos caminos surgen dos preguntas fundamentales:

Sean ${displaystyle x}$ y ${displaystyle y}$ puntos en ${displaystyle mathbb {Z} ^{d}}$. Un SAW sobre ${displaystyle mathbb {Z} ^{d}}$ es una función ${displaystyle w:{0,1,...,n}longrightarrow mathbb {Z} ^{d}}$ que satisface las siguientes condiciones:

En ésta definición la condición 2. establece que el camino transita solo por las aristas de la rejilla (pasos de longitud 1) y no permite pasos en dirección diagonal; y la condición 3. garantiza que en efecto el camino no pasa por un punto que ya había recorrido.

Un modelo derivado de los caminos aleatorios simples es el de los caminos auto-evitados, que han sido estudiados durante casi medio siglo y fue desarrollado inicialmente en química física con la intención de analizar el comportamiento de cadenas de polímeros cuando se colocan en un buen disolvente (pues los polímeros tienen la característica de que ninguna cadena se puede cruzar en ningún punto). La respuesta al problema presentado por químicos y físicos fue tratar de encontrar un modelo simplificado que capturara la propiedad esencial de los polímeros, inicialmente el mejor de ellos se basó en los caminos aleatorios y fue propuesto hace 60 años por el químico alemán Kuhn. Una nueva respuesta fue descubierta por el nobel Paul Flory en términos de caminos aleatorios auto-evitados y desde entonces los físicos han tratado de verificar sus predicciones y los matemáticos de establecer su rigurosidad.

Con la invención de los computadores, un nuevo progreso fue logrado mediante el modelado de caminos aleatorios auto-evitados en rejillas cuadradas y cúbicas. En 1954 Wall, Hiller y Wheeler, y en 1955 Rosenbluth trataron de programar simulaciones de SAWs pero la probabilidad de alcanzar la longitud ${displaystyle n}$ antes de su auto-intersección fue mínima. En 1982, el físico Nienhuis encontró una solución exacta para un modelo de dos dimensiones, entonces el resultado presentado por Flory era correcto, pero esta hipótesis nunca fue probada con la rigurosidad matemática necesaria. Finalmente, en la década de 1980, Hara, Slade, Lawler, Schramm, Werner y otros matemáticos en un intento por establecer resultados rigurosos lograron avances significativos.

En general, se consideran caminos auto-evitados sobre la rejilla cuadrada pero también se pueden construir SAWs sobre diferentes tipos de rejillas regulares como se observa a continuación (ejemplos bidimensionales):

Sea ${displaystyle c_{n}}$ el número de SAWs de longitud ${displaystyle n}$ sobre la rejilla ${displaystyle mathbb {Z} ^{d}}$. Para valores pequeños de ${displaystyle n}$ se puede conocer ${displaystyle c_{n}}$, por ejemplo

Sin embargo, debido al crecimiento acelerado se vuelve casi imposible determinar el valor de ${displaystyle c_{n}}$ a medida que ${displaystyle n}$ aumenta (Tabla 1).

Gracias a Jensen, Pönitz y Tittmann se conocen la cota inferior y superior de ${displaystyle c_{n}}$ como sigue:

${displaystyle d^{n}leq c_{n}leq 2d(2d-1)^{n-1}}$

Además, se conjetura que en los SAWs ${displaystyle c_{n}}$ crece exponencialmente y su comportamiento está dado por: ${displaystyle c_{n}sim Amu ^{n}n^{gamma -1}}$ donde ${displaystyle A,gamma }$ son constantes positivas que dependen de la dimensión. ${displaystyle mu }$ se conoce como la constante de conectividad y ${displaystyle gamma }$ como exponente critico. El valor de ${displaystyle mu }$ es finito y positivo pero no es conocido con exactitud en cualquier dimensión ${displaystyle d}$ de la rejilla ${displaystyle mathbb {Z} ^{d}}$ y su existencia se sigue del siguiente límite siempre definido (Hammersley y Morton - 1954)

${displaystyle mu =lim _{nlongrightarrow infty }(c_{n})^{1/n}}$

De la expresión del acotamiento para ${displaystyle c_{n}}$ mencionada con anterioridad, se puede deducir: ${displaystyle dleq mu leq 2d-1}$

Una propiedad de ${displaystyle c_{n}}$ es que la sucesión ${displaystyle {c_{n}}_{ngeq 0}}$ es superaditiva, pues los SAWs de longitud ${displaystyle n+m}$ pueden ser formados por concatenaciones de SAW de longitud ${displaystyle n}$ y de longitud ${displaystyle m}$, pero no todas estas concatenaciones son SAW lo cual significa que ${displaystyle c_{m+n}leq c_{n}c_{m}}$ y tomando logaritmo a ambos lados se obtiene que

${displaystyle log(c_{n+m})leq log(c_{n})+log(c_{m})}$

El lema de Fekete junto con la expresión anterior garantizan la existencia de ${displaystyle mu }$.

Para el caso 2-dimensional de la rejilla cuadrada la mejor aproximación de esta constante es ${displaystyle mu =2.638158530323pm 2 imes 10^{-12}}$, en la rejilla triangular ${displaystyle mu =4.15079}$ y en la rejilla hexagonal el valor de ${displaystyle mu }$ está dado por ${displaystyle mu ={sqrt {2+{sqrt {2}}}}}$, valor conjeturado por Nienhuis (1982) y probado recientemente por Duminil- Copin y Smirnov (2010).

Contar la cantidad de SAWs de longitud ${displaystyle n}$ que existen en una rejilla hypercubica ${displaystyle mathbb {Z} ^{d}}$ es uno de los problemas abiertos más importantes en la teoría de la combinatoria. Se puede asumir que los caminos comienzan en el origen y se mueven a través de la red hasta completar ${displaystyle n}$ pasos. El número de caminos de longitud ${displaystyle nleqslant 34}$ y ${displaystyle nleqslant 21}$ para las dimensiones ${displaystyle d=2}$ y ${displaystyle d=3}$, respectivamente, han sido enumerados por Madras y Slade.

Teniendo en cuenta cada una de las diferentes dimensiones (${displaystyle d=1,2,3,4,5,dots }$) se tiene lo siguiente:

Los casos más importantes serán así ${displaystyle d=2,3,4}$.

De otro lado, no es posible encontrar el valor exacto de la constante de conectividad ${displaystyle mu }$ para las diferentes dimensiones de la rejilla ${displaystyle mathbb {Z} ^{d}}$, sin embargo existen aproximaciones como se muestra en el tabla 2.

Un polígono auto-evitado, o self-avoiding polygon (SAP), sobre una rejilla regular es un SAW de ${displaystyle n}$ pasos cerrado, es decir, un SAP es un camino cerrado que no se interseca consigo mismo excepto en el caso para el cual el punto de partida es adyacente al punto de llegada. Se observa entonces que un SAP es un caso particular de un SAW.
Una definición alternativa de un polígono auto-evitado es: un subgrafo conexo (de un enrejado) cuyos vértices son de grado 0 o 2.

En mecánica estadística los SAPs sobre enrejados regulares se consideran problemas interesantes de combinatoria y resultan ser de gran utilidad para modelar diversos fenómenos biológicos.

Un problema fundamental en el estudio de estos polígonos es determinar o calcular el número de SAPs de perímetro ${displaystyle m}$ notado por ${displaystyle p_{m}}$, así como también el número de SAPs de área ${displaystyle n}$ notado por ${displaystyle a_{n}}$. Se puede definir una función generadora de perímetro de la siguiente manera:

${displaystyle P(x)=sum _{m}p_{m}x^{m}}$

Sobre la rejilla cuadrada el SAP más pequeño que se puede construir es el cuadrado unitario cuyo perímetro es 4.

En la serie presentada en la tabla 3 se puede observar la manera en la que aumenta el número de SAPs con perímetro dado sobre la rejilla cuadrada (El perímetro es siempre par a menos que se considere otra rejilla regular como la triangular o la hexagonal).

De manera análoga se define una función generadora de área como sigue:

${displaystyle A(q)=sum _{n}a_{n}q^{n}}$

Si ${displaystyle p_{m,n}}$ denota el número de polígonos de perímetro ${displaystyle m}$ y área ${displaystyle n}$, la función generadora asociada está dada por

${displaystyle (x,q)=sum _{m,n}p_{m,n}x^{m}q^{n}}$

Como es el caso de los SAWs, el número de SAPs también crece exponencialmente, este hecho se observa a partir de la expresión

${displaystyle mu =lim _{m o infty }(p_{2m}^{frac {1}{2m}})}$

Además, las constantes de crecimiento ${displaystyle mu }$ asociadas al caso de los polígonos y, al de los caminos, coinciden. Adicional a esto existe otra constante de crecimiento para los SAPs relacionada con la función generadora de área ${displaystyle lambda =lim _{n o infty }(a_{n}^{frac {1}{n}})}$.