隨機圖相變（the random-graph phase transition）

隨機圖相變是 G(n,p) 在平均度數 np 越過 1 時整體結構所經歷的劇變。它是離散網路世界中水之結冰或磁化開始的對應物，也是隨機圖理論在數學物理中佔有一席之地的原因。它回答的問題是：恰在臨界密度附近，當邊被加入時，連通分量的大小與數目究竟發生了什麼？

寫 p = c/n。有三個區間。次臨界（c < 1）：所有分量皆為 O(log n)，各幾乎是棵樹，最大者大小約為 (log n)/(c - 1 - log c)。臨界（c = 1，更精確地 p = 1/n）：最大的數個分量為 n^(2/3) 階，此尺度上有許多個，且具有帶剩餘邊的非平凡隨機結構。超臨界（c > 1）：湧現一個大小為線性 rho(c) n 的唯一巨人，而第二大者回到 O(log n)。此相變是連續的（巨人比例 rho(c) 自 0 連續上升），但歷史名稱「雙跳」來自透過 G(n,m) 觀察它：當 m 增過 n/2 條邊時，最大分量先從 O(log n) 跳到 n^(2/3)（在臨界點），再跳到線性大小，兩次質變。c = 1 附近的精細結構是臨界窗口 p = (1 + lambda n^(-1/3))/n（固定實數 lambda），其中重新標度的分量大小收斂（Aldous）到具拋物漂移的布朗運動的偏移段長度——一個與連續體之間的優美聯繫。

這是從第一原理嚴格證明的湧現集體現象的典範，也是理解滲流、伊辛模型、可滿足性門檻與傳染病模型中相變的範本。它之所以重要，是因為它顯示微觀、獨立的隨機性能產生帶有普適標度指數的尖銳宏觀相變（n^(2/3) 的分量大小、n^(-1/3) 的窗口寬度）。一個誠實的提醒：確切的常數與連續體極限依賴於模型為平均場（厄多斯-雷尼無幾何）；在格子上，對應的滲流相變有不同、依維度而定的指數，而上述臨界窗口圖像是平均場、無幾何場景所特有的。