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 cuadrada 2-dimensional  formada por los puntos en  cuyas componentes son enteras. Un SAW es por lo tanto un camino de longitud  que recorre las aristas de la rejilla sin interceptarse consigo mismo.

En el estudio de estos caminos surgen dos preguntas fundamentales:

 ¿Cuántos SAWs de longitud  se pueden construir sobre determinada rejilla?
 ¿Cuál es el comportamiento asintótico de un SAW de longitud , cuando  tiende a infinito?

Definición 

Sean  y  puntos en . Un SAW sobre  es una función  que satisface las siguientes condiciones:  

  y 
  para todo 
  siempre que  

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

Constante de conectividad 

Sea  el número de SAWs de longitud  sobre la rejilla . Para valores pequeños de  se puede conocer , por ejemplo 

 
 
 
 . 

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

Gracias a Jensen, Pönitz y Tittmann se conocen la cota inferior y superior de  como sigue: 

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

De la expresión del acotamiento para  mencionada con anterioridad, se puede deducir: 

Una propiedad de  es que la sucesión  es superaditiva, pues los SAWs de longitud  pueden ser formados por concatenaciones de SAW de longitud  y de longitud , pero no todas estas concatenaciones son SAW lo cual significa que  y tomando logaritmo a ambos lados se obtiene que

El lema de Fekete junto con la expresión anterior garantizan la existencia de .

Para el caso 2-dimensional de la rejilla cuadrada la mejor aproximación de esta constante es , en la rejilla triangular  y en la rejilla hexagonal el valor de  está dado por , 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  que existen en una rejilla hypercubica  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  pasos. El número de caminos de longitud  y  para las dimensiones  y , respectivamente, han sido enumerados por Madras y Slade.

Teniendo en cuenta cada una de las diferentes dimensiones () se tiene lo siguiente:

 : el problema es trivial ya que el camino sólo puede tomar dos direcciones la positiva o la negativa y continuar hasta completar los  pasos, por lo tanto existen 2 SAWs de tamaño , es decir, . También está determinada la constante de conectividad . La relación  se cumple trivialmente tomando  y 

 : Para los casos en que la dimensión del hipercubo  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 .

Los casos más importantes serán así .

 : El cálculo del número de caminos de tamaño  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  para todo  finito. en la sección anterior se mencionó el valor  conocido como exponente crítico, para  este exponente tiene el valor .

 : 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 y el método de expansión de encajes (utilizado para todo ). El valor de  predicho por el método de Montecarlo es consistente con el resultado  bajo la extensión por encajes.

 : los resultados se obtienen mediante un factor de corrección logarítmica ( ). El comportamiento de  para ésta dimensión se basa en la fórmula , donde  representa un comportamiento asintótico, así, a medida que aumenta  la constante es más cercana a dicho valor,  y  son constantes. En el caso  la constante  toma el valor 

De otro lado, no es posible encontrar el valor exacto de la constante de conectividad  para las diferentes dimensiones de la rejilla , 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  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  notado por , así como también el número de SAPs de área  notado por . Se puede definir una función generadora de perímetro de la siguiente manera:

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:

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

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

Además, las constantes de crecimiento  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 .

Algoritmo de un SAW en 2D 

   
   number of steps made,  
  desired length of the walk 
  is self-avoiding.  
 if not visited  then
           if  then 
                     print " is a SAW" 
 else
            visited  = true; 
            ; 
            ; 
            ; 
            ; 
            visited  = false;

Referencias

Bibliografía

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

Geometría discreta
Polígonos
Física computacional
Química computacional