Let \(G=V,E)\) be an arbitrary graph, \(|V|= n\). The \(Q\)-state Potts model is defined as follows: Let \((V_1,\ldots, V_{Q})\) be an ordered partition of the set \(V\) of vertices into (possibly empty) disjoint subsets. The partition defines a configuration \(\sigma\), the vertex \(v\in V_{j}\) being assigned a colour \(j\). Let \(D(\sigma)\) be the set of edges between colour classes; the measure of the configuration \(\sigma\) is given by \(\mu(\sigma) = \exp(-\beta |D(\sigma)|)\), where the coupling constant \(\beta\) is assumed to be positive (the ferromagnetic case). Hence, the probability that the system is in the state \(\sigma\) is defined as \(Z(G)^{-1}\exp(-\beta|D(\sigma)|)\), where \(Z(G) = \sum_\sigma\exp(-\beta |D(\sigma)|)\) is the partition function, the sum being taken over all configurations.
The Swendsen-Wang process [R. Swendsen and J.-S. Wang, Phys. Rev. Lett. 58, 86-88 (1987)]was proposed as a Markov chain Monte Carlo method for estimating the partition function \(Z(G)\). Let \(P_{t,\sigma}\) be the law of the process at time \(t\) under the condition that the initial state is \(\sigma\), and let \(\pi\) be the stationary distribution. Set \(d(t) = \max_\sigma \|P_{t,\sigma} -\pi\|\), where we use \(\|\cdot\|\) to denote the variation distance. The Swendsen-Wang process is called rapidly mixing if the mixing time \(\min\{t; d(t)\leq 1/e\}\) is bounded by a polynomial in \(n\). This property (or the lack thereof) is studied for various classes of graphs. For example, it is shown that for trees the mixing time is \(O(n)\) for any \(\beta\).