A Refined Graph Container Lemma and Applications to the Hard‐Core Model on Bipartite Expanders

Journal article

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 $$ G $$ and λ > 0 $$ \lambda >0 $$ , the hard‐core model on G $$ G $$ at activity λ $$ \lambda $$ is the probability distribution μ G , λ $$ {\mu}_{G,\lambda } $$ on independent sets in G $$ G $$ given by μ G , λ ( I ) ∝ λ | I | $$ {\mu}_{G,\lambda }(I)\propto {\lambda}^{\mid I\mid } $$ . As one of our main applications, we show that the hard‐core model at activity λ $$ \lambda $$ on the hypercube Q d $$ {Q}_d $$ exhibits a ‘structured phase’ for λ = Ω ( log 2 d / d 1 / 2 ) $$ \lambda =\Omega \left({\log}^2d/{d}^{1/2}\right) $$ in the following sense: in a typical sample from μ Q d , λ $$ {\mu}_{Q_d,\lambda } $$ , most vertices are contained in one side of the bipartition of Q d $$ {Q}_d $$ . This improves upon a result of Galvin, which establishes the same for λ = Ω ( log d / d 1 / 3 ) $$ \lambda =\Omega \left(\log d/{d}^{1/3}\right) $$ . As another application, we establish a fully polynomial‐time approximation scheme (FPTAS) for the hard‐core model on a d $$ d $$ ‐regular bipartite α $$ \alpha $$ ‐expander, with α > 0 $$ \alpha >0 $$ fixed, when λ = Ω ( log 2 d / d 1 / 2 ) $$ \lambda =\Omega \left({\log}^2d/{d}^{1/2}\right) $$ . This improves upon the bound λ = Ω ( log d / d 1 / 4 ) $$ \lambda =\Omega \left(\log d/{d}^{1/4}\right) $$ due to the first author, Perkins and Potukuchi. We discuss similar improvements to results of Galvin‐Tetali, Balogh‐Garcia‐Li and Kronenberg‐Spinka.

Authors: Jenssen, M; Malekshahian, A; Park, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Random Structures and Algorithms
• Volume: 68
• Issue: 1
• Article number: e70041
• Publication date: 2026-01-12
• Acceptance date: 2025-12-10
• DOI: 10.1002/rsa.70041
• EISSN: 1098-2418
• ISSN: 1042-9832
• Language: English
• Keywords: hard‐core model; container lemma; phase transition; container algorithm