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' $\hat{I}»>0$, with higher $\hat{I}»$ 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 $\hat{I}»$, 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 $\hat{I}»$, depending on $H$ and the maximum degree of $G$.

Minor revision. This version accepted for publication in Combinatorics, Probability and Computing