Skip to main content

Section 8.3 Lifts of Graphs and Related Tricks

In the previous section, we proved that the independence polynomial of a triangle-free regular graph is maximized by a disjoint union of complete bipartite graphs, but we left open the problem of determining the maximum over all graphs (including those with triangles). In this section, we finish the job. Along the way, we will see a few clever double-counting tricks which are useful for analyzing statistical physics models other than the independence polynomial. Actually, as a warm up, let’s use the results from the previous section to prove a really slick and easy result about the Widom--Rowlinson model from Example 8.1.5. Interestingly, in this case, the maximizer is a disjoint union of cliques. This proof comes from this paper: https://arxiv.org/abs/1606.03718v2.

Proof.

Let \(G\) be any \(d\)-regular graph and consider \(G\times K_2\) where we regard the vertex set of \(K_2\) as being \(\{0,1\}\) so that \(V(G\times K_2)=V(G)\times\{0,1\}\text{.}\) Let \(G'\) be obtained from \(G\) by adding the edges \((v,0)(v,1)\) for all \(v\in V(G)\text{.}\) We claim that
\begin{equation*} \hom(G,W_{\text{WR}}) = |\mathcal{I}(G')|. \end{equation*}
Can you see how to prove this? Now, using the fact that \(G'\) is triangle-free (in fact, it is bipartite) and \((d+1)\)-regular, Corollary 8.2.8 tells us that
\begin{equation*} |\mathcal{I}(G')|\leq |\mathcal{I}(K_{d+1,d+1})|^{2n/2(d+1)} = |\mathcal{I}(K_{d+1,d+1})|^{n/(d+1)}. \end{equation*}
But now, notice that \(K_{d+1}' = K_{d+1,d+1}\text{.}\) So, using the correspondence between \(\hom(G,W_{\text{WR}})\) and \(|\mathcal{I}(G')|\) proved above (but in the opposite direction), we get \(|\mathcal{I}(K_{d+1,d+1})|^{n/(d+1)}=\hom(K_{d+1},W_{\text{WR}})^{n/(d+1)}\text{.}\) Putting it all together completes the proof.

Observation 8.3.2.

Let \(a_\lambda=(\lambda,1,\lambda)\text{.}\) By following the same argument as in the proof of Theorem 8.3.1, I believe (but havent’t checked) that one can get that
\begin{equation*} \hom(G,(a_\lambda,W_{\text{WR}}))\leq \hom(K_{d+1},(a_\lambda,W_{\text{WR}}))^{n/(d+1)} \end{equation*}
for any \(d\)-regular graph \(G\) with \(n\) vertices.
The focus of this section is on applying similar “double-counting tricks” akin to the one used in the proof of Theorem 8.3.1. Let us now settle the problem of maximizing the number of independent sets in a triangle-free graph once and for all. The argument below is due to Zhao [298].

Proof.

We follow the presentation of this proof from this paper of Csikvári https://arxiv.org/abs/1612.01295. We note that \(|\mathcal{I}(G\sqcup G)|=|\mathcal{I}(G)|^2\) and so it suffices to show that \(|\mathcal{I}(G\sqcup G)|\leq |\mathcal{I}(G\times K_2)|\text{.}\) So, to prove the inequality, it suffices show that every graph \(G\) satisfies
\begin{equation*} |\mathcal{I}_k(G\sqcup G)|\leq |\mathcal{I}_k(G\times K_2)| \end{equation*}
where \(\mathcal{I}_k(H)\) is the collection of independent sets of cardinality \(k\) in a graph \(H\text{.}\) If this can be done, then we will be finished by Corollary 8.2.8 since \(G\times K_2\) is triangle-free and has \(2n\) vertices. We view both \(G\sqcup G\) and \(G\times K_2\) as graphs on vertex set \(V(G)\times\{0,1\}\) in the natural way (in the first graph, adjacency is between vertices with the same second coordinate and in the second graph adjacency requires the second coordinate to be different). Order the vertices of \(G\) by \(v_1,\dots,v_n\) in an arbitrary way.
Now, let \(\phi:\mathcal{I}_k(G\sqcup G)\to \{0,1,2\}^{n}\) be a map defined by letting the \(i\)th coordinate of \(\phi(I)\) be equal to \(|I\cap \{(v_i,0),(v_i,1)\}|\) for each \(I\in\mathcal{I}_k(G\sqcup G)\) and \(1\leq i\leq n\text{.}\) That is, \(\phi(I)\) is a vector that records how many times each vertex of \(G\) is “covered” by the independent set \(I\text{.}\) We define \(\psi\) in an analogous way, but where the domain of \(\psi\) is \(\mathcal{I}_k(G\times K_2)\text{.}\) Say that a vector \(z\in \{0,1,2\}^n\) is “good” if for every \(i\) such that \(z_i=2\) we have that \(z_j=0\) for all neighbours \(v_j\) of \(v_i\text{.}\) Let \(Z\) be the set of all good vectors. If you think about it, any vector \(z\) such that \(\phi^{-1}(z)\neq \emptyset\) or \(\psi^{-1}(z)\neq \emptyset\) must be good. See why? Therefore,
\begin{equation*} |\mathcal{I}_k(G\sqcup G)|=\sum_{z\in Z}|\phi^{-1}(z)| \end{equation*}
and, similarly,
\begin{equation*} |\mathcal{I}_k(G\times K_2)|=\sum_{z\in Z}|\psi^{-1}(z)|. \end{equation*}
Given \(z\in Z\text{,}\) let \(k(z)\) be the number of components of the subgraph of \(G\) induced by \(\{v_i: z_i=1\}\text{.}\) We have
\begin{equation*} |\psi^{-1}(z)| \geq 2^{k(z)}. \end{equation*}
Do you see why? On the other hand, for any \(z\in Z\text{,}\)
\begin{equation*} |\phi^{-1}(z)| \leq 2^{k(z)}. \end{equation*}
To see this, think about taking a vertex in one of the components of \(\{v_i: z_i=1\}\) and looking at its preimage under \(\phi\text{.}\) WLOG it is on the “left” side of \(G\sqcup G\text{.}\) Now, look at the neighbours of that vertex in the component. Which side are they on? And so on. Putting these two inequalities together completes the proof.
The proof of Theorem 8.3.3 above actually applies to give an inequality for a more general class of objects called “lifts” which we define next.

Definition 8.3.4.

Given a graph \(G\) and a function \(\ell:E(G)\to \{0,1\}\text{,}\) let \(L(G,\ell)\) be the graph with vertex set \(V(G)\times \{0,1\}\) where \((u,i)\) is adjacent to \((v,j)\) if \(uv\in E(G)\) and \(i\equiv j+\ell(uv)\bmod 2\text{.}\) We call \(L(G,\ell)\) a \(2\)-lift of \(G\text{.}\)

Note 8.3.5.

Observe that, if \(G\) is \(d\)-regular, then so is any \(2\)-lift of \(G\text{.}\)
The most basic \(2\)-lifts are the graphs \(G\sqcup G\text{,}\) which you get by setting \(\ell\equiv 0\text{,}\) and the graph \(G\times K_2\) which you get from setting \(\ell\equiv 1\text{.}\) The argument given in the proof of Theorem 8.3.3 actually generalizes straightforwardly to yield the following.
The technique in the proof of Theorem 8.3.3 is known as the “bipartite swapping trick”. It can be applied in broader settings than just independent sets. In this paper https://arxiv.org/abs/1104.3704, Zhao generalizes the technique a lot, as does Csikvári in this paper https://arxiv.org/abs/1612.01295. A particularly nice result that illustrates the applicability of this method is the following theorem proved (in a more general form) in Lemma 3.4 of https://arxiv.org/abs/1809.09462. This (essentially) generalizes Theorem 8.3.6. The proof below is one that I came up with after failing to understand the others that I read! The idea is similar to the proofs that exist in papers, but it is just explained in a somewhat different way.
NOTE: I have not been able to make this proof work! So, please skip this.

Proof.

To make the notation simpler, let us label the entries of \(W\) as follows:
\begin{equation*} W=\begin{bmatrix}a & c\\ c & b\end{bmatrix}. \end{equation*}
So, the \(\det(W)\geq0\) if and only if \(ab\geq c^2\text{.}\) Now, let us define two more matrices as follows:
\begin{equation*} W_0=\begin{bmatrix}a^2 & ac & ac & c^2\\ ac & ab & c^2 & bc\\ ac & c^2 & ab & bc \\ c^2 & bc & bc & b^2\end{bmatrix}, \end{equation*}
\begin{equation*} W_1=\begin{bmatrix}a^2 & ac & ac & c^2\\ ac & c^2 & ab & bc\\ ac & ab & c^2 & bc \\ c^2 & bc & bc & b^2\end{bmatrix}, \end{equation*}
where we view the rows/columns of \(W_0\) and \(W_1\) as being indexed by the elements of \(\{1,2\}^2\) in the lexicographic order: \((1,1),(1,2),(2,1),(2,2)\text{.}\) E.g., \(W_0(1,2,1,2)\) is the entry on the 2nd row and 2nd column in \(W_0\text{,}\) which is \(ab\text{,}\) whereas \(W_1(1,2,1,2)=c^2\text{.}\) Now, we claim that, for any \(\ell:E(G)\to\{0,1\}\text{,}\)
\begin{equation*} \hom(L(G,\ell),W) = \sum_{f:V(G)\to\{1,2\}^2}\left(\prod_{uv\in E(G)}W_{\ell(uv)}(f(u),f(v))\right). \end{equation*}
Let us explain why this equation is true. Recall that \(V(L)=V(G)\times\{0,1\}\text{.}\) For any function \(g:V(L)\to\{1,2\}\) there is a corresponding function \(f_g:V(G)\to\{1,2\}^2\) obtained by setting \(f_g(v)=(g(v,0),g(v,1))\text{.}\) The correspondence between \(g\) and \(f_g\) is a bijection. The homomorphism density of \(L\) in \(W\) is the sum over all \(g:V(L)\to\{1,2\}\) of the product over all edges of \(g\) of the entry of \(W\) on the row and column corresponding to the images of the endpoints of the edge under \(g\text{.}\) Recall that the edges of \(L\) are of the form \((u,0)(v,0)\) and \((u,1)(v,1)\) where \(uv\in E(G)\) and \(\ell(uv)=0\) and \((u,0)(v,1)\) and \((u,1)(v,0)\) where \(uv\in E(G)\) and \(\ell(uv)=1\text{.}\) So, for each \(uv\in E(G)\text{,}\) the product of the two edges of \(L\) corresponding to \(uv\) depend on the values of \(f_g(u)\) and \(f_g(v)\) and \(\ell(uv)\) in the way described by the matrices \(W_0\) and \(W_1\) (this is worth checking to convince yourself!). So, the above equation for \(\hom(L(G,\ell),W)\) holds (unless I’ve messed something up).
So, now let’s see how to use this to complete the proof. Let’s assume \(\det(W)\geq 0\) or, in other words, \(ab\geq c^2\text{.}\) The proof for non-positive determinant is pretty much the same. Let us take a function \(\ell:E(G)\to\{0,1\}\) and \(f:V(G)\to\{1,2\}^2\) and think about the term of the above sum corresponding to \(f\text{.}\) How does it change if we replace \(\ell\) with the function that maps every edge to zero? Well, the matrices \(W_0\) and \(W_1\) are equal for all of their entries except for the \(2\times2\) submatrix in the middle. So, the only edges whose “contribution” to the term corresponding to \(f\) change are those edges \(uv\) with \(\ell(uv)=1\) and \(f(u),f(v)\in\{(1,2),(2,1)\}\text{.}\) Call these edges “special.” Since we are assuming \(ab\geq c^2\text{,}\) for any special edge \(uv\text{,}\) if \(f(u)=f(v)\) then changing \(\ell\) to the all zero function increases the contribution of that edge from \(c^2\) to \(ab\) and, if \(f(u)\neq f(v)\text{,}\) then it decreases it from \(ab\) to \(c^2\text{.}\) Suppose that we colour an edge \(uv\) of \(G\) blue if it is special and \(f(u)=f(v)\) and red if it is special and \(f(u)\neq f(v)\text{.}\) Note that the red edges must form a bipartite graph, but that there is no such restriction on the blue edges. It feels like it should be possible to exploit this, but I can’t figure out how to do it!!! So, this proof is incomplete...
The next theorem is not really related to counting homomorphisms, but it is another beautiful application of \(2\)-lifts, so let’s prove it. Let \(\mathcal{M}_k(G)\) denote the set of all matchings of cardinality \(k\) in \(G\) and let \(\mathcal{M}(G)=\bigcup_{k=0}^\infty\mathcal{M}_k(G)\text{.}\)

Proof.

Let’s prove the first inequality. The idea is similar to the proof of Theorem 8.3.3. This time, the “good” vectors assign numbers 0, 1 or 2 to the edges of \(G\) depending on how many times that edge is covered. This time, we need to add an additional restriction on “good” vectors that they must have the property that the components of edges of label 1 must form paths or even cycles, or else there is no way to pull it back into a matching in any \(2\)-lift of \(G\text{.}\) Now, any good vector can pull back in exactly \(2^{k(z)}\) ways in \(G\times K_2\) but only at most \(2^{k(z)}\) ways in \(L\) and so we win.
For the second inequality, we follow https://arxiv.org/abs/1406.0766. We note that, since \(G\) is bipartite, every cycle in \(G\) is even. So, in this case, we can define a vector to be “good” if every component of edges labelled 1 forms a path or cycle (without needing to stipulate that the cycle is even, since this follows from bipartiteness). Now its not hard to see that good vector pulls back in \(2^{k(z)}\) ways in \(G\sqcup G\) and at most \(2^{k(z)}\) ways in \(L\text{.}\)
The second assertion in Theorem 8.3.8 (the one about bipartite graphs) has some interesting consequences. As it turns out, it implies that the number of matchings in a \(d\)-regular bipartite graph can be bounded below in terms of the “number of matchings” in an infinite \(d\)-regular tree. Here, we use quotations to signify that, obviously, the number of matchings in such a graph is infinite and so this statement requires a bit of care to make rigorous. One way to make sense of this is to observe that a \(d\)-regular graph of girth at least \(m\) has the same “local structure” as an infinite \(d\)-regular tree up to neighbourhoods of distance \(m/2\text{.}\) So, to make this statement about infinite trees a bit more rigorous, let us explain why the number of matchings in a \(d\)-regular bipartite graph can be bounded below in terms of a graph of high girth. By Theorem 8.3.8, it suffices to show that one can get graphs of arbitrarily high girth by repeatedly taking lifts of \(G\text{.}\) Let \(g(G)\) denote the girth of a graph \(G\text{.}\)

Proof.

First, we remark that any \(2\)-lift \(L\) of a graph \(G\) satisfies \(g(L)\geq g(G)\text{.}\) So, if we let \(k=g(G)\text{,}\) then all we need to do is show that there exists a \(2\)-lift of \(G\) which has strictly fewer \(k\)-cycles than \(G\) does. If we can do this, then we repeatedly apply this until there are no cycles of length \(k\text{,}\) and then until there are no cycles of length \(k+1\text{,}\) and so on.
Choose \(\ell:E(G)\to \{0,1\}\) uniformly at random and consider the \(2\)-lift \(L=L(G,\ell)\) of \(G\text{.}\) Let \(X\) be the random variable that counts the number of \(k\)-cycles in \(L\text{.}\) Since the girth of \(G\) is \(k\text{,}\) every \(k\)-cycle in \(L\) must come from a \(k\)-cycle in \(G\text{;}\) i.e. it can’t come from a shorter cycle. Also, for any \(k\)-cycle in \(G\text{,}\) it can either give rise to two cycles of length \(k\) in \(L\) or one cycle of length \(2k\text{.}\) Interestingly, for any given \(k\)-cylce, each of these events is equally likely; i.e. they both occur with probability \(1/2\text{.}\) This is a little bit subtle, so think about why it is true (Hint: Binomial Theorem). So, if \(N_k\) is the number of \(k\)-cycles in \(G\text{,}\) then
\begin{equation*} \mathbb{E}(X)=\frac{1}{2}\cdot 2N_k = N_k. \end{equation*}
This is enough to conclude that there exists a \(2\)-lift with at most as many \(k\)-cycles as \(G\text{,}\) but we need a strict inequality. To see that it can be made strict, all we need to do is to show that there exists a \(2\)-lift with more than \(N_k\) cycles of length \(k\text{;}\) if this is true, then we know that \(X\) has some probability of being larger than its expected value (which is \(N_k\)) and so it also has some probability of being less than its expected value. But this is easy because \(G\sqcup G\) is a \(2\)-lift of \(G\) that has twice as many cycles of length \(k\) as \(G\) does and so we are done.
Now, if you combine Theorem 8.3.8 and the fact that \(|\mathcal{M}(G\sqcup G)|=|\mathcal{M}(G)|^2\) with Lemma 8.3.9, you get that, if \(G\) is a bipartite \(d\)-regular graph, then
\begin{equation*} |\mathcal{M}(G)|\geq |\mathcal{M}(G_i)|^{1/2^i} \end{equation*}
where \(G_i\) is a bipartite \(d\)-regular graph with \(2^i|V(G)|\) vertices where \(g(G_i)\to\infty\text{.}\) In the “limit” as \(i\to\infty\text{,}\) the local structure of these graphs resembles an infinite \(d\)-regular tree. When speaking about “limits” here, I mean something called Benjamini--Schramm limits, but let’s not go into too much detail about that!
From the results in this section, it may be tempting to speculate that the function \(\hom(G,(a,W))\) might always be maximized among \(d\)-regular graphs by taking \(G\) to be a disjoint union of complete bipartite graphs or cliques. In fact, this exact statement was actually conjectured by Galvin in 2013. However, the following result of Sernau from https://arxiv.org/abs/1510.01833 disproves this.

Proof.

Let \(d+2\leq n\leq 2d-1\) and let \(G\) be any connected \(d\)-regular graph with \(n\) vertices. Note that no such graph can exist for \(d=2\) (because \(2d-1<d+2\)) or \(d=3\) (by handshaking) but it should probably exist for any \(d\geq4\) (I didn’t check).
Observe that \(G\) is not a disjoint union of cliques because it is connected and \(d\)-regular and has more than \(d+1\) vertices. So, by Brooks’ Theorem, \(G\) is \(d\)-colourable. For \(m\in\mathbb{N}\) let \(W_m\) be the adjacency matrix of a disjoint union of \(m\) cliques on \(d\) vertices. We claim that, if \(m\) is large enough, then \(W_m\) satisfies the properties in the theorem. Since \(G\) is \(d\)-colourable, we have
\begin{equation*} \hom(G,W_m)\geq m>0. \end{equation*}
Also, since \(K_{d+1}\) is not \(d\)-colourable, we have
\begin{equation*} \hom(K_{d+1},W_m)=0. \end{equation*}
So, the first inequality in the theorem holds. Now, since \(n<2d\) we can choose \(m\) large enough so that
\begin{equation*} m^{1-\frac{n}{2d}} > \hom(K_{d,d},K_d)^{\frac{n}{2d}}. \end{equation*}
If we rearrange this a bit, it tells us that
\begin{equation*} m > \hom(K_{d,d},K_d)^{\frac{n}{2d}} m^{\frac{n}{2d}} =\left(m\cdot\hom(K_{d,d},K_d)\right)^{\frac{n}{2d}} = \hom(K_{d,d},W_m)^{\frac{n}{2d}}. \end{equation*}
Since we already know that \(\hom(G,W_m)\geq m\text{,}\) this completes the proof.