Caminata de autoevitación

En matemáticas , un camino autoevitante ( SAW , por sus siglas en inglés) es una secuencia de movimientos en una red (un camino reticular ) que no visita el mismo punto más de una vez. Este es un caso especial de la noción de camino en la teoría de grafos . Un polígono autoevitante ( SAP , por sus siglas en inglés) es un camino autoevitante cerrado en una red. Se sabe muy poco rigurosamente sobre el camino autoevitante desde una perspectiva matemática, aunque los físicos han proporcionado numerosas conjeturas que se consideran ciertas y que están fuertemente respaldadas por simulaciones numéricas.

En física computacional , un camino autoevitante es una trayectoria en cadena en R² o R³ con un número determinado de nodos, típicamente ^{con una longitud de paso fija ,} y tiene la propiedad de no cruzarse a sí mismo ni a otro camino. Un sistema de caminos autoevitantes satisface la condición de volumen excluido . En dimensiones superiores, se cree que el camino autoevitante se comporta de forma muy similar a un camino aleatorio ordinario .

Las SAW y las SAP desempeñan un papel fundamental en la modelización del comportamiento topológico y de teoría de nudos de moléculas con forma de hilo o bucle, como las proteínas . De hecho, es posible que las SAW hayan sido introducidas por primera vez por el químico Paul Flory ^{[ 1 ]} para modelar el comportamiento real de entidades con forma de cadena, como disolventes y polímeros , cuyo volumen físico impide la ocupación múltiple del mismo punto espacial.

Los SAW son fractales . Por ejemplo, en d = 2 la dimensión fractal es 4/3, para d = 3 es cercana a 5/3 mientras que para d ≥ 4 la dimensión fractal es 2. La dimensión se llama dimensión crítica superior por encima de la cual el volumen excluido es despreciable. Un SAW que no satisface la condición de volumen excluido fue estudiado recientemente para modelar la geometría de superficie explícita resultante de la expansión de un SAW. ^{[ 2 ]} El tamaño promedio de un camino autoevitante aumenta con respecto a su longitud según un exponente que es el recíproco de la dimensión fractal. El radio de giro de un SAW depende de la potencia 3/4 de la longitud en dos dimensiones, y aproximadamente de la potencia 3/5 en tres dimensiones.

Las propiedades de las SAW no se pueden calcular analíticamente, por lo que se emplean simulaciones numéricas. El algoritmo de pivote es un método común para simulaciones de Monte Carlo de cadenas de Markov para la medida uniforme en caminatas autoevitantes de n pasos. El algoritmo de pivote funciona tomando una caminata autoevitante y eligiendo aleatoriamente un punto en ella, para luego aplicar transformaciones simétricas (rotaciones y reflexiones) a la caminata después del n -ésimo paso y crear una nueva.

Calcular el número de caminos autoevitantes en cualquier red dada es un problema computacional común . Actualmente no se conoce ninguna fórmula, aunque existen métodos de aproximación rigurosos. ^{[ 3 ] [ 4 ]}

Uno de los fenómenos asociados con los caminos autoevitantes y los modelos de física estadística en general es la noción de universalidad , es decir, la independencia de las observables macroscópicas de los detalles microscópicos, como la elección de la red. Una cantidad importante que aparece en las conjeturas sobre leyes universales es la constante de conexión , definida de la siguiente manera. Sea c _n el número de caminos autoevitantes de n pasos. Dado que cada camino autoevitante de ( n + m ) pasos puede descomponerse en un camino autoevitante de n pasos y un camino autoevitante de m pasos, se deduce que c _{n + m} ≤ c _n c _m . Por lo tanto, la secuencia {log c _n } es subaditiva y podemos aplicar el lema de Fekete para demostrar que existe el siguiente límite:

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

μ se denomina constante de conectividad , ya que c _n depende de la red particular elegida para el recorrido, al igual que μ . El valor exacto de μ solo se conoce para la red hexagonal, hallada por Stanislav Smirnov y Hugo Duminil-Copin , donde es igual a: ^{[ 5 ]}

${\displaystyle {\sqrt {2+{\sqrt {2}}}}.}$

Para otras redes, μ solo se ha aproximado numéricamente y se cree que ni siquiera es un número algebraico . Se conjetura que ^{[ 6 ]}

${\displaystyle c_{n}\approx \mu ^{n}n^{\frac {11}{32}}}$

cuando n → ∞ , donde μ depende de la red, pero la corrección de la ley de potencias${\displaystyle n^{\frac {11}{32}}}$No; en otras palabras, se cree que esta ley es universal.

