Имеет ли бесконечный граф диагоналей бесконечный компонент?

Предположим, что мы соединяем точки используя набор неориентированных ребер E , так что либо связано с , либо связано с , независимо и равномерно случайным образом для всех .$V = \mathbb{Z}^2$$E$( i + 1 , j + 1 $(i, j)$$(i + 1, j + 1)$( i , j + 1 ) i , $(i + 1, j)$$(i, j + 1)$$i, j$

(Вдохновлено названием и обложкой этой книги .)

Какова вероятность того, что этот граф имеет бесконечно большую связную компоненту? Аналогично, рассмотрим , дополнение к плоскому вложению графа. Какова вероятность того, что дополнение имеет бесконечный связный компонент?$\mathbb{R}^2 \setminus G$

Ясно, что если все диагонали указывают одинаково, и граф, и его дополнение имеют бесконечную составляющую. Как насчет равномерного случайного графа вышеупомянутого вида?

Вероятность равна 0.

Это следует из следующей теоремы (см. Теорему 5.33 в вероятности Гримметта на графах, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Теорема. Рассмотрим перколяцию связей на , где каждое ребро между точками решетки открыто с вероятностью $\mathbb Z^2$ . Вероятность того, что начало координат находится в бесконечной связной компоненте, равно 0.$\frac12$

Мы можем свести нашу проблему к этой проблеме: в основном это всего лишь две непересекающиеся (но зависимые) копии перколяции связей на . Рассмотрим конфигурацию D 1, где ребра образуют бесконечную решетку алмазов, содержащих начало координат. Если мы перевернем все ребра, мы получим еще одну бесконечную решетку алмазов D 2 . Рассмотрим пересечение фактической конфигурации с D 1 и с D 2 . Каждый из них является именно моделью перколяции связей на Z 2 , только что повернул 45 ∘ . Следовательно, вероятность того, что любая точка находится в бесконечном кластере, равна 0 (нет ребра в D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$может быть подключен к ребру в ).$D_2$

В заключение отметим, что сумма счетного числа событий с вероятностью 0 имеет вероятность 0; сумма по вероятности того, что любая точка решетки находится в бесконечном кластере.

(Существование сколь угодно больших компонентов - это красная сельдь. Нужно исправить точку и спросить, находится ли она в неограниченном компоненте.)

Хм, хорошо, вот одна первая попытка. Давайте рассмотрим две важные вещи:

1. Если этот граф имеет бесконечно большую связную компоненту, то по лемме Кенига о бесконечности он имеет бесконечно простой путь.
2. Случай, когда граф имеет бесконечный простой путь, не зависит от каждого отдельного выбора ориентации ребер (и, следовательно, каждого конечного набора вариантов ребер). Следовательно, это хвостовое событие, и по закону Колмогорова «ноль один» вероятность равна нулю или единице.

Так это ноль или один? Это не сразу ясно, хотя мы можем сделать предположение, поскольку по теореме «бесконечные обезьяны с пишущими машинками» этот граф содержит простые пути произвольно большой длины с вероятностью один. Конечно, требуется больше, чтобы строго доказать, что он на самом деле имеет бесконечный путь с вероятностью один.

Вот некоторые слабые эмпирические доказательства того, что ответ - да. Пусть - случайный граф на 2 n + 1 × 2 n + $G_n$$2n+1 \times 2n+1$ решетке определенный путем случайного выбора каждой диагонали. Вот график оценки вероятности достижимости в зависимости от (без учета вершин, которые всегда недоступны из-за четности).$n$

Если мы масштабируем квадрат до $[0,1]^2$

Тем не менее, также возможно, что я не рассчитал достаточно далеко, чтобы увидеть нисходящий тренд ( $n = 800$

Код здесь: https://gist.github.com/girving/16a0ffa1f0abb08934c2

Обновление: как отмечено в комментариях, лемма не подразумевает бесконечные пути в конце концов, так что этот ответ в целом неверен. Не уверен, что его можно использовать другим вероятностным способом.

Ответ: да, существует бесконечный путь. Действительно, бесконечный путь существует для каждого такого графа; вероятность не требуется.

$G$$n \times n$$n \ge 2$ . Тогда есть либо путь слева направо через вершины четной четности, либо путь сверху вниз через вершины нечетной четности.

$G$ локально двойственны, поэтому препятствие в одной четности является связью в другой. Однако я опущу детали, так как их сложно записать без картинок и / или анализа случая.

Если лемма верна, то, как отметил Джо, бесконечный вариант следует из Кёнига. ( Обновление: неправильно, см. Комментарии)