# Enumerating independent sets in Abelian Cayley graphs

Aditya Potukuchi  and  Liana Yepremyan

###### Abstract.

We show that any connected Cayley graph $\Gamma$ on an Abelian group of order
$2n$ and degree $\tilde{\Omega}(\log n)$ has at most $2^{n+1}(1+o(1))$
independent sets. This bound is tight up to to the $o(1)$ term when $\Gamma$
is bipartite. Our proof is based on Sapozhenko’s graph container method and
uses the Plünnecke-Rusza-Petridis inequality from additive combinatorics.

Department of Mathematics, Statistics, and Computer Science, University of
Illinois at Chicago, 851 S Morgan St, Chicago, IL, USA. Email:
<EMAIL_ADDRESS>Research supported in part by NSF grant CCF-1934915.

Department of Mathematics, London School of Economics, London WC2A 2AE, UK.
Email<EMAIL_ADDRESS>Research supported by Marie Sklodowska Curie
Global Fellowship, H2020-MSCA-IF-2018:846304.

##  1\. Introduction

An _independent set_ in a graph is a set of vertices with no two having an
edge between them. For a graph $G$, let $i(G)$ denote the number of
independent sets in a graph $G$. The study of $i(G)$ in a $d$-regular graph on
a given number of vertices goes back to Granville, who was interested in this
quantity because of connections to combinatorial group theory. In 1988 at a
Number Theory Conference in Banff, he suggested that if $G$ is a $d$-regular
graph on $2n$ vertices then $i(G)\leq 2^{(1+o(1))n}$, where the $o(1)$ term
goes to zero as $d$ goes to infinity. Note that this is tight up to the $o(1)$
term since a bipartite $d$-regular graph has at least $2^{n+1}-1$ independent
sets, just by counting all subsets of both sides in the bipartition. Alon
[Alo91] settled this conjecture and proved that $i(G)\leq
2^{\left(1+O(d^{-0.1})\right)n}$. He also suggested that the right bound is
$(2^{d+1}-1)^{n/d}$, achieved by a disjoint union of $n/d$ complete bipartite
graphs $K_{d,d}$, whenever $d$ divides $n$. This was later also conjectured by
Kahn [Kah01] and proved for bipartite graphs. The full conjecture was proved
by Zhao [Zha10] who showed that the bound for general $d$-regular graphs
follows from the bipartite version.

For irregular graphs, Kahn conjectured [Kah01] that a similar bound must hold,
more precisely, $i(G)\leq\prod_{uv\in
E(G)}i(K_{d_{G}(u),d_{G}(v)})^{1/d_{G}(u)d_{G}(v)},$ and equality holds when
$G$ is a union of vertex disjoint complete bipartite graphs with appropriate
sizes. It was first proved to be true for all graphs of maximum degree at most
$5$ by Galvin and Zhao [GZ11] with computer assistance. The full conjecture
was recently proved by Sah, Sawhney, Stoner and Zhao [SSSZ19] using a Hölder-
type inequality.

Back to $d$-regular graphs, the results of Kahn and Zhao show that for any
$d$-regular graph on $2n$ vertices, $i(G)\leq 2^{n+\frac{n}{d}+o(1)}$, with
the extremal example being a union of complete bipartite graphs. So, a natural
question is weather $i(G)$ is much smaller if we require the extremal graph to
have higher edge-connectivity. More specifically, can the $n/d$ term be
significantly reduced? The answer is no, and in Appendix A, we describe the
construction of a $d$-regular graph on $2n$ vertices that is at least $(d-1)$
edge-connected and has at least $2^{n+\Omega(n/d)}$ independent sets.

However, if we require the extremal graph to have some stronger connectivity
properties, such as being an expander, then more is known. For example, for
the $d$-dimensional discrete hypercube, $Q_{d}$, that is the graph on vertex
set $\\{0,1\\}^{d}$ where two vertices are adjacent if they differ in exactly
one coordinate, Korshunov and Sapozhenko [KS83] proved that
$i(Q_{d})=2\sqrt{e}(1+o(1))\cdot 2^{2^{d-1}}$, when $d\rightarrow\infty$.
Sapozhenko [Sap87] using the container method gave a simplified proof of this
result (see [Gal19] for a beautiful exposition of this method). The ideas
introduced in this method have proved to be extremely useful, finding a number
of applications in combinatorics. upper bound on phase transition on the
hardcore model on $\mathbb{Z}^{d}$ [GK04], lower bounds for mixing for Glauber
dynamics for hardcore model in bipartite regular graphs [GT06], enumerating
uniform intersecting set systems [BGLW21], enumerating $q$-colorings of the
discrete torus [Gal03], [KJ20], [JK20], phase coexistence of the $3$-coloring
model in $\mathbb{Z}^{d}$ [GKRS15], more detailed descriptions of independent
sets in the hypercube [BGL21], [Gal10], [JP20], [JPP21b], [KP19], [Par21], and
faster algorithms for approximately counting independent sets in bipartite
graphs [JPP21a].

##  2\. Our results

The motivation of this paper is to consider the question of determining $i(G)$
for families of graphs with some underlying structure. A natural example are
Cayley graphs. Let $\mathcal{F}$ denote a finite Abelian group. An _Abelian
Cayley graph_ for $\mathcal{F}$ with generator set $D\subseteq\mathcal{F}$, is
a graph whose vertices are given by the elements of $\mathcal{F}$, and
(directed) edges $\\{(u,u+x)~{}|~{}x\in D\\}$. If $D=-D$, then we may assume
the graph is undirected. Our main result is the following.

######  Theorem 1.

Let $\Gamma$ be a connected Abelian Cayley graph on $2n$ vertices and degree
$\Omega(\log n\cdot(\log\log{n})^{11})$. Then,

$i(\Gamma)\leq 2^{n+1}\cdot\left(1+o(1)\right).$

This is asymptotically tight whenever $\Gamma$ is bipartite. In this case, the
theorem says that most independent sets come from subsets of either part.

Apart from exhibiting this property in Cayley graphs, extending the
aforementioned techniques to graphs where the guarantees in typical uses of
container method are unavailable seems to be of independent interest.

In Theorem 1 make no attempt to optimize the lower bound on $d$ for the
conclusion of the Theorem to hold. However, we are unable to reduce this to
$\Omega(\log n)$, which we believe is the truth. In fact, we conjecture:

######  Conjecture.

Fix $\epsilon>0$ and let $\Gamma$ be a connected Abelian Cayley graph on $2n$
vertices and degree $(2+\epsilon)\log n$. Then,

$i(\Gamma)\leq 2^{n+1}\cdot(1+o(1)).$

This conjecture, if true, would be optimal. The natural guess for the tight
case is the example described in Appendix B. We use the looser bound of
$\tilde{\Omega}(\log n)$ in a couple of places in the proof, but we believe
that the main bottleneck is in Lemma 13.

Let us set up some basic notation for the proof. In what follows, the notation
is focused on bipartite graphs. The reason is that in the proof of Theorem 1,
that the main part is the case when $\Gamma$ is bipartite. The non-bipartite
case is handled using a theorem of Zhao [Zha10].

Let us now restrict ourselves to the case when $\Gamma$ is bipartite, and use
$(X,Y)$ to denote the bipartition, where $|X|=|Y|=n$. Since the graph is
connected and $|D|$-regular, for any $S\subseteq X$, we have $|N(S)|\geq|S|$
with equality holding if and only if $S=X$. One can verify that the graph is
connected if and only if the set $D$ is a _generating set_ of the group, i.e.,
every element in $\mathcal{F}$ can be written as a sum of elements from $D$.
Throughout the paper, we use sumset notation: For $A,B\subseteq\mathcal{F}$,
we use $A+B$ to denote the set $\\{a+b~{}|~{}a\in A,~{}b\in B\\}$, and
$2A=A+A$. Thus the set of neighbors of a set $A$, $N_{\Gamma}(A)$ is just the
set $A+D$.

Let $\Gamma^{2}$ denote the square graph of $\Gamma$, i.e.,
$V(\Gamma^{2})=V(\Gamma)$ and $u\sim_{\Gamma^{2}}v$ if and only if
$N_{\Gamma}(u)\cap N_{\Gamma}(v)\neq\emptyset$. For a subset $A\subset X$, we
use $G$ to denote $N(A)$. We say that $A$ is $2$-linked if $A$ is connected in
$\Gamma^{2}$. Let us define $[A]:=\\{u\in X~{}|~{}N(u)\subseteq G\\}$ to be
the _closure_ of $A$. If $|[A]|\leq n/2$, we call $A$ _small_. Let
$\mathcal{G}(a,g)$ denote the number of small $2$-linked sets $A$ such that
$|[A]|=a$, and $|G|=g$. Let us define $t=g-a$. The main lemma in the proof is
the following:

######  Lemma 2.

If $\Gamma$ is an bipartite connected Cayley graph with bipartition $(X,Y)$
with $|X|=|Y|=n$, and generator set $D$, such that

  1. (1)

$\frac{|D|}{\log^{8}|D|}=\Omega(\log n)$,

  2. (2)

$|D|\leq n^{1/3}$, and

  3. (3)

$|2D|\geq|D|\log^{3}|D|$

Then we have for every $a,g$

$|\mathcal{G}(a,g)|\leq 2^{g-\Omega\left({t}\right)}.$

### Remark

For comparison, the graph container lemma of Sapozhenko, improved by Kahn and
Park [KP19] says the following:

######  Lemma 3.

If $\Gamma$ is a $d$-regular bipartite graph with $d\gg\log n$ and bipartition
$(X,Y)$ such that

  1. (1)

Every two vertices have at most $O(1)$ common neighbors

  2. (2)

For every small set $A\subset X$, we have that
$t\geq\Omega\left(g\frac{\log^{2}d}{d^{2}}\right)$,