El camino autoevitante creciente (GSAW) es un proceso dinámico en el que un camino comienza en el origen de una red y da un paso a un sitio desocupado en una dirección aleatoria. Cuando no hay sitios adyacentes vacíos, se dice que el camino está atrapado, similar al escenario final del videojuego Snake . En una red cuadrada, se sabe por simulaciones de computadora que el número promedio de pasos alcanzado por un camino autoevitante creciente es aproximadamente 71. ^{[ 7 ]} El camino más corto que lleva al atrapamiento en una red cuadrada es de seis pasos, y se puede lograr comenzando en una red vacía y moviéndose hacia arriba, derecha, derecha, abajo, abajo, izquierda y arriba. El número promedio de pasos para el atrapamiento depende de la red o red, es similar para la red de panal pero cerca de 78 para la red triangular . La longitud promedio de atrapamiento es mucho mayor en tres dimensiones, siendo cercana a 4000 para la red cúbica simple . ^{[ 8 ]} Las estadísticas de la caminata autoevitante tradicional asumen que cada caminata de una longitud dada es igualmente probable, lo cual no es el caso para las GSAW. Por ejemplo, hay 100 SAW de red cuadrada de longitud 4 que comienzan en el origen, y cuatro que son completamente rectas, de modo que hay una probabilidad de 0,04 de que una SAW sea recta. Sin embargo, una GSAW debe dar su primer paso en cualquier dirección con probabilidad 1, su segundo en la misma dirección con probabilidad 1/3, al igual que su tercer y cuarto pasos. Por lo tanto, la probabilidad de que una GSAW sea recta es 1/81≈0,012. Por esta razón, se observa empíricamente en simulaciones que las GSAW tienen un exponente de escala menor (la relación entre el radio de giro promedio y la longitud) que el 3/4 predicho por el modelo de Flory, y se observa que está cerca de 0,68. ^{[ 9 ]}

Los polígonos autoevitantes en tres dimensiones pueden formar nudos . En una red cúbica simple, el polígono autoevitante anudado más corto es un nudo de trébol que ocupa 24 vértices. ^{[ 10 ]} A medida que se consideran polígonos autoevitantes de mayor longitud, la probabilidad de encontrar nudos aumenta. Está demostrado que a medida que aumenta la longitud de un SAP elegido al azar, la probabilidad de encontrar un nudo disminuye exponencialmente , lo que implica que la probabilidad de que un polígono autoevitante esté anudado se acerca al 100% a medida que aumenta su longitud. La longitud de un SAP en la que la probabilidad de anudar en una red cúbica centrada en las caras alcanza el 50% es aproximadamente 100 000, y esto puede variar en otras redes. ^{[ 11 ]} Los caminos autoevitantes que no están cerrados en polígonos también pueden formar enredos que se reconocen coloquialmente como nudos, pero estos no se consideran formalmente nudos dentro de la teoría de nudos a menos que los dos extremos del camino estén conectados de alguna manera.

Los recorridos autoevitantes también se han estudiado en el contexto de la teoría de redes . ^{[ 12 ]} En este contexto, es habitual tratar el SAW como un proceso dinámico, de modo que en cada paso de tiempo un caminante salta aleatoriamente entre nodos vecinos de la red. El recorrido termina cuando el caminante alcanza un estado de callejón sin salida, de modo que ya no puede avanzar a nodos recién no visitados. Recientemente se descubrió que en las redes de Erdős-Rényi , la distribución de longitudes de camino de dichos SAW de crecimiento dinámico se puede calcular analíticamente y sigue la distribución de Gompertz . ^{[ 13 ]} Para redes arbitrarias, la distribución de longitudes de camino del recorrido, la distribución de grados de la red no visitada y la distribución del tiempo de primera llegada a un nodo se pueden obtener resolviendo un conjunto de ecuaciones de recurrencia acopladas. ^{[ 14 ]}

Consideremos la medida uniforme en caminatas autoevitantes de n pasos en el plano completo. Actualmente se desconoce si el límite de la medida uniforme cuando n → ∞ induce una medida en caminatas infinitas en el plano completo. Sin embargo, Harry Kesten ha demostrado que existe tal medida para caminatas autoevitantes en el semiplano. Una cuestión importante relacionada con las caminatas autoevitantes es la existencia e invariancia conforme del límite de escala , es decir, el límite cuando la longitud de la caminata tiende a infinito y la malla de la red tiende a cero. Se conjetura que el límite de escala de la caminata autoevitante se describe mediante la evolución de Schramm-Loewner con parámetro κ = 8 / 3 .

• Fenómenos críticos : física asociada a los puntos críticos. 
• Camino hamiltoniano : camino en un grafo que visita cada vértice exactamente una vez. 
• Recorrido del caballo : un conjunto de problemas matemáticos en un tablero de ajedrez. 
• Paseo aleatorio : proceso que forma un camino a partir de muchos pasos aleatorios. 
• Serpiente – Género de videojuegos 
• Universalidad : concepto en mecánica estadística 
• Curvas que llenan el espacio : todas son autoevitantes.

• Secuencia OEIS A007764 (Número de caminos de torres que no se intersecan (o se evitan a sí mismos) que unen esquinas opuestas de una cuadrícula n × n) : el número de caminos que se evitan a sí mismos que unen esquinas opuestas de una cuadrícula N × N , para N de 0 a 12. También incluye una lista extendida hasta N = 21.
• Weisstein, Eric W. "Caminata autoevitable" . MathWorld .
• Applet de Java para una caminata autoevitante en 2D
• Implementación genérica en Python para simular ondas acústicas superficiales (SAW) y expandir FiberWalks en redes cuadradas de n dimensiones.
• Software de Norris para generar ondas acústicas superficiales (SAW) en el cubo de diamante .