Заповніть випадкову сітку, де кожен вузол незалежно відкритий з імовірністю p. При критичному порозі pc ≈ 0.5927 вперше з'являється охоплюючий кластер, що з'єднує верх з низом — це неперервний (другого роду) фазовий перехід, що вивчається у статистичній фізиці.
pc ≈ 0.5927 (2D квадратна сітка, вузлова перколяція)
D = 91/48 ≈ 1.896 (фрактальна розмірність при критичності)
τ = 187/91 ≈ 2.055 (показник розміру кластера: n(s) ~ s^{-τ})
ν = 4/3 (показник кореляційної довжини)
β = 5/36 (показник параметра порядку)Критичні показники 2D перколяції були доведені суворо Смірновим (Медаль Філдса 2010) за допомогою конформної інваріантності та SLE (еволюція Шрама–Льовнера). Фрактальний кластер при pc має однакову геометрію на будь-якій 2D сітці — явище, зване універсальністю.
Теорія перколяції вивчає, як утворюються зв'язані шляхи через випадкове середовище. У вузловій перколяції кожна клітинка сітки незалежно є «відкритою» з імовірністю p. Коли p перевищує критичний поріг pc, з'являється нескінченний охоплюючий кластер — класичний неперервний фазовий перехід.
Для вузлової перколяції на 2D квадратній сітці pc ≈ 0.5927. Нижче цього значення всі кластери залишаються скінченними; вище нього гігантський охоплюючий кластер виникає з імовірністю, що наближається до 1 зі зростанням розміру сітки.
Охоплюючий кластер — зв'язана компонента відкритих вузлів, що з'єднує верхній рядок сітки з нижнім. Його перша поява при pc відповідає фазовому переходу, аналогічно до замерзання рідини або намагнічування матеріалу.
Union-Find (Система непересічних множин) ефективно групує вузли у зв'язані компоненти. Коли відкривається новий вузол, він об'єднується з відкритими сусідами. Зі стисненням шляху та об'єднанням за рангом кожна операція виконується за майже O(1) амортизованого часу — значно швидше за обхід у ширину для великих сіток.
Саме при p = pc охоплюючий кластер є фракталом з гаусдорфовою розмірністю D = 91/48 ≈ 1.896 у 2D. Це означає, що якщо виміряти «масу» (кількість вузлів) кластера всередині кола радіуса r, вона масштабується як r^D, а не r^2, як для суцільного диска.
У вузловій перколяції кожна вершина незалежно відкрита з імовірністю p. У зв'язковій перколяції кожне ребро між сусідами відкрите з імовірністю p. Обидві мають фазові переходи, але при різних порогах: для зв'язкової перколяції на квадратній сітці pc = 0.5 точно завдяки симетрії самодуальності.
У критичній точці кореляції поширюються на всі масштаби, що породжує безмасштабну поведінку. Імовірність того, що вузол належить кластеру розміру s, підпорядковується n(s) ~ s^(-τ) при τ = 187/91 ≈ 2.055 у 2D. На логарифмічній гістограмі це видно як пряма лінія — помітна у симуляції при p ≈ 0.593.
Перколяція моделює протікання рідини через пористу породу, електропровідність у композитних матеріалах, поширення лісових пожеж, розповсюдження епідемій по мережах контактів та квантове тунелювання у невпорядкованих середовищах. Фазовий перехід відповідає критичній точці у кожній з цих систем.
На скінченній L×L сітці перехід розмитий у смузі ~L^(-1/ν) навколо pc, де ν = 4/3 — показник кореляційної довжини. Більші сітки дають чіткіші переходи. Саме тому симуляції на малих сітках показують удавані пороги, що розсіяні навколо справжнього pc, а степеневий закон гістограми чіткий лише на великих сітках.
Універсальність означає, що критичні показники (D, τ, ν, β) залежать лише від просторової вимірності, а не від мікроскопічних деталей сітки. Усі 2D моделі перколяції — квадратна, трикутна, стільникова, вузлова чи зв'язкова — мають ті самі показники, утворюючи один клас універсальності. Це було доведено суворо Смірновим за допомогою SLE.