Then we have for every $a,g$

$|\mathcal{G}(a,g)|\leq 2^{g-\Omega\left({t}\right)}.$

Condition $2$ imposes certain expansion conditions on the graph, which is not
true in general for Cayley graphs. We overcome this using tools from additive
combinatorics.

###  2.1. Organization

In section 3, we state some results from additive combinatorics that are
useful. The end of this section contains the proof of Theorem 1 using Lemma 2.
Section 4 is dedicated to the proof of Lemma 2. The proof of Lemma 2, using
Lemma 13, Lemma 17, and Lemma 18 is given in Subsection 4.1. Some preliminary
lemmas are proved in Subsection 4.2, after which, Subsections 4.3, 4.4, and
4.5 are dedicated to the proofs of Lemmas 13, 17, and 18 respectively.

##  3\. Preliminaries

Here, we will state some results from additive combinatorics that will be
useful to us. The first is the Plünnecke-Rusza-Petridis inequality [Pl70],
[Ruz89], [Ruz90], [Pet14]:

######  Theorem 4 (Plünnecke-Ruzsa-Petridis Inequality).

Let $M,D\subset\mathcal{F}$ such that $|M+D|=\alpha|M|$. Then for any
nonnegative integer $j$, there is a subset $M^{\prime}\subseteq M$ such that
$|M^{\prime}+jD|\leq\alpha^{j}|M^{\prime}|$.

We will also need a theorem by Olson [Ols84] which is a Cauchy-Davenport type
theorem for general Abelian groups.

######  Theorem 5 ([Ols84]).

Let $M,N\subseteq\mathcal{F}$ such that $0\in N$. Then either $M+2N=M+N$ or
$|M+N|\geq|M|+|N|/2$.

We can easily derive the following from Theorem 5 by applying it for
$N^{\prime}=N-a$, for some element $a\in N$ such that $0\in N^{\prime}$.

######  Corollary 6.

Let $M,N\subseteq\mathcal{F}$. Then either $|M+2N|=|M+N|$ or
$|M+N|\geq|M|+|N|/2$.

While the Plünnecke-Ruzsa-Petridis inequality as stated, gives no guarantee on
the size of the set $M^{\prime}$ (in the theorem statement), one may obtain
such a theorem through repeated applications of a general version of Theorem
4:

######  Theorem 7 ([GR09], part II, Theorem $1.7.3$).

Let $M,D,N\subset\mathcal{F}$ such that $|M|=m$, and let $1\leq j<h$ be
positive integers, with $\gamma:=h/j$. Let $|(M+jD)\setminus(N+(j-1)D)|=s$,
and $\ell<m$ be a positive integer. There is a subset $M^{\prime}\subseteq M$
such that $|M^{\prime}|>\ell$, and

$\displaystyle|(M^{\prime}+hD)\setminus(N+(h-1)D)|$
$\displaystyle\leq\frac{s^{\gamma}}{\gamma}\left(\frac{1}{(m-\ell)^{\gamma-1}}-\frac{1}{m^{\gamma-1}}\right)+\left(\frac{s}{m-\ell}\right)^{\gamma}\left(|M^{\prime}|-\ell\right).$

In fact, eventually, we will want a set $M^{\prime}\subseteq M$ such that each
$M^{\prime}+iD$ is small (see Lemma 21), which may be obtained by repeated
application of Theorem 7.

As mentioned before, we need the following theorem of Zhao [Zha10] which
allows to prove our main result just for bipartite graphs. Here, $\Gamma\times
K_{2}$ is a bipartite graph with vertex set $V(\Gamma)\times\\{1,2\\}$ and
(undirected) edge set
$\\{\\{(u,1)(v,2)\\},\\{(v,1),(u,2)\\}~{}|~{}\\{u,v\\}\in E(\Gamma)\\}$.

######  Theorem 8 ([Zha10]).

For any graph $\Gamma$, we have $i(\Gamma\times K_{2})\geq i(\Gamma)^{2}$.

We will use the following theorem, originally due to Lovász [Lov75] and Stein
[Ste74].

######  Theorem 9 ([Lov75], [Ste74]).

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

We will also use the following (see for e.g. [Knu98], p.396, Ex.11).

######  Proposition 10.

The number of rooted trees with maximum degree $d$ and $n$ internal vertices
is at most

$\frac{\binom{dn}{n}}{(d-1)n+1}\leq(ed)^{n}.$

We use $\log(\cdot)$ to denote $\log_{2}(\cdot)$. Finally, throughout the
proof, we assume that $n$ (and therefore $d$) is large enough.

###  3.1. Proof of Theorem 1 from Lemma 2

First, a sketch of the proof: Consider a bipartite Cayley graph $\Gamma$ with
bipartition $(X,Y)$ with $|X|=|Y|=n$. Every independent set of $\Gamma$ is a
subset $A\sqcup B$ such that $A\subseteq X$ and $B\subseteq Y\setminus N(A)$.
Moreover, observe that the independence number of $\Gamma$ is $n$ and so one
of $A$ or $B$ must have size at most $n/2$. Thus, the total number of
independent sets is at most

(1) $\sum_{\begin{subarray}{c}A\subset X\\\ |A|\leq
n/2\end{subarray}}2^{n-|N(A)|}+\sum_{\begin{subarray}{c}B\subset Y\\\ |B|\leq
n/2\end{subarray}}2^{n-|N(B)|}=2\cdot\sum_{\begin{subarray}{c}A\subset X\\\
|A|\leq n/2\end{subarray}}2^{n-|N(A)|}$

where the equality is due to symmetry. The goal is to show that

$\sum_{\begin{subarray}{c}A\subset X\\\ \emptyset\neq|A|\leq
n/2\end{subarray}}2^{n-|N(A)|}=o(2^{n+1}).$

So, the main point behind Lemma 2 is a way of quantifying the fact that there
are not too many sets $A$ for which $2^{-|N(A)|}$ is relatively large.

Henceforth, let $\Gamma$ be a bipartite Cayley graph over an Abelian group
$\mathcal{F}$ of order $2n$ and set of generators $D=-D$. We impose a couple
of constraints on $D$, namely

  1. (1)

$|D|\leq n^{1/3}$, and

  2. (2)

$|2D|\geq|D|\log^{3}|D|$.

We first show that these can be assumed w.l.o.g., when $d=\tilde{\Omega}(\log
n)$.

######  Proposition 11.

Let $D\subseteq\mathcal{F}$ such that $|D|\geq 10\log{n}(\log{\log{n}})^{k}$
for some fixed $k>0$. For any $0<\alpha\leq(\log{\log{n}})^{k}$, if
$|2D|\leq\alpha|D|$ then there is a $D^{\prime}\subset D$ such that

  1. (1)

$D^{\prime}=-D^{\prime}$

  2. (2)

$D^{\prime}$ is a generating set

  3. (3)

$|D^{\prime}|=\Theta\left(\frac{|D|}{\alpha}\right)$

  4. (4)

$|D^{\prime}+D^{\prime}|\geq\alpha|D^{\prime}|$.

###### Proof.

Set $p:=\frac{1}{15\alpha}$. Choose $P$ to be a $p$-random subset of $D$, and
$S\subseteq D$ be a minimal generating set of $\mathcal{F}$. Note that
$|S|\leq\log{n}$. Set

$D^{\prime}=P\cup-P\cup S\cup-S$

Property $(1)$ and $(2)$ easily follow from the definition of $D^{\prime}$. To
see that property $(3)$ holds, we use the Chernoff bound (Theorem $1.1$ in
[DP09]): A binomially distributed variable $X\sim\operatorname{Bin}(n,p)$ for
all $0<a\leq 3/2$ we have

$\mathbb{P}{[|X-\mathbf{E}[X]|\geq a\mathbf{E}[X]]}\leq
2e^{-\frac{a^{2}}{3}\mathbf{E}[X]}.$

Indeed, $\mathbb{E}[|P|]=p|D|=\frac{|D|}{15\alpha}$. By Chernoff’s bounds and
using that $|D|=\tilde{\Omega}(\log{n})$, we have that with high probability,
$\frac{|D|}{20\alpha}\leq|P|\leq\frac{|D|}{10\alpha}$.

Thus property (3) follows from the fact that
$|S|\leq\log{n}\leq\frac{|D|}{10\alpha}$. So we have, with high probability

(2) $\frac{|D|}{20\alpha}\leq|D^{\prime}|\leq\frac{2|D|}{5\alpha}$

.

For property $(4)$: For every $u\in D+D$, define

$R_{u}:=\left\\{\\{x,y\\}\subset D~{}|~{}x+y=u\right\\},$

i.e., the set of _representations_ of $u$ in $D+D$. Denote $r_{u}=|R_{u}|$.
Let

$D_{\ell}=\left\\{u\in D+D~{}|~{}r_{u}\geq\frac{|D|}{2\alpha}\right\\}.$

Using an averaging argument, we have that $|D_{\ell}|\geq|D|/2$. For $u\in
D^{\prime}+D^{\prime}$, define

$R_{u}^{\prime}:=\left\\{\\{x,y\\}\subset P~{}|~{}x+y=u\right\\}.$

and $r_{u}^{\prime}=|R_{u}^{\prime}|$. The main observation is that the
elements of $R_{u}$ are pairwise disjoint. Therefore, for each $u\in
D_{\ell}$, we have $\mathbb{P}(u\not\in
P+P)=\mathbb{P}(r^{\prime}_{u}=0)\leq(1-p^{2})^{r_{u}}\ll\frac{1}{|D|^{2}}$.
By the Union Bound, and using the fact that $|D_{\ell}|\leq|2D|\leq|D|^{2}$,
we have that with high probability, every $u\in D_{\ell}$ satisfies
$r^{\prime}_{u}=0$, therefore the following series of inequalities hold.

$|D^{\prime}+D^{\prime}|\geq|P+P|\geq|D_{\ell}|\geq|D|/2\geq\alpha|D^{\prime}|$

where the last inequality follows from (2). ∎

So if $|D|>n^{1/3}$, set $D^{\prime\prime}\subset D$ to be an arbitrary subset
such that that $D^{\prime\prime}=-D^{\prime\prime}$ and
$\frac{n^{1/3}}{2}\leq|D^{\prime}|\leq n^{1/3}$. Otherwise set
$D^{\prime\prime}=D$. Now if
$|2D^{\prime\prime}|\leq|D^{\prime\prime}|\log^{3}|D^{\prime\prime}|$, let
$D^{\prime}\subseteq D^{\prime\prime}$ be the subset guaranteed by Proposition
11. Otherwise, set $D^{\prime}=D^{\prime\prime}$. Now consider the Cayley
graph $\Gamma^{\prime}$ on $\mathcal{F}$ with the generator set
$D^{\prime}\subseteq D$. Since $\Gamma^{\prime}$ is a subgraph of $\Gamma$, we
have that $2^{n+1}\leq i(\Gamma^{\prime})\leq i(\Gamma)$. The first inequality
is because $X$ and $Y$ are both independent sets of $\Gamma$, each of size
$n$. Henceforth, at the cost of a factor of $\frac{1}{\log^{O(1)}|D|}$, we
shall assume that the generating set $D$ satisfies $|D|\leq n^{1/3}$ and
$|2D|\geq|D|\log^{3}|D|$. Theorem 1, therefore follows from

######  Theorem 12.

Let $\Gamma$ be a connected undirected Cayley graph on $2n$ vertices and
generating set $D$ such that

  1. (1)

$\frac{|D|}{\log^{8}|D|}=\Omega(\log n)$,

  2. (2)

$|D|\leq n^{1/3}$, and

  3. (3)

$|2D|\geq|D|\log^{3}|D|$.

Then,

$i(\Gamma)\leq 2^{n+1}\cdot(1+o(1)).$

###### Proof of Theorem 12.

We first prove the theorem for the case when $\Gamma$ be bipartite with
bipartition $(X,Y)$. Recall that we say a subset $A\subset X$ or $A\subset Y$
is _small_ if $|[A]|\leq n/2$. Let $I\in\mathcal{I}(\Gamma)$ be any
independent set. Since $|I|\leq n$, we must have that either $I\cap X$ or
$I\cap Y$ is small. Thus we have

$\displaystyle i(\Gamma)$ $\displaystyle\leq 2\sum_{A\subseteq
X,~{}\text{small}}2^{n-|N(A)|}$ $\displaystyle=2^{n+1}\sum_{A\subseteq
X,~{}\text{small}}2^{-|N(A)|}$ $\displaystyle\leq
2^{n+1}\sum_{k}\sum_{\begin{subarray}{c}A_{1},\ldots,A_{k}\subseteq X\\\
\text{small, }2-\text{linked}\end{subarray}}2^{-\sum_{i\leq k}|N(A_{i})|}$
$\displaystyle\leq
2^{n+1}\sum_{k}\frac{1}{k!}\left(\sum_{\begin{subarray}{c}A~{}\text{small,
}\\\ 2-\text{linked}\end{subarray}}2^{-|N(A)|}\right)^{k}$ $\displaystyle\leq
2^{n+1}\exp\left(\sum_{\begin{subarray}{c}A~{}\text{small, }\\\
2-\text{linked}\end{subarray}}2^{-|N(A)|}\right)$
$\displaystyle=2^{n+1}\exp\left(\sum_{\begin{subarray}{c}1\leq a\leq n/2\\\
d/2\leq t\leq n\end{subarray}}\sum_{\begin{subarray}{c}A~{}2-\text{linked}\\\
|[A]|=a,|N(A)|=g\end{subarray}}2^{-g}\right)$
$\displaystyle=2^{n+1}\exp\left(\sum_{\begin{subarray}{c}1\leq a\leq n/2\\\
d/2\leq t\leq n\end{subarray}}|\mathcal{G}(a,g)|2^{-g}\right)$
$\displaystyle\leq 2^{n+1}\exp\left(n\cdot\sum_{d/2\leq
t}2^{-\Omega(t)}\right)$ $\displaystyle\leq 2^{n+1}\exp\left(n\cdot
2^{-\Omega(d)}\right)$ $\displaystyle=2^{n+1}(1+o(1)).$

Here, the second last inequality is by Lemma 2. The last inequality is because
Theorem 6 gives that for any set $A$ of size at most $n/2$,
$|A+D|\geq|A|+\frac{t}{2}$. Finally, the last (asymptotic) equality follows
because $d=\omega(\log n)$.

To handle the case when $\Gamma$ non-bipartite, let
$\Gamma^{\prime}=\Gamma\times K_{2}$, and observe that $\Gamma^{\prime}$ is a
Cayley graph on $4n$ vertices on the group $\mathcal{F}\times\mathbb{Z}_{2}$
with generator set $D\times\\{1\\}$. Moreover, the fact that $\Gamma$ is non-
bipartite implies that $\Gamma^{\prime}$ is also connected (see, for example,
Theorem $3.4$ in [BHM80]). So by Theorem 8 and the preceding proof, we have

$i(\Gamma)^{2}\leq i(\Gamma^{\prime})\leq 2^{2n+1}(1+o(1))$

which gives that $i(\Gamma)\leq 2^{n+1/2}(1+o(1))$. ∎

##  4\. Proof of Lemma 2

Recall that we are given an undirected bipartite Cayley graph with bipartition
$X\cup Y$ with $|X|=|Y|=n$ and generator set $D$. We have the following three
conditions on $D$:

  1. (1)

$|D|\leq n^{1/3}$,

  2. (2)

$\log n=O\left(\frac{|D|}{\log^{8}|D|}\right)$, and

  3. (3)

$|2D|\geq|D|\log^{3}|D|$.

Also recall for a subset $A\subset X$, we say that $A$ is small if $|[A]|\leq
n/2$. We use $G$ to denote $N(A)$, with $|[A]|=a$, $|G|=g$, and $t=g-a$. Let
us abbreviate $d:=|D|$ and $d_{2}:=|2D|$. The proof of Lemma 2 has three
components, and we describe them here.

Define the _boundary_ of $G$ as

$G^{\prime}:=\\{v\in G~{}|~{}N(v)\cap[A]^{c}\neq\emptyset\\},$

which are the vertices in $G$ that are connected to vertices outside $[A]$.
The first component to the proof of Lemma 2 is the following:

######  Lemma 13.

There is a family $\mathcal{C}_{1}\subset 2^{Y}$ that satisfies the following
three properties

  1. (1)

$|C|=O\left(\frac{td_{2}}{\log^{3}d}\right)$ for every $C\in\mathcal{C}_{1}$

  2. (2)

$|\mathcal{C}_{1}|\leq 2^{O\left(\frac{t}{\log d}\right)}$

  3. (3)

For every $2$-linked $A\subset X$, there is a $C\in\mathcal{C}_{1}$ such that
$G^{\prime}\subseteq C$.

Lemma 13 offers a starting point from which ideas from the aforementioned
container method may be used effectively. The first of these ideas is the
notion of “$\varphi$ -approximation”:

Let $\varphi=d-\frac{\sqrt{d}}{\log d}$, and define for every $\alpha>0$,
$G_{\alpha}:=\\{u\in G~{}|~{}d_{[A]}(u)\geq\alpha\\}$. So in particular,
$G_{d}=\\{u\in G~{}|~{}N(u)\subseteq[A]\\}$.

######  Definition 14.

A set $F\subseteq G$ is a $\varphi$-approximation for $A$ if

  1. (1)

$F\supseteq G_{\varphi}$

  2. (2)

$N(F)\supseteq[A]$

Second, is notion of “$\psi$-approximation”. Let $\psi=d/\log d$.

######  Definition 15.

For a $d$-regular bipartite graph with bipartition $(X,Y)$, we say that
$(S,F)\in 2^{X}\times 2^{Y}$ is a $\psi$-approximation for $A$ if
$S\supseteq[A]$, $F\subseteq G$ and the following two conditions hold:

  1. (1)

$d_{F}(u)\geq d-\psi$ for every $u\in S$

  2. (2)

$d_{X\setminus S}(v)\geq d-\psi$ for every $v\in Y\setminus F$.

The following is a useful property of the $\psi$-approximation (Lemma $5.3$ in
[Gal19]).

######  Lemma 16.

Let $(S,F)$ be a $\psi$-approximation for $A$. Then
$|S|\leq|F|+2\frac{t\psi}{d-\psi}$.

The second component to the proof of Lemma 2 is the following:

######  Lemma 17.

For every $C\in\mathcal{C}_{1}$, there is a family $\mathcal{C}_{2}(C)\subset
2^{Y}$ of size at most

$2^{O\left(\frac{t}{\log d}\right)}$

such that $\mathcal{C}_{2}(C)$ contains a $\varphi$-approximation for every
small set $A\subset X$ whose boundary is contained in $C$.

The requirement that $\Gamma$ is an “expander” is a crucial point in [Sap87],
which does not apply to general Cayley graphs. As mentioned before, the main
idea here is to try and overcome this by using $\mathcal{C}_{1}$. This lemma
is the only place where we use the fact that $|D|\leq n^{1/3}$ and the fact
that $A$ is small. Let us denote
$\mathcal{C}_{2}:=\bigcup_{C\in\mathcal{C}_{1}}\mathcal{C}_{2}(C)$.

The final component to the proof of Lemma 2 is the following:

######  Lemma 18.

For every $F\in\mathcal{C}_{2}$, there is a family
$\mathcal{C}_{3}(F)\subseteq 2^{X}\times 2^{Y}$ of size at most

