Apakah grafik diagonal yang tak terhingga memiliki komponen yang tak terbatas?

Misalkan kita menghubungkan titik-titik menggunakan set tepi yang tidak diarahkan sedemikian sehingga salah satu terhubung ke , atau terhubung ke , secara independen dan seragam secara acak untuk semua .$V = \mathbb{Z}^2$$E$$(i, j)$$(i + 1, j + 1)$$(i + 1, j)$$(i, j + 1)$$i, j$

(Terinspirasi oleh judul dan sampul buku ini .)

Berapa probabilitas bahwa grafik ini memiliki komponen terhubung yang jauh lebih besar? Demikian pula, pertimbangkan $\mathbb{R}^2 \setminus G$ , pelengkap planar embedding grafik. Berapa probabilitas bahwa komplemen memiliki komponen yang terhubung tanpa batas?

Jelas, jika semua diagonal menunjuk dengan cara yang sama, grafik dan komplemennya memiliki komponen yang tak terbatas. Bagaimana dengan grafik acak yang seragam dari jenis di atas?

Probabilitasnya adalah 0.

Ini mengikuti dari teorema berikut (lihat Teorema 5.33 dalam Probabilitas Grimmett pada Grafik, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf ):

Teorema Pertimbangkan perkolasi ikatan pada , di mana setiap tepi antara titik-titik kisi terbuka dengan probabilitas $\mathbb Z^2$ . Probabilitas bahwa titik asal berada dalam komponen terhubung tanpa batas adalah 0.$\frac12$

Kita bisa mengurangi dari masalah kita untuk masalah ini: pada dasarnya itu hanya 2 menguraikan (tapi tergantung) salinan perkolasi obligasi pada . Pertimbangkan konfigurasi D 1 di mana tepi membentuk kisi tak terbatas berlian yang mengandung asal. Jika kita membalik semua sisi, kita mendapatkan kisi tak terbatas lain dari berlian D 2 . Pertimbangkan persimpangan konfigurasi aktual dengan D 1 dan dengan D 2 . Masing-masing adalah persis model perkolasi ikatan pada Z 2 , hanya diputar 45 ∘ . Probabilitas bahwa setiap titik dalam cluster yang tak terbatas adalah maka 0 (Tidak ada tepi di D $\mathbb Z^2$$D_1$$D_2$$D_1$$D_2$$\mathbb Z^2$$45^{\circ}$$D_1$dapat dihubungkan ke tepi dalam ).$D_2$

Untuk menyimpulkan, perhatikan bahwa jumlah dari sejumlah peristiwa yang dapat dihitung dengan probabilitas 0 memiliki probabilitas 0; jumlah di atas probabilitas bahwa setiap titik kisi berada di kluster tak terbatas.

(Keberadaan komponen besar yang sewenang-wenang adalah herring merah. Seseorang harus memperbaiki suatu poin, dan bertanya apakah itu dalam komponen yang tidak terikat.)

Hmm, well, ini satu upaya pertama. Mari kita amati dua hal penting:

1. Jika grafik ini memiliki komponen terhubung yang tak terhingga besar, oleh lemma infinity König, ia memiliki jalur sederhana tak terbatas.
2. Kejadian bahwa grafik memiliki jalur sederhana tanpa batas tidak tergantung pada setiap pilihan individu dari orientasi tepi (dan dengan demikian, setiap set pilihan tepi terbatas). Karena itu, ini adalah peristiwa ekor dan menurut hukum nol-satu Kolmogorov probabilitasnya adalah nol atau satu.

Jadi, apakah nol atau satu? Tidak segera jelas, meskipun kita dapat membuat dugaan, karena oleh teorema "monyet tak terbatas dengan mesin tik", grafik ini berisi jalur sederhana panjang sewenang-wenang dengan probabilitas satu. Tentu saja, lebih banyak diperlukan untuk membuktikan secara ketat bahwa itu sebenarnya memiliki jalur tanpa batas dengan probabilitas satu.

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

$[0,1]^2$

$n = 800$

Kode di sini: https://gist.github.com/girving/16a0ffa1f0abb08934c2

Pembaruan: Seperti yang ditunjukkan dalam komentar, lemma tidak menyiratkan jalan yang tidak terbatas, jadi jawaban ini secara keseluruhan salah. Tidak yakin apakah itu dapat digunakan dengan cara probabilistik lain.

Jawabannya adalah ya: ada jalan tanpa batas. Memang, ada jalan tanpa batas untuk setiap grafik seperti itu; probabilitas tidak diperlukan.

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

$G$

Jika lemma itu benar, versi infinite mengikuti dari König seperti dicatat oleh Joe. ( Perbarui: Salah, lihat komentar)