Glauber dynamics for the hard-core model on bounded-degree H -free graphs

The hard-core model has as its configurations the independent sets of some graph instance G . The probability distribution on independent sets is controlled by a ‘fugacity’ λ > 0 , with higher λ leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph H is excluded as an induced subgraph. If H is a subdivided claw then, for all λ , the mixing time is O(nlog n) , where n is the order of G . This extends a result of Chen and Gu for claw-free graphs. When H is a path, the set of possible instances is finite. For all other H , the mixing time is exponential in n for sufficiently large λ , depending on H and the maximum degree of G .