$2^{O\left(\frac{t\log^{4}d}{\sqrt{d}}\right)}$

which contains a $\psi$-approximation for every $A$ such that
$F\in\mathcal{C}_{2}$ which is a $\varphi$-approximation for $A$.

Define $\mathcal{C}_{3}:=\bigcup_{F\in\mathcal{C}_{2}}\mathcal{C}_{3}(F)$.

Given the above three lemmas, we prove Lemma 2 as follows:

###  4.1. Reconstruction: Proof of Lemma 2 given Lemmas 13, 17, and 18

First,we upper bound the size of $\mathcal{C}_{3}$. Lemmas 13, 17, and 18
imply that

$\displaystyle|\mathcal{C}_{3}|$ $\displaystyle\leq
2^{O\left(\frac{t\log^{4}d}{\sqrt{d}}\right)}\cdot|\mathcal{C}_{2}|$
$\displaystyle\leq 2^{O\left(\frac{t\log^{4}d}{\sqrt{d}}\right)}\cdot
2^{O\left(\frac{t}{\log d}\right)}\cdot|\mathcal{C}_{1}|$ $\displaystyle\leq
2^{O\left(\frac{t\log^{4}d}{\sqrt{d}}\right)}\cdot 2^{O\left(\frac{t}{\log
d}\right)}\cdot 2^{O\left(\frac{t}{\log d}\right)}$ $\displaystyle\leq
2^{O\left(\frac{t}{\log d}\right)}.$

Then, we use the following, which follows from methods of Kahn and Park
[KP19], stated explicitly by Park [Par21]

######  Lemma 19.

For each $\psi$-approximation $(S,F)$, there are at most

$2^{g-\Omega(t)}$

sets $A$ such that $(S,F)$ is a $\psi$-approximation for $A$.

Thus we have

$\displaystyle\mathcal{G}(a,g)$ $\displaystyle\leq
2^{g-\Omega(t)}\cdot|\mathcal{C}_{3}|$ $\displaystyle\leq 2^{g-\Omega(t)}.$

Before we proceed to prove the lemmas 13, 17, and 18, we prove a few more
preliminary results.

###  4.2. More preliminaries

We will use a consequence of Theorem 7 which tells us that given a bipartite
Cayley graph with bipartition $(X,Y)$, we can always select an almost spanning
subset of a given vertex set in $X$ or $Y$ whose second and third neighborhood
in comparison to the first neighborhood is not much larger. Note that the
following is an easy observation, while Lemma 21 shows that in the trivial
bound $|M+iD|\leq m+td^{i}$ can be improved if one chooses an appropriate
large subset of $M$.

######  Fact 20.

If $M\subseteq X$ with $|M|=m$ and $|M+D|=m+t$, then for every $i\geq 2$, we
have $|M+iD|\leq m+d^{i}\cdot t$.

######  Lemma 21.

Let $M\subseteq X$ with $|M|=m$, and $|M+D|=m+t$. Then, for any
$k\in\mathbb{N}$ and $c\geq 4$, there is an $M^{(k)}\subseteq M$ with
$|M\setminus M^{(k)}|\leq k\cdot\frac{t}{c}$ and

$|M^{(k)}+(i+1)D|\leq m+(2i)^{i+1}\cdot c^{i}\cdot t$

for each $i\leq k$.

###### Proof.

We prove this by induction on $k$.

Set $N=M+\\{e\\}$ for some $e\in D$, $j=1$, $h=2$, $s=t$, and
$\ell=m-\frac{t}{c}$. Since $M+D\supseteq N$, and $|N|=|M|$, we have that
$|(M+D)\setminus N|=t$. Theorem 7 guarantees the existence of a set
$M^{(1)}\subseteq M$ such that $|M\setminus M^{\prime}|\leq\frac{t}{c}$ and

$\displaystyle|(M^{(1)}+2D)\setminus(N+D)|$
$\displaystyle\leq\frac{t^{2}}{2}\left(\frac{c}{t}-\frac{1}{m}\right)+c^{2}\left(m-\left(m-\frac{t}{c}\right)\right)$
$\displaystyle\leq 2c\cdot t.$

Therefore, $|M^{(1)}+2D|\leq|(M^{(1)}+2D)\setminus(N+D)|+|N+D|\leq m+t+2ct\leq
m+3ct$ which completes the base case of the induction.

For $i\geq 2$, let us assume that there is an $M^{(i)}\subseteq
M^{(i-1)}\cdots M^{(1)}\subset M$ such that

  * •

$|M^{(i^{\prime}-1)}\setminus M^{(i^{\prime})}|\leq\frac{t}{c}$

  * •

$|M^{(i^{\prime})}+(i^{\prime}+1)D|\leq|M^{(i^{\prime})}|+(2i^{\prime})^{i^{\prime}+1}\cdot
c^{i^{\prime}}t$

For each $i^{\prime}\leq i$. Set $N=M^{(i)}+\\{e\\}$ for some $e\in D$. Since
$M^{(i)}+(i+1)D\supseteq N+iD$, we have

$\displaystyle|(M^{(i)}+(i+1)D)\setminus(N+iD)|$
$\displaystyle=|M^{(i)}+(i+1)D|-|N+iD|$
$\displaystyle=|M^{(i)}+(i+1)D|-|M^{(i)}+iD|$
$\displaystyle\leq|M^{(i)}+(i+1)D|-|M^{(i)}|$
$\displaystyle\leq(2i)^{i+1}\cdot c^{i}t.$

Now apply Theorem 7 with $M=M^{(i)}$, $N=M^{(i)}+\\{e\\}$ for some $e\in D$,
$j=i+1$, $h=i+2$, and $\ell=|M^{(i)}|-\frac{t}{c}$,
$s:=|(M^{i}+(i+1)D)\setminus(N+iD)|\leq(2i)^{i+1}\cdot c^{i}t$. So again, we
obtain a set $M^{(i+1)}\subseteq M^{(i)}$ of size at least
$\ell\geq|M^{(i)}|-\frac{t}{c}$ and

$\displaystyle|(M^{(i+1)}+(i+2)D)\setminus(N+(i+1)D)|$
$\displaystyle\leq\frac{((2i)^{i+1}\cdot
c^{i}t)^{\frac{i+2}{i+1}}}{(i+2)/(i+1)}\left(\left(\frac{c}{t}\right)^{\frac{1}{i+1}}-\left(\frac{1}{m}\right)^{\frac{1}{i+1}}\right)+(2i)^{i+2}\cdot
c^{i+2}\left(|M^{(i)}|-\left(|M^{(i)}|-\frac{t}{c}\right)\right)$
$\displaystyle\leq 2\cdot(2i)^{i+2}\cdot c^{i+1}t,$

and therefore,

$\displaystyle|(M^{(i+1)}+(i+2)D)|$
$\displaystyle\leq|N+(i+1)D|+2\cdot(2i)^{i+2}\cdot c^{i+1}t$
$\displaystyle=|M^{(i)}+(i+1)D|+2\cdot(2i)^{i+2}\cdot c^{i+1}t$ (3)
$\displaystyle\leq|M^{(i)}|+(2i)^{i+1}c^{i}t+2\cdot(2i)^{i+2}\cdot c^{i+1}t$
(4)
$\displaystyle\leq|M^{(i+1)}|+\frac{t}{c}+(2i)^{i+1}c^{i}t+2\cdot(2i)^{i+2}\cdot
c^{i+1}t$ $\displaystyle\leq|M^{(i+1)}|+(2(i+1))^{i+2}c^{i+1}t.$

Here, (3) follows from the induction hypothesis, and (4) follows from
$|M^{i+1}\setminus M^{(i)}|\leq\frac{t}{c}$. Thus we have
$M^{(k)}\subseteq\cdots\subseteq M^{(1)}\subseteq M$ and for every $i\leq k$,
we have $|M^{(i-1)}\setminus M^{(i)}|\leq\frac{t}{c}$ and

$\displaystyle|M^{(k)}+(i+1)D|$ $\displaystyle\leq|M^{(i)}+(i+1)D|$
$\displaystyle\leq|M^{(i)}|+(2i)^{i+1}\cdot c^{i}t$ $\displaystyle\leq
m+(2i)^{i+1}\cdot c^{i}t$

for each $i\leq k$ as claimed. ∎

Next, as a corollary of Theorem 4 and Theorem 6, we have the following:

######  Corollary 22.

Let $M\subseteq X$ such that $|M|\leq|X|/2$ and $|M+D|=\alpha|M|$, and
$M+2D\neq X$. Then $|2D|\leq 2(\alpha^{2}-1)|M|$.

###### Proof.

A direct application of Theorem 4 gives us an $M^{\prime}\subseteq M$ that

(5) $|M^{\prime}+2D|\leq\alpha^{2}|M^{\prime}|.$

Since $\Gamma$ is connected, $D$ is a generating set, and so we must have that
$|M^{\prime}+4D|>|M^{\prime}+2D|$. Indeed, suppose otherwise, then it must be
the case that $|M^{\prime}+2D|=|M^{\prime}+3D|=|M^{\prime}+4D|$, since for any
two sets $A,B\in\mathcal{F}$, $|A+2B|\geq|A+B|$. But since
$M^{\prime}+3D=N_{\Gamma}(M^{\prime}+2D)$, this gives us that
$M^{\prime}+2D=X$ or $\Gamma$ is disconnected, which is a contradiction. So
Theorem 6 gives us that

(6) $|M^{\prime}+2D|\geq|M^{\prime}|+(1/2)\cdot|2D|.$

Combining (5) and (6) gives us that $|2D|\leq 2(\alpha^{2}-1)|M^{\prime}|\leq
2(\alpha^{2}-1)|M|$. ∎

We also need the following easy observation.

######  Proposition 23.

