Before revision:  Due to the global nature of the updatesof the Swendsen-Wang algorithm, the underlying Markov chain often mixes rapidly in the low temperature region (large \beta) where long-range correlations impair the convergence rate of local chains such as the Glauber dynamics. With few exceptions, tight bounds on the convergence rate of the Swendsen-Wang algorithm only hold for high temperature regions (small \beta) corresponding to the uniqueness or the decay of correlations region. We present tight bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree that extend to the non-uniqueness region . Specifically, we show that a spatial mixing property known as the Variance Mixing condition introduced by Martinelli et al. ( 2004)implies constant spectral gap of the Swendsen-Wang dynamics .
After revision:  Due to the global nature of its updates. We present optimal bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree that extend to the non-uniqueness region . Specifically, we show that a spatial mixing property known as the Variance Mixing condition introduced by Martinelli et al. ( 2004)implies constant spectral gap of the Swendsen-Wang dynamics .