Le graphique infini des diagonales a-t-il une composante infinie?

Supposons que nous connectons les points de $V = \mathbb{Z}^2$ utilisant l'ensemble des bords non orientés $E$ telle sorte que $(i, j)$ soit connecté à $(i + 1, j + 1)$ , ou $(i + 1, j)$ soit connecté à $(i, j + 1)$ , indépendamment et uniformément au hasard pour tout $i, j$ .

(Inspiré par le titre et la couverture de ce livre .)

Quelle est la probabilité que ce graphique ait une composante connectée infiniment grande? De même, considérons , le complément de l'incorporation planaire du graphique. Quelle est la probabilité que le complément ait une composante connectée infinie?$\mathbb{R}^2 \setminus G$

De toute évidence, si toutes les diagonales pointent de la même manière, le graphique et son complément ont une composante infinie. Que diriez-vous d'un graphique aléatoire uniforme du type ci-dessus?

La probabilité est 0.

Cela découle du théorème suivant (voir le théorème 5.33 dans la probabilité de Grimmett sur les graphiques, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Théorème Considérons la percolation des liaisons sur , où chaque arête entre les points du réseau est ouverte avec probabilité $\mathbb Z^2$ . La probabilité que l'origine se trouve dans une composante connectée infinie est 0.$\frac12$

Nous pouvons réduire de notre problème à ce problème: il ne s'agit essentiellement que de 2 copies disjointes (mais dépendantes) de la percolation de liaison sur . Considérons la configuration D 1 où les bords forment un réseau infini de diamants contenant l'origine. Si nous inversons tous les bords, nous obtenons un autre réseau infini de diamants D 2 . Considérons l'intersection de la configuration réelle avec D 1 et avec D 2 . Chacun d' entre eux est exactement le modèle de percolation obligataire sur Z 2 , juste tourné 45 ∘ . La probabilité qu'un point se trouve dans l'amas infini est donc de 0 (pas de front dans D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$peut être connecté à un bord en ).$D_2$

Pour conclure, notez que la somme d'un nombre dénombrable d'événements avec une probabilité 0 a une probabilité 0; additionner la probabilité que tout point de réseau se trouve dans un groupe infini.

(L'existence de composants arbitrairement grands est un hareng rouge. Il faut fixer un point et demander s'il est dans un composant illimité.)

Hmm, eh bien, voici une première tentative. Observons deux choses importantes:

1. Si ce graphe a une composante connectée infiniment grande, par le lemme de König, il a un chemin simple infini.
2. L'événement selon lequel le graphique a un chemin simple infini est indépendant de chaque choix individuel d'orientation des bords (et donc de chaque ensemble fini de choix de bords). C'est donc un événement de queue et selon la loi zéro-un de Kolmogorov, la probabilité est soit zéro soit un.

Alors, est-ce zéro ou un? Ce n'est pas immédiatement clair, bien que nous puissions faire une supposition, puisque par le théorème des "singes infinis avec des machines à écrire", ce graphique contient des chemins simples de longueur arbitrairement grande avec une probabilité un. Bien sûr, il en faut plus pour prouver rigoureusement qu'il a en fait un chemin infini avec une probabilité un.

Voici quelques preuves empiriques faibles que la réponse est oui. Soit un graphe aléatoire sur le réseau 2 n + 1 × 2 n + 1 défini en choisissant chaque diagonale au hasard. Voici un graphique des estimations de probabilité d'accessibilité en fonction de n (en ignorant les sommets qui sont toujours inaccessibles en raison de la parité).$G_n$$2n+1 \times 2n+1$$n$

Si nous redimensionnons le carré à $[0,1]^2$ , la probabilité semble converger vers une fonction lisse indépendante de l'échelle, ce qui signifierait encore plus: que la probabilité que l'origine atteigne l'infini est positive.

Cependant, il est également possible que je n'aie pas calculé assez loin pour voir la tendance à la baisse (le graphique semble un peu plus petit que les autres).$n = 800$

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

Mise à jour: Comme indiqué dans les commentaires, le lemme n'implique pas de chemins infinis après tout, donc cette réponse est globalement fausse. Je ne sais pas s'il peut être utilisé d'une autre manière probabiliste.

La réponse est oui: un chemin infini existe. En effet, un chemin infini existe pour chacun de ces graphiques; la probabilité n'est pas requise.

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

$G$

Si le lemme est vrai, la version infinie découle de König comme l'a noté Joe. ( Mise à jour: faux, voir les commentaires)