Skip to main content

Section 6.2 Independent Sets in Regular Graphs

A graph \(G\) is d-regular if every vertex of \(G\) has degree \(d\text{.}\) In this section, we focus on the problem of determining how many independent sets a \(d\)-regular graph can have. After a bit of pondering, one may come up with the following natural example.
described in detail following the image
“A container with a fingerprint.”

Example 6.2.1.

Suppose that \(n\) is a multiple of \(2d\) and consider the graph \(H_{d,n}\) obtained by taking a disjoint union of \(\frac{n}{2d}\) copies of \(K_{d,d}\text{.}\) The number of independent sets in \(K_{d,d}\) is
\begin{equation*} 2^{d+1}-1 \end{equation*}
(pick one side of the bipartition and then pick a subset of that side; subtract one because \(\emptyset\) was counted twice). Therefore, the number of independent sets in \(H_{d,n}\) is
\begin{equation*} \left(2^{d+1}-1\right)^{\frac{n}{2d}}\text{.} \end{equation*}
For large \(d\text{,}\) this is roughly
\begin{equation*} 2^{(1/2+O(1/d))n}\text{.} \end{equation*}
Our goal will be to prove an upper bound on the number of independent sets which is close (but does not quite match) the value achieved in Example 6.2.1. In proving this result, we will use that any set of more than \(n/2\) vertices in a \(d\)-regular graph must contain a reasonably large number of edges.

Proof.

Proof.

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:
  1. Initialize \(C_S:=V(G)\) and \(F_S=\emptyset\text{.}\)
  2. 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.
    1. If \(v_i\notin S\text{,}\) then update \(C_S:=C_S\setminus\{v_i\}\) and go back to Step 2.
    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*}
Recall that, for any \(n\geq1\) (see Proposition 6.2.4 below for a proof),
  1. \(\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).
  1. \(\binom{n}{k-1}\leq \binom{n}{k}\) for \(1\leq k\leq n/2\) and
  2. \(\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*}
Finally, by (6.2.1) and (6.2.2), this is at most
\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}\)
For the sake of completeness, let’s quickly prove the three simple inequalities involving binomial coefficients that we needed in the proof of Theorem 6.2.3.

Proof.

For every subset \(S\) of \([n]\) of cardinality \(k-1\text{,}\) there are \(n-k+1\) elements of \([n]\) that can be added to \(S\) to obtain a subset of \([n]\) of size \(k\text{.}\) Likewise, for every subset of cardinality \(k\text{,}\) there are \(k\) elements that can be removed to get a subset of cardinality \(k-1\text{.}\) Therefore, by double counting,
\begin{equation} (n-k+1)\binom{n}{k-1} = k\binom{n}{k}\text{.}\tag{6.2.6} \end{equation}
So, Statement a holds.
Finally, for Statement b, iterating the bound in (6.2.6) and using the fact that \(\binom{n}{0}=1\) gives us
\begin{equation*} \binom{n}{k}=\frac{n!}{k!(n-k)!}\text{.} \end{equation*}
Therefore,
\begin{equation*} \binom{n}{k} = \prod_{i=0}^{k-1}\frac{n-i}{k-i} \leq\frac{n^k}{k!}\text{.} \end{equation*}
Now, recall that \(e^x = \sum_{n=0}^\infty \frac{x^n}{n!}\) for any \(x\in\mathbb{R}\text{.}\) Thus,
\begin{equation*} e^k=\sum_{n=0}^\infty \frac{k^n}{n!} \geq \frac{k^k}{k!}\text{.} \end{equation*}
Putting these bounds together completes the proof.
A proper \(q\)-colouring of a graph \(G\) is a mapping \(f:V(G)\to \{1,\dots,q\}\) such that if \(uv\in E(G)\text{,}\) then \(f(u)\neq f(v)\text{.}\) In Exercise 11 in Section 6.4, we will follow an argument similar to the proof of Theorem 6.2.3 to prove the following bound on the number of \(q\)-colourings of a \(d\)-regular graph.
Here are a couple of YouTube videos related to this application of the container method: