Approximately counting independent sets in bipartite graphs via graph containers

Abstract.

By implementing algorithmic versions of Sapozhenko’s graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. Our first algorithm applies to $d$-regular, bipartite graphs satisfying a weak expansion condition: when $d$ is constant, and the graph is a bipartite $\mathrm{\Omega }({\log }^{2}d/d)$-expander, we obtain an FPTAS for the number of independent sets. Previously such a result for $d>5$ was known only for graphs satisfying the much stronger expansion conditions of random bipartite graphs. The algorithm also applies to weighted independent sets: for a $d$-regular, bipartite $\alpha$-expander, with $\alpha >0$ fixed, we give an FPTAS for the hard-core model partition function at fugacity $\lambda =\mathrm{\Omega }(\log d/d^{1/4})$. Finally we present an algorithm that applies to all $d$-regular, bipartite graphs, runs in time $\exp \left(O\left(n\cdot \frac{{\log }^{3}d}{d}\right)\right)$, and outputs a $(1+o(1))$-approximation to the number of independent sets.

1. Introduction

Let $ℐ(G)$ denote the set of independent sets of a graph $G$ and $i(G)=|ℐ(G)|$ denote the number of independent sets of $G$. Computing $i(G)$ is a #P-hard problem, even when restricted to bounded degree, bipartite graphs [47]. Even approximating $i(G)$ (to a constant or even subexponential factor) remains NP-hard, even when restricted to $d$-regular graphs with $d\ge 6$ [53].

Intuitively, one might expect the problem of approximating $i(G)$ to be easier on the class of bipartite graphs; for one, there is a polynomial-time algorithm to find a maximum-size independent set in a bipartite graph while the corresponding problem is NP-hard for general graphs. Dyer, Goldberg, Greenhill, and Jerrum [11] defined the counting problem #BIS (bipartite independent set) and showed that several natural combinatorial counting problems are as hard to approximate as #BIS. These problems include counting stable matchings, approximating the ferromagnetic Potts model partition function ($q\ge 3$) [24, 15], counting the number of $q$-colorings in a bipartite graph ($q\ge 3$), and approximating the ferromagnetic Ising model partition with non-uniform external fields [23].

The search for approximation algorithms for $i(G)$ that exploit bipartite structure generally falls into two categories. The first approach finds classes of graphs on which polynomial-time approximation algorithms exist. Liu and Lu [41] gave the first such algorithm, providing an FPTAS for the number of independent sets in bipartite graphs in which degrees on one side are bounded by $5$, while degrees on the other side are unrestricted. Another line of work in this direction includes [31] in which approximation algorithms are given for the hard-core partition function $Z_G(\lambda )$ (counting weighted independent sets) in bounded-degree, bipartite expander graphs, based on two tools from statistical physics: polymer models and the cluster expansion (following [28]). This work was followed by several improvements, extensions, and generalizations including [40, 5, 7, 13, 12, 14, 8]. All of these algorithms are ‘low-temperature’ algorithms: they exploit the fact that on a bipartite graph with sufficient expansion, most (weighted) independent sets have few vertices from one side of the bipartition; that is, they are close to one of the two ground states consisting of all subsets of one side. In contrast, the algorithms of Weitz [55] (an FPTAS for $i(G)$ in graphs of maximum degree at most $5$) and Liu and Lu [41] are ‘high-temperature’ algorithms, exploiting correlation decay properties of the uniform distribution on $ℐ(G)$ (or more generally the hard-core model of weighted independent sets) for small vertex degrees.

The second category of bipartite approximation algorithms are those that apply to all bipartite graphs, with running times better than what is known for general graphs. The main result in this direction is the algorithm of Goldberg, Lapinskas, and Richerby [25] which provides an $ϵ$-relative approximation to $i(G)$ for bipartite graphs, running in time $O(2^{.2372n}{(1/ϵ)}^{O(1)})$, beating the best known running time for general graphs of $O(2^{.268n}{(1/ϵ)}^{O(1)})$ from the same paper (in comparison, the best known running time for exact counting algorithms for general graphs is $O(2^{.3022n})$ [21]).

1.1. Main results

In this paper we use tools from combinatorics, namely the graph container method of Sapozhenko to give new approximate counting algorithms for independent sets in bipartite graphs. Our first result is an FTPAS for $i(G)$ for weakly expanding, $d$-regular bipartite graphs, for constant $d$.

For $z>0$, we say that $\widehat{z}$ is an $ϵ$-relative approximation to $z$ if $(1-ϵ)\le z/\widehat{z}\le (1+ϵ)$. A fully polynomial-time approximation scheme (FPTAS) is an algorithm that for every $ϵ>0$ outputs an $ϵ$-relative approximation to $i(G)$ and runs in time polynomial in $|V(G)|$ and $1/ϵ$. We let ${\mu }_G$ denote the uniform distribution on $ℐ(G)$. A polynomial-time sampling scheme for ${\mu }_G$ runs in time polynomial in $|V(G)|$ and $1/ϵ$ and outputs an independent set with distribution $\widehat{\mu }$ within $ϵ$ total variation distance of ${\mu }_G$.

For $\alpha >0$, we say that a $d$-regular bipartite graph $G$ with bipartition $X,Y$ is a bipartite $\alpha$-expander if for every $A\subseteq X$ and $A\subseteq Y$ of size at most $|X|/2$, we have

(1) $|N(A)|\ge (1+\alpha )|A|.$

Theorem 1.

There exists a constant $C_1>0$ so that for $d$ fixed and sufficiently large, and $\alpha =\frac{C_1{\log }^{2}d}{d}$, there is an FPTAS for $i(G)$ and a polynomial-time sampling scheme for ${\mu }_G$ for the class of $d$-regular, bipartite $\alpha$-expander graphs.

Previous results on expander graphs include an FPTAS for $i(G)$ in the case that $G$ is a typical $d$-regular, random bipartite graph [31, 40, 8]. These algorithms exploit the very strong expansion conditions satisfied by a random graph: sets of size $\tilde{O}(n/d)$ on each side of the bipartition expand by a factor $\tilde{\mathrm{\Omega }}(d)$.

A natural and powerful generalization of the notion of counting independent sets is to consider weighted independent sets in the form of the hard-core model partition function (also known as the independence polynomial)

$$Z_G(\lambda )=\sum _{I\in ℐ(G)}{\lambda }^{|I|}.$$

The corresponding probability measure on independent sets, known as the hard-core model, is given by

$${\mu }_{G,\lambda }(I)=\frac{{\lambda }^{|I|}}{Z_G(\lambda )}.$$

Taking $\lambda =1$ gives $i(G)$ and ${\mu }_G$. In previous works, an FPTAS for $Z_G(\lambda )$ for bounded-degree, bipartite $\alpha$-expanders was obtained for $\lambda$ much larger than $1$, specifically $\lambda \ge K{\mathrm{\Delta }}^{c/\alpha }$ for constants $c,K>1$ [31, 7, 12]. In particular, under the expansion conditions of Theorem 1, these algorithms require $\lambda \ge {\mathrm{\Delta }}^{\tilde{\mathrm{\Omega }}(\mathrm{\Delta })}$.

Our next result adapts the algorithm of Theorem 1 to work for bipartite $\alpha$-expanders for $\lambda$ much smaller than $1$.

Theorem 2.

For every $\alpha >0$ there exists a constant $C_2>0$ so that for $d\ge 3$ and $\lambda >\frac{C_2\log d}{d^{1/4}}$ there is an FPTAS for $Z_G(\lambda )$ and a polynomial-time sampling scheme for ${\mu }_{G,\lambda }$ for the class of $d$-regular, bipartite $\alpha$-expanders.

In fact in proving Theorems 1 and 2 we can interpolate between the two cases, letting the lower bound on $\lambda$ shrink as the expansion condition gets stronger. The more general condition obtained is essentially the same as the condition for slow mixing of Glauber dynamics given by Galvin and Tetali [20].

Our next result is an approximation algorithm for $i(G)$ for all (not necessarily expanding) $d$-regular bipartite graphs $G$, where $d$ may either be constant or growing with the size of the graph, $n$. When $d\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$, the algorithm runs in subexponential time. This algorithm estimates $i(G)$ by separating the contribution from non-expanding sets and expanding sets on each side of the bipartition and uses the expander algorithm of Theorem 1 as a subroutine.

Theorem 3.

For every $c>0$, there is a randomized algorithm that given a $d$-regular, $n$-vertex bipartite graph $G$ outputs an $n^{-c}$-relative approximation to $i(G)$ with probability at least $2/3$ and runs in time

$$\exp \left(O\left(\frac{n{\log }^{3}d}{d}\right)\right).$$

Note that while the algorithm of Theorem 3 applies more generally than that of Theorem 1, the algorithmic guarantees are weaker in several senses (in addition to the slower running time): the algorithm uses randomness and the accuracy is limited to being polynomially small in $n$. Moreover we do not provide a corresponding sampling algorithm for Theorem 3; the problem is not self-reducible for regular graphs, and so there is not a direct reduction of approximate sampling to counting. We can overcome this in Theorem 1, however, using the self-reducibility of polymer models.

1.2. Background

The study of independent sets plays a central role in combinatorics since a broad range of problems can be phrased in terms of independent sets in graphs (and more generally hypergraphs). The container method is one of the most powerful combinatorial tools for studying independent sets. At a high level, the container method exploits a clustering phenomenon exhibited by independent sets which can often be used to deduce useful structural information for typical independent sets in a given graph or hypergraph. For graphs, the method was developed in the early 1980’s by Kleitman and Winston [35, 36] and was independently discovered by Sapozhenko who used the method to enumerate independent sets in regular graphs [49, 50]. See the survey of Samotij [48] for background and examples. The full potential of the container method only recently became apparent with the powerful generalization of the method to the context of hypergraphs developed by Saxton and Thomason [52] and Balogh, Morris and Samotij [4]. These developments have made the container method one of the most influential tools in modern combinatorics.

In this paper, we will only need ideas from the theory of graph containers, and our treatment is most closely related to that of Sapozhenko [49]. A canonical application of Sapozhenko’s version of the container method is his proof that the number of independent sets in the $d$-dimensional hypercube, $Q_d$, is asymptotically equal to $2\sqrt{e}\cdot 2^{2^{d-1}}$ (a result originally proved by Korshunov and Sapozhenko [38]). See also Galvin’s exposition of Sapozhenko’s proof [18].

