| Tóm tắt: | We study the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics. Long et al. studied the case $q=2$, the Swendsen-Wang algorithm for the mean-field ferromagnetic Ising model, and showed that the mixing time satisfies: (i) $\Theta(1)$ for $\beta<\beta_c, $(ii) $\Theta(n^{1/4})$for$\beta=\beta_c,$ (iii)$ \Theta(\log n)$ for $\beta>\beta_c,$ where $\beta_c $is the critical temperature for the ordered/disordered phase transition. In contrast, for $q\geq 3$ there are two critical temperatures $0<\beta_u<\beta_{rc} $that are relevant. We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the $n$-vertex complete graph satisfies: (i) $\Theta(1) $for$ \beta<\beta_u, $(ii) $\Theta(n^{1/3}) $for $\beta=\beta_u,$ (iii) $\exp(n^{\Omega(1)})$ for$ \beta_u<\beta<\beta_{rc}, $and (iv)$ \Theta(\log{n})$ for $\beta\geq\beta_{rc}$. These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.
|
|---|