Swendsen-Wang Algorithm on the Mean-Field Potts Model
summary
Analyzes the Swendsen–Wang chain on the complete-graph Potts model and pins mixing regimes to two explicit thresholds: below the first threshold the chain mixes in constant time, at the first/uniqueness threshold mixing is polynomial, between thresholds mixing is n^{Θ(1)} (provable upper bounds), and above the second threshold mixing drops to Θ(log n) to reach O(√n) coupling scale. Proofs use the Erdos-Renyi giant component to derive a one-dimensional map F for the largest color class, and a potential-function variance window to convert stochastic fluctuations into drift near criticality; second-moment and small-subgraph-conditioning issues obstruct extending results to random Δ-regular graphs.
AI-written summary · about