Recently, Jenssen and Perkins [32] used Sapozhenko’s graph containers for $Q_d$ (and Galvin’s extension to weighted independent sets [17]) along with the theory of polymer models and the cluster expansion to deduce refined counting estimates and detailed probabilistic information for independent sets in $Q_d$. The polymer models they consider closely resemble those used by Jenssen, Perkins and Keevash [31] to design approximate counting algorithms in bipartite expander graphs. However, the hypercube $Q_d$ is a far weaker expander than the graphs considered in [31], ruling out a direct application of the the cluster expansion method. To overcome this obstacle, they showed that the container method arises naturally as a tool for proving cluster expansion convergence. This synthesis of the cluster expansion and the container method has now seen a number of applications to enumeration problems in combinatorics [30, 33, 9, 3].

Graph containers have in fact been used previously in a number of results in theoretical computer science, including [20, 16, 19]. These results use Sapozhenko’s techniques to prove a type of negative algorithmic result: that the Glauber dynamics (a local Markov chain) for sampling independent sets (or $q$-colorings) in bipartite graphs with sufficient expansion exhibit torpid mixing; that is, the mixing time is exponentially large in the size of the graph.

In this paper, we return to the algorithmic context to prove positive results, showing that the container method can be algorithmically implemented to design efficient approximate counting and sampling algorithms for a broad class of bipartite graphs. There is in fact a connection been the torpid mixing results above and the current algorithmic results: a key step in using polymer models and the cluster expansion as algorithms to approximately count independent sets in bipartite graphs is showing that most (weighted) independent sets can be accounted for by one of two polymer models that capture small deviations from independent sets that are fully contained in one side of the bipartition. This step (Lemmas 16 below) amounts to proving a kind of torpid mixing result, closely related to the result of Galvin and Tetali who proved torpid mixing for $d$-regular bipartite $\alpha$-expanders, for $\alpha =\mathrm{\Omega }({\log }^{3}d/d)$ [20, Corollary 1.3], similar to the class of graphs to which Theorem 1 applies.

While Theorem 1 gives efficient approximate counting and sampling algorithms for a larger class of bipartite expander graphs than previous approaches, it does not say much about the tractability of #BIS, beyond ruling out a class of graphs as hard examples. In another prominent approximation problem of undetermined complexity, the Unique Games problem, efficient approximation algorithms for expander graphs [2, 37, 44] were later leveraged via graph decompositions into expanding pieces to find subexponential-time algorithms for all instances [1]. This suggests a very natural goal of finding much faster algorithms for approximating #BIS.

Question 1.

Is there a subexponential-time approximation algorithm for #BIS?

Theorem 3 makes a small step in this direction, giving subexponential-time algorithms for regular graphs of growing degree, using an expander algorithm as a subroutine to account for the contribution to $i(G)$ from expanding sets. Non-expanding sets are accounted for separately, also using ideas from graph containers. It is tempting to think that algorithmic graph decomposition results (e.g. [45, 6]) could be used in conjunction with expander algorithms for #BIS, but it is not clear to us how to use results that bound the number of edges between expanding pieces to obtain improved approximation algorithms for #BIS, and so this remains an interesting direction for future research.

1.3. Outline

In Section 2 we give a brief warm-up to show how ideas from graph containers can be used for approximately counting independent sets in graphs. In Section 3 we present the graph container results we will need for the main algorithmic results. In Section 4 we define a polymer model which we will use to approximate the number of independent sets in expander graphs. In Section 5 we prove Theorem 1. In Section 6 we prove Theorem 3. In Section 7 we extend the graph container results of Section 3 and the polymer model of Section 4 to the case of weighted independent sets to prove Theorem 2.

2. Warm-up: algorithms from containers

In this section, we demonstrate how ideas from graph containers can be used to design faster algorithms to approximately count independent sets in (not necessarily bipartite) $d$-regular graphs. This section is intended as a warm-up which introduces the interplay between the container method and counting algorithms, and is not needed for the proofs of Theorems 1, 2 and 3.

Let us assume that we have an algorithm $A$ that runs in time $a(n)$ on a general (not necessarily $d$-regular) graph $G$ on $n$ vertices and outputs an $ϵ$-relative approximation to $i(G)$. We will show that if $G$ is $d$-regular for $d=\omega (1)$, one can obtain an algorithm running in time $a(n/2)\cdot 2^{o(n)}$.

Let $T:=n\ln d/d$. We note that throughout the paper, we let $\ln$ denote the natural logarithm and let $\log$ denote ${\log }_2$. We may then write

where is the number of independent sets of $G$ of size less than $T$, and $i_{\ge T}(G)$ is the the number of independent sets of size at least $T$. One can compute by brute-force in time $\left(\genfrac{}{}{0pt}{}{n}{T}\right)\cdot \mathrm{poly}(n)$. To compute $i_{\ge T}(G)$, we use a subtle idea of Sapozhenko [51] (also see [29], [34]) with a tighter analysis. First, we fix an ordering $\prec$ of the vertices of the graph $G$. Given a subset $S\subseteq V(G)$ and vertex $v\in V(G)$, we let $d_S(v)$ denote the number of neighbor of $v$ in $S$. The following algorithm takes an independent set $I$ of size at least $T$ as input and returns a “certificate” $\xi$:

• $t,i\leftarrow 0$, $\xi \leftarrow {(0)}^n$, $V_0\leftarrow V(G)$

• while $t\le T$ do

  • $v\leftarrow {\mathrm{argmax}}_{v\in V_i}{d}_{V_i}(v)$ with ties broken using $\prec$

  • if $v\in I$

    • $V_{i+1}\leftarrow V_i\setminus (\{v\}\cup N(v))$

    • $t\leftarrow t+1$, $i\leftarrow i+1$, ${\xi }_i\leftarrow 1$.

  • if $v\notin I$

    • $V_{i+1}\leftarrow V_i\setminus \{v\}$

    • $i\leftarrow i+1$.

• return $\xi$

It is worth noting that $\xi$ is not the indicator vector of any subset of $V(G)$, but rather an indicator vector describing the steps at which a vertex $v\in I$ is removed from $V_i$. Assume that the algorithm runs for $k=k(\xi )$ steps (i.e., $k$ is that final value that $i$ takes in the execution of the algorithm) when the output is $\xi$ and let $V_{\xi }=V_k$. A key property of $\xi$ is that it determines both $V_{\xi }$, and $I\cap (V(G)\setminus V_{\xi })$. We may therefore group independent sets according to their certificate $\xi$ and write

(2) $$i_{\ge T}(G)=\sum _{\begin{array}{c}\xi \in {\{0,1\}}^n,\\ |\xi |=T\end{array}}i(G[V_{\xi }]).$$

The advantage of this expression is that the number of possible certificates $\left(\genfrac{}{}{0pt}{}{n}{T}\right)$ is relatively small and, as we show next, the size of each $V_{\xi }$ is close to $n/2$. We have therefore exploited the clustering phenomenon of independent sets characteristic of the container method to effectively halve the size of the input graph to our algorithm (albeit at the expense of losing regularity of the graph).

We now give the argument to bound the size of each $V_{\xi }$. For any subset $S\subseteq V(G)$, let us denote $e_S$ to be the number of edges in the induced subgraph $G[S]$. A straightforward extension of the Hoffman bound (see e.g. [10, 43, 22, 27]), and using the fact that the smallest eigenvalue of a $d$-regular graph is at least $-d$, gives us

$$2e_S\ge \frac{2d}{n}{|S|}^2-d|S|.$$

So for $i\le k$, we have

(3) $$\underset{v\in V_i}{\max }{d}_{V_i}(v)\ge \frac{2e_{V_i}}{|V_i|}\ge \frac{d}{n}\left(2|V_i|-n\right),$$

and so if $v\in I$, then $|V_{i+1}|\le |V_i|\left(1-\frac{2d}{n}\right)+d$, and so at the end of the algorithm, we have $|V_k|\le \frac{n}{2}+O\left(\frac{n\ln d}{d}\right)$.

Thus, if we have an algorithm $A$ running in time $a(n)=a(n,ϵ)$ on general graphs on $n$ vertices which outputs an $ϵ$-relative approximation to $i(G)$ for a general graph $G$ on $n$ vertices, then an $ϵ$-relative approximation to (2) may be computed in time $\left(\genfrac{}{}{0pt}{}{n}{T}\right)\cdot a\left(\frac{n}{2}+O\left(\frac{n\ln d}{d}\right)\right)$. Combining this with the brute-force computation of gives an algorithm running in time

$$\mathrm{poly}(n)\cdot {\left(\genfrac{}{}{0pt}{}{n}{\frac{n\ln d}{d}}\right)}^2\cdot a\left(\frac{n}{2}+O\left(\frac{n\ln d}{d}\right)\right)$$

that outputs an $ϵ$-relative approximation to $i(G)$ for a $d$-regular graph $G$ on $n$ vertices. So in particular, if $d=\omega (1)$, then using the algorithm of Goldberg, Lapinskas, and Richerby [25] as a blackbox, we obtain a $2^{(0.134+o(1))n}$ time algorithm for approximating $i(G)$ in $d$-regular graphs on $n$ vertices. We will see below in Section 6 that with more sophisticated ideas this running time can be made subexponential provided that the error $ϵ=n^{-a}$ for some $a>0$ (Theorem 3).

3. Graph container lemmas

In this section we introduce results from the theory of graph containers that will be key for the algorithms of Theorems 1, 2 and 3. Many of the ideas here have their roots in the aforementioned container method of Sapozhenko [49].

We assume throughout that $G$ is a $d$-regular bipartite graph on $2n$ vertices with bipartition $X,Y$, so $|X|=|Y|=n$. For a subset $A\subseteq X$, we use $W$ to denote $N(A)$. Let us define $[A]:=\{u\in X|N(u)\subseteq W\}$ to be the closure of $A$. Let us call $A$ $2$-linked if the subgraph of $G^2$ induced by $A$ is connected. We say that $A$ is expanding if

$$|W|-|[A]|\ge (C_1/2)\frac{{\log }^{2}d}{d}|W|,$$

where the constant $C_1>0$ will be sufficiently large and chosen later. Otherwise, we say that $A$ is non-expanding.

Let $𝒢(v,a,w)$ denote the set of $2$-linked expanding sets $A$ such that $A\ni v$, $|[A]|=a$, and $|W|=w$. Let ${𝒢}^{\prime }(v,a)$ be the set of $2$-linked non-expanding sets $A\ni v$ such that $A=[A]$, and $|A|=a$.

Remark: Observe that if $G$ is a bipartite $\alpha$-expander (as defined at (1)) then

(4) $$|N(A)|\ge (1+\alpha )|[A]|$$

