Understand
The hardcore model is a model of lattice gas systems which has received much attention in statistical physics, probability theory and theoretical computer science.
- It is the probability distribution over independent sets $I$ of a graph weighted proportionally to $\lambda^{|I|}$ with fugacity parameter $\lambda$.
- We prove that at the uniqueness threshold of the hardcore model on the $d$-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree $d$.
- Specifically, we show that unless NP$=$RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree $d$ for fugacity $\lambda_c(d) < \lambda < \lambda_c(d) + \epsilon(d)$ where $\lambda_c = \frac{(d-1)^{d-1}}{(d-2)^d}$ is the uniqueness threshold on the $d$-regular tree and $\epsilon(d)>0$.