O gráfico infinito de diagonais possui um componente infinito?

Suponha que conectemos os pontos de usando o conjunto de arestas não direcionadas modo que esteja conectado a ou está conectado a , independentemente e uniformemente de forma aleatória para todos os . E ( i , j ) ( i + 1 , j + 1 ) ( i + 1 , j ) ( i , j + 1 ) i , $V = \mathbb{Z}^2$$E$$(i, j)$$(i + 1, j + 1)$$(i + 1, j)$$(i, j + 1)$$i, j$

(Inspirado no título e na capa deste livro .)

Qual é a probabilidade de esse gráfico ter um componente conectado infinitamente grande? Da mesma forma, considere , o complemento da incorporação planar do gráfico. Qual é a probabilidade de o complemento ter um componente infinito conectado?$\mathbb{R}^2 \setminus G$

Claramente, se todas as diagonais apontam da mesma maneira, o gráfico e seu complemento têm um componente infinito. Que tal um gráfico aleatório uniforme do tipo acima?

A probabilidade é 0.

Isso se segue do seguinte teorema (consulte o Teorema 5.33 em Probabilidade de Grimmett em Gráficos, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Teorema Considere a percolação da ligação em , onde cada aresta entre os pontos da rede é aberta com probabilidade . A probabilidade de a origem estar em um componente conectado infinito é 0.$\mathbb Z^2$$\frac12$

Podemos reduzir do nosso problema para esse problema: basicamente são apenas duas cópias disjuntas (mas dependentes) da percolação de vínculo em . Considere a configuração qual as arestas formam uma malha infinita de diamantes contendo a origem. Se todas as arestas, obteremos outra treliça infinita de diamantes . Considere a interseção da configuração real com e com . Cada um deles é exatamente o modelo de percolação de ligações em , apenas girado . A probabilidade de que qualquer ponto esteja no cluster infinito é, portanto, 0 (Nenhuma aresta em pode ser conectada a uma aresta em .).D 1 D 2 D 1 D 2 Z 2 45 ∘ D 1 D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$$D_2$

Para concluir, observe que a soma de um número contável de eventos com probabilidade 0 tem probabilidade 0; soma sobre a probabilidade de que qualquer ponto de rede esteja em um cluster infinito.

(A existência de componentes arbitrariamente grandes é um arenque vermelho. Deve-se fixar um ponto e perguntar se ele está em um componente ilimitado.)

Hmm, bem, aqui está uma primeira tentativa. Vamos observar duas coisas importantes:

1. Se este gráfico tiver um componente conectado infinitamente grande, pelo lema infinito de König, ele terá um caminho infinito e simples.
2. O evento em que o gráfico possui um caminho simples e infinito é independente de cada opção individual de orientação da aresta (e, portanto, de cada conjunto finito de opções de arestas). Portanto, é um evento de cauda e, pela lei zero-um de Kolmogorov, a probabilidade é zero ou um.

Então, é zero ou um? Não está claro de imediato, embora possamos adivinhar, pois pelo teorema "macacos infinitos com máquinas de escrever", esse gráfico contém caminhos simples de comprimento arbitrariamente grande com probabilidade 1. Certamente, é necessário mais para provar rigorosamente que ele realmente tem um caminho infinito com probabilidade.

Aqui estão algumas evidências empíricas fracas de que a resposta é sim. Seja um gráfico aleatório na rede 2 n + 1 × 2 n + 1 definida escolhendo cada diagonal aleatoriamente. Aqui está um gráfico das estimativas de probabilidade de alcançabilidade vs. n (ignorando os vértices que são sempre inacessíveis devido à paridade).$G_n$$2n+1 \times 2n+1$$n$

Se redimensionarmos o quadrado para , a probabilidade parece convergir para uma função suave independente da escala, o que significaria ainda mais: que a probabilidade da origem atingir o infinito é positiva.$[0,1]^2$

No entanto, também é possível que eu não tenha calculado o suficiente para ver a tendência de queda (o gráfico parece um pouco menor que os outros).$n = 800$

Código aqui: https://gist.github.com/girving/16a0ffa1f0abb08934c2

Atualização: Como apontado nos comentários, o lema não implica caminhos infinitos, afinal, portanto, esta resposta geral está errada. Não tenho certeza se pode ser usado de outra maneira probabilística.

A resposta é sim: existe um caminho infinito. De fato, existe um caminho infinito para cada gráfico; probabilidade não é necessária.

$G$$n \times n$$n \ge 2$

$G$

Se o lema é verdadeiro, a versão infinita segue König, como observado por Joe. ( Atualização: Errado, veja comentários)