for each $A\subseteq X$ or $A\subseteq Y$ such that $|[A]|\le n/2$. Indeed, if $|[A]|\le n/2$, then $|N(A)|=|N([A])|\ge (1+\alpha )|[A]|$. Since $\alpha \le 1$, inequality (4) implies that $|[A]|\le |N(A)|(1-\alpha /2)$, and so

(5) $$|N(A)|-|[A]|\ge (\alpha /2)|N(A)|$$

for each $A$ such that $|[A]|\le n/2$. In the following, condition (5) is slightly more convenient to work with and motivates our definition of an expanding set.

We now state our main technical lemmas. The first bounds the number of expanding sets and the second bounds the number of non-expanding sets (and gives an algorithm to enumerate them).

Lemma 4.

There is an absolute constant $c_1>0$ such that for every $v,a,w$ we have

$$|𝒢(v,a,w)|\le 2^{w-c_1(w-a)}.$$

Lemma 5.

There is an absolute constant $c_2>0$ such that for every $v,a$, we have

$$|{𝒢}^{\prime }(v,a)|\le 2^{c_2\frac{a{\log }^{2}d}{d}}.$$

Moreover, there is an algorithm running in time $2^{O\left(\frac{a{\log }^{2}d}{d}\right)}\cdot \mathrm{poly}(n)$ that outputs the set ${𝒢}^{\prime }(v,a)$.

Recall that for a subset $A\subseteq X$, we use $W$ to denote $N(A)$, with $|[A]|=a$, $|W|=w$. Set $t=w-a$. For every $s>0$, let $W_s=\{u\in W|d_{[A]}(u)\ge s\}$. We next define a notion of an approximation of the set $W$ (which in turn determines $[A]$).

Definition 6.

A set $F\subseteq W$ is an essential subset for $A$ if

1. $F\supseteq W_{d/2}$

2. $N(F)\supseteq [A]$.

The next lemma gives a family $𝒞(v,a,w)\subset 2^Y$ that contains an essential subset for each member of $𝒢(v,a,w)$. Crucially the set of approximating sets $𝒞(v,a,w)$ is far smaller than $𝒢(v,a,w)$.

Lemma 7.

There is a family $𝒞(v,a,w)\subset 2^Y$ of size at most

$$2^{\frac{16w{\log }^{2}d}{d}}$$

such that $𝒞(v,a,w)$ contains an essential subset of every $2$-linked set $A\ni v$ such that $|[A]|=a$ and $|W|=w$. Moreover, there is an algorithm running in time $2^{\frac{16w{\log }^{2}d}{d}}\cdot \mathrm{poly}(n)$ that outputs the set $𝒞(v,a,w)$.

We prove Lemma 7 below.

The following lemma of Park [46] strengthens a result of Sapozhenko [49] (the lemma is proved implicitly in [34] also).

Lemma 8.

There is an absolute constant $c_3>0$ such that the following holds: for every $F\subseteq X$, let $𝒢(F,a,w)$ be the set of expanding $2$-linked sets $A\subseteq X$ such that $|[A]|=a$, $|W|=w$, and $F$ is an essential subset of $A$. Then

$$|𝒢(F,a,w)|\le 2^{w-c_3\left(w-a\right)}.$$

With these lemmas in hand, we now prove Lemma 4 and Lemma 5.

Proof of Lemma 4.

First note that

(6) $𝒢(v,a,w)\subseteq {\displaystyle \bigcup _{F\in 𝒞(v,a,w)}}𝒢(F,a,w)$

and so by Lemmas 7 and 8, we have that

$|𝒢(v,a,w)|$ $\le {\displaystyle \sum _{F\in 𝒞(v,a,w)}}|𝒢(F,a,w)|$

$\le |𝒞(v,a,w)|\cdot \underset{F\in 𝒞(v,a,w)}{\max }|𝒢(F,a,w)|$

$\le 2^{\frac{16w{\log }^{2}d}{d}}\cdot 2^{w-c_3\left(w-a\right)}$

$\le 2^{w-\left(\frac{c_3}{2}\right)\left(w-a\right)}$

where for the last inequality we used that $w-a\ge (C_1/2)\frac{{\log }^{2}d}{d}w$ by the definition of an expanding set and assumed that $C_1>64/c_3$. ∎

Proof of Lemma 5.

Let $F$ be an essential subset of $A$ where $A$ is non-expanding. Note that each vertex in $W\setminus F$ has at least $d/2$ neighbors in ${[A]}^c$, and there are at most $d(w-a)$ edges between $W$ and ${[A]}^c$. It follows that

$$(d/2)\cdot |W\setminus F|\le d(w-a)$$

and so

$$|W\setminus F|\le 2(w-a)\le C_1\frac{{\log }^{2}d}{d}w.$$

Moreover, $W\setminus F\subset N^2(F)$, and $N^2(F)\le w{d}^2$, and so there are at most

$$\left(\genfrac{}{}{0pt}{}{w{d}^2}{\le C_{1}w({\log }^{2}d)/d}\right)\le 2^{O\left(\frac{a{\log }^{3}d}{d}\right)}$$

choices for $W$, each of which determines a $[A]$. Let ${𝒢}^{\prime }(F,a)$ denote the collection of $A\subset X$ such that $A=[A]$, $v\in A$, $A$ is $2$-linked, non-expanding and $F$ is an essential subset for $A$. Then by the above

$$|{𝒢}^{\prime }(F,a)|=2^{O\left(\frac{a{\log }^{3}d}{d}\right)}.$$

Moreover, we can generate the set ${𝒢}^{\prime }(F,a)$ in time $2^{O\left(\frac{a{\log }^{3}d}{d}\right)}\mathrm{poly}(n)$ by listing each set $W$ that is a union of $F$ with a subset of $N^2(F)$ of size at most $C_{1}w({\log }^{2}d)/d$, generating the corresponding closed set $[A]$ such that $N(A)=W$, and checking it satisfies the required conditions.

Now, by Lemma 7,

(7) ${𝒢}^{\prime }(v,a)\subseteq {\displaystyle \bigcup _{w\in [a,a\left(1+C_1\frac{{\log }^{2}d}{d}\right)]}}{\displaystyle \bigcup _{F\in 𝒞(v,a,w)}}{𝒢}^{\prime }(F,a)$

and so

$$|{𝒢}^{\prime }(v,a)|\le \left(C_1\frac{a{\log }^{2}d}{d}\right)\cdot 2^{O\left(\frac{a{\log }^{3}d}{d}\right)}=2^{O\left(\frac{a{\log }^{3}d}{d}\right)}.$$

Similarly, by (7), Lemma 7, and the above algorithm for generating ${𝒢}^{\prime }(F,a)$, we may generate ${𝒢}^{\prime }(v,a)$ in time $2^{O\left(\frac{a{\log }^{3}d}{d}\right)}\cdot \mathrm{poly}(n)$. ∎

We will need a covering result originally due to Lovász [42] and Stein [54].

Theorem 9.

Let $H$ be a bipartite graph on vertex sets $P$ and $Q$ where the degree of each vertex in $P$ is at least $a$ and the degree of each vertex in $Q$ is at most $b$. Then there is subset $Q^{\prime }\subset Q$ of size at most $\frac{|Q|}{a}(1+\ln b)$ such that $P\subseteq N(Q^{\prime })$.

We record the following corollary of Theorem 9 which we will use in the proof of Lemma 7.

Corollary 10.

Let $A\subseteq X$ be $2$-linked and let $A\ni v$. Then the following hold:

1. There exists a $2$-linked subset $A^{\prime }\subseteq A$ of size at most $2\frac{a}{d}\ln d+2\frac{w}{d}$ such that $A^{\prime }\ni v$ and $N(A^{\prime })$ is an essential subset for $A$.

2. There exists a $2$-linked subset $A^{\prime \prime }\subseteq A$ of size at most $2\frac{a}{d}\ln d+2\frac{w}{d}+2(w-a)$ such that $N(A^{\prime \prime })=W$.

Proof.

We begin by proving (1). Let $A_0\subset [A]$ be a maximal subset of vertices containing $v$ with pairwise disjoint neighborhoods. Clearly $|A_0|\le \frac{w}{d}$ and $N^2(A_0)\supseteq A$. Theorem 9 guarantees a subset $A_1\subseteq A$ of size at most $2\frac{a}{d}\ln d$ such that $W_{d/2}\supseteq N(A_1)$. Suppose $A_0\cup A_1$ is not $2$-linked, then there are at most $\frac{w}{d}$ $2$-linked components. Indeed, this is true since $N(A_0\cup A_1)\subseteq W$ and each two linked component covers at least $d$ vertices of $W$. Since $[A]$ is $2$-linked, it follows that one can choose a subset $A_2\subseteq [A]$ of size at most $\frac{w}{d}$ such that $A^{\prime }:=A_0\cup A_1\cup A_2$ is $2$-linked. We note that $|A^{\prime }|\le 2\frac{a}{d}\ln d+2\frac{w}{d}$. To show that $N(A^{\prime })$ is an essential subset for $A$ observe that

• $N^2(A^{\prime })\supseteq N^2(A_0)\supseteq [A]$, and

• $W_{d/2}\subseteq N(A_1)\subseteq N(A^{\prime })$.

We now turn to (2). Note that each vertex in $W\setminus W_{d/2}$ has at least $d/2$ neighbors in ${[A]}^c$, and there are at most $d(w-a)$ edges between $W$ and ${[A]}^c$. It follows that

$$(d/2)\cdot |W\setminus W_{d/2}|\le d(w-a)$$

and so

$$|W\setminus W_{d/2}|\le 2(w-a).$$

Let $A_3\subseteq A$ be a minimal cover of $W\setminus W_{d/2}$. We have that $|A_3|\le |W\setminus W_{d/2}|\le 2(w-a)$, and every vertex of $A_3$ is at a distance $2$ from some vertex in $A_0\subseteq A^{\prime }$ by the maximality of $A_0$. Thus $A^{\prime \prime }=A^{\prime }\cup A_3$ is $2$-linked, $|A^{\prime \prime }|\le 2(w-a)+|A^{\prime }|$ and $N(A^{\prime \prime })\supseteq W$, completing the proof. ∎

Finally we prove Lemma 7. The proof we present is different and simpler than the one in [49], whose proof works for a quantitatively weaker notion of expansion, but in return, asks that no two vertices share many common neighbors.

Proof of Lemma 7.

Let $A\ni v$ be a $2$-linked subset as in the statement of the lemma. By Corollary 10, there exists a $2$-linked subset $A^{\prime }\subset A$ of size at most $4\frac{w}{d}\ln d$ such that $v\ni A^{\prime }$ and $N(A^{\prime })$ is an essential subset for $A$. In view of this, we let $ℬ(v,a,w)$ be the set of all $2$-linked subsets of $A$, containing $v$, of size at most $4\frac{w}{d}\ln d$ and let

