Fix \(0 \lt \varepsilon\lt 1\text{.}\) Let \(m=m(\varepsilon)\) be an integer chosen large enough so that
\begin{equation}
m\cdot e \lt 2^{\varepsilon m/3}\tag{6.2.1}
\end{equation}
and then let \(d=d(\varepsilon)\) be large enough so that
\begin{equation}
d>\frac{3m}{2\varepsilon}\text{.}\tag{6.2.2}
\end{equation}
Our goal is to show that every \(d\)-regular graph on \(n\) vertices has at most \(2^{(1/2+\varepsilon)n}\) independent sets.
Let \(G\) be any such graph. Fix an arbitrary ordering \(v_1,\dots,v_n\) on the vertices of \(G\text{.}\) For each independent set \(S\) of \(G\text{,}\) we construct a set \(F_S\) called the fingerprint of \(S\) and a set \(C_S\) called the container of \(S\) by applying the following algorithm:
Initialize \(C_S:=V(G)\) and \(F_S=\emptyset\text{.}\)
-
While there exists a vertex in \(C_S\) with at least \(m\) neighbours in \(C_S\text{,}\) let \(v_i\) be a vertex of \(C_S\) such that \(|N(v_i)\cap C_S|\) is maximum and, subject to this, the index \(i\) is minimum.
If
\(v_i\notin S\text{,}\) then update
\(C_S:=C_S\setminus\{v_i\}\) and go back to
Step 2.
If
\(v_i\in S\text{,}\) then update
\(F_S:=F_S\cup\{v_i\}\) and
\(C_S:=C_S\setminus (\{v\}\cup N(v))\) and go back to
Step 2.
When this algorithm terminates, every vertex of
\(C_S\) has at most
\(m\) neighbours in
\(C_S\text{.}\) Therefore, the number of edges within
\(C_S\) is at most
\(|C_S|\cdot m/2 \leq nm/2\text{.}\) Thus, by
Lemma 6.2.2,
\begin{equation}
|C_S|\leq \frac{n}{2} + \frac{n\cdot m}{2d}\text{.}\tag{6.2.3}
\end{equation}
Each time a vertex is added to \(F_S\text{,}\) the cardinality of \(C_S\) decreases by more than \(m\text{.}\) Therefore,
\begin{equation}
|F_S|\leq \frac{n}{m}\text{.}\tag{6.2.4}
\end{equation}
Also, by construction, for every independent set \(S\text{,}\)
\begin{equation}
F_S\subseteq S\subseteq F_S\cup C_S\text{.}\tag{6.2.5}
\end{equation}
This is because every element of \(S\) that was deleted from \(C_S\) was added to \(F_S\text{.}\)
The crucial, but extremely subtle, observation is that any two independent sets \(S\) and \(T\) such that \(F_S=F_T\) must also satisfy \(C_S=C_T\text{.}\) Indeed, if you think through the algorithm, and apply induction, you can see that, if \(F_S=F_T\text{,}\) then the algorithm will select the same vertex in each step and behave in exactly the same way with respect to \(S\) or \(T\text{.}\) So, we can let \(g\) be a function mapping subsets of \(V(G)\) of cardinality at most \(n/m\) to sets of cardinality at most \(n/2 + nm/(2d)\) with the property that
\begin{equation*}
g(F_S) = C_S \text{ for every independent } S\subseteq V(G)\text{.}
\end{equation*}
For each set
\(F\) of cardinality at most
\(n/m\text{,}\) let
\(\mathcal{I}_F\) be the collection of independent sets
\(S\) of
\(G\) such that
\(F_S=F\text{.}\) Then, by
(6.2.3),
(6.2.4) and
(6.2.5), the number of independent sets in
\(G\) is at most
\begin{equation*}
\sum_{F: |F|\leq n/m}|\mathcal{I}_F| \leq\sum_{F: |F|\leq n/m}|\{S\subseteq V(G): F\subseteq S\subseteq g(F)\}
\end{equation*}
\begin{equation*}
= \sum_{F: |F|\leq n/m}\left[\sum_{j=0}^{|g(F)|-|F|}\binom{|g(F)|-|F|}{j}\right]
\end{equation*}
\begin{equation*}
\leq \sum_{i=0}^{n/m} \left[\binom{n}{i}\sum_{j=0}^{n/2-i}\binom{n/2 + nm/2d - i}{j}\right]\text{.}
\end{equation*}
\(\sum_{k=0}^n\binom{n}{k}= 2^n\text{.}\)
Therefore, for any \(i\text{,}\) the “inner summation” can be bounded above as follows
\begin{equation*}
\sum_{j=0}^{n/2-i}\binom{n/2 + nm/2d - i}{j}\leq 2^{n/2+nm/2d}\text{.}
\end{equation*}
The following inequalities are also standard (again, see
Proposition 6.2.4 for proofs).
\(\binom{n}{k-1}\leq \binom{n}{k}\) for \(1\leq k\leq n/2\) and
\(\binom{n}{k}\leq \left(\frac{en}{k}\right)^k\text{.}\)
Therefore,
\begin{equation*}
\sum_{i=0}^{n/m}\binom{n}{i}\leq (n/m+1)\left(\frac{ne}{n/m}\right)^{n/m}=(n/m+1)\left(me\right)^{n/m}
\end{equation*}
and so the number of independent sets in \(G\) is at most
\begin{equation*}
(n/m+1)\left(me\right)^{n/m}2^{n/2 + nm/2d}\text{.}
\end{equation*}
\begin{equation*}
2^{(1/2 + \varepsilon)n}
\end{equation*}
where, here, we also use the fact that
\(n>d > m\) and so, by
(6.2.1), we also have
\(n/m+1 \lt 2^{\varepsilon n/3}\)