Let $D^{\prime}\subseteq D$ such that $|D\setminus
D^{\prime}|\leq\sqrt{d}/\log d$. Then
$|D+D^{\prime}|\geq(|2D|)(1-\left(1/\log^{2}d\right))$.

###### Proof.

We have that $2D=(D+D^{\prime})\cup(2\cdot(D\setminus D^{\prime}))$. Since
$|2\cdot(D\setminus D^{\prime})|\leq|D\setminus
D^{\prime}|^{2}\leq|D|/\log^{2}|D|$, the claim follows. ∎

Corollary 22 also gives us the following, which is the only place we use the
fact that $|D|\leq n^{1/3}$.

######  Corollary 24.

Let $D^{\prime}\subset D$ such that $|D^{\prime}|\geq d-\sqrt{d}/\log d$, and
let $M\supseteq\\{u\\}+D^{\prime}$ and $|M|\leq|X|/2$ for some
$u\in\mathcal{F}$. Then the following holds:

$|M+D|\geq|M|+|2D|/6.$

###### Proof.

The statement is clearly true for $|M|\leq(1/6)\cdot|2D|$ because of
Proposition 23, since
$|M+D|\geq|D^{\prime}+D|\geq|2D|(1-1/(\log^{2}|D|))\geq|M|+|2D|/6$.

For $|M|>(1/6)\cdot|2D|$, suppose we had $|M+D|<|M|+|2D|/6$. Then Fact 20
gives us that

$\displaystyle|M+2D|$ $\displaystyle<|M|+|D|\cdot|2D|/6$
$\displaystyle\leq|M|+|D|^{3}/6$ $\displaystyle\leq|X|/2+|X|/6$
$\displaystyle<|X|.$

This is the only place we use $|D|\leq n^{1/3}$. Since $M$ satisfies the
hypothesis of Corollary 22, we have that

$\displaystyle|2D|$ $\displaystyle\leq
2\left(\left(1+\frac{|2D|}{6|M|}\right)^{2}-1\right)|M|$
$\displaystyle<2\left(3\cdot\frac{|2D|}{6|M|}\right)|M|$ $\displaystyle=|2D|$

which is a contradiction. The second inequality is because $(1+x)^{2}<1+3x$
for $x\in(0,1)$. ∎

###  4.3. Boundaries: Proof of Lemma 13

Applying Lemma 21 setting $M=[A]$ and $c=\log^{2}d$, there is an
$\underline{A}\subseteq[A]$ such that

  * 1.

$|[A]\setminus\underline{A}|\leq 4\frac{t}{\log^{2}d}$

  * 2.

$|N^{i}(\underline{A})|\leq a+O(t\log^{2(i-1)}d)$ for each $i\in[4]$.

Moreover, we may assume that $\underline{A}=[\underline{A}]$. Suppose not,
replacing $\underline{A}$ by $[\underline{A}]$ (which is possible because
$[A]$ is closed and so, $[\underline{A}]\subseteq[A]$) does not violate either
of the properties. Define $\underline{G}:=N(\underline{A})$ and
$\underline{G}^{\prime}:=\\{u\in
N(\underline{A})~{}|~{}N(u)\cap\underline{A}^{c}\neq\emptyset\\}$ to be the
boundary of $\underline{G}$. Observe that

(7) $G^{\prime}\subseteq\underline{G}^{\prime}\cup
N([A]\setminus\underline{A}).$

Before we proceed, let us make a few definitions. Define
$G_{0}:=N^{3}(\underline{A})\setminus\underline{G}$,
$A_{0}:=N^{2}(\underline{A})\setminus\underline{A}$, and
$A_{1}:=N^{4}(\underline{A})\setminus N^{2}(\underline{A})$. Lemma 21 implies
that $|A_{0}|=O(t\log^{2}d)$, $|G_{0}|=O(\log^{4}d)$, and
$|A_{1}|=O(\log^{6}d)$.

We have $N(G_{0})\subseteq A_{0}\cup A_{1}$. So, by Theorem 9, there is a set
$Z_{1}\subset A_{0}\cup A_{1}$ such that

$|Z_{1}|\leq O\left(\frac{|A_{0}\cup A_{1}|\log
d}{d}\right)=O\left(\frac{t\log^{7}d}{d}\right)$

and

(8) $G_{0}\subseteq N(Z_{1}).$

Let $\underline{G}^{\prime}=G_{L}\sqcup G_{S}$, where

$G_{S}:=\\{v\in\underline{G}^{\prime}~{}|~{}d_{A_{0}}(v)\geq d/2\\}.$

Since we have $|A_{0}|=O(t\log^{2}d)$, by Theorem 9, there is a subset
$Z_{2}\subset A_{0}$ of size at most $O\left(\frac{t\log^{3}d}{d}\right)$ such
that

(9) $G_{S}\subseteq N(Z_{2}).$

Applying Lemma 21 with $M=\underline{G}^{c}$ gives that there is a subset
$M^{\prime}\subseteq\underline{G}^{c}$ such that
$|M^{\prime}|\geq|\underline{G}^{c}|-\frac{2t}{\log^{3}d}$ and
$|M^{\prime}+3D|\leq|\underline{G}^{c}|+O(t\log^{6}d)$. Set
$A_{2}:=|M^{\prime}+3D|\cap\underline{A}$. We have that
$|A_{2}|=O(t\log^{6}d)$.

Let $G^{\prime\prime}:=G_{L}\cap N^{2}(M^{\prime})$. We have that each vertex
in $G^{\prime\prime}$ must have at least $d/2$ neighbors in $A_{2}$. So, by
Theorem 9, there is a subset $Z_{3}\subset A_{2}$ of size at most
$\frac{|A_{2}|\log d}{d}=O\left(\frac{t\log^{7}d}{d}\right)$ such that

(10) $G^{\prime\prime}\subseteq N(Z_{3}).$

Since $\underline{A}$ is closed, we have
$\underline{A}^{c}=N(\underline{G}^{c})$. So, $G_{L}\subseteq
N^{2}\left(\underline{G}^{c}\right)$ and therefore,

(11) $G_{L}\setminus G^{\prime\prime}\subseteq
N^{2}(\underline{G}^{c}\setminus M^{\prime}).$

Moreover, every $u\in G_{L}\setminus G^{\prime\prime}$ satisfies
$(N^{2}(u)\cap\underline{G}^{c})\subseteq N(A_{0})=G_{0}$, and therefore,

(12) $N^{2}(G_{L}\setminus G^{\prime\prime})\cap\underline{G}^{c}\subseteq
G_{0}.$

Taking (11) and (12) together, we have that

(13) $G_{L}\setminus G^{\prime\prime}\subseteq
N^{2}\left(\left(\underline{G}^{c}\setminus M^{\prime}\right)\cap
G_{0}\right).$

Thus, since we have

$\underline{G}^{\prime}=G_{S}\sqcup G^{\prime\prime}\sqcup(G_{L}\setminus
G^{\prime\prime}),$

we have, using (9), (10), and (13),

(14) $\underline{G}^{\prime}\subseteq N(Z_{2})\cup N(Z_{3})\cup
N^{2}\left(\left(\underline{G}^{c}\setminus M^{\prime}\right)\cap
G_{0}\right).$

For $([A]\setminus\underline{A})$, we have the following:

######  Claim 25.

The number of possibilities for $[A]\setminus\underline{A}$’s for a given
$Z_{1}$ is at most $2^{O\left(\frac{t}{\log d}\right)}$.

###### Proof.

Since $[A]$ is $2$-linked, we must have that every $2$-linked component in
$[A]\setminus\underline{A}$ has at least one vertex in with
$N^{2}(\underline{A})\setminus\underline{A}$. Since we have that

$N^{2}(\underline{A})\setminus\underline{A}=A_{0}\subseteq N(G_{0})\subseteq
N^{2}(Z_{1}),$

we can choose $[A]\setminus\underline{A}$ from a given $Z_{1}$ by the
following procedure: (1) Choose one vertex per $2$-linked component of
$[A]\setminus\underline{A}$ from $N^{2}(Z_{1})$, (2) specify the sizes of
these $2$-linked components and finally, (3) specify the vertices in each of
these components by specifying the BFS tree starting from the chosen vertices
in some predetermined order.

The first can be done in $\binom{|N^{2}(Z_{1})|}{\leq\frac{4t}{\log^{2}d}}$
ways, the second in $2^{\frac{8t}{\log^{2}d}}$ ways, and the third, using
Proposition 10, in $d^{\frac{8t}{\log^{2}d}}$ ways.

Since $|Z_{1}|=O\left(\frac{t\log^{7}d}{d}\right)$, we have that
$|N^{2}(Z_{1})|\leq d^{2}|Z_{1}|=O(td\log^{7}d)$. Therefore, the total number
of choices for $[A]\setminus\underline{A}$ is at most $2^{O\left(\frac{t}{\log
d}\right)}$. ∎

Recalling (7) and (14), we have that

$G^{\prime}\subseteq N(Z_{2})\cup N(Z_{3})\cup
N^{2}\left(\left(\underline{G}^{c}\setminus M^{\prime}\right)\cap
G_{0}\right)\cup N([A]\setminus\underline{A})$

The size of each possible $([A]\setminus\underline{A})$ described by Claim 25
is at most $\frac{4t}{\log^{2}d}$. Each of the sets $Z_{2}$, and $Z_{3}$ are
of size at most $O\left(\frac{t\log^{7}d}{d}\right)$. Finally,
$(\underline{G}^{c}\setminus M^{\prime})\cap G_{0}$ is a set of size at most
$|\underline{G}^{c}\setminus M^{\prime}|\leq\frac{t}{\log^{4}d}$. Putting
these together, we have