$$𝒞(v,a,w)=\{N(A):A\in ℬ(v,a,w)\}.$$

It remains to upper bound the size of $𝒞(v,a,w)$ and describe an algorithm that outputs the set. Note that $|ℬ(v,a,w)|=|𝒞(v,a,w)|$ and $|ℬ(v,a,w)|$ is at most the number of trees in $G^2$ containing $v$ as the root with at most $4\frac{w\log d}{d}$ vertices. Note that the maximum degree in $G^2$ is at most $d(d-1)$. So $ℬ(v,a,w)$ can be enumerated using the following procedure:

1. Assume an ordering on the neighbors of every vertex in the graph $G^2$. Let us use $v_i$ to denote the $i$’th neighbor of a vertex $v$. Let us also denote $v_0=v$.

2. Generate a list $S\in {\{0,\mathrm{\dots },d(d-1)\}}^{8\frac{w\ln d}{d}}$.

3. Consider the set $T_S=\{v^{(0)},\mathrm{\dots },v^{(s)}\}$ where $v^{(0)}=v$ and $v^{(i)}=v_{S_i}^{(i-1)}$.

4. If $|T_S|\le 4\frac{w\ln d}{d}$, then output $T_S$.

Consider any tree in $G^2$ with root $v$ and $s\le 4\frac{w\ln d}{d}$ nodes. There is at least one choice of the list $S$ that causes the above procedure to output the vertices of this tree, namely, if $(S_1,\mathrm{\dots },S_{2s})$ is the DFS traverse order and $S_i=0$ for $i\ge 2s$.

For each list $S$, the procedure takes $\mathrm{poly}(n)$ time, and the number of possible lists is ${(d(d-1)+1)}^{8\frac{w}{d}\ln d}\le 2^{\frac{16w{\log }^{2}d}{d}}$. Therefore there is an algorithm running in time $2^{\frac{16w{\log }^{2}d}{d}}\cdot \mathrm{poly}(n)$ that outputs the set $𝒞(v,a,w)$. ∎

4. Polymer Models

In this section we introduce a variant of the polymer models used by Jenssen, Keevash, and Perkins [31] to obtain approximation algorithms for bipartite expander graphs. Polymer models originated in statistical physics (e.g. [26, 39]) as a means to study spin models on lattices. Recently they were used to design algorithms for spin models at low temperatures [28].

Fix a $d$-regular bipartite graph $G$ with bipartition $(X,Y)$ of size $n$ each. A polymer of $G$ is a $2$-linked, expanding subset of $X$. Recall, from the previous section, that a set $A\subseteq X$ is expanding if

(8) $|N(A)|-|[A]|\ge (C_1/2){\displaystyle \frac{|N(A)|{\log }^{2}d}{d}}$

where $C_1$ is the constant from Theorem 1. Let $𝒫(G)$ denote the set of all polymers of $G$. The weight of a polymer $\gamma$ is given by $2^{-|N(\gamma )|}=:w_{\gamma }$. We call two polymers $\gamma$ and ${\gamma }^{\prime }$ compatible if $\gamma \cup {\gamma }^{\prime }$ is not $2$-linked, and incompatible otherwise, in which case we write $\gamma \nsim {\gamma }^{\prime }$. Let $\mathrm{\Omega }(G)$ denote the collection all subsets of mutually compatible polymers (including the empty set). The polymer model partition function is

(9) $${\mathrm{\Xi }}_G^X:=\sum _{\mathrm{\Lambda }\in \mathrm{\Omega }(G)}\prod _{\gamma \in \mathrm{\Lambda }}{w}_{\gamma },$$

and the associated Gibbs distribution ${\nu }_G^X$ on $\mathrm{\Omega }(G)$ defined by

$${\nu }_G^X(\mathrm{\Lambda })=\frac{{\prod }_{\gamma \in \mathrm{\Lambda }}{w}_{\gamma }}{{\mathrm{\Xi }}_G^X}\text{for}\mathrm{\Lambda }\in \mathrm{\Omega }(G).$$

When the weights of the polymer model are small enough one can hope to understand the partition function and the Gibbs distribution via perturbative techniques, and in particular, the cluster expansion.

For a tuple $\mathrm{\Gamma }$ of polymers, the incompatibility graph, $H(\mathrm{\Gamma })$, is the graph with vertex set $\mathrm{\Gamma }$ and an edge between any two incompatible polymers. A cluster $\mathrm{\Gamma }$ is an ordered tuple of polymers so that $H(\mathrm{\Gamma })$ is connected. Let us use $𝒞(G)$ to denote the set of all clusters of $G$. The cluster expansion of ${\mathrm{\Xi }}_G^X$ is the formal series expansion

(10) $$\ln {\mathrm{\Xi }}_G^X=\sum _{\mathrm{\Gamma }\in 𝒞(G)}\varphi (H(\mathrm{\Gamma }))\prod _{\gamma \in \mathrm{\Gamma }}{w}_{\gamma },$$

where $\varphi$ is the Ursell function defined by

$$\varphi (H)=\sum _{\begin{array}{c}{E}^{\prime }\subseteq E(H)\\ (V(H),E^{\prime })\text{connected}\end{array}}{(-1)}^{|E^{\prime }|}.$$

Since $𝒞(G)$ is an infinite set, the series in (10) is an infinite sum. In our application, we will work with a truncated sum after after establishing a fast enough rate of convergence. For these convergence bounds, (as in [28, 31]) we use a special case of the Koteckỳ–Preiss condition [39].

Theorem 11 ([39]).

Fix functions $f:𝒫(G)\to [0,\mathrm{\infty })$ and $g:𝒫(G)\to [0,\mathrm{\infty })$. Suppose that for every $\gamma \in 𝒫(G)$, we have

(11) $$\sum _{{\gamma }^{\prime }\sim ̸\gamma }{w}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}\le f(\gamma ).$$

Then the cluster expansion converges absolutely. Moreover, for every vertex $v$,

(12) $$\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}\left|\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{w}_{\gamma }\right|e^{g(\mathrm{\Gamma })}\le 1.$$

We will use this to obtain some relevant structural information about the polymer model. For polymers $\gamma$, define modified polymer weights ${\tilde{w}}_{\gamma }=2^{-|N(\gamma )|}\cdot 2^{\frac{|\gamma |{\log }^{2}d}{d}}$ and let

(13) ${\tilde{\mathrm{\Xi }}}_G^X={\displaystyle \sum _{\mathrm{\Lambda }\in \mathrm{\Omega }(G)}}{\displaystyle \prod _{\gamma \in \mathrm{\Lambda }}}{\tilde{w}}_{\gamma }$

be the modified polymer model partition function. We first show that this polymer model satisfies the Koteckỳ-Preiss condition for a suitable choice of functions $f$ and $g$.

Lemma 12.

Consider the modified polymer model where the polymers are all the $2$-linked subsets $A\subseteq X$ that are expanding, and the weight of a polymer $\gamma$ is given by

$${\tilde{w}}_{\gamma }=2^{-|N(\gamma )|}\cdot 2^{\frac{|\gamma |{\log }^{2}d}{d}}.$$

Let $f(\gamma )=\ln 2\cdot \frac{|\gamma |{\log }^{2}d}{d}$, and $g(\gamma )=2\ln 2\cdot \frac{|N(\gamma )|{\log }^{2}d}{d}$. Then for $d$ sufficiently large, every polymer $\gamma$ satisfies (11). The conclusion also holds for the original polymer model with weights $w_{\gamma }$ and the same choice of functions $f(\cdot ),g(\cdot )$.

Proof of Lemma 12.

It suffices to prove the claim for the modified polymer model since ${\tilde{w}}_{\gamma }>w_{\gamma }$ for all $\gamma$.

Recall, from the proof of Lemma 4 that $c_1\ge c_3/2\ge 64/C_1$. We evaluate

${\displaystyle \sum _{{\gamma }^{\prime }\sim ̸\gamma }}{\tilde{w}}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$ $\le {\displaystyle \sum _{v\in \gamma }}{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{\tilde{w}}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{2}^{-|N({\gamma }^{\prime })|}{e}^{2f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}\left({\displaystyle \sum _{t\ge (C_1/2)\frac{w{\log }^{2}d}{d}}}|𝒢(v,w-t,w)|2^{-w}\cdot e^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}\right)$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}{e}^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}\left({\displaystyle \sum _{t\ge (C_1/2)\frac{w{\log }^{2}d}{d}}}|𝒢(v,w-t,w)|2^{-w}\right)$

$\le |\gamma |{\displaystyle \sum _{w\ge d}}{e}^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}\left({\displaystyle \sum _{t\ge (C_1/2)\frac{w{\log }^{2}d}{d}}}{2}^{-c_1\cdot t}\right)$

$\le d|\gamma |{\displaystyle \sum _{w\ge d}}{e}^{4\ln 2\cdot \frac{w{\log }^{2}d}{d}}{2}^{-8\frac{w{\log }^{2}d}{d}}$

$\le d^2|\gamma |2^{-4{\log }^{2}d}$

$\ll \ln 2\cdot {\displaystyle \frac{|\gamma |{\log }^{2}d}{d}}=f(\gamma ).\mathit{∎}$

Therefore, Theorem 11 gives us that

(14) ${\displaystyle \sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}}\left|\varphi (\mathrm{\Gamma }){\displaystyle \prod _{\gamma \in \mathrm{\Gamma }}}{w}_{\gamma }\right|e^{g(\gamma )}\le 1,$

and the same with ${\tilde{w}}_{\gamma }$ replacing $w_{\gamma }$.

Now define the exponential of the truncated cluster expansion

(15) $${\mathrm{\Xi }}_G^X(\mathrm{\ell }):=\exp \left(\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \Vert \mathrm{\Gamma }\Vert \le \mathrm{\ell }\end{array}}\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{w}_{\gamma }\right),$$

where $\Vert \mathrm{\Gamma }\Vert :={\sum }_{\gamma \in \mathrm{\Gamma }}|\gamma |$. The following lemma bounds the error in approximating ${\mathrm{\Xi }}_G^X$ by ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$.

Lemma 13.

We have for every $\mathrm{\ell }\ge 1$,

(16) $$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell })\right|\le n\cdot 2^{-2\frac{\mathrm{\ell }{\log }^{2}d}{d}}.$$

In particular, if $\mathrm{\ell }\ge \frac{d}{2{\log }^{2}d}\log (n/ϵ)$, then

$$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell })\right|\le ϵ.$$

Proof.

