## Preliminary list of abstracts

**Note:** We are using the fantastic MathJax JavaScript library to typeset the mathematics on this web page.
You can right-click on a formula to zoom in or to select the rendering engine you like (all under 'Settings').
Under Firefox the default renderer turns out to be MathML (which is quick), but you might prefer the HTML-CSS renderer for more faithful LaTeX rendering.
If you encounter any problems with this setup: then please email us!

Click here to go back to the list of abstracts.

*Keywords:*Swendsen-Wang; Rapid mixing; Ising model

- Ullrich, Mario (Mathematical Institute, FSU Jena, Germany)

Let $G=(V,E)$ be a graph with finite vertex set
$V$ and edge set $E\subseteq\binom{V}{2}$,
where $\binom{V}{2}$ is the set of all subsets of $V$ with 2
elements, $N:=\vert{V}\vert$.
The *Ising model* is defined as the set of possible
configurations $\Omega_{\rm IS}=\{-1,1\}^V$,
together with the probability measure
\[
\pi_\beta(\sigma) \;:=\; \pi^{G}_\beta(\sigma) \;=\; \frac1{Z_\beta}\,
\exp\biggl\{\beta\sum_{\{u,v\}\in E}
\boldsymbol{1}_{\{\sigma(u)=\sigma(v)\}}\biggr\},
\]
where $u\leftrightarrow v$ means that $u$ and $v$ are neighbors in $G$,
$Z$ is the
normalization constant and $\beta\ge0$ is called the inverse
temperature.

The goal is to generate an (approximate) sample with respect to $\pi_\beta$ in time that is polynomial in the number of vertices $N$. This is possible with "local" Markov chains (like the Metropolis algorithm) if $\beta$ is below some critical value, i.e. $\beta\le\beta_c$, but impossible for larger values.

We prove that the mixing time of the Swendsen-Wang algorithm cannot be much slower than the mixing time of any local Markov chain if the maximum degree of the underlying graph is bounded. I.e. if the maximal degree of $G$ is $\Delta$, then \[ \lambda(P_{\rm SW}) \;\ge\; c^\Delta\,\lambda(P_{\rm L}), \] where $P_{\rm SW}$ (resp. $P_{\rm L}$) is the transition matrix of the Swendsen-Wang (resp. any local) Markov chain, $\lambda(\cdot)$ denotes the spectral gap and $c$ is some constant that depends only on the temperature. As a consequence we get rapid mixing of the Swendsen-Wang algorithm for the two-dimensional Ising model at high temperatures.

Furthermore we present a modified version of the Swendsen-Wang chain that is applicable for planar graphs $G$ and prove that it is rapidly mixing at all temperatures. This seems to be the first Markov chain for the Ising model that is proved to mix in polynomial time for all temperatures.

*ArXiv e-prints*, November 2010.

*in preparation*.