$\displaystyle|N(Z_{2})\cup N^{2}((\underline{G}^{c}\setminus M^{\prime})\cap
G_{0})\cup N(Z_{3})\cup N([A]\setminus\underline{A})|$ $\displaystyle\leq
d|Z_{2}|+d|Z_{3}|+d_{2}|\underline{G}^{c}\setminus
M^{\prime}|+d|[A]\setminus\underline{A}|$
$\displaystyle=O\left(\frac{td_{2}}{\log^{3}d}\right).$

To count the number of possibilities for this, each tuple
$\left(Z_{2},Z_{3},(\underline{G}^{c}\setminus
M^{\prime}),([A]\setminus\underline{A})\right)$ is described as follows:

  * •

The sets $Z_{2}$, and $Z_{3}$ are specified explicitly by sets of size
$O\left(\frac{t\log^{7}d}{d}\right)$ each. This gives at most

$\binom{n}{O\left(\frac{t\log^{7}d}{d}\right)}^{2}$

possibile descriptions.

  * •

The set $(\underline{G}^{c}\setminus M^{\prime})\cap G_{0}$ is specified by

    * –

Specifying $Z_{1}$, which is a set of size
$O\left(\frac{t\log^{7}d}{d}\right)$. This has

$\binom{n}{O\left(\frac{t\log^{7}d}{d}\right)}$

possible descriptions.

    * –

Specifying the subset of $N(Z_{1})$ of the size at most
$|\underline{G}^{c}\setminus M^{\prime}|\leq\frac{2t}{\log^{2}d}$. This has at
most $\binom{|N(Z_{1})|}{2t/\log^{2}d}=2^{O\left(\frac{t}{\log d}\right)}$
possible descriptions.

  * •

Specifying $[A]\setminus\underline{A}$ as in Claim 25 using $Z_{1}$, which has
at most $2^{O\left(\frac{t}{\log d}\right)}$ descriptions.

So in total, the number of possible descriptions (and therefore, the number)
of tuples $\left(Z_{2},Z_{3},(\underline{G}^{c}\setminus
M^{\prime}),([A]\setminus\underline{A})\right)$ is at most

$\binom{n}{\frac{t\log^{7}d}{d}}^{2}\cdot\binom{n}{\frac{t\log^{7}d}{d}}\cdot
2^{O\left(\frac{t}{\log d}\right)}=2^{O\left(\frac{t}{\log d}\right)}$

Where in the last equality, we have used $d/\log^{8}d=\Omega(\log n)$.

###  4.4. $\varphi$-approximation: Proof of Lemma 17

We will first pre-process the graph using the following contraction algorithm
given a $C\in\mathcal{C}_{1}$.

  * •

$R\leftarrow X$, $B\leftarrow\emptyset$

  * •

While $Y\supsetneq C$ do

    * –

Let $u\in Y\setminus C$ be arbitrary.

    * –

$Y\leftarrow Y\setminus\\{u\\}$.

    * –

$X\leftarrow X\setminus N(u)\cup\\{v^{\prime}\\}$ where
$N(v^{\prime})=\cup_{v\in N(u)}N(v)$ with multiplicities.

    * –

$R\leftarrow R\setminus N(u)$, $B\leftarrow B\setminus
N(u)\cup\\{v^{\prime}\\}$

Let $\mathcal{F}^{\prime}$ be the final graph after the algorithm terminates
with parts $X^{\prime}$ and $Y^{\prime}$. The set $R$ consists of all vertices
whose neighbors are all in $C$, and the set $B$ are all vertices obtained
through the above mentioned contraction algorithm. Since at each step, the
algorithm contracts a vertex in $Y$ with it’s (current) neighborhood, every
vertex in $B$ is obtained via the contraction of _all_ the vertices in
$N(S)_{d}$ for some $S\subseteq X$. Thus, the set $B$ is given by
$\\{v_{S}\\}$ where $S\subset X$ and $v_{S}$ corresponds to the subset $S\cup
N(S)_{d}$, and

(15) $N(v_{S})=N(S)\setminus N(S)_{d}.$

Before the start of the algorithm, every vertex in $Y\setminus C$ has all its
neighbors either in $[A]$ or $[A]^{c}$. Consider the partition $B=B_{A}\sqcup
B_{A^{c}}$ defined as $B_{A}:=\\{v_{S}\in B~{}|~{}S\subset[A]\\}$. Similarly,
partition $R=R_{A}\sqcup R_{A^{c}}$ where $R_{A}=R\cap[A]$.

We have that for every set $S$, $|N(S)_{0}|\leq|S|$, and $S\supseteq N(u)$ for
every $u\in N(S)_{d}$. Moreover, $A$ is small. Thus Corollary 24, and (15)
together imply that every vertex in $B_{A}$ has degree at least $d_{2}/6$.

Define $Q_{0}$ to be a $p=\left(\frac{60\log d}{d_{2}}\right)$-random subset
of $Y\cap G$. The following four properties hold with probability at least
$1/5$.

  1. (1)

$|Q_{0}|\leq O\left(\frac{t}{\log^{2}d}\right)$.

  2. (2)

$\nabla(Q_{0},(R_{A^{c}}\cup B_{A^{c}}))=O\left(\frac{t}{\log^{2}d}\right)$.

  3. (3)

$\\#\\{u\in B_{A}~{}|~{}Q_{0}\cap
N(u)=\emptyset\\}=O\left(\frac{t}{d^{7}}\right)$.

  4. (4)

$|(G_{\varphi}\cap C)\setminus N(N_{R_{A}\cup
B_{A}}(Q_{0}))|=O\left(\frac{t}{d^{8}}\right)$.

First we observe that $\mathbf{E}[|Q_{0}|]\leq p|C|$. Thus the probability
that Property $1.$ does not hold is at most, using Markov’s inequality, $1/5$.
Next, we observe

$\mathbf{E}[|\nabla(Q_{0},(R_{A^{c}}\cup B_{A^{c}}))|]=ptd=\frac{td\log
d}{d_{2}}\leq\frac{10t}{\log^{2}d}.$

Thus the probability that Property $2.$ does not hold is, again by Markov’s
inequality, at most $1/5$.

Define $Q_{1}:=\nabla(Q_{0},(R_{A^{c}}\cup B_{A^{c}}))$ .

For property $3.$, we use the fact that every vertex in $B_{A}$ has degree at
least $\Omega(d_{2})$. So for each $u\in B_{A}$, we have $\mathbb{P}(Q_{0}\cap
B_{A}=\emptyset)\leq(1-p)^{d_{2}/6}\leq d^{-10}$. Moreover, after the
algorithm $|X^{\prime}|\leq d|C|\leq td^{3}$. So we have

$\mathbf{E}[\\#\\{u\in B_{A}~{}|~{}Q_{0}\cap N(u)=\emptyset\\}]\leq td^{-7}.$

Therefore, the probability that Property $3.$ does not hold is again at most
$1/5$.

Define $Q_{2}:=\\{u\in B_{A}~{}|~{}Q\cap N(u)=\emptyset\\}\\}$.

Let us abbreviate $C^{\prime}:=C\cap G_{\varphi}$. Property $4.$ follows from
using the fact that for every $u\in C^{\prime}$, $|N(N_{R_{A}\cup
B_{A}}(u))|\geq d_{2}/6$. Indeed, since any $u\in C^{\prime}$ has at least
$\varphi$ edges to $A$, and therefore to $R_{A}\cup B_{A}$. Thus we may apply
Corollary 24 to obtain the desired bound on $|N(N_{R_{A}\cup B_{A}}(u))|$. So
for any given $u$, we have that $\mathbb{P}(Q_{0}\cap N(N_{R_{A}\cup
B_{A}}(u))=\emptyset)\leq(1-p)^{d_{2}/6}\leq d^{-10}$, and so

$\mathbf{E}[\\#\\{u~{}|~{}N(N_{R_{A}\cup B_{A}}(u))\cap
Q_{0}=\emptyset\\}]\leq|C|\cdot d^{-10}\leq td^{-8}.$

So the probability that Property $4.$ does not hold is again at most $1/5$.

Define $Q_{3}:=C^{\prime}\setminus N(N_{R_{A}\cup B_{A}}(Q_{0}))$.

Finally, by the Union Bound, the probability that either of the properties
does not hold is at most $4/5$, and so in particular, there is a choice for
$Q_{0}$ (and therefore, for $Q_{1}$, $Q_{2}$, and $Q_{3}$) that satisfies all
four properties.

We claim that given $Q_{0}$, $Q_{1}$, $Q_{2}$, and $Q_{3}$, one can construct
a set $Z_{1}\subseteq G$ such that $Z_{1}\supseteq G_{\varphi}$. Indeed, since
using $Q_{0}$ and $Q_{1}$, one can construct $N(N_{R_{A}\cup
B_{A}}(Q_{0}))\subseteq G$. So far, this is missing all the vertices in
$Q_{3}$ and $G_{d}\setminus C$. We have $Q_{3}$ provided, and finally, by
$Q_{2}$, and the neighbors of $Q_{0}$, one can determine $B_{A}$, and
therefore, $G_{d}\setminus C$.

Now the only vertices in $A$ uncovered by $Z_{1}$ are $R_{A}\setminus
N(Z_{1})$, since by construction, $N(Z_{1})\supset B_{A}$. Note that every
vertex in $R_{A}\setminus N(Z_{1})$ has degree $d$ to $G\setminus Z_{1}$.
Moreover, $|G\setminus Z_{1}|\leq t\sqrt{d}\log d$. This is because
$Z_{1}\supseteq G_{\varphi}$, and each vertex in $G\setminus Z_{1}$
contributes at least $\sqrt{d}/\log d$ edges to $\nabla(G,[A]^{c})$, which is
a set of size $td$. Thus by Theorem 9, can specify a further
$O\left(\frac{t\log^{3}d}{\sqrt{d}}\right)$ vertices in $C$ such that
$N(C)\supset R_{A}\setminus Z_{1}$. Let $Z_{2}$ denote this set of vertices.
The final $\varphi$-approximation is $Z_{1}\cup Z_{2}$. We count the number of
these as follows:

  1. (1)

