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

Abstract 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’ $\lambda \gt 0$ , with higher $\lambda$ 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 $\lambda$ , the mixing time is $O(n\log 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 $\lambda$ , depending on $H$ and the maximum degree of $G$ .