DIMACS Working Group on Current Topics in Markov Chains and Phase Transitions

March 26 - 30, 2007
Georgia Institute of Technolgy

Dana Randall, Georgia Institute of Technolgy, randall@cc.gatech.edu
Eric Vigoda, Georgia Institute of Technolgy, vigoda@cc.gatech.edu
Presented under the auspices of the Special Focus on Discrete Random Systems.

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
Contacting the Center
Document last modified on October 20, 2005.