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.

${\displaystyle {m+n \choose m,n}}$

En el estudio de estos caminos surgen dos preguntas fundamentales:

1. ¿Cuántos SAWs de longitud ${\displaystyle n}$ se pueden construir sobre determinada rejilla?
2. ¿Cuál es el comportamiento asintótico de un SAW de longitud ${\displaystyle n}$, cuando ${\displaystyle n}$ tiende a infinito?

SAW sobre la rejilla cuadrada^[2]​

Definición

 

SAW sobre la rejilla tridimensional 1x1x1

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:

1. ${\displaystyle w(0)=x}$  y ${\displaystyle w(n)=y}$ 
2. ${\displaystyle ||w(i+1)-w(i)||=1}$  para todo ${\displaystyle i\in \{0,1,...,n-1\}}$ 
3. ${\displaystyle w(i)\neq w(j)}$  siempre que ${\displaystyle i\neq j}$ 

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.

Historia

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.

Algunos tipos de rejillas regulares

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):

Rejilla cuadrada: Cuatro cuadrados tienen un vértice en común.     Rejilla triangular: Formada por triángulos equiláteros adyacentes.     Rejilla hexagonal: Forma semejante a la de una colmena

Constante de conectividad

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

• ${\displaystyle c_{1}=2d}$ 
• ${\displaystyle c_{2}=2d(2d-1)}$ 
• ${\displaystyle c_{3}=2d(2d-1)^{2}}$ 
• ${\displaystyle c_{4}=2d(2d-1)^{3}-2d(2d-2)}$ .

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).

 

Tabla 1: Número de ${\displaystyle c_{n}}$  sobre la rejilla cuadrada 2-dimensional.

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 A\mu ^{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 _{n\longrightarrow \infty }(c_{n})^{1/n}}$ 

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

Una propiedad de ${\displaystyle c_{n}}$  es que la sucesión ${\displaystyle \{c_{n}\}_{n\geq 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.638158530323\pm 2\times 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).

SAWs sobre rejillas de dimensión mayor

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 n\leqslant 34}$  y ${\displaystyle n\leqslant 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:

• ${\displaystyle d=1}$ : el problema es trivial ya que el camino sólo puede tomar dos direcciones la positiva o la negativa y continuar hasta completar los ${\displaystyle n}$  pasos, por lo tanto existen 2 SAWs de tamaño ${\displaystyle n}$ , es decir, ${\displaystyle c_{n}=2}$ . También está determinada la constante de conectividad ${\displaystyle \mu =\lim _{n\longrightarrow \infty }2^{1/n}=1}$ . La relación ${\displaystyle c_{n}\sim A\mu ^{n}n^{\gamma -1}}$  se cumple trivialmente tomando ${\displaystyle A=2}$  y ${\displaystyle \gamma =1}$ 

• ${\displaystyle d\geq 5}$ : Para los casos en que la dimensión del hipercubo ${\displaystyle \mathbb {Z} ^{d}}$  es demasiado grande, el estudio de los SAWs se puede reducir al concepto de los caminos aleatorios simples ya que la probabilidad de que el camino se intercepte a sí mismo es menor a medida que aumenta la dimensión. El proceso matemático que permite realizar dicha simplificación es la expansión de encajes .

 

Tabla 2: Intervalo estimado de ${\displaystyle \mu }$  para las dimensiones d=2,3,4,5,6.

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

• ${\displaystyle d=2}$ : El cálculo del número de caminos de tamaño ${\displaystyle n}$  en esta dimensión está fundamentado por su asociación al proceso SLE (Stochastic Loewner evolution), y sustentado por los métodos de simulación numérica de Montecarlo , mediante los cuales se calcula de manera precisa el valor de ${\displaystyle c_{n}}$  para todo ${\displaystyle n}$  finito. en la sección anterior se mencionó el valor ${\displaystyle \gamma }$  conocido como exponente crítico, para ${\displaystyle d=2}$  este exponente tiene el valor ${\displaystyle \gamma =43/32}$ .

• ${\displaystyle d=3}$ : no tiene un método matemático exacto para proporcionar resultados. sin embargo existen tres métodos computacionales de los cuales se obtienen valores aproximados para la constantes más importantes, a saber: El método de Montecarlo; un artículo acerca de métodos computacionales para la física teórica^[3]​ y el método de expansión de encajes (utilizado para todo ${\displaystyle d\geq 3}$ ).^[4]​ El valor de ${\displaystyle \gamma =1.1575}$  predicho por el método de Montecarlo es consistente con el resultado ${\displaystyle \gamma =1.1568}$  bajo la extensión por encajes.

• ${\displaystyle d=4}$ : los resultados se obtienen mediante un factor de corrección logarítmica (${\displaystyle \log(n)^{1/4}.}$  ). El comportamiento de ${\displaystyle c_{n}}$  para ésta dimensión se basa en la fórmula ${\displaystyle c_{n}\sim A\log(n)^{1/4}\mu ^{n}n^{\gamma -1}}$ , donde ${\displaystyle \sim }$  representa un comportamiento asintótico, así, a medida que aumenta ${\displaystyle n}$  la constante es más cercana a dicho valor, ${\displaystyle A}$  y ${\displaystyle \gamma }$  son constantes. En el caso ${\displaystyle d=4}$  la constante ${\displaystyle \gamma }$  toma el valor ${\displaystyle 1}$ 

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.

Polígonos auto-evitados (SAP)

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.

 

SAPs sobre la rejilla cuadrada (Imagen tomada de http://arxiv.org/pdf/cond-mat/0302513.pdf)

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.

 

Tabla 3: Número de SAPs sobre la rejilla cuadrada 2-dimensional según perímetro dado.

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\to \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\to \infty }(a_{n}^{\frac {1}{n}})}$ .

