Many local Markov chains based on local dynamics are known to undergo a phase transition as a parameter λ of the system is varied. For example, in the context of independent sets, the Gibbs distribution assigns each independent set a weight λ|I|, and a natural Markov chain adds or deletes a single vertex at each step. It is believed that there is a critical point λc such that for λ < λc, local dynamics converge in polynomial time while for λ > λc they require exponential time. A parallel phenomenon arises in statistical physics in the context of determining whether there is a unique limiting distribution (e.g., for independent sets) on the infinite lattice, known as a Gibbs state. While there has been progress in making such observations rigorous, many recent results have been the direct or indirect outcome of interdisciplinary collaboration, building on insights from both disciplines.
This working group will promote more collaborations by bringing together researchers from computer science, combinatorics, probability, and mathematical physics to study topics central to the interplay between work on Markov chains and on phase transitions in random structures. Topics to be emphasized include
Next: Call for Participation
Workshop Index
DIMACS Homepage