Fast algorithms, slow mixing, and the cluster expansion.

We discuss a method based on the cluster expansion from statistical physics for designing efficient sampling algorithms for spin models on graphs. We show how the same method can be used to establish slow mixing of the Glauber dynamics of these models. We also discuss applications of the cluster expansion method to some classical problems in combinatorics.