The set $Q_{0}$, $Q_{3}$, and $Z_{2}$ are subsets of $C$, each of size at most
$\frac{50t}{\log^{2}d}$, so the number of choices for these sets are at most
$\binom{|C|}{\frac{50t}{\log^{2}d}}^{3}\leq 2^{O\left(\frac{t}{\log
d}\right)}$.

  2. (2)

Since $|Q_{2}|\leq\frac{5t}{d^{7}}$, the number of choices for this is at most
$\binom{|X^{\prime}|}{\frac{5t}{d^{7}}}\leq\binom{td^{3}}{\frac{t}{d^{7}}}=2^{O\left(\frac{t\log
d}{d^{7}}\right)}$.

  3. (3)

Finally, the number of choices for $Q_{1}$ are at most
$\binom{td}{|Q_{1}|}\leq 2^{O\left(\frac{t}{\log d}\right)}$.

Thus for every $C\in\mathcal{C}_{1}$, there is a set of at most
$2^{O\left(\frac{t}{\log d}\right)}$ many $\varphi$-approximations for all
sets $A$ such that $C$ contains the boundary of $A$.

###  4.5. $\psi$-approximation: Proof of Lemma 18

Recall that $\psi=\frac{d}{\log d}$ and $\varphi=d-\frac{\sqrt{d}}{\log d}$.
Fix an order $\ll$ on $X\cup Y$ and do the following procedure

  * •

Initialize $F^{\prime}\leftarrow F$.

  * •

While $\mathcal{Q}:=\\{u\in[A]~{}|~{}d_{G\setminus
F^{\prime}}(u)\geq\psi\\}\neq\emptyset$ do

    * –

Let $u\in\mathcal{Q}$ be smallest w.r.t. $\ll$

    * –

$F^{\prime}\leftarrow F^{\prime}\cup N(u)$.

  * •

Initialize $F^{\prime\prime}\leftarrow F^{\prime}$, $S\leftarrow\\{u\in
X~{}|~{}d_{F^{\prime\prime}}(u)\geq d-\psi\\}$

  * •

While $\mathcal{Q}^{\prime}:=\\{w\in
Y~{}|~{}d_{S^{\prime\prime}}(w)>\psi\\}\neq\emptyset$ do

    * –

$w\in\mathcal{Q}^{\prime}$ be smallest w.r.t. $\ll$

    * –

$S^{\prime\prime}\leftarrow S^{\prime\prime}\setminus N(w)$.

  * •

return $(S^{\prime\prime},F^{\prime\prime})$.

The fact that $(S^{\prime\prime},F^{\prime\prime})$ is a $\psi$-approximation
can be verified easily. We will only focus on enumerating the number of such
pairs for a given $F$. Every pair is determined completely by the set of
vertices $u$ chosen in the first loop and the set of vertices $w$ chosen in
the second.

First, we observe that before the first loop,
$td=\nabla(G,[A]^{c})\geq|G\setminus F^{\prime}|\cdot(d-\varphi)$, and so
$|G\setminus F^{\prime}|\leq\frac{td}{d-\varphi}$. So in the first loop, each
$u\in\mathcal{Q}$ removes at least $\psi$ vertices from this set, and
therefore, the first loop is run for at most $\frac{td}{\psi\cdot(d-\varphi)}$
times. Moreover, we have

$\mathcal{Q}\subseteq N(G\setminus F^{\prime})\subseteq
N(N^{2}(F^{\prime})\setminus F^{\prime})\subseteq N(N^{2}(G)\setminus
F^{\prime})$

where the second containment follows since $F^{\prime}\supseteq F$. So by
Theorem 20, using the fact that $N^{2}(G)=N^{3}(A)$, we have

$|\mathcal{Q}|\leq d(|N^{2}(G)|-|F^{\prime}|)\leq O(td^{4}).$

Therefore, the number of ways of choosing the vertices $u$ from
$N(N^{2}(F^{\prime})\setminus F^{\prime})$ in the first loop is at most

$\binom{O(td^{4})}{\leq\frac{td}{\psi\cdot(d-\varphi)}}\leq
2^{O\left(\frac{td\log d}{\psi\cdot(d-\varphi)}\right)}.$

Next, we observe that before the second loop,
$td=\nabla(G,[A]^{c})\geq|S^{\prime\prime}\setminus A|(d-\psi)$ and so
$|S^{\prime\prime}\setminus A|\leq td/(d-\psi)$. So in the second loop, each
$w\in\mathcal{Q}^{\prime}$ removes at least $\psi$ vertices from this set, and
therefore, the second loop is run for at most $\frac{td}{\psi(d-\psi)}$ times.
Moreover, we have

$\mathcal{Q}^{\prime}\subseteq N^{2}(G\setminus F^{\prime})\subseteq
N^{2}(N^{2}(F^{\prime})\setminus F^{\prime})\subseteq N^{2}(N^{2}(G)\setminus
F^{\prime})$

Where the second containment follows since $F^{\prime\prime}\supseteq F$. So
by Theorem 20, using the fact that $N^{2}(G)=N^{3}(A)$, we have

$|\mathcal{Q}^{\prime}|\leq d^{2}(|N^{2}(G)|-|F^{\prime}|)\leq O(td^{5}).$

Therefore, the number of ways of choosing the vertices $w$ from
$N^{2}(N^{2}(F^{\prime})\setminus F^{\prime})$ in the first loop is at most

$\binom{O(td^{5})}{\leq\frac{td}{\psi(d-\psi)}}\leq 2^{O\left(\frac{td\log
d}{\psi(d-\psi)}\right)}.$

which completes the proof.

##  5\. Acknowledgements

We would like to thank Will Perkins for various insightful conversations on
the topic. We are also grateful to Dhruv Mubayi, who asked the question on the
number of independent sets in Cayley graphs on $\mathbb{Z}_{2n}$ (see Appendix
B), which essentially motivated our research on this problem.

## References

  * [Alo91] N. Alon.  Independent sets in regular graphs and sum-free subsets of finite groups.  Israel Journal of Mathematics, 73:247–256, 1991.
  * [BGL21] József Balogh, Ramon I. Garcia, and Lina Li.  Independent sets in the middle two layers of boolean lattice.  Journal of Combinatorial Theory, Series A, 178:105341, 2021.
  * [BGLW21] József Balogh, Ramon I. Garcia, Lina Li, and Adam Zsolt Wagner.  Intersecting families of sets are typically trivial.  arXiv preprint arXiv:2104.03260, 2021.
  * [BHM80] Richard A. Brualdi, Frank Harary, and Zevi Miller.  Bigraphs versus digraphs via matrices.  Journal of Graph Theory, 4(1):51–73, 1980.
  * [DP09] Devdatt P. Dubhashi and Alessandro Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, 2009.
  * [Gal03] David Galvin.  On homomorphisms from the Hamming cube to $\mathbb{Z}$.  Israel Journal of Mathematics, 138(1):189–213, 2003.
  * [Gal10] David Galvin.  A threshold phenomenon for random independent sets in the discrete hypercube.  Combinatorics, Probability and Computing, 20:27 – 51, 2010.
  * [Gal19] David Galvin.  Independent sets in the discrete hypercube.  arXiv preprint arXiv:1901.01991, 2019.
  * [GK04] David Galvin and J. Kahn.  On phase transition in the hard-core model on $\mathbb{Z}^{d}$.  Combinatorics, Probability and Computing, 13:137 – 164, 2004.
  * [GKRS15] David Galvin, J. Kahn, D. Randall, and G. Sorkin.  Phase coexistence and torpid mixing in the 3-coloring model on $\mathbb{Z}^{d}$.  SIAM J. Discret. Math., 29:1223–1244, 2015.
  * [GR09] Alfred Geroldinger and Imre Z Ruzsa.  Combinatorial Number Theory and Additive Group Theory. Advanced Courses in Mathematics - CRM Barcelona. Birkhäuser Basel : Imprint: Birkhäuser, 1st ed. 2009. edition, 2009.
  * [GT06] David J. Galvin and Prasad Tetali.  Slow mixing of glauber dynamics for the hard-core model on regular bipartite graphs.  Random Struct. Algorithms, 28(4):427–443, 2006.
  * [GZ11] David Galvin and Yufei Zhao.  The number of independent sets in a graph with small maximum degree.  Graphs and Combinatorics, 27:177–186, 2011.
  * [JK20] Matthew Jenssen and Peter Keevash.  Homomorphisms from the torus.  arXiv preprint arXiv:2009.08315, 2020.
  * [JP20] Matthew Jenssen and Will Perkins.  Independent sets in the hypercube revisited.  Journal of the London Mathematical Society, 102(2):645–669, 2020\.
  * [JPP21a] Matthew Jenssen, Will Perkins, and Aditya Potukuchi.  Approximately counting independent sets in bipartite graphs via graph containers.  arXiv preprint arXiv:2109.03744, 2021.
  * [JPP21b] Matthew Jenssen, Will Perkins, and Aditya Potukuchi.  Independent sets of a given size and structure in the hypercube.  arXiv preprint arXiv:2106.09709, 2021.
  * [Kah01] J. Kahn.  An entropy approach to the hard-core model on bipartite graphs.  Combinatorics, Probability and Computing, 10:219 – 237, 2001.
  * [KJ20] J. Kahn and J.Park.  The number of 4-colorings of the Hamming cube.  Israel Journal of Mathematics, 236(2):629–649, 2020.
  * [Knu98] D.E. Knuth.  The Art of Computer Programming, volume 1-3.  Addison-Wesley Longman Publishing Co., Inc., 1998.
  * [KP19] Jeff Kahn and Jinyoung Park.  The number of maximal independent sets in the Hamming cube.  arXiv preprint arXiv:1909.04283, 2019.
  * [KS83] AD Korshunov and AA Sapozhenko.  The number of binary codes with distance 2.  Problemy Kibernet, 40:111–130, 1983.
  * [Lov75] L. Lovász.  On the ratio of optimal integral and fractional covers.  Discret. Math., 13:383–390, 1975.
  * [Ols84] J. E. Olson.  On the sum of two sets in a group.  Journal of Number Theory, 18:110–120, 1984.
  * [Par21] Jinyoung Park.  Note on the number of balanced independent sets in the Hamming cube.  arXiv preprint arXiv:2103.11198, 2021.
  * [Pet14] G. Petridis.  The plünnecke–ruzsa inequality: An overview.  In Combinatorial and Additive Number Theory, pages 229–241. Springer New York, 2014.
  * [Pl70] Helmut Plünnecke.  Eine zahlentheoretische anwendung der graphentheorie.  Journal für die reine und angewandte Mathematik, 243:171–183, 1970.
  * [Ruz89] Imre Z Ruzsa.  An application of graph theory to additive number theory.  Scientia, Ser. A, 3(97-109):9, 1989.
  * [Ruz90] Imre Z Ruzsa.  Addendum to: An application of graph theory to additive number theory.  Scientia Ser. A, 4:93–94, 1990.
  * [Sap87] AA Sapozhenko.  On the number of connected subsets with given cardinality of the boundary in bipartite graphs.  Metody Diskret Analiz, 45:42–70, 1987.
  * [Sas21] Igal Sason.  A generalized information-theoretic approach for bounding the number of independent sets in bipartite graphs.  Entropy, 23(3), 2021.
  * [SSSZ19] Ashwin Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao.  The number of independent sets in an irregular graph.  Journal of Combinatorial Theory, Series B, 138:172–195, 2019.
  * [Ste74] S. Stein.  Two combinatorial covering theorems.  J. Comb. Theory, Ser. A, 16:391–397, 1974.
  * [Zha10] Y. Zhao.  The number of independent sets in a regular graph.  Comb. Probab. Comput., 19:315–320, 2010.