First recall that for a cluster $\mathrm{\Gamma }$,

$$g(\mathrm{\Gamma })=\sum _{\gamma \in \mathrm{\Gamma }}g(\gamma )=2\ln 2\frac{{\log }^{2}d}{d}\sum _{\gamma \in \mathrm{\Gamma }}|N(\gamma )|\ge 2\ln 2\frac{{\log }^{2}d}{d}\Vert \mathrm{\Gamma }\Vert .$$

It follows from (14) that

$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell })\right|$ $=\left|{\displaystyle \sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \Vert \mathrm{\Gamma }\Vert >\mathrm{\ell }\end{array}}}\varphi (\mathrm{\Gamma }){\displaystyle \prod _{\gamma \in \mathrm{\Gamma }}}{w}_{\gamma }\right|$

$\le {\displaystyle \sum _v}{\displaystyle \sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\\ \Vert \mathrm{\Gamma }\Vert >\mathrm{\ell }\end{array}}}\left|\varphi (\mathrm{\Gamma }){\displaystyle \prod _{\gamma \in \mathrm{\Gamma }}}{w}_{\gamma }\right|$

$\le n{e}^{-2\ln 2\frac{\mathrm{\ell }{\log }^{2}d}{d}}$

$=n\cdot 2^{-2\frac{\mathrm{\ell }{\log }^{2}d}{d}}.\mathit{∎}$

Let $\Vert 𝚲\Vert ={\sum }_{\gamma \in 𝚲}|\gamma |$ for $𝚲\sim {\nu }_G^X$. We have the following large deviation result for $\Vert 𝚲\Vert$, following [32, Lemma 16].

Lemma 14.

For any $\delta \in (0,1)$, there is a $d_0=d_0(\delta )$ such for $d\ge d_0$, we have

$$\mathbb{P}(\Vert 𝚲\Vert \ge \delta n)\le 2^{-\left(\frac{\delta n{\log }^{2}d}{2d}\right)}.$$

Proof.

With ${\tilde{\mathrm{\Xi }}}_G^X$ as defined at (13), we have that $\ln {\tilde{\mathrm{\Xi }}}_G^X-\ln {\mathrm{\Xi }}_G^X=\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }$ for $\zeta =\frac{\ln 2{\log }^{2}d}{d}$. Summing (14) over all $v$, and using the fact that $|N(\gamma )|\ge d$ for every $\gamma$, we get

(17) $$\ln {\tilde{\mathrm{\Xi }}}_G^X\le \sum _v\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}\left|\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{\tilde{w}}_{\gamma }\right|\le n\cdot 2^{-2{\log }^{2}d}.$$

Therefore, we have

$\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }\le \ln {\tilde{\mathrm{\Xi }}}_G^X\le n\cdot 2^{-2{\log }^{2}d},$

and so by Markov’s inequality we have

$\mathbb{P}(\Vert 𝚲\Vert \ge \delta n)$ $\le \exp \left(-\zeta \delta n+n\cdot 2^{-2{\log }^{2}d}\right)$

$\le 2^{-\frac{\delta n{\log }^{2}d}{2d}},$

where the last inequality follows because $(1/2)\ln 2\ge {(\delta {\log }^{2}d)}^{-1}\cdot d\cdot 2^{-2{\log }^{2}d}$ for large enough $d$. ∎

Approximate counting and sampling for polymer models

Here, we will use an algorithm from [31] to approximate ${\mathrm{\Xi }}_G^X$ and approximately sample from ${\nu }_G^X$.

Lemma 15.

Then there is an FPTAS for ${\mathrm{\Xi }}_G^X$ that runs in time ${(n/ϵ)}^{O(d)}$. Moreover, for every $ϵ>0$ there is a randomized algorithm that runs in time ${(n/ϵ)}^{O(d)}$ that outputs a configuration $\mathrm{\Lambda }\in \mathrm{\Omega }(G)$ with distribution ${\nu }_{\text{alg}}^X$ so that .

To give a sense of the above algorithms, we briefly describe the FPTAS for ${\mathrm{\Xi }}_G^X$. Using Lemma 13, it is enough to compute ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$ (as defined in (15)) where $\mathrm{\ell }=\lceil \frac{d}{2{\log }^{2}d}\log (n/ϵ)\rceil$.

This may be done by

1. listing all clusters $\mathrm{\Gamma }$ of size at most $\mathrm{\ell }$,

2. computing $\varphi (\mathrm{\Gamma })$,

3. computing ${\prod }_{\gamma \in \mathrm{\Gamma }}{w}_{\gamma }$, and

4. evaluating ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$ by exponentiating the truncated cluster expansion.

To approximately sample from ${\nu }_G^X$ we appeal to the self-reducibility of the abstract polymer model, see [28, Theorem 10].

Remark 1.

In the proof of Theorem 3 in Section 6, we will in fact need to approximate the partition function of various subgraphs of $G$. These subgraphs, $H\subseteq G$, all have the following form: $H$ is the subgraph induced on vertex set $X^{\prime }\cup Y^{\prime }$ for some $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$ such that $N(X^{\prime })\subseteq Y^{\prime }$. For such a subgraph, we define a polymer of $H$ to be an expanding $2$-linked subset of $X^{\prime }$ and define the partition function ${\mathrm{\Xi }}_H^{X^{\prime }}$ in the obvious way. We note that the polymers of $H$ are a subset of the polymers of $G$. In particular, since the polymer model on $G$ satisfies the hypothesis of Theorem 11, the polymer model on $H$ also satisfies the hypothesis of Theorem 11 with the same functions $f$ and $g$. In particular, Lemmas 13, 14 and 15 also apply to the polymer model on $H$.

5. An algorithm for expander graphs: proof of Theorem 1

In this section, we prove Theorem 1. We assume throughout that $G$ is a $d$-regular bipartite $\alpha$-expander with $\alpha =C_1\frac{\log d}{d}$. We let $X,Y$ denote the vertex classes of $G$ and let $n=|X|=|Y|$. We note that by (5), we have that $|N(A)|-|A||\ge (C_1/2)\frac{|N(A)|{\log }^{2}d}{d}$ for every $A\subset X$ or $A\subset Y$ such that $|[A]|\le n/2$, i.e. each such set $A$ is expanding.

First we show that $i(G)$ can be approximated well by a linear combination of the polymer model partition functions ${\mathrm{\Xi }}_G^X$ and ${\mathrm{\Xi }}_G^Y$ (as defined in (9)). We may then use the algorithm of Section 4 to approximate ${\mathrm{\Xi }}_G^X$ and ${\mathrm{\Xi }}_G^Y$. Recall that we let $ℐ=ℐ(G)$ denote the set of independent sets of $G$. For the sampling algorithms, we show that ${\mu }_G$ can be approximated by a mixture of probability distributions on $ℐ$ derived from the polymer measures ${\nu }_G^X$, ${\nu }_G^Y$. We let ${\widehat{\nu }}_G^X$ denote the probability distribution on $ℐ$ defined as follows:

1. Sample a collection of compatible polymers $\mathrm{\Lambda }$ from the measure ${\nu }_G^X$.

2. Set $I=J\cup {\bigcup }_{\gamma \in \mathrm{\Lambda }}\gamma$ where $J$ is a uniformly random subset of $Y\backslash {\bigcup }_{\gamma \in \mathrm{\Lambda }}N(\gamma )$.

We define ${\widehat{\nu }}_G^Y$ analogously and define the mixture

