Refine search
Actions for selected content:
1 results
Glauber dynamics for the hard-core model on bounded-degree
$H$-free graphs
- Part of
-
- Journal:
- Combinatorics, Probability and Computing , First View
- Published online by Cambridge University Press:
- 19 September 2025, pp. 1-12
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
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$.