Algoritmo de un SAW en 2D^[5]​

${\displaystyle SAW(i,N)}$  
${\displaystyle i=}$  number of steps made, ${\displaystyle 0<i<N}$  
${\displaystyle N=}$  desired length of the walk 
${\displaystyle (x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i-1},y_{i-1})}$  is self-avoiding. 
 
if not visited ${\displaystyle (x_{i},y_{i})}$  then  if ${\displaystyle i=N}$  then 
  print "${\displaystyle (x_{0},y_{0}),...(x_{N},y_{N})}$  is a SAW" 
else visited ${\displaystyle (x_{i},y_{i})}$  = true; 
 ${\displaystyle x_{i+1}=x_{i}+1;y_{i+1}=y_{i};SAW(i+1,N)}$ ; 
 ${\displaystyle x_{i+1}=x_{i}-1;y_{i+1}=y_{i};SAW(i+1,N)}$ ; 
 ${\displaystyle x_{i+1}=x_{i};y_{i+1}=y_{i}+1;SAW(i+1,N)}$ ; 
 ${\displaystyle x_{i+1}=x_{i};y_{i+1}=y_{i}-1;SAW(i+1,N)}$ ; 
 visited ${\displaystyle (x_{i},y_{i})}$  = false; 

Referencias

1. Wikipedia. «Lattice graph» |url= incorrecta con autorreferencia (ayuda). 
2. «Self-avoiding walk simulation». 
3. R. Guida, J. Zinn-Justin. «Critical exponents of the N-vector model». 
4. N. Clisby, R. Liang, and G. Slade. J. Phys. «Self-avoiding walk enumeration via the lace expansion.».  Falta la |url= (ayuda)
5. «Recursive 2D SAW Algorithm». 

Bibliografía

• Slade Gordon, Madras Neal (1996). The Self-Avoding Walk. Birkhäuser. 

Enlaces externos

• http://mathworld.wolfram.com/Self-AvoidingWalkConnectiveConstant.html
• http://mathworld.wolfram.com/Self-AvoidingWalk.html
• http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r21/pdf
• http://www.ams.org/journals/bull/1998-35-04/S0273-0979-98-00762-9/S0273-0979-98-00762-9.pdf
• http://www.asiapacific-mathnews.com/02/0204/0001_0010.pdf
• http://stat.math.uregina.ca/~kozdron/Research/Students/Jabib.pdf
• https://www.math.ubc.ca/~slade/spa_proceedings.pdf

•   Datos: Q7448025