Usuário(a):Wilkruvic/Testes4

Um grafo tridimensional de percolação local

Em física estatística e matemática, a teoria da percolação descreve o comportamento de grupos conectados em um grafo aleatório. As aplicações da teoria da percolação à ciência dos materiais e outros domínios são discutidas no verbete percolação.

Introdução

Uma questão representativa (e a origem do nome) é a seguinte. Suponha que um líquido é despejado no topo de um material poroso. O líquido será capaz de fazer seu caminho de poro a poro e atingir o fundo? Esta questão física é modelada matematicamente como uma rede tridimensional de n x n x n vértices, geralmente chamados de "locais", em que a aresta ou "ligação" entre dois vizinhos pode estar aberta (permitindo a passagem do líquido) com probabilidade p, ou fechada com probabilidade 1 – p, assumindo-se que são independentes. Por isso, para uma dada p, qual é a probabilidade de que um caminho aberto (sendo um caminho uma sequência de "ligações" abertas) exista do topo ao fundo? O comportamento para um n grande é de interesse primário. Este problema, agora chamado de percolação de ligação, foi introduzido na literatura de matemática por Broadbent & Hammersley (1957), e tem sido estudado intensivamente por matemáticos e físicos desde então.

Em um modelo matemático levemente diferente para obter um grafo aleatório, o local está "ocupado" com probabilidade p ou "vazio" (no caso em que suas arestas foram removidas) com probabilidade 1-p; o problema correspondente é chamado de percolação local. A questão é a mesma: para uma dada p, qual é a probabilidade de que um caminho exista do topo ao fundo?

Certamente, as mesmas questões podem ser feitas a qualquer dimensão da rede. Como é muito típico, na verdade, é mais fácil examinar redes infinitas do que redes grandes. Neste caso, a questão correspondente é: existe um grupo aberto infinito? Isto é, há um caminho de pontos conectados de infinito comprimento "através" da rede? Pela lei zero-um de Kolmogorov, para qualquer p dada, a probabilidade de que um grupo infinito exista é zero ou um. Já que esta probabilidade é uma função crescente de p (prova via argumento de acoplamento), deve haver um p crítico (denotado por p_c) abaixo do qual a probabilidade é sempre 0 e acima do qual a probabilidade é sempre 1. Na prática, esta criticidade é muito fácil de observar. Mesmo para um n tão baixo quanto 100, a probabilidade de um caminho aberto do topo ao fundo aumenta bruscamente de muito próxima de zero a muito próxima de um em um curto intervalo de valores de p.

Em alguns casos, p_c pode ser calculado explicitamente. Por exemplo, para o reticulado quadrado Z² em duas dimensões, p_c = 1/2 para percolação de ligação, um fato que foi uma questão aberta por mais de 20 anos e que foi finalmente resolvido por Harry Kesten no começo da década de 1980. Um caso limite para reticulados em muitas dimensões é dado pelo reticado de Bethe (um tipo específico de grafo de Cayley), cujo limiar está em p_c = 1/(z − 1) para um número de coordenação z. Para a maioria dos grafo reticulados infinitos, p_c não pode ser calculada com exatidão.

Detalhe de uma percolação de ligação no reticulado quadrado em duas dimensões com probabilidade de percolação p = 0.51

Universalidade

O princípio da universalidade afirma que o valor numérico da p_c é determinado pela estrutura local do grafo, enquanto que o tipo de comportamento dos grupos observado abaixo da, na e acima da p_c é independente da estrutura local e, por isso, em algum sentido, é mais natural considerar estes comportamentos do que a p_c propriamente. Esta universalidade também quer dizer que, para uma dada dimensão, os vários expoentes críticos, a dimensão fractal dos grupos em p_c é independente do tipo de reticulado e do tipo da percolação (isto é, de ligação ou local). No entanto, recentemente, a percolação tem sido realizada em um retículo estocástico plano ponderado e descobriu-se que, ainda que a dimensão do retículo estocástico plano ponderado coincida com a dimensão do espaço em que está inserido, sua classe de universalidade é diferente daquela de todos os reticulados planos conhecidos.

Fases

Subcrítica e supercrítica

O principal fato na fase subcrítica é o "decaimento exponential". Isto é, quando p < p_c, a probabilidade de que um ponto específico (por exemplo, a origem) esteja contido em um grupo aberto de tamanho r (o que significa um conjunto máximo conectado de arestas "abertas" do grafo) decai a zero exponencialmente em r. Isto foi provado para a percolação em três ou mais dimensões por Menshikov (1986) e independentemente por Aizenman & Barsky (1987). Em duas dimensões, formou parte da prova de Kesten de que p_c = 1/2.

O grafo dual do reticulado quadrado Z² também é um reticulado quadrado. Isto segue do fato de que, em duas dimensões, a fase supercrítica é dual em relação a um processo de percolação subcrítica. Isto oferece essencialmente informação completa sobre o modelo supercrítico com d = 2. O principal resultado para a fase supercrítica em três ou mais dimensões é que, para N suficientemente grande, há um grupo aberto infinito na laje bidimensional Z² × [0, N]^d−2. Isto foi provado por Grimmett & Marstrand (1990).

Em duas dimensões com p < 1/2, há, com probabilidade um, um grupo fechado infinito (um grupo fechado é o conjunto máximo conectado de arestas "fechadas" do grafo). Assim, a fase subcrítica pode ser definida como ilhas abertas finitas em um oceano infinito fechado. Quando p > 1/2, ocorre simplesmente o oposto, com ilhas fechadas finitas em um oceano aberto infinito. A imagem é mais complicada quando d ≥ 3 sendo p_c < 1/2, havendo coexistência entre grupos abertos e fechados infinitos para p entre p_c e 1 − p_c.

