Caminho autoevitante

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,^[1] 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.

Três exemplos em um grafo de grade quadrada 8x8.

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.^[2]^[3] 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.^[4]

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.^[5]^[6] 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 \times 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 \leq c n c 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 :^[7]

{\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 \to \infty$ , 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.^[8] 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.^[9]

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 \to \infty$ 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 .$

Referências

↑ P. Flory (1953). Principles of Polymer Chemistry. [S.l.]: Cornell University Press. 672 páginas. ISBN 9780801401343
↑ S. Havlin, D. Ben-Avraham (1982). «New approach to self-avoiding walks as a critical phenomenon». J. Phys. A. 15. 321 páginas. doi:10.1088/0305-4470/15/6/013
↑ S. Havlin, D. Ben-Avraham (1982). «Theoretical and numerical study of fractal dimensionality in self-avoiding walks». Phys. Rev. A. 26 (3). 1728 páginas. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728
↑ A. Bucksch, G. Turk, J.S. Weitz (2014). «The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion». PLOS ONE. 9 (1): e85585. doi:10.1371/journal.pone.0085585
↑ Hayes B (julho–agosto de 1998). «How to Avoid Yourself». American Scientist. 86 (4). doi:10.1511/1998.31.3301
↑ Liśkiewicz M; Ogihara M; Toda S (julho de 2003). «The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes». Theoretical Computer Science. 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X
↑ Duminil-Copin, Hugo; Smirnov, Stanislav (1 de maio de 2012). «The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)». Annals of Mathematics. 175 (3): 1653–1665. doi:10.4007/annals.2012.175.3.14
↑ Carlos P. Herrero (2005). «Self-avoiding walks on scale-free networks». Phys. Rev. E. 71 (3). 1728 páginas. doi:10.1103/PhysRevE.71.016103
↑ Tishby, Biham, Katzav (2016), The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, arXiv:1603.06613.

Bibliografia

Madras, N.; Slade, G. (1996). The Self-Avoiding Walk. [S.l.]: Birkhäuser. ISBN 978-0-8176-3891-7
Lawler, G. F. (1991). Intersections of Random Walks. [S.l.]: Birkhäuser. ISBN 978-0-8176-3892-4
Madras, N.; Sokal, A. D. (1988). «The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk». Journal of Statistical Physics. 50. doi:10.1007/bf01022990
Fisher, M. E. (1966). «Shape of a self-avoiding walk or polymer chain». Journal of Chemical Physics. 44 (2). 616 páginas. Bibcode:1966JChPh..44..616F. doi:10.1063/1.1726734

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». MathWorld (em inglês)
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.

[1] P. Flory (1953). Principles of Polymer Chemistry. [S.l.]: Cornell University Press. 672 páginas. ISBN 9780801401343

[2] S. Havlin, D. Ben-Avraham (1982). «New approach to self-avoiding walks as a critical phenomenon». J. Phys. A. 15. 321 páginas. doi:10.1088/0305-4470/15/6/013

[3] S. Havlin, D. Ben-Avraham (1982). «Theoretical and numerical study of fractal dimensionality in self-avoiding walks». Phys. Rev. A. 26 (3). 1728 páginas. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728

[4] A. Bucksch, G. Turk, J.S. Weitz (2014). «The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion». PLOS ONE. 9 (1): e85585. doi:10.1371/journal.pone.0085585

[5] Hayes B (julho–agosto de 1998). «How to Avoid Yourself». American Scientist. 86 (4). doi:10.1511/1998.31.3301

[6] Liśkiewicz M; Ogihara M; Toda S (julho de 2003). «The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes». Theoretical Computer Science. 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X

[7] Duminil-Copin, Hugo; Smirnov, Stanislav (1 de maio de 2012). «The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)». Annals of Mathematics. 175 (3): 1653–1665. doi:10.4007/annals.2012.175.3.14

[8] Carlos P. Herrero (2005). «Self-avoiding walks on scale-free networks». Phys. Rev. E. 71 (3). 1728 páginas. doi:10.1103/PhysRevE.71.016103

[9] Tishby, Biham, Katzav (2016), The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, arXiv:1603.06613.

[10] Madras, N.; Slade, G. (1996). The Self-Avoiding Walk. [S.l.]: Birkhäuser. ISBN 978-0-8176-3891-7

[11] Lawler, G. F. (1991). Intersections of Random Walks. [S.l.]: Birkhäuser. ISBN 978-0-8176-3892-4

[12] Madras, N.; Sokal, A. D. (1988). «The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk». Journal of Statistical Physics. 50. doi:10.1007/bf01022990

[13] Fisher, M. E. (1966). «Shape of a self-avoiding walk or polymer chain». Journal of Chemical Physics. 44 (2). 616 páginas. Bibcode:1966JChPh..44..616F. doi:10.1063/1.1726734

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]