Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs
Häggström 1996 猜想被解決，取樣 q 條件從 Δ⁵ 降至 C log Δ，跨越多項式至對數的量級改進
- Häggström 1996 猜想完整解決：p > p_s 時 Δ-正則樹隨機簇模型的 Gibbs 測度唯一存在
- 取樣 q 條件從 Δ⁵ 壓縮至 C log Δ，混合時間降至近最優的 n^{1+o(1)}
- 弱空間混合速率 c* 被精確刻畫，但 q > 1 全參數低溫取樣仍是開放問題
Häggström 於 1996 年提出的猜想塵封近 30 年後被徹底解決：在 Δ-正則樹低溫區間 p > p_s，隨機簇模型恰好存在唯一 Gibbs 測度。同步實現的算法突破是：對隨機正則圖的取樣，所需 q 條件從 q ≥ Δ⁵ 壓縮至 q ≥ C log Δ，量級從多項式躍降至對數。
隨機簇模型：相變三分律與閉合公式 p_s = q/(Δ+q−2)
隨機簇模型（random-cluster model） 是一類依賴型隨機子圖分布，由邊存在概率 p ∈ (0,1) 與叢集權重 q ≥ 1 兩個參數決定。q = 1 時，它退化為獨立 Bernoulli 滲流；q 為整數且 q ≥ 2 時，它通過精確耦合等價於鐵磁 Ising/Potts 自旋模型——這意味著為隨機簇模型設計的高效取樣算法，可以直接轉化為 Potts 模型的取樣算法，包括著名的 Swendsen-Wang 算法（一種基於隨機簇耦合的高效非局部 Markov chain）。
對 q > 2 的情況，模型在 p 變化時呈現「三分律」：高溫區（p < p_u）邊之間的相關性隨距離指數衰減；低溫區（p > p_s）出現線性大小的唯一巨型連通分量；中間的「共存區間」(p_u, p_s) 則是兩種相態並存、Markov chain 混合時間呈指數慢的困難地帶。在樹和隨機圖等非 amenable 圖上，這個共存區間是一段有限寬度的參數範圍，而非單一臨界點。
低溫臨界值 p_s 有精確閉合公式：p_s(q, Δ) = q / (Δ + q − 2)。本文的目標正是 p > p_s 這個低溫唯一性區間，此前對它的理解一直殘缺不全——Häggström 1996 年猜想所指向的正是這個空缺。
消息遞歸破解 Häggström 猜想：弱空間混合的精確速率
Häggström 1996 年的論文已建立了 p < p_u 的唯一性與 (p_u, p_s) 的非唯一性，卻對 p > p_s 只留下猜想。後來 Jones（1999）與 Grimmett-Janson（2005）只將唯一性推進到 p ≳ log Δ / Δ 的範圍，遠高於 p_s，形成長達近 30 年的缺口；同一猜想並被收入 Grimmett 的經典教科書（Conjecture 10.97）。
Theorem 1.1 對所有實數 q > 1 和 p > p_s 完整建立唯一性，徹底關閉這個問題。核心工具是弱空間混合（weak spatial mixing, WSM）：邊界條件對中心區域的影響隨距離 h 以 e^{−c*·h} 速率指數衰減。為此論文引入「消息函數（message function）」f(v)，定義為頂點 v 的子樹中，v 被連接到有線邊界分量的概率的一個單調變換，並滿足遞歸關係 f(w) = ∏_{v: child of w} Φ(f(v))。
這個遞歸的分析揭示：當 p > p_s 時，它在 (0,1) 內有一個吸引不動點 z，而 f = 0 的不動點變得不穩定。只要葉節點被連接到邊界的概率均勻正向有界（即 θ-wired 邊界條件），遞歸以指數速率收斂到 z，衰減率 c 等於遞歸函數在 z 的導數。這一方法的精妙之處在於直接命中 p_s 的精確閾值，而舊方法（如 Jones 1999 的分支過程論證）需要額外餘量，才能越過 p_s。
Theorem 1.2 與 1.3：近最優混合時間 n^{1+o(1)}
基於弱空間混合，論文進一步建立了 Markov chain 的收斂時間界。Theorem 1.2 對有線邊界條件下的 (Δ−1)-ary 樹，在全低溫唯一性區間 p > p_s，證明隨機簇 Glauber 動態（heat-bath Glauber dynamics，逐邊更新的 Markov chain）的混合時間為 n^{1+o(1)} = n(log n)^{O(log log n)}，接近線性最優。此前最好結果（Blanca-Chen-Štefaňkovič 等，2023）用 Potts 耦合的熵分解僅對整數 q 達到 O(n log n)，本文推廣至所有實數 q > 1。
混合時間證明採用「塊動態（block dynamics）」遞歸：將樹的邊分為頂部塊 B₀ 和底部塊 B₁，兩者保持顯著重疊。B₁ 先更新後，因模型在 p > p_s 時隨機優佔超臨界 Bernoulli 滲流，B₀ 的葉節點有正密度被連通到 B₁ 底部邊界，從而在 B₀ 上誘導 θ-wired 邊界條件，可直接調用弱空間混合完成耦合。遞歸估計代入 h = O(log n) 即得 Theorem 1.2。
Theorem 1.3 是最重要的算法結果：對所有 p > p_s，當 q ≥ C₀ log Δ 時，隨機 Δ-正則圖以高概率具有混合時間 n^{1+o(1)}，提供了隨機簇模型與 Potts 模型的高效取樣算法。先前全 p > p_s 有效的最好算法，對整數 q 需要 q ≥ Δ⁵，對非整數 q 需要 q ≥ exp(Ω(Δ))；本文統一壓縮至對數量級。對整數 q，這同時給出 Swendsen-Wang 動態的混合時間界 n^{2+o(1)}（通過已有比較估計得出）。
q ≥ C log Δ 的技術門檻與 q > 1 全覆蓋的開放問題
從 Δ⁵ 到 log Δ 的量級躍升，根植於對弱空間混合速率 c 的精確刻畫。分析隨機圖時，需對圖中 n 個頂點中心的 Θ(log n) 球同時做聯合估計（union bound），要求衰減率 c 足夠大以壓制對數因子。c 正比於遞歸函數在 z 的導數，僅在 q 足夠大時達到所需量級，最終導出 q ≥ C₀ log Δ 的條件。
弱空間混合本身對所有 q > 1 和 p > p_s 均成立，因此預期 Theorem 1.3 對所有 q > 1 同樣成立，但目前的局部化分析方案在此遇到技術障礙。完整覆蓋低溫區間的 q > 1 全參數高效取樣，仍是這一領域的核心開放問題。
Häggström 1996 年猜想在本文中被徹底關閉；隨機正則圖取樣的 q 條件從 Δ⁵ 壓縮至 log Δ，但 q > 1 全覆蓋目標尚待攻克。