  We give an FPTAS and an efficient sampling algorithm for the high-fugacity
hard-core model on bounded-degree bipartite expander graphs and the
low-temperature ferromagnetic Potts model on bounded-degree expander graphs.
The results apply, for example, to random (bipartite) $\Delta$-regular graphs,
for which no efficient algorithms were known for these problems (with the
exception of the Ising model) in the non-uniqueness regime of the infinite
$\Delta$-regular tree. We also find efficient counting and sampling algorithms
for proper $q$-colorings of random $\Delta$-regular bipartite graphs when $q$
is sufficiently small as a function of $\Delta$.