$${\widehat{\mu }}_G=\frac{{\mathrm{\Xi }}_G^X}{{\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y}{\widehat{\nu }}_G^X+\frac{{\mathrm{\Xi }}_G^Y}{{\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y}{\widehat{\nu }}_G^Y.$$

Lemma 16.

For $n$ sufficiently large,

$$2^n\cdot \left({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y\right)$$

is an $ϵ$-relative approximation to $i(G)$ where $ϵ=2^{-\frac{n{\log }^{2}d}{60d}}.$ Moreover,

$${\Vert {\mu }_G-{\widehat{\mu }}_G\Vert }_{TV}\le 2ϵ.$$

Proof.

Let us define

$${ℐ}_X:=\{I\in ℐ|\text{every}2\text{-linked component of}I\cap X\text{is expanding}\}$$

i.e. the set of all $I$ such that ${\nu }_G^X(I)>0$. We note that since the independence number of $G$ is $n$, we have that for each $I\in ℐ$,

$$\min (|[I\cap X]|,|[I\cap Y]|)\le n/2.$$

In particular, every component of either $I\cap X$ or $I\cap Y$ is expanding. Therefore $ℐ={ℐ}_X\cup {ℐ}_Y$ and so

(18) $i(G)=|{ℐ}_X|+|{ℐ}_Y|-|{ℐ}_X\cap {ℐ}_Y|.$

Note that

(19) $${ℐ}_X=2^n\cdot {\mathrm{\Xi }}_G^X$$

and moreover, the set of $2$-linked components of $I\cap X$ for a uniformly chosen $I\in {ℐ}_X$ is distributed exactly accordingly to ${\nu }_G^X$. It will suffice to bound the size of ${ℐ}_X\cap {ℐ}_Y$.

Letting ${ℐ}_X^{\delta }=\{I\in {ℐ}_X:|I\cap X|\le \delta n\}$, for $\delta \in (0,1)$, it follows by Lemma 14 that

(20) $$|{ℐ}_X\backslash {ℐ}_X^{\delta }|\le |{ℐ}_X|\cdot 2^{-\frac{\delta n{\log }^{2}d}{2d}}.$$

Defining ${ℐ}_Y$, ${ℐ}_Y^{\delta }$, analogously and taking $\delta =1/30$ we have

(21) $$|{ℐ}_X^{\delta }\cap {ℐ}_Y^{\delta }|\le \left(\genfrac{}{}{0pt}{}{2n}{\le 2\delta n}\right)\le 2^n\cdot 2^{-\frac{n{\log }^{2}d}{60d}-1}\le |{ℐ}_X|\cdot 2^{-\frac{n{\log }^{2}d}{60d}-1}.$$

By (19), (20) and (21) we conclude that

(22) $|{ℐ}_X\cap {ℐ}_Y|\le |{ℐ}_X\backslash {ℐ}_X^{\delta }|+|{ℐ}_Y\backslash {ℐ}_Y^{\delta }|+|{ℐ}_Y^{\delta }\cap {ℐ}_X^{\delta }|\le 2^n({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)2^{\frac{-n{\log }^{2}d}{60d}},$

and therefore, by (18),

(23) $2^n({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)\cdot \left(1-2^{\frac{-n{\log }^{2}d}{60d}}\right)\le i(G)\le 2^n({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y).$

This completes the proof of the first claim. For the second claim we recall the following formula for the total variation distance between discrete probability measures:

(24) ${\Vert {\mu }_G-{\widehat{\mu }}_G\Vert }_{TV}={\displaystyle \sum _{I:{\widehat{\mu }}_G(I)>{\mu }_G(I)}}{\widehat{\mu }}_G(I)-{\mu }_G(I).$

We note that for $I\in {ℐ}_X\mathrm{△}{ℐ}_Y$, ${\widehat{\mu }}_G(I)=2^{-n}{({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)}^{-1}$, whereas for $I\in {ℐ}_X\cap {ℐ}_Y$, ${\widehat{\mu }}_G(I)=2^{1-n}{({\mathrm{\Xi }}_G^X+{\mathrm{\Xi }}_G^Y)}^{-1}$. It follows from (23) that ${\widehat{\mu }}_G(I)>{\mu }_G(I)$ only if $I\in {ℐ}_X\cap {ℐ}_Y$. By (22) and (24), we then have

$${\Vert {\mu }_G-{\widehat{\mu }}_G\Vert }_{TV}\le 2\cdot 2^{\frac{-n{\log }^{2}d}{60d}}.\mathit{∎}$$

Now we prove Theorem 1.

Proof of Theorem 1.

Set ${ϵ}_0=2^{-\frac{n{\log }^{2}d}{60d}}$. First suppose $ϵ\le 2{ϵ}_0$, then $i(G)$ may be computed exactly and a uniformly random independent set can be sampled by brute-force in time $2^{n+o(n)}={(1/ϵ)}^{O(d/{\log }^{2}d)}$.

Now suppose $ϵ>2{ϵ}_0$. By Lemma 16, it is enough to compute an $(ϵ/4)$-relative approximation to both ${\mathrm{\Xi }}_G^X$ and ${\mathrm{\Xi }}_G^Y$. By using the algorithm given by Lemma 15, this takes time ${(n/ϵ)}^{O(d)}$.

For the approximate sampling algorithm, we note that by Lemma 16, it is enough to obtain an $ϵ/2$-approximate sample from ${\widehat{\mu }}_G$. We do this as follows: we first compute $ϵ/8$-relative approximations to ${\mathrm{\Xi }}_G^X$ and ${\mathrm{\Xi }}_G^Y$ by computing ${\mathrm{\Xi }}_G^X(\mathrm{\ell })$ and ${\mathrm{\Xi }}_G^Y(\mathrm{\ell })$ respectively, with $\mathrm{\ell }$ chosen as in Lemma 15. We then pick $X$ or $Y$ with respective probabilities ${\mathrm{\Xi }}_G^X(\mathrm{\ell })/({\mathrm{\Xi }}_G^X(\mathrm{\ell })+{\mathrm{\Xi }}_G^Y(\mathrm{\ell }))$ and ${\mathrm{\Xi }}_G^Y(\mathrm{\ell })/({\mathrm{\Xi }}_G^X(\mathrm{\ell })+{\mathrm{\Xi }}_G^Y(\mathrm{\ell }))$, and then use the polymer sampling algorithm of Lemma 15 to approximately sample a configuration of compatible polymers $\mathrm{\Lambda }$ from $X$ (resp. $Y$), accurate to within total variation distance $ϵ/8$. Given the polymer configuration $\mathrm{\Lambda }$ we then independently select each vertex of $Y\setminus N(\mathrm{\Lambda })$ (resp. $X\setminus N(\mathrm{\Lambda })$) with probability $1/2$ and add these to the independent set. The distribution of the output is then within total variation distance $ϵ/2$ of ${\widehat{\mu }}_G$. See the sampling algorithm of [31] for details on the calculation of this bound. ∎

6. An algorithm for general regular bipartite graphs: Proof of Theorem 3

In this section we prove Theorem 3, giving an algorithm that, for any constant $c>0$, returns an $n^{-c}$-relative approximation for the number of independent sets in a general $d$-regular bipartite graph. As in the previous sections we let $G$ denote a $d$-regular graph on $2n$ vertices with vertex classes $X$ and $Y$. The algorithm proceeds by separating the contribution of expanding and non-expanding $2$-linked sets of $X$ to the independent set count. To estimate the the contribution from non-expanding components, we use a simple argument inspired by the container method (see Lemma 17 below). To estimate the contribution from expanding components, we appeal to the algorithm of Lemma 15.

We begin with the the following lemma which will allow us to group non-expanding components according to their closure. We say that a set $A\subseteq X$ is closed if $A=[A]$.

Lemma 17.

Let $A\subseteq X$ be a $2$-linked, closed, non-expanding set. Then there is a randomized $\mathrm{poly}(n)\cdot {ϵ}^{-2}\ln (1/\delta )\cdot 2^{O\left(\frac{|A|{\log }^{2}d}{d}\right)}$-time algorithm that outputs an $ϵ$-relative approximation to the number of $2$-linked $B\subseteq A$ such that $N(B)=N(A)$ with probability at least $1-\delta$.

Proof.

Let $W=N(A)$, $w=|W|$ and $a=|[A]|$. Let

$$𝒟:=\{B\subseteq A|N(B)=W\text{and}B\text{is}2\text{-linked}\}$$

be the set whose size we would like to estimate. By Corollary 10 there exists a set $A^{\prime }\in 𝒟$ of size at most

$$2\frac{a}{d}\ln d+2\frac{w}{d}+2(w-a)=O\left(\frac{a{\log }^{2}d}{d}\right).$$

It follows that

$$|𝒟|\ge 2^{a-O\left(\frac{a{\log }^{2}d}{d}\right)}.$$

Indeed every superset $B\supseteq A^{\prime }$ satisfies $N(B)=W$ and $B$ is $2$-linked. The first property is clear, since $N(B)\supseteq N(A^{\prime \prime })=W$. The second property holds because every vertex in $B$ is either in $A^{\prime }$ or at a distance $2$ from some vertex in $A^{\prime }$, which is itself $2$-linked. It follows that $|𝒟|$ can be estimated to relative error $ϵ$ by sampling

$$\frac{1}{{ϵ}^2}\ln (1/\delta )\cdot 2^{O\left(\frac{a{\log }^{2}d}{d}\right)}$$

subsets of $A$. ∎

The algorithm

For a closed, $2$-linked subset $A\subseteq X$, let us denote

$$𝒟(A):=\mathrm{\#}\{B\subseteq A|B\text{is}2\text{-linked},N(B)=N(A)\}.$$

We now define an algorithm with inputs a graph $G$ on $n$ vertices and an accuracy parameter $ϵ>0$ as follows. Let $L:=\lceil \frac{d}{2{\log }^{2}d}\log (2n/ϵ)\rceil$. If $d\le \sqrt{n}$, the algorithm is as follows:

1. List all vectors $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$ of positive integers such that $\mathrm{\ell }\le n/d$ and $\sum a_i\le n$.

2. For each vector $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$ from Step 1, list all sets $\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$ such that the $N(A_i)$’s are pairwise disjoint and $A_i\in {𝒢}^{\prime }(v_i,a_i)$ for some $v_i\in X$ for each $i$.

3. For each set $\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$ from Step 2, compute $\widetilde{𝒟}(A_i)$, which is a $(ϵ/2n)$-relative approximation to $𝒟(A_i)$ using Lemma 17, setting $\delta =(1/3)\cdot 2^{-n^2}$ for all $i$.

4. For each set $A=\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$ from Step 2, let $Y_A=Y\setminus N({\cup }_{i=1}^{\mathrm{\ell }}{A}_i)$, $X_A=X\setminus N^2({\cup }_{i=1}^{\mathrm{\ell }}{A}_i)$, $G_A=G[X_A\cup Y_A]$ and compute ${\mathrm{\Xi }}_{G_A}^{X_A}(L)$.

5. Output

   $$\sum _{\mathrm{\ell }=0}^{n/d}\sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}\left(\prod _{i=1}^{\mathrm{\ell }}\widetilde{𝒟}(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\mathrm{\Xi }}_{G_A}^{X_A}(L)\right).$$

If $d>\sqrt{n}$, the algorithm is to run Steps 1-3 above and output

(25) ${\displaystyle \sum _{\mathrm{\ell }=0}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}\widetilde{𝒟}(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\right).$

Proof of Theorem 3

We first prove the correctness of the algorithm: for any $c>0$ and $ϵ=n^{-c}$, the output is an an $ϵ$-relative approximation to $i(G)$. As before we let $X,Y$ denote the vertex classes of $G$. Suppose first that $d\le \sqrt{n}$. We then have

$i(G)$ $=2^{|Y|}\cdot {\displaystyle \sum _{t=0}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_t\text{compatible}\\ A_{i}2\text{-linked}\forall i\end{array}}}\left({\displaystyle \prod _{i=1}^t}{2}^{-N(A_i)}\right)$

$=2^{|Y|}\cdot {\displaystyle \sum _{t=0}^{n/d}}{\displaystyle \sum _{\mathrm{\ell }=0}^t}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding},\\ 2\text{-linked}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}{2}^{-N(A_i)}\cdot {\displaystyle \sum _{\begin{array}{c}{A}_{\mathrm{\ell }+1},\mathrm{\dots },A_t\\ \subseteq X\setminus N^2({\cup }_{j=1}^{\mathrm{\ell }}{A}_j)\\ \text{compatible}\\ \forall i{A}_i\text{expanding},\\ 2\text{-linked}\end{array}}}{\displaystyle \prod _{i=\mathrm{\ell }+1}^t}{2}^{-N(A_i)}\right)$

$=2^{|Y|}\cdot {\displaystyle \sum _{t=0}^{n/d}}{\displaystyle \sum _{\mathrm{\ell }=0}^t}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}{\displaystyle \sum _{\begin{array}{c}{B}_1,\mathrm{\dots },B_{\mathrm{\ell }}\\ \forall i,B_i\subseteq A_i,\\ N(B_i)=N(A_i),\\ B_{i}2\text{-linked}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}{2}^{-N(A_i)}\cdot {\displaystyle \sum _{\begin{array}{c}{A}_{\mathrm{\ell }+1},\mathrm{\dots },A_t\\ \subseteq X\setminus N^2({\cup }_{j=1}^{\mathrm{\ell }}{A}_j)\\ \text{compatible}\\ \forall i{A}_i\text{expanding},\\ 2\text{-linked}\end{array}}}{\displaystyle \prod _{i=\mathrm{\ell }+1}^t}{2}^{-N(A_i)}\right)$

$={\displaystyle \sum _{\mathrm{\ell }=1}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}{\displaystyle \sum _{\begin{array}{c}{B}_1,\mathrm{\dots },B_{\mathrm{\ell }}\\ \forall i,B_i\subseteq A_i,\\ N(B_i)=N(A_i),\\ B_{i}2\text{-linked}\end{array}}}\left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\displaystyle \sum _{t=1}^{n/d-\mathrm{\ell }}}{\displaystyle \sum _{\begin{array}{c}{A}_1^{\prime },\mathrm{\dots },A_t^{\prime }\\ \subseteq X\setminus N^2({\cup }_{j=1}^{\mathrm{\ell }}{A}_j)\\ \text{compatible}\\ \forall i{A}_i^{\prime }\text{expanding},\\ 2\text{-linked}\end{array}}}{\displaystyle \prod _{i=1}^t}{2}^{-N(A_i^{\prime })}\right)$

