Caminho autoevitante

Um caminho autoevitante em um retículo quadrado.

Em matemática, um caminho autoevitante é uma sequência de movimentos em um retículo que não visita o mesmo ponto mais de uma vez. Este é um caso especial da noção de caminho da teoria dos grafos. Um polígono autoevitante é um caminho autoevitante fechado em um retículo. O termo caminho autoevitante foi introduzido pelo químico Paul Flory, a fim de modelar o comportamento real de entidades de configuração em cadeia, tais como solventes e polímeros, cujos volumes físicos proíbem múltiplas ocupações do mesmo ponto espacial. Muito pouco é conhecido rigorosamente a respeito dos caminhos auto-evitantes a partir de uma perspectiva matemática, apesar de que físicos terem provido numerosas conjecturas que são acreditadas serem verdade e fortemente apoiadas por simulações matemáticas, e que existam diversas conjecturas que foram obtidas por meio de simulações computacionais.

Em física computacional um caminho autoevitante é um caminho em cadeia em ${\text{R}}^{2}$ ou ${\text{R}}^{3}$ com um certo número de nós, tipicamente um passo de tamanho fixo e com uma propriedade imperativa de que ele não cruza a si mesmo ou outro caminho. Um sistema de caminhos autoevitantes satisfaz a chamada condição do volume excluído. Em dimensões mais altas, acredita-se que um caminho autoevitante deve se comportar de modo bastante próximo de um passeio aleatório. Caminhos autoevitantes e polígonos autoevitantes ocupam um papel central em modelagem topológica e teoria dos nós no comportamento de moléculas em forma de filamentos e loops, como proteínas. Caminhos autoevitantes são fractais. Por exemplo, em $d=2$ a dimensão fractal é $4/3$, para $d=3$ é próxima a $5/3$ enquanto para $d\geq 4$, a dimensão fractal é $2$. A dimensão é chamada dimensão crítica superior quando acima dela o volume excluído é insignificante. Um caminho autoevitante que não satisfaz a condição de volume excluído foi recentemente estudado para modelar superfícies geométricas explícitas resultante da expansão do caminho autoevitante.

As propriedades dos caminhos autoevitantes não podem ser calculadas analiticamente, então simulações numéricas são empregadas. O algoritmo de pivô é um método comum para simulações de Monte Carlo via Cadeias de Markov (MCMC) para medidas uniformes em caminhos autoevitantes de n passos. O algoritmo de pivô trabalha pegando um caminho autoevitante e aleatoriamente escolhendo um ponto desse caminho, e então aplicando uma operação simétrica (rotações e reflexões) no caminho depois do enésimo passo para criar um novo caminho. Calcular o número de caminhos autoevitantes em cada rede é um problema computacional comum. Não existe nenhuma fórmula conhecida para determinar o número de caminhos autoevitantes, embora existam métodos rigorosos para a aproximação. Conjectura-se que achar o número de caminhos dessa espécie seja um problema NP-difícil. Para caminhos autoevitantes, do fim de uma diagonal a outra, com apenas movimentos em posição positiva, existem exatamente ${m+n \choose m,n}$ caminhos para um retículo retangular m × n.

Universalidade

Um dos fenômenos associados com caminhos autoevitantes e modelos estatísticos físicos bidimensionais em geral é a noção de universalidade, isto é, independência de observáveis macroscópicos a partir de detalhes microscópicos, assim como a escolha do retículo. Uma quantidade importante que aparece em conjecturas para leis universais é a constante conectiva, definida como segue:

Seja $c_{n}$ o número de caminhos autoevitantes de n passos. Uma vez que todo caminho autoevitante de (n+m) passos pode ser decomposto em um caminho autoevitante de n passos e um caminho autoevitante de m passos, segue que c_n+m ≤ c_nc_m. Portanto, a sequência {log($c_{n}$)} é subaditiva e podemos aplicar o lema de Fekete para mostrar que o seguinte limite existe:

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

Sendo μ a constante conectiva, uma vez que c_n depende do retículo escolhido para o caminho, assim também é com μ. O valor exato para μ só é conhecido para o retículo hexagonal, onde é igual a :

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

Para outros retículos, μ só foi aproximado numericamente, e não se acredita tratar de acredita de um número algébrico. Conjectura-se que

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

quando n → ∞, onde μ depende do retículo, mas a correção da lei de potência $n^{\frac {11}{32}}$não; em outras palavras, acredita-se que essa lei seja universal.

Caminhos autoevitantes em redes

Caminhos autoevitantes também têm sido estudados no contexto da análise de rede. Nesse contexto, é comum tratar caminhos autoevitantes como um processo dinâmico, de modo que a cada passo temporal um andarilho aleatoriamente salta entre nós vizinhos na rede. A caminhada acaba quando o andarilho atinge um estado sem saída, de modo que não pode mais avançar para nós vizinhos não visitados. Constatou-se recentemente que nas redes Erdős–Rényi, a distribuição do comprimento de caminho de tais caminhos autoevitantes com crescimento dinâmico podem ser calculados analiticamente, e segue a distribuição de Gompertz.

Limites

Considere a medida uniforme em um caminho autoevitante de n passos em todo o plano. Atualmente é desconhecido se o limite da medida uniforme quando n → ∞ induz uma medida em caminhos infinitos. Contudo, Harry Kesten tem mostrado que assim como uma medida existe para caminhos autoevitantes na metade do plano. Uma questão importante envolvendo caminhos autoevitantes é a existência e invariância conforme do limite de escala, isso é, o limite de tamanho do caminho vai para o infinito, e a malha do retículo vai para zero. Se conjectura que o limite de escala para caminhos autoevitantes seja descrito por uma evolução Schramm–Loewner com parâmetro κ = 83.

Ligações externas

• OEIS A007764 : o número de caminhos autoevitantes unindo cantos opostos de um grid N x N, com N indo de 0 a 12. Também inclui uma lista estendida até N = 21.
• Weisstein, Eric W. «Self-Avoiding Walk» (em inglês). MathWorld 
• Java applet of a 2D self-avoiding walk
• Generic python implementation to simulate SAWs and expanding FiberWalks on a square lattices in n-dimensions.
• Software Norris para gerar caminhos autoevitantes em um diamante cúbico.

  Categoria:Polígonos Categoria:Geometria discreta Categoria:Física computacional Categoria:Química computacional