Slow Mixing for the Hard-Core Model on Z^2

ACO Student Seminar
Friday, December 7, 2012 - 1:10pm
1 hour (actually 50 minutes)
Skiles 005
College of Computing, Georgia Tech
The hard-core model has attracted much attention across several disciplines, representing lattice gases in statistical physics and independent sets in discrete mathematics and computer science. On finite graphs, we are given a parameter \lambda, and an independent set I arises with probability proportional to \lambda^{|I|}. We are interested in determining the mixing time of local Markov chains that add or remove a small number of vertices in each step. On finite regions of Z^2 it is conjectured that there is a phase transition at some critical point \lambda_c that is approximately 3.79. It is known that local chains are rapidly mixing when \lambda < 2.3882. We give complementary results showing that local chains will mix slowly when \lambda > 5.3646 on regions with periodic (toroidal) boundary conditions and when \lambda > 7.1031 with non-periodic (free) boundary conditions. The proofs use a combinatorial characterization of configurations based on the presence or absence of fault lines and an enumeration of a new class of self-avoiding walks called taxi walks. (Joint work with Antonio Blanca, David Galvin and Prasad Tetali)