Finite Markov chains in statistical mechanics and combinatorics

Finite Markov chains can be viewed as random walks in a finite set. In applications, this set often consists of certain combinatorial objects whose typical properties are to be understood. If the set is large, obtaining exact solutions to such problems is generally infeasible. Markov chains can provide a highly efficient method to generate randomized approximations in such cases, but only if they equilibrate at a rate that grows slowly with the size of the set of objects under study. We will study several classes of Markov chains that have been developed to study a number of notoriously difficult problems in statistical mechanics and combinatorics, and determine under what conditions they provide efficient approximation schemes.