$={\displaystyle \sum _{\mathrm{\ell }=1}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}𝒟(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\mathrm{\Xi }}_{G_A}^{X_A}\right)$

$=(1\pm ϵ){\displaystyle \sum _{\mathrm{\ell }=1}^{n/d}}{\displaystyle \sum _{\begin{array}{c}{A}_1,\mathrm{\dots },A_{\mathrm{\ell }}\text{compatible}\\ \forall i,A_i\text{non-expanding}\\ 2\text{-linked, closed}\end{array}}}\left({\displaystyle \prod _{i=1}^{\mathrm{\ell }}}\widetilde{𝒟}(A_i)\right)\cdot \left(2^{|Y|-{\sum }_{i=1}^{\mathrm{\ell }}N(A_i)}\cdot {\mathrm{\Xi }}_{G_A}^{X_A}(L)\right).$

For the last equality we used that by Remark 1, we may apply Lemma 13 to $G_A$, and so ${\mathrm{\Xi }}_{G_A}^{X_A}(L)$ is an $ϵ$-relative approximation to ${\mathrm{\Xi }}_{G_A}^{X_A}$. Observe that there are at most $2^{n^2}$ many choices of nonexpanding $A_1,\mathrm{\dots },A_{\mathrm{\ell }}$. So by union bounding over all these choices, the last summation is exactly what the algorithm outputs with probability at least $1-\delta \cdot 2^{n^2}=2/3$, we have the required approximation guarantee. If $d\ge \sqrt{n}$, then we note that since the polymers of $G_A$ are a subset of the the polymers of $G$, we have by (17) that $\ln {\mathrm{\Xi }}_{G_A}^{X_A}\le \ln {\mathrm{\Xi }}_G^X\le 2^{-\mathrm{\Omega }({\log }^{2}n)}$. It follows that $1$ is trivially an $ϵ$-relative approximation to ${\mathrm{\Xi }}_{G_A}^{X_A}$ (recall that $ϵ=n^{-c}$) and so (25) is an $ϵ$-relative approximation to $i(G)$.

We now show that if $ϵ=n^{-c}$, with $c>0$ fixed, the above algorithm runs in time $2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$. We consider the algorithm step by step.

Step 1. For $\mathrm{\ell }\le n/d$, and $k\le n$ the number of vectors $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$ of positive integers such that $\sum a_i=k$ (i.e. the number of ordered partitions of $k$ with $\mathrm{\ell }$ parts) is

$$\left(\genfrac{}{}{0pt}{}{k-1}{\mathrm{\ell }-1}\right)\le \left(\genfrac{}{}{0pt}{}{n}{n/d}\right)=2^{O\left(\frac{\log d}{d}n\right)}.$$

Moreover, it is clear that the set of all such partitions can be listed in time $2^{O\left(\frac{\log d}{d}n\right)}$ and so Step 1 takes time $2^{O\left(\frac{\log d}{d}n\right)}$.

Step 2. Let $(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$ be a vector of positive integers such that $\mathrm{\ell }\le n/d$ and $\sum a_i\le n$. We first list all tuples vertices $\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}\subset X$ which takes time $\left(\genfrac{}{}{0pt}{}{n}{\mathrm{\ell }}\right)=2^{O\left(\frac{\log d}{d}n\right)}$. For each $\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}$, we then appeal to Lemma 5 to output the tuple $({𝒢}^{\prime }(v_1,a_1),\mathrm{\dots },{𝒢}^{\prime }(v_{\mathrm{\ell }},a_{\mathrm{\ell }}))$ in time $2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$. We note that by Lemma 5

$$|{𝒢}^{\prime }(v_1,a_1)\times \mathrm{\dots }\times {𝒢}^{\prime }(v_{\mathrm{\ell }},a_{\mathrm{\ell }})|\le \prod _{i=1}^{\mathrm{\ell }}{2}^{O\left(\frac{{\log }^{3}d}{d}{a}_i\right)}=2^{O\left(\frac{{\log }^{3}d}{d}n\right)}.$$

We may therefore check each element of ${𝒢}^{\prime }(v_1,a_1)\times \mathrm{\dots }\times {𝒢}^{\prime }(v_{\mathrm{\ell }},a_{\mathrm{\ell }})$ to see if it satisfies the required conditions and output the desired list in time $2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$.

Step 3. Given a set $\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$ from Step 2, we use Lemma 17 to compute an $ϵ/n$-relative approximation $\widetilde{𝒟}(A_i)$ to $𝒟(A_i)$ for all $i$. This takes time

$${(ϵ/n)}^{-2}\ln (1/\delta )2^{O\left(\frac{{\log }^{2}d}{d}n\right)}=2^{O\left(\frac{{\log }^{2}d}{d}n\right)}$$

where we recall that $ϵ=n^{-C}$ and $\delta =(1/3)\cdot 2^{-n^2}$.

Step 4. If , then given any set $A=\{A_1,\mathrm{\dots },A_{\mathrm{\ell }}\}$ from Step 2, we may compute ${\mathrm{\Xi }}_{G_A}^{X_A}(L)$ in time ${(n/ϵ)}^{O(d)}=2^{O\left(\frac{{\log }^{2}d}{d}n\right)}$ by the algorithm in Section 4 restricted to polymers of $G_A$. If $d\ge \sqrt{n}$, we skip Step 4.

We conclude that the algorithm takes time $2^{O\left(\frac{{\log }^{3}d}{d}n\right)}$ in total.

7. Weighted independent sets: proof of Theorem 2

The proof of Theorem 2 will follow the same lines as that of Theorem 1, with the main difference being that polymer weights will now be $w_{\gamma }=\frac{{\lambda }^{|\gamma |}}{{(1+\lambda )}^{|N(\gamma )|}}$, generalizing the $\lambda =1$ case of Theorem 1.

We assume throughout this section that $G$ is a $d$-regular, bipartite $\alpha$-expander with bipartition $X,Y$ of size $n$ each.

Define a polymer model with polymers consisting of the small $2$-linked, subsets of $X$ (resp. $Y$) with two polymers compatible if their union is not $2$-linked (recall that $\gamma \subset X$ is small if $|[\gamma ]|\le n/2$). The weight of a polymer $\gamma$ is $w_{\gamma }=\frac{{\lambda }^{|\gamma |}}{{(1+\lambda )}^{|N(\gamma )|}}$. Let ${\mathrm{\Xi }}_G^X(\lambda )$ be the polymer model partition function and ${\nu }_{G,\lambda }^X$ be the corresponding Gibbs measure on collections of compatible polymers.

Theorem 2 follows from the following two lemmas. Lemma 18 below is the analogue of Lemma 15 and Lemma 19 is the analogue of Lemma 16.

Lemma 18.

For every $\alpha >0$, there exists $C_2>0$ so that if $\lambda \ge \frac{C_2\log d}{d^{1/4}}$ then there is an FPTAS to compute ${\mathrm{\Xi }}_G^X(\lambda )$ and ${\mathrm{\Xi }}_G^Y(\lambda )$ and a polynomial-time sampling scheme for ${\nu }_{G,\lambda }^X$ and ${\nu }_{G,\lambda }^Y$.

As in Section 5, we define a probability measure on independent sets as a mixture of measures derived from the two polymer models. Define the distribution ${\widehat{\nu }}_{G,\lambda }^X$ on $ℐ(G)$ as follows.

1. Sample a collection of compatible polymers $\mathrm{\Lambda }$ from the measure ${\nu }_{G,\lambda }^X$.

2. Set $I=J\cup {\bigcup }_{\gamma \in \mathrm{\Lambda }}\gamma$ where $J$ is a random subset of $Y\backslash {\bigcup }_{\gamma \in \mathrm{\Lambda }}N(\gamma )$ formed by including each vertex independently with probability $\lambda /(1+\lambda )$.

Define ${\widehat{\nu }}_{G,\lambda }^Y$ analogously and define the mixture

$${\widehat{\mu }}_{G,\lambda }=\frac{{\mathrm{\Xi }}_G^X(\lambda )}{{\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda )}{\widehat{\nu }}_{G,\lambda }^X+\frac{{\mathrm{\Xi }}_G^Y(\lambda )}{{\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda )}{\widehat{\nu }}_{G,\lambda }^Y.$$

Lemma 19.

For every $\alpha >0$, there exists $C_2>0$ so that if $\lambda \ge \frac{C_2\log d}{d^{1/4}}$ then for $n$ sufficiently large,

$${(1+\lambda )}^n\left({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda )\right)$$

is an $ϵ$-relative approximation to $Z_G(\lambda )$ and

where $ϵ=\exp (-\mathrm{\Omega }(n))$, with the implicit constant a function of $d$.

To prove Lemmas 18 and 19 we extend the estimates of Sections 3 and 4 to the more general case. The main graph container lemma comes from the paper of Galvin and Tetali [20]. Let us define

$${𝒲}_{\lambda }(v,a,w):=\sum _{\begin{array}{c}A\subset X\\ |[A]|\le n/2,\\ A\text{is}2\text{-linked}\\ |N(A)|=w\end{array}}{\lambda }^{|A|}{(1+\lambda )}^{-w},$$

and

$$\beta (\lambda ):=\frac{{\log }^2(1+\lambda )}{\log (1+\lambda )+\log (2d^5/\alpha )}.$$

We use the following lemma from [20].

Lemma 20.

There are constants $c_4$ and $c_5$ such that the following holds: Let $G$ be a bipartite $\alpha$-expander and suppose $\lambda >0$. If $\beta (\lambda )$ satisfies

$$\beta (\lambda )\ge c_4\max \{\frac{\log (d^5/\alpha )}{\sqrt{d}},\frac{2{\log }^{2}d}{\alpha d}\}.$$

Then

$${𝒲}_{\lambda }(v,a,w)\le 2^{-c_5(w-a)\beta (\lambda )}.$$

