Czy nieskończony wykres przekątnych ma nieskończony składnik?

Załóżmy, że łączymy punkty za pomocą zestawu niekierowanych krawędzi E tak, że albo ( i , j ) jest podłączony do ( i + 1 , j + 1 ) , albo ( i + 1 , j ) jest podłączony do ( i , j + 1 ) , niezależnie i równomiernie losowo dla wszystkich i , j .$V = \mathbb{Z}^2$$E$$(i, j)$$(i + 1, j + 1)$$(i + 1, j)$$(i, j + 1)$$i, j$

(Zainspirowany tytułem i okładką tej książki .)

Jakie jest prawdopodobieństwo, że ten wykres ma nieskończenie duży połączony komponent? Podobnie weź pod uwagę $\mathbb{R}^2 \setminus G$ , dopełnienie płaskich osadzenia na wykresie. Jakie jest prawdopodobieństwo, że dopełnienie ma nieskończenie związany komponent?

Oczywiście, jeśli wszystkie przekątne wskazują w ten sam sposób, zarówno wykres, jak i jego dopełnienie mają nieskończony składnik. Co powiesz na jednolity losowy wykres powyższego rodzaju?

Prawdopodobieństwo wynosi 0.

Wynika to z następującego twierdzenia (patrz Twierdzenie 5.33 w prawdopodobieństwie Grimmetta na wykresach, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Twierdzenie Rozważ perkolację wiązań na , gdzie każda krawędź między punktami sieci jest otwarta z prawdopodobieństwem $\mathbb Z^2$ . Prawdopodobieństwo, że początek jest w nieskończenie połączonym składniku, wynosi 0.$\frac12$

Możemy zredukować nasz problem do tego problemu: w zasadzie są to tylko 2 rozłączne (ale zależne) kopie perkolacji wiązania na . Rozważ konfigurację D 1, w której krawędzie tworzą nieskończoną sieć diamentów zawierających pochodzenie. Jeśli odwrócimy wszystkie krawędzie, otrzymamy kolejną nieskończoną sieć diamentów D 2 . Rozważ przecięcie faktycznej konfiguracji z D 1 i D 2 . Każdy z nich jest dokładnie modelem perkolacji wiązania na Z 2 , właśnie obróconym o 45 ∘ . Prawdopodobieństwo, że dowolny punkt znajduje się w nieskończonej gromadzie, wynosi więc 0 (Brak krawędzi w D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$może być podłączony do krawędzi w ).$D_2$

Podsumowując, należy zauważyć, że suma policzalnej liczby zdarzeń z prawdopodobieństwem 0 ma prawdopodobieństwo 0; suma ponad prawdopodobieństwo, że dowolny punkt sieci znajduje się w nieskończonej grupie.

(Istnienie dowolnie dużych komponentów to czerwony śledź. Należy naprawić punkt i zapytać, czy jest to komponent nieograniczony.)

Hmm, cóż, oto pierwsza próba. Zauważmy dwie ważne rzeczy:

1. Jeśli ten wykres ma nieskończenie duży połączony komponent, na podstawie lematu nieskończoności Königa, ma nieskończoną prostą ścieżkę.
2. Zdarzenie, w którym wykres ma nieskończoną prostą ścieżkę, jest niezależne od każdego indywidualnego wyboru orientacji krawędzi (a zatem od każdego skończonego zestawu wyborów krawędzi). Dlatego jest to wydarzenie ogonowe i według prawa zerowego jeden Kołmogorowa prawdopodobieństwo wynosi zero lub jeden.

Czy to zero, czy jeden? Nie jest od razu jasne, choć możemy zgadywać, ponieważ dzięki twierdzeniu o „nieskończonych małpach z maszynami do pisania” wykres ten zawiera proste ścieżki o dowolnej długości z prawdopodobieństwem jeden. Oczywiście potrzeba więcej, aby rygorystycznie udowodnić, że faktycznie ma ona nieskończoną ścieżkę z prawdopodobieństwem.

Here's some weak empirical evidence that the answer is yes. Let $G_n$ be a random graph on the $2n+1 \times 2n+1$ lattice defined by picking each diagonal randomly. Here's a plot of reachability probability estimates vs. $n$ (ignoring the vertices which are always unreachable due to parity).

If we rescale the square to $[0,1]^2$, the probability appears to converge to a smooth function independent of scale, which would mean even more: that the probability of the origin reaching infinity is positive.

However, it's also possible that I haven't computed far enough out to see the downwards trend (the $n = 800$ plot does seem a little smaller than the others).

Code here: https://gist.github.com/girving/16a0ffa1f0abb08934c2

Update: As pointed out in the comments, the lemma does not imply infinite paths after all, so this answer overall is wrong. Not sure if it can be used in another probabilistic way.

The answer is yes: an infinite path exists. Indeed, an infinite path exists for every such graph; probability is not required.

Lemma: Let $G$ be any diagonal graph on the $n \times n$ lattice, with $n \ge 2$. Then there is either a path from left to the right through even parity vertices or a path from the top to the bottom through odd parity vertices.

Proof sketch: This is essentially the determinacy theorem in Hex on a different graph. The even and odd parity halves of $G$ are locally dual, so an obstruction in one parity is a connection in the other. However, I will omit the details since they're hard to write down without pictures and/or case analysis.

If the lemma is true, the infinite version follows from König as noted by Joe. (Update: Wrong, see comments)