A refined graph container lemma and applications to the hard-core model on bipartite expanders

Abstract

We establish a refined version of a graph container lemma due to Galvin and discuss several applications related to the hard-core model on bipartite expander graphs. Given a graph $G$ and $\hat{I}»>0$, the hard-core model on $G$ at activity $\hat{I}»$ is the probability distribution $\hat{I}{¼}_{G,\hat{I}»}$ on independent sets in $G$ given by $\hat{I}{¼}_{G,\hat{I}»}(I)\propto \hat{I}{»}^{|I|}$. As one of our main applications, we show that the hard-core model at activity $\hat{I}»$ on the hypercube $Q_d$ exhibits a `structured phase' for $\hat{I}»=\hat{I}\text{c◯}({\log }^{2}d/d^{1/2})$ in the following sense: in a typical sample from $\hat{I}{¼}_{Q_d,\hat{I}»}$, most vertices are contained in one side of the bipartition of $Q_d$. This improves upon a result of Galvin which establishes the same for $\hat{I}»=\hat{I}\text{c◯}(\log d/d^{1/3})$. As another application, we establish a fully polynomial-time approximation scheme (FPTAS) for the hard-core model on a $d$-regular bipartite $\hat{I}\pm$-expander, with $\hat{I}\pm >0$ fixed, when $\hat{I}»=\hat{I}\text{c◯}({\log }^{2}d/d^{1/2})$. This improves upon the bound $\hat{I}»=\hat{I}\text{c◯}(\log d/d^{1/4})$ due to the first author, Perkins and Potukuchi. We discuss similar improvements to results of Galvin-Tetali, Balogh-Garcia-Li and Kronenberg-Spinka.