Crítica

O modelo tem uma singularidade no ponto crítico p = p_c acreditada como sendo do tipo de uma lei de potência. A teoria do escalamento prevê a existência de expoentes críticos, dependendo do número d de dimensões, que determina a classe da singularidade. Quando d = 2, estas previsões são corroboradas por argumentos da teoria do campo conformal e da evolução de Schramm–Loewner e incluem valores numéricos previstos para os expoentes. Em sua maioria, estas previsões são conjeturais, exceto quando o número d de dimensões satisfaça as condições d = 2 ou d ≥ 19. Elas incluem:

• Não há grupos infinitos (abertos ou fechados).
• A probabilidade de que haja um caminho aberto a partir de algum ponto fixo (por exemplo, a origem) a uma distância r decresce polinomialmente, isto é, está na ordem de r ^α para algum α.
  • α não depende do reticulado particular escolhido ou de outros parâmetros locais. Depende apenas da dimensão d (esta é uma instância do princípio da universalidade).
  • α_d decresce de d = 2 até d = 6 e então permanece fixo.
  • α₂ = −5/48.
  • α₆ = −1.
• A forma de um grupo grande em duas dimensões é conformemente invariante.

Em dimensão ≥ 19, estes fatos são em grande parte provados pelo uso de uma técnica conhecida como expansão de renda. Acredita-se que uma versão da expansão de renda deve ser válida para 7 ou mais dimensões, talvez com implicações também para o caso limiar de 6 dimensões. A conexão da percolação com a expansão de renda é encontrada em Hara & Slade (1990).

Em dimensão 2, o primeiro fato ("não há percolação na fase crítica") é provado para muitos reticulados, usando dualidade. Progressos substanciais têm sido feitos na percolação bidimensional pela conjetura de Oded Schramm de que o limite escalar de um grupo grande pode ser descrito em termos de uma evolução de Schramm-Loewner. A conjetura foi provada por Smirnov (2001) no caso especial da percolação local no retículo triangular.

Modelos diferentes

• O primeiro modelo estudado foi a percolação de Bernoulli. Neste modelo, todas as ligações são independentes. Este modelo é chamado de percolação de ligação pelos físicos.
• Uma generalização foi introduzida em seguida pelo modelo de grupo aleatório de Fortuin-Kasteleyn, que têm muitas conexões com o modelo Ising e outros modelos Potts.
• A percolação de Bernoulli (ou de ligação) em grafos completos é um exemplo de grafo aleatório. A probabilidade crítica é p = 1/N, em que N é um número de vértices (locais) do grafo.
• A percolação de bootstrap remove células ativas dos grupos quando eles têm muito poucos vizinhos ativos e olha para a conectividade das células remanescentes.
• A percolação direcionada, que tem conexões com o processo de contato.
• A percolação de primeira passagem.
• A percolação por invasão.
• A percolação com conexões de dependência foi introduzida por Parshani et al.
• Modelo de opinião.

Ver também

• Modelo Erdős–Rényi
• Fractal
• Teoria dos grafos
• Análise de rede
• Rede sem escala
• Problema do caminho mínimo

Referências

• Aizenman, Michael; Barsky, David (1987), «Sharpness of the phase transition in percolation models», Communications in Mathematical Physics, 108 (3): 489–526, Bibcode:1987CMaPh.108..489A, doi:10.1007/BF01212322 
• Bollobás, Béla; Riordan, Oliver (2006), Percolation, ISBN 0521872324, Cambridge University Press 
• Broadbent, Simon; Hammersley, John (1957), «Percolation processes I. Crystals and mazes», Proceedings of the Cambridge Philosophical Society, 53: 629–641, Bibcode:1957PCPS...53..629B, doi:10.1017/S0305004100032680 
• Bunde A. and Havlin S. (1996), Fractals and Disordered Systems, Springer 
• Cohen R. and Havlin S. (2010), Complex Networks: Structure, Robustness and Function, Cambridge University Press 
• Grimmett, Geoffrey (1999), Percolation, Springer 
• Grimmett, Geoffrey; Marstrand, John (1990), «The supercritical phase of percolation is well behaved», Proceedings of the Royal Society A, 430 (1879): 439–457, Bibcode:1990RSPSA.430..439G, doi:10.1098/rspa.1990.0100 
• Hara, Takashi; Slade, Gordon (1990), «Mean-field critical behaviour for percolation in high dimensions», Communications in Mathematical Physics, 128 (2): 333–391, Bibcode:1990CMaPh.128..333H, doi:10.1007/BF02108785 
• Kesten, Harry (1982), Percolation theory for mathematicians, Birkhauser 
• Menshikov, Mikhail (1986), «Coincidence of critical points in percolation problems», Soviet Mathematics Doklady, 33: 856–859 
• Smirnov, Stanislav (2001), «Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits», Comptes Rendus de l'Academie des Sciences, 333 (3): 239–244, Bibcode:2001CRASM.333..239S, doi:10.1016/S0764-4442(01)01991-7 
• Stauffer, Dietrich; Aharony, Anthony (1994), Introduction to Percolation Theory, ISBN 978-0-7484-0253-3 2nd ed. , CRC Press 

Ligações externas

• PercoVIS: a Mac OS X program to visualize percolation on networks in real time
• Interactive Percolation
• Kesten, Harry (May 2006), «What Is ... Percolation?» (PDF), Providence, RI: American Mathematical Society, Notices of the American Mathematical Society, ISSN 1088-9477, 53 (5): 572–573 
• Austin, David (July 2008), Percolation: Slipping through the Cracks, American Mathematical Society 
• Nanohub online course on Percolation Theory
• Introduction to Percolation Theory: short course by Shlomo Havlin