Counting independent sets in percolated graphs via the Ising model

Anna Geisler, Mihyun Kang, Michail Sarantis, Ronen Wdowinski · 2025

Read Counting independent sets in percolated graphs via the Ising model by Anna Geisler, Mihyun Kang, Michail Sarantis, Ronen Wdowinski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08715.txt.

Introduction

Anna Geisler, Mihyun Kang, Michail Sarantis, and Ronen Wdowinski work in combinatorics and statistical physics in this two thousand twenty-five paper. They count independent sets in random subgraphs formed by keeping each edge of a graph with some fixed probability. Their setting is regular bipartite graphs with certain vertex-isoperimetric properties. The work extends earlier results by Kronenberg and Spinka on the percolated hypercube.

The method combines graph containers with the cluster expansion from statistical physics. Along the way the authors expand the partition function of the Ising model in a certain parameter range and prove a refined container lemma for that model. Applications include even tori of growing side length. The refined lemma also mildly improves recent bounds by Jenssen, Malekshahian, and Park.

Catalog record

CREATORAnna Geisler, Mihyun Kang, Michail Sarantis, Ronen Wdowinski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08715

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counting independent sets in percolated graphs via the Ising model Anna Geisler, Mihyun Kang, Michail Sarantis, Ronen Wdowinski Abstract . Given a graph G G , we form a random subgraph G p G_{p} by including each edge of G G independently with probability p p . We provide an asymptotic expansion of the expected number of independent sets in random subgraphs of regular bipartite graphs satisfying certain vertex-isoperimetric properties, extending the work of Kronenberg and Spinka on the percolated hypercube. Combining graph containers with the cluster expansion from statistical physics, we give an expansion of the partition function of the Ising model in a certain range of the parameters. Among other applications, we obtain results for even tori of growing side-length. As a tool, we prove a refined container lemma for the Ising model, which mildly improves recent bounds of Jenssen, Malekshahian, and Park. Keywords. independent sets, Ising model, container method, cluster expansion 1. Introduction 1.1. Motivation and background An independent set in a graph G=(V(G),E(G)) is a vertex subset I\subseteq V(G) such that no two vertices in I are connected by an edge. We denote by \mathcal{I}(G) the collection of independent sets of G and set i(G)\coloneqq|\mathcal{I}(G)| . Independent sets arise naturally in various combinatorial and algorithmic problems, and thus their study has been a long-standing topic inspiring a variety of methods and results. This includes a wealth of results on problems concerning their enumeration, sampling, algorithmic hardness, as well as structural and extremal properties. Since the problem of exact enumeration is known to be hard [ 7 , 59 ] , it is natural to pursue asymptotic results. One of the main techniques in this direction is via a probabilistic analysis of the hard-core model. Let G be a finite graph. The hard-core model on G with fugacity \lambda>0 samples independent sets I\in\mathcal{I}(G) with probability \mathbb{P}(\boldsymbol{I}=I)=\frac{\lambda^{|I|}}{Z_{G}(\lambda)}, where Z_{G}(\lambda)=\sum_{I\in\mathcal{I}(G)}\lambda^{|I|} is the partition function of the model, also known as the independence polynomial of G . Since Z_{G}(1)=i(G) , studying the partition function in a range including \lambda=1 implies a corresponding enumerative result. A graph that has drawn particular interest is the d -dimensional hypercube Q^{d} , whose vertex set is \{0,1\}^{d} and two vertices are adjacent if they differ in exactly one coordinate. A celebrated and influential result of Korshunov and Sapozhenko [ 41 ] states that i(Q^{d})=(1+o(1))2\sqrt{e}2^{2^{d-1}}. Galvin [ 25 ] extended their technique to the hard-core model on Q^{d} and described the typical structure of independent sets, as well as approximations of the partition function, for various values of the fugacity \lambda . Later, Jenssen and Perkins [ 36 ] proved that i(Q^{d})=2\sqrt{e}2^{2^{d-1}}\left(1+\frac{3d^{2}-3d-2}{8\cdot 2^{d}}+O\left(d^{4}2^{-2d}\right)\right), and furthermore they provide an algorithm to compute any number of terms of the cluster expansion. Questions about independent sets are also an active area of research on various random graphs models [ 8 , 14 , 20 , 43 , 44 , 53 ] . The percolated graph G_{p} is a random graph obtained from the base graph G after independently retaining each edge with probability p . Percolation is a broad and deep subject on its own (see e.g., [ 10 , 27 ] ), and in particular the percolated hypercube Q^{d}_{p} has been extensively studied for its various structural and combinatorial properties [ 1 , 11 , 9 , 18 , 19 , 28 , 60 ] . It is natural to extend the result of Korshunov and Sapozhenko [ 41 ] to its percolated setting, and Kronenberg and Spinka [ 45 ] initiated this line of work and studied the random variable i(Q^{d}_{p}) (see also [ 13 ] for a more recent work on the distribution of i(Q^{d}_{p}) ). The first key observation of Kronenberg and Spinka was the equivalence, in expectation, of the hard-core model on percolated graphs to the antiferromagnetic Ising model in the unpercolated setting, thus eliminating the randomization of the graph. The antiferromagnetic Ising model on a graph G has two parameters, the fugacity \lambda>0 and the inverse temperature \beta\in(0,\infty) , and it samples any subset I\subseteq V(G) of vertices with probability \mathbb{P}(\boldsymbol{I}=I)=\frac{\lambda^{|I|}e^{-\beta|E(I)|}}{Z_{G}(\lambda,\beta)}, where Z_{G}(\lambda,\beta)=\sum_{I\subseteq V(G)}\lambda^{|I|}e^{-\beta|E(I)|} is the partition function. Note that configurations I with neighboring sites occupied are allowed, but are exponentially penalized by \beta|E(I)| according to the number of such instances. The hard-core model may informally be viewed as the special case when \beta=\infty . An elementary, yet important observation of Kronenberg and Spinka [ 45 , Proposition 1.7] is that for p=1-e^{-\beta} , (1) \mathbb{E}[Z_{G_{p}}(\lambda)]=Z_{G}(\lambda,\beta). All the theorems in [ 45 ] , as well as in our current work, are then derived from the study of the Ising model on the base graph G . The common strategy for deriving the asymptotics of the partition functions above is verifying the convergence of the cluster expansion of the partition function’s logarithm, and this also involves finding an appropriate graph container lemma. 1.2. Main themes and results. The goals of this paper are two-fold. Our first goal concerns asymptotic enumeration of independent sets and explores how far beyond we can go from the hypercube Q^{d} , so that we can derive similar asymptotic results for more general regular bipartite graphs with similar mild vertex-expansion properties. We describe a set of technical conditions for a graph G under which a container lemma and the convergence of the cluster expansion for the Ising and the hard-core model are guaranteed, generalizing the work of Kronenberg and Spinka [ 45 ] on the hypercube. The parameterized isoperimetric conditions we impose allow us to apply our results to graphs with weaker vertex-expansion than previously considered examples. Our second goal is to improve the graph container lemma applicable to the Ising model. Such a graph container lemma is also of interest for other purposes, but here it allows us to show that our asymptotic results hold for values of the fugacity \lambda beyond previous works. Previous results in the hard-core model had to assume that \lambda=\tilde{\Omega}(d^{-1/3}) in order to apply a container lemma of Galvin [ 25 ] (where \tilde{\Omega} hides a polylogarithmic factor). Jenssen, Malekshahian, and Park [ 30 ] recently proved a refined container lemma allowing them to improve the range of validity to \lambda=\tilde{\Omega}(d^{-1/2}) . We give an alternative proof of this result that also works in the Ising model while also slightly improving the polylogarithmic factor. The main ingredients of our proof are entropy tools by Peled and Spinka [ 55 ] . 1.2.1. Vertex-isoperimetry As noted in the past, e.g., in [ 26 , 36 ] , the key properties of the hypercube relevant to the container lemma and the cluster expansion are its isoperimetric inequalities and the fact that it is regular bipartite. Apart from the hypercube, isoperimetric inequalities were used in similar settings for the middle layers of the Boolean lattice [ 4 ] , even tori [ 29 , Lemma 6.1] , and, more generally, Cartesian product graphs [ 15 ] . The similarities among these results are evident, and it is therefore natural to expect the method of [ 36 , 45 ] to work for a broad class of regular bipartite graphs with vertex-isoperimetric properties akin to the hypercube. As stated before, one of our goals in this

Read the complete text