The hypothesis of the above lemma says that $\alpha \beta (\lambda )\ge 2c_4\cdot \frac{{\log }^{2}d}{d}$. However, in our application, we will also assume that that $\beta (\lambda )$ is also large enough to ensure

(26) $$\alpha \beta (\lambda )\ge \frac{4000}{c_5}\cdot \frac{{\log }^{2}d}{d}.$$

This may be done by assuming that $\lambda \ge \frac{C\log d}{d^{1/4}}$ for a large enough constant $C_2$.

We now prove Lemma 18.

Proof of Lemma 18.

As in the proof of Lemma 15, the FPTAS and polynomial-time sampling scheme will follow from verifying the Koteckỳ-Preiss condition for the polymer model.

The polymer model satisfies (11) with $f(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|\gamma |}{8}$ and $g(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|N(\gamma )|}{8}$ as shown by the following computation.

${\displaystyle \sum _{{\gamma }^{\prime }\sim ̸\gamma }}{w}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$ $\le {\displaystyle \sum _{v\in \gamma }}{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{w}_{{\gamma }^{\prime }}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{{\gamma }^{\prime }\sim ̸v}}{\lambda }^{|\gamma |}{(1+\lambda )}^{-|N({\gamma }^{\prime })|}{e}^{f({\gamma }^{\prime })+g({\gamma }^{\prime })}$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}\left({\displaystyle \sum _{t\ge (\alpha /2)w}}{𝒲}_{\lambda }(v,w-t,w)\cdot e^{c_5\alpha \ln 2\frac{\beta (\lambda )w}{4}}\right)$

$\le |\gamma |\cdot \underset{v\in \gamma }{\max }{\displaystyle \sum _{w\ge d}}{e}^{c_5\alpha \ln 2\frac{\beta (\lambda )w}{4}}\left({\displaystyle \sum _{t\ge (\alpha /2)w}}{𝒲}_{\lambda }(v,w-t,w)\right)$

$\le |\gamma |{\displaystyle \sum _{w\ge d}}{2}^{c_5\alpha \frac{\beta (\lambda )w}{4}}\left({\displaystyle \sum _{t\ge (\alpha /2)w}}{2}^{-c_5\beta (\lambda )t}\right)$

$\le 2d|\gamma |{\displaystyle \sum _{w\ge d}}{2}^{c_5\alpha \frac{\beta (\lambda )w}{4}}{2}^{-c_5\alpha \frac{\beta (\lambda )w}{2}}$

$\le 4d^2|\gamma |2^{-c_5\alpha \frac{\beta (\lambda )d}{4}}$

$\le 4d^2|\gamma |2^{-500{\log }^{2}d}\cdot 2^{-c_5\alpha \frac{\beta (\lambda )d}{8}}$

$\le |\gamma |\cdot c_5\alpha {\displaystyle \frac{\beta (\lambda )}{16}}.$

The last inequality follows because for $d\ge 3$, we have and for any $x,y>0$, we have $2^{-x}\le \frac{x}{2y}$ if $x\ge 500{\log }^{2}y$.

Define ${\mathrm{\Xi }}_G^X(\mathrm{\ell },\lambda )$ to be the exponential of the truncated cluster expansion as in (15). By the calculation of Lemma 13, we have for every $\mathrm{\ell }\ge 1$,

(27) $$\left|\ln {\mathrm{\Xi }}_G^X(\lambda )-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell },\lambda )\right|\le n\cdot 2^{-500\frac{{\log }^{2}d\cdot \mathrm{\ell }}{d}}.$$

In particular, if $\mathrm{\ell }\ge \frac{d}{1000{\log }^{2}d}\log (n/ϵ)$, then

$$\left|\ln {\mathrm{\Xi }}_G^X-\ln {\mathrm{\Xi }}_G^X(\mathrm{\ell },\lambda )\right|\le ϵ.\mathit{∎}$$

We now prove Lemma 19.

Proof of Lemma 19.

Consider a modified polymer model with weights ${\tilde{w}}_{\gamma }(\lambda )={\lambda }^{|\gamma |}{(1+\lambda )}^{-|N(\gamma )|}{2}^{c_5\alpha \frac{\beta (\lambda )}{16}}$. The calculation in the proof of Lemma 18 shows that the modified polymer model with weights ${\tilde{w}}_{\gamma }(\lambda )$ satisfies (11) with $f(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|\gamma |}{16}$ and $g(\gamma )=c_5\alpha \ln 2\frac{\beta (\lambda )|N(\gamma )|}{8}$.

Let ${\tilde{\mathrm{\Xi }}}_G^X(\lambda )$ denote the modified polymer model partition function as in (13). We then have

$$\ln {\tilde{\mathrm{\Xi }}}_G^X(\lambda )-\ln {\mathrm{\Xi }}_G^X(\lambda )=\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }$$

for $\zeta =c_5\alpha \ln 2\frac{\beta (\lambda )}{16}$. Summing (14) over all $v$, and using the fact that $|N(\gamma )|\ge d$ for every $\gamma$, we get (as in (17))

(28) $$\ln {\tilde{\mathrm{\Xi }}}_G^X\le \sum _v\sum _{\begin{array}{c}\mathrm{\Gamma }\in 𝒞(G)\\ \mathrm{\Gamma }\ni v\end{array}}\left|\varphi (\mathrm{\Gamma })\prod _{\gamma \in \mathrm{\Gamma }}{\tilde{w}}_{\gamma }\right|\le n\cdot 2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}.$$

Therefore, we have

$\ln 𝐄e^{\zeta \cdot \Vert 𝚲\Vert }\le \ln {\tilde{\mathrm{\Xi }}}_G^X\le n\cdot 2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}.$

Fix any $\delta \ge \frac{10}{\sqrt{d}}$. By Markov’s inequality, we have

$\mathbb{P}(\Vert 𝚲\Vert \ge \delta n)$ $\le \exp \left(-\zeta \delta n+n\cdot 2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}\right)$

$\le 2^{-c_5\alpha \frac{\beta (\lambda )}{32}\cdot \delta n}$

(29) $\le 2^{-\frac{100{\log }^{2}d}{d}\cdot \delta n},$

where the penultimate inequality follows because for any $x,y>0$, we have $2^{-x\cdot y}\le \frac{x}{2\sqrt{y}}$ if $x\ge 500{\log }^{2}y$, and therefore

$$2^{-c_5\alpha \beta (\lambda )\frac{d}{8}}\le \frac{c_5\alpha \beta (\lambda )}{16\sqrt{d}}\le \frac{\zeta \delta }{2}.$$

The final inequality (7) follows from (26).

As in the proof of Lemma 16, let ${ℐ}_X=\{I\in ℐ:{\nu }_{G,\lambda }^X(I)>0\}$ i.e.  the set of all $I$ such that each $2$-linked component of $I\cap X$ is small. For $\delta >0$, let ${ℐ}_X^{\delta }=\{I\in {ℐ}_X:|I\cap X|\le \delta n\}$ and define ${ℐ}_Y$, ${ℐ}_Y^{\delta }$ similarly. As in Lemma 16, $ℐ={ℐ}_X\cup {ℐ}_Y$ and so

(30) $Z_G(\lambda )={\displaystyle \sum _{I\in {ℐ}_X}}{\lambda }^{|I|}+{\displaystyle \sum _{I\in {ℐ}_Y}}{\lambda }^{|I|}-{\displaystyle \sum _{I\in {ℐ}_X\cap {ℐ}_Y}}{\lambda }^{|I|}={(1+\lambda )}^n({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda ))-{\displaystyle \sum _{I\in {ℐ}_X\cap {ℐ}_Y}}{\lambda }^{|I|}.$

Now, let $I$ be a random independent set chosen from the distribution ${\nu }_{G,\lambda }^X$. It follows from (7) that for $\delta \ge \frac{10}{\sqrt{d}}$,

(31) $$\mathbb{P}(|I\cap X|>\delta n)=\sum _{I\in {ℐ}_X\backslash {ℐ}_X^{\delta }}\frac{{\lambda }^{|I|}}{{(1+\lambda )}^n{\mathrm{\Xi }}_G^X(\lambda )}\le 2^{-\frac{100{\log }^{2}d}{d}\cdot \delta n}.$$

Furthermore, we have

${\displaystyle \sum _{I\in {ℐ}_X^{\delta }\cap {ℐ}_Y^{\delta }}}{\displaystyle \frac{{\lambda }^{|I|}}{{(1+\lambda )}^n{\mathrm{\Xi }}_G^X(\lambda )}}$ $\le {\displaystyle \frac{{\sum }_{i,j\le \delta n}\left(\genfrac{}{}{0pt}{}{n}{i}\right)\left(\genfrac{}{}{0pt}{}{n}{j}\right){\lambda }^{i+j}}{{(1+\lambda )}^n}}$

$={\displaystyle \frac{{\left({\sum }_{i\le \delta n}\left(\genfrac{}{}{0pt}{}{n}{i}\right){\lambda }^i\right)}^2}{{(1+\lambda )}^n}}$

$={(1+\lambda )}^n\mathbb{P}{\left(\mathrm{Bin}(n,{\displaystyle \frac{\lambda }{1+\lambda }})\le \delta n\right)}^2$

This quantity can be made to be at most $e^{-\frac{\delta n}{16}}$ for $\delta =\frac{\lambda }{100(1+\lambda )}$. We note that $\delta \ge \frac{C{\log }^{2}d}{d^{1/4}}\ge \frac{10}{\sqrt{d}}$ for a large enough $C$, and so

${\displaystyle \sum _{I\in {ℐ}_X\cap {ℐ}_Y}}{\lambda }^{|I|}$ $\le {\displaystyle \sum _{I\in {ℐ}_X\backslash {ℐ}_X^{\delta }}}{\lambda }^{|I|}+{\displaystyle \sum _{I\in {ℐ}_Y\backslash {ℐ}_Y^{\delta }}}{\lambda }^{|I|}+{\displaystyle \sum _{I\in {ℐ}_X^{\delta }\cap {ℐ}_Y^{\delta }}}{\lambda }^{|I|}$

$\le {(1+\lambda )}^n({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda ))e^{-\mathrm{\Omega }(n)}.$

By (30), we conclude that

$\left|{\displaystyle \frac{Z_G(\lambda )}{{(1+\lambda )}^n({\mathrm{\Xi }}_G^X(\lambda )+{\mathrm{\Xi }}_G^Y(\lambda ))}}-1\right|=e^{-\mathrm{\Omega }(n)}.$

The bound on total variation distance follows in the same manner as in the proof of Lemma 16. ∎