¿El gráfico infinito de diagonales tiene un componente infinito?

Supongamos que conectamos los puntos de usando el conjunto de bordes no dirigidos modo que esté conectado a o está conectado a , de forma independiente y uniforme al azar para todo . 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 por el título y la portada de este libro ).

¿Cuál es la probabilidad de que este gráfico tenga un componente conectado infinitamente grande? Del mismo modo, considere , el complemento de la incrustación plana del gráfico. ¿Cuál es la probabilidad de que el complemento tenga un componente infinito conectado?$\mathbb{R}^2 \setminus G$

Claramente, si todas las diagonales apuntan de la misma manera, tanto el gráfico como su complemento tienen un componente infinito. ¿Qué tal un gráfico aleatorio uniforme del tipo anterior?

La probabilidad es 0.

Esto se desprende del siguiente teorema (ver Teorema 5.33 en Probabilidad de gráficos de Grimmett, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Teorema Considere la percolación de enlaces en , donde cada borde entre los puntos de la red está abierto con probabilidad $\mathbb Z^2$ . La probabilidad de que el origen esté en un componente infinito conectado es 0.$\frac12$

Podemos reducir nuestro problema a este problema: básicamente son solo 2 copias disjuntas (pero dependientes) de percolación de enlaces en . Considere la configuración D 1 donde los bordes forman una red infinita de diamantes que contienen el origen. Si volteamos todos los bordes, obtenemos otra red infinita de diamantes D 2 . Considere la intersección de la configuración real con D 1 y con D 2 . Cada uno de estos es exactamente el modelo de percolación de enlaces en Z 2 , recién girado 45 ∘ . La probabilidad de que cualquier punto esté en el grupo infinito es, por lo tanto, 0 (sin arista en D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$se puede conectar a un borde en ).$D_2$

Para concluir, tenga en cuenta que la suma de un número contable de eventos con probabilidad 0 tiene probabilidad 0; suma sobre la probabilidad de que cualquier punto reticular esté en un grupo infinito.

(La existencia de componentes arbitrariamente grandes es una pista falsa. Uno debería arreglar un punto y preguntar si está en un componente ilimitado).

Hmm, bueno, aquí hay un primer intento. Observemos dos cosas importantes:

1. Si este gráfico tiene un componente conectado infinitamente grande, por el lema de infinito de König, tiene una ruta simple infinita.
2. El evento de que el gráfico tenga una ruta simple infinita es independiente de cada elección individual de orientación de borde (y, por lo tanto, cada conjunto finito de opciones de borde). Por lo tanto, es un evento de cola y, según la ley de cero uno de Kolmogorov, la probabilidad es cero o uno.

Entonces, ¿es cero o uno? No está claro de inmediato, aunque podemos adivinar, ya que según el teorema de "monos infinitos con máquinas de escribir", este gráfico contiene senderos simples de longitud arbitrariamente grande con probabilidad uno. Por supuesto, se necesita más para demostrar rigurosamente que realmente tiene un camino infinito con probabilidad uno.

$G_n$$2n+1 \times 2n+1$$n$

$[0,1]^2$

$n = 800$

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

Actualización: como se señaló en los comentarios, el lema no implica caminos infinitos después de todo, por lo que esta respuesta en general es incorrecta. No estoy seguro si se puede usar de otra manera probabilística.

La respuesta es sí: existe un camino infinito. De hecho, existe un camino infinito para cada gráfico; No se requiere probabilidad.

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

$G$

Si el lema es verdadero, la versión infinita se sigue de König como lo señaló Joe. ( Actualización: Incorrecto, ver comentarios)