Hat der unendliche Graph der Diagonalen eine unendliche Komponente?

Angenommen, wir verbinden die Punkte von mit der Menge ungerichteter Kanten E , sodass entweder ( i , j ) mit ( i + 1 , j + 1 ) oder ( i + 1 , j ) mit ( i , j + 1 ) , unabhängig und gleichmäßig zufällig für alle i , j .$V = \mathbb{Z}^2$$E$$(i, j)$$(i + 1, j + 1)$$(i + 1, j)$$(i, j + 1)$$i, j$

(Inspiriert vom Titel und Cover dieses Buches .)

Wie groß ist die Wahrscheinlichkeit, dass dieser Graph eine unendlich große zusammenhängende Komponente hat? In ähnlicher Weise betrachten wir , das Komplement der planaren Einbettung des Graphen. Wie groß ist die Wahrscheinlichkeit, dass das Komplement eine unendliche zusammenhängende Komponente hat?$\mathbb{R}^2 \setminus G$

Wenn alle Diagonalen in die gleiche Richtung weisen, haben sowohl der Graph als auch sein Komplement eine unendliche Komponente. Wie wäre es mit einem einheitlichen Zufallsgraphen der oben genannten Art?

Die Wahrscheinlichkeit ist 0.

Dies folgt aus dem folgenden Satz (siehe Satz 5.33 in Grimmetts Wahrscheinlichkeit auf Graphen, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Theorem Betrachten Sie die Perkolation von Bindungen auf , wobei jede Kante zwischen Gitterpunkten mit Wahrscheinlichkeit 1 offen ist$\mathbb Z^2$ . Die Wahrscheinlichkeit, dass der Ursprung in einer unendlichen zusammenhängenden Komponente liegt, ist 0.$\frac12$

Wir können unser Problem auf dieses Problem reduzieren: Grundsätzlich sind es nur 2 disjunkte (aber abhängige) Kopien der Bindungsperkolation von . Betrachten Sie die Konfiguration D 1, bei der die Kanten ein unendliches Gitter aus Diamanten bilden, das den Ursprung enthält. Wenn wir alle Kanten umdrehen, erhalten wir ein weiteres unendliches Gitter von Diamanten D 2 . Betrachten Sie den Schnittpunkt der tatsächlichen Konfiguration mit D 1 und mit D 2 . Jedes davon ist genau das Modell der Bindungsperkolation auf Z 2 , nur um 45 ° gedreht . Die Wahrscheinlichkeit, dass ein Punkt im unendlichen Cluster liegt, ist daher 0 (keine Kante in D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$kann mit einer Kante in .).$D_2$

Abschließend sei angemerkt, dass die Summe einer abzählbaren Anzahl von Ereignissen mit der Wahrscheinlichkeit 0 die Wahrscheinlichkeit 0 hat; Summe über die Wahrscheinlichkeit, dass sich ein Gitterpunkt in einem unendlichen Cluster befindet.

(Die Existenz beliebig großer Komponenten ist ein roter Hering. Man sollte einen Punkt festlegen und fragen, ob er sich in einer unbegrenzten Komponente befindet.)

Hmm, nun, hier ist ein erster Versuch. Lassen Sie uns zwei wichtige Dinge beobachten:

1. Wenn dieser Graph eine unendlich große zusammenhängende Komponente hat, hat er nach König's Unendlich-Lemma einen unendlich einfachen Pfad.
2. Das Ereignis, dass der Graph einen unendlich einfachen Pfad hat, ist unabhängig von jeder einzelnen Wahl der Kantenausrichtung (und somit von jeder endlichen Menge von Kantenwahlen). Daher ist es ein Endereignis und nach Kolmogorovs Null-Eins-Gesetz ist die Wahrscheinlichkeit entweder Null oder Eins.

Also, ist es null oder eins? Es ist nicht sofort klar, obwohl wir eine Vermutung anstellen können, da dieser Graph nach dem Satz "Unendliche Affen mit Schreibmaschinen" einfache Pfade beliebig großer Länge mit Wahrscheinlichkeit eins enthält. Natürlich ist mehr erforderlich, um konsequent zu beweisen, dass es tatsächlich einen unendlichen Pfad mit einer Wahrscheinlichkeit von eins gibt.

Hier sind einige schwache empirische Beweise dafür, dass die Antwort ja lautet. Sei ein zufälliger Graph auf dem 2 n + 1 × 2 n + 1- Gitter, das durch zufälliges Auswählen jeder Diagonale definiert wird. Hier ist eine grafische Darstellung der Schätzungen der Erreichbarkeitswahrscheinlichkeit gegenüber n (wobei die Eckpunkte ignoriert werden, die aufgrund der Parität immer nicht erreichbar sind).$G_n$$2n+1 \times 2n+1$$n$

Wenn wir das Quadrat auf skalieren, scheint die Wahrscheinlichkeit zu einer glatten Funktion zu konvergieren, die von der Skalierung unabhängig ist. Dies würde noch mehr bedeuten: Die Wahrscheinlichkeit, dass der Ursprung unendlich wird, ist positiv.$[0,1]^2$

Es ist jedoch auch möglich, dass ich nicht weit genug gerechnet habe, um den Abwärtstrend zu erkennen (das Diagramm mit scheint ein wenig kleiner zu sein als die anderen).$n = 800$

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

Update: Wie in den Kommentaren erwähnt, impliziert das Lemma schließlich keine unendlichen Pfade, sodass diese Antwort insgesamt falsch ist. Ich bin nicht sicher, ob es auf eine andere probabilistische Weise verwendet werden kann.

Die Antwort lautet ja: Es gibt einen unendlichen Weg. In der Tat existiert für jeden solchen Graphen ein unendlicher Pfad ; Wahrscheinlichkeit ist nicht erforderlich.

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

$G$

Wenn das Lemma wahr ist, folgt die unendliche Version aus König, wie von Joe bemerkt. ( Update: Falsch, siehe Kommentare)