##  Appendix A Connected graphs with many independent sets

In this section, we sketch the construction of a $d$-regular graph on $2n$
vertices which is $(d-1)$-connected and has $2^{n+\Omega(n/d)}$ independent
sets.

Let $n$ and $d$ be such that $(4d-2)|n$ and let $t:=\frac{n}{4d-2}$. For
$i\in\left[t\right]$ let $H_{i}$ be a bipartite graph with bipartition
$(X_{i},Y_{i}\sqcup Z_{i})$ where each $|X_{i}|=2d-2$, and each
$|Y_{i}|=|Z_{i}|=d$ such that the following properties hold for each $i$:

  * 1.

$d(u)=d$ for $u\in X_{i}$.

  * 2.

$d(v)=d-1$ for $v\in Y_{i}\cup Z_{i}$.

  * 3.

$H_{i}$ is $(d-1)$-connected.

Let $G$ be a graph obtained by placing a matching between $Z_{i}$ and
$Y_{(i+1)\mod t}$ for each $i\in\left[t\right]$.

We have that $G$ is a $d$-regular $(d-1)$-connected bipartite graph on $2n$
vertices.

Let $L_{i}:=X_{i}$ if $i$ is odd and $Y_{i}\cup Z_{i}$ if $i$ is even.
Similarly, let $R_{i}:=Y_{i}\cup Z_{i}$ if $i$ is odd and $X_{i}$ if $i$ is
even.

We say _interval_ of $[t]$ to mean a subset of consecutive integers. Let
$S\subseteq[t]$ be a collection of $c$ distinct intervals where each interval
starts and ends on a distinct odd number. Suppose that $c=\delta t$ for some
fixed (TBD) constant $\delta$. Define

$M(S):=\bigcup_{i\in S}L_{i}\cup\bigcup_{i\not\in S}R_{i}$

######  Claim 26.

For each such $S$, $M(S)$ is a maximal independent set of size at least
$n-2c$.

###### Proof.

Let $C\subset S$ be an interval that starts and ends on an odd number, and let
$X=\bigcup_{i\in C}L_{i}$. From the construction of $G$, have
$N(X)=\bigcup_{i\in C}R_{i}$, and so

$N\left(\bigcup_{i\in S}L_{i}\right)=\bigcup_{i\in S}R_{i}.$

Therefore, $\bigcup_{i\in S}L_{i}\cup\bigcup_{i\not\in S}R_{i}$ is a maximal
independent set.

Moreover, from construction, we have $|N(X)|=|X|+2$. Therefore,

$\left|N\left(\bigcup_{i\in S}L_{i}\right)\right|=\left|\bigcup_{i\in
S}L_{i}\right|+2c,$

and so $\left|\bigcup_{i\not\in S}R_{i}\right|=n-\left|\bigcup_{i\in
S}L_{i}\right|-2c$, which completes the proof. ∎

There are at least $\binom{t/2}{2c}\geq 2^{\Omega(\log(1/\delta))c}$ such
$S$’s obtained by choosing the endpoints of the $c$ intervals. Let

$I(S):=\\{I\in\mathcal{I}(G)~{}|~{}\forall i\in S,~{}L_{i}\cap
I\neq\emptyset~{}\text{and }\forall i\not\in S,~{}R_{i}\cap
I\neq\emptyset\\}.$

For distinct $S_{1}$, $S_{2}$, we have that $I(S_{1})\cap I(S_{2})=\emptyset$,
and so

$i(G)\geq\sum_{S}|I(S)|.$

With this in mind, we have

$\displaystyle|I(S)|$ $\displaystyle=\prod_{i\in
S}\left(2^{|L_{i}|}-1\right)\cdot\prod_{i\not\in S}\left(2^{|R_{i}|}-1\right)$
$\displaystyle=\prod_{i\in
S}2^{|L_{i}|}\left(1-\frac{1}{2^{|L_{i}|}}\right)\cdot\prod_{i\not\in
S}2^{|R_{i}|}\left(1-\frac{1}{2^{|R_{i}|}}\right)$
$\displaystyle\geq\left(\prod_{i\in S}2^{|L_{i}|}\cdot\prod_{i\not\in
S}2^{|R_{i}|}\right)\cdot\left(1-\frac{1}{2^{d}}\right)^{t}$
$\displaystyle\geq 2^{n-2c-O\left(\frac{t}{2^{d}}\right)}$

distinct independent sets for a small enough $\delta$, and so

$\displaystyle i(G)$ $\displaystyle\geq\sum_{S}|I(S)|$ $\displaystyle\geq
2^{\Omega(\log(1/\delta)c)}\cdot 2^{n-2c-O\left(\frac{t}{2^{d}}\right)}$
$\displaystyle=2^{n+\Omega(c)}$
$\displaystyle=2^{n+\Omega\left(\frac{n}{d}\right)}$

for a small enough $\delta$.

##  Appendix B Cayley graphs on $\mathbb{Z}_{2n}$

Here, we describe a Cayley graph on $2n$ vertices, degree $(2-o(1))\log n$ and
$\omega(2^{n})$ independent sets.

Fix an $\epsilon>0$. Take $\Gamma$ to be a Cayley graph over $\mathbb{Z}_{2n}$
with the generator set $\\{-d+2i~{}|~{}0\leq i\leq d\\}$ for any odd integer
$d\geq(1+\epsilon)\log n$. Let $X$ and $Y$ be the sides of the bipartite
graph, with $|X|=|Y|=n$. Observe that $X$ and $Y$ are the cosets of the
subgroup of order $n$, i.e., $X$ and $Y$ partition $\mathbb{Z}_{2n}$ into
‘even’ and ‘odd’ elements respectively.

Observe that for each small $2$-linked set $A\subseteq X$, we have that
$G=N(A)$ is just an arithmetic progression of common difference $2$. Thus, we
can define the _start_ and _end_ of $G$ as the first and the $|G|$’th element
respectively in this progression. Moreover, $|G|=|[A]|+d$.

Enumerating the number of small $2$-linked $A$’s such that $|[A]|=a$ and
$|G|=g$ where $g-a=d$ can be done as follows: Let $u,v\in[A]$ be the vertices
that cover the _start_ and _end_ of $G$. Observe that every vertex in
$G\setminus(N(u)\cup N(v))$ has at least $d$ neighbors in $[A]$. Thus a
uniformly random subset of $[A]$ covers $G\setminus(N(u)\cup N(v))$ with
probability at least $(1-n\cdot 2^{-d})=(1-o(1))$. Thus at least $(1/4-o(1))$
fraction of subsets of $[A]$ have $G$ as their neighborhood. Thus we have

$\mathcal{G}(a,g)=\begin{cases}\Theta\left(n\cdot 2^{g-d}\right)&\text{if
$g-a=d$}\\\ 0&\text{otherwise}.\end{cases}$

One may verify that plugging this bound in the proof of Theorem 1 gives that
$i(\Gamma)\leq 2^{n+1}(1+o(1))$ whenever $d\geq(2+\epsilon)\log n$.

When $d\leq(2-\epsilon)\log n$ we have:

$\displaystyle i(\Gamma)$ $\displaystyle\geq\sum_{A\subseteq
X,~{}\text{small}}2^{n-|N(A)|}$ $\displaystyle=2^{n}\sum_{A\subseteq
X,~{}\text{small}}2^{-N(A)}$ $\displaystyle\geq
2^{n}\left(1+\sum_{\begin{subarray}{c}\emptyset\neq A\subseteq
X,~{}\text{small}\\\ 2-\text{linked}\end{subarray}}2^{-N(A)}\right)$
$\displaystyle\geq\Omega\left(2^{n}\cdot\left(\sum_{g=d}^{n}n\cdot
2^{-d}\right)\right)$ $\displaystyle=\omega\left(2^{n}\right).$