  We study two widely used algorithms for the Potts model on rectangular
subsets of the hypercubic lattice Z^d - heat bath dynamics and the
Swendsen-Wang algorithm - and prove that, under certain circumstances, the
mixing in these algorithms is torpid or slow. In particular, we show that for
heat bath dynamics throughout the region of phase coexistence, and for the
Swendsen-Wang algorithm at the transition point, the mixing time in a box of
side length L with periodic boundary conditions has upper and lower bounds
which are exponential in L^{d-1}. This work provides the first upper bound of
this form for the Swendsen-Wang algorithm, and gives lower bounds for both
algorithms which significantly improve the previous lower bounds that were
exponential in L/(log L)^2.
