Definition 4.2.1.
Given graphs \(H\) and \(G\text{,}\) a homomorphism from \(H\) to \(G\) is a function \(f:V(H)\to V(G)\) such that \(f(u)f(v)\in E(G)\) whenever \(uv\in E(H)\text{.}\)
Section 4.2 Supersaturation for Quadrangles
Theorem 3.3.10 (or Theorem 3.4.1) implies that the Turán density of any bipartite graph is zero, and so if \(G\) is a graph with \(\Omega(n^2)\) edges and sufficiently many vertices, then it must contain every small bipartite graph as a subgraph. Our focus in this section is on obtaining a sharp bounds on the number of copies of \(C_4\) in a graph with \(\Omega(n^2)\) edges, akin to the Goodman Bound proved in the previous section. Rather than counting “copies” of \(C_4\) in the way that we have been so far, it will be convenient to instead count “homomorphisms” of \(C_4\text{.}\) Consider the following definition.
“Supersaturated quadrangles.”
Definition 4.2.2.
Let Hom(H,G) be the set of all homomorphisms from \(H\) to \(G\) and define \(\hom(H,G)=|\Hom(H,G)|\text{.}\)
Definition 4.2.3.
Given graphs \(H\) and \(G\text{,}\) the homomorphism density of \(G\) in \(H\) is the quantity \(t(H,G)\) defined by
\begin{equation*}
t(H,G):= \frac{\hom(H,G)}{|V(G)|^{|V(H)|}}\text{.}
\end{equation*}
Note that \(|V(G)|^{|V(H)|}\) is nothing more than the number of functions from \(V(H)\) to \(V(H)\text{;}\) thus, \(t(H,G)\) can be equivalently interpreted as the probability that a random function \(f:V(H)\to V(G)\) is a homomorphism. It is time for a few examples.
Example 4.2.4.
For any graph \(G\text{,}\) a homomorphism from \(K_2\) to \(G\) is nothing more than a mapping \(f:V(K_2)\to V(G)\) such that the two vertices in the image of \(f\) are adjacent. Given any edge \(uv\) of \(G\text{,}\) there are precisely two homomorphisms from \(K_2\) to \(G\) whose image is \(\{u,v\}\text{.}\) Therefore,
\begin{equation*}
t(K_2,G) = \frac{2|E(G)|}{|V(G)|^2}\text{.}
\end{equation*}
Looking back to the statement of Theorem 4.1.1, we see that \(t(K_2,G)\) is precisely the value of \(p\) in the statement.
Example 4.2.5.
Similarly to Example 4.2.4, for any graph \(G\text{,}\) the number of homomorphisms from \(K_3\) to \(G\) is \(6\) times the number of triangles in \(G\text{.}\) Thus,
\begin{equation*}
t(K_3,G) = \frac{6(\#\text{ of triangles in } G)}{|V(G)|^3}\text{.}
\end{equation*}
Observation 4.2.6.
Combining Examples 4.2.4 and Example 4.2.5, we see that Theorem 4.1.1 can be restated rather elegantly as
\begin{equation*}
t(K_3,G)\geq t(K_2,G)\cdot (2t(K_2,G)-1)
\end{equation*}
for every graph \(G\text{.}\)
Let us briefly discuss how the homomorphism density \(t(H,G)\) relates to counting “copies” of \(H\) in \(G\text{.}\) On one hand, every copy of \(H\) in \(G\) gives us at least one homomorphism from \(H\) to \(G\) by simply mapping \(H\) to that copy. The other direction is not quite so immediate. Of course, an injective homomorphism from \(H\) to \(G\) gives us a copy of \(H\) in \(G\text{,}\) but not all homomorphisms are injective. However, the number of non-injective homomorphisms from \(H\) to \(G\) is always \(O\left(|V(G)|^{|V(H)|-1}\right)\text{.}\) So, if the number of vertices in \(G\) is large and \(\hom(H,G)\gg |V(G)|^{|V(H)|-1}\text{,}\) then the contribution of non-injective homomorphisms to \(t(H,G)\) is negligible.
Recall from Theorem 3.4.3 and Example 3.4.4 that \(\ex(n,C_4)=\Theta(n^{3/2})\text{.}\) The corresponding supersaturation question asks: how many \(4\)-cycles must appear in a graph in which the number of edges is significantly greater than \(n^{3/2}\text{?}\) For example, what about a graph with \(\Theta(n^2)\) edges? The following result provides a supersaturation bound of this type.
Theorem 4.2.7. Sidorenko [264].
For any graph \(G\text{,}\)
\begin{equation*}
t(C_4,G)\geq t(K_2,G)^4\text{.}
\end{equation*}
Proof.
We start by proving an analogous bound for the \(3\)-vertex path \(P_3\text{.}\) The number of homomorphisms from \(P_3\) to \(G\) is precisely
\begin{equation*}
\sum_{v\in V(G)}d(v)^2
\end{equation*}
which, by Corollary C.0.6, is at least
\begin{equation*}
\frac{1}{|V(G)|}\left(\sum_{v\in V(G)}d(v)\right)^2 = \frac{4|E(G)|^2}{|V(G)|}\text{.}
\end{equation*}
Thus, dividing both sides by \(|V(G)|^3\) and recalling Example 4.2.4 yields
\begin{equation}
t(P_3,G)\geq t(K_2,G)^2\text{.}\tag{4.2.1}
\end{equation}
We now apply a similar argument to turn this into a lower bound on \(t(C_4,G)\text{.}\) The number of homomorphisms from \(C_4\) to \(G\) is precisely
\begin{equation*}
\sum_{(u,v)\in V(G)^2}|N(u)\cap N(v)|^2
\end{equation*}
which, by Corollary C.0.6, is at least
\begin{equation*}
\frac{1}{|V(G)|^2}\left(\sum_{(u,v)\in V(G)^2}|N(u)\cap N(v)|\right)^2\text{.}
\end{equation*}
Now, the key observation here is that \(\sum_{(u,v)\in V(G)^2}|N(u)\cap N(v)|\) is, in fact, also equal to the number of homomorphisms from \(P_3\) to \(G\text{.}\) Therefore, dividing both sides by \(|V(G)|^4\) and applying (4.2.1) gives us
\begin{equation*}
t(C_4,G)\geq \frac{1}{|V(G)|^6}\left(t(P_3,G)|V(G)|^3\right)^2 = t(P_3,G)^2 \geq t(K_2,G)^4\text{.}
\end{equation*}
This completes the proof.
Let us conclude this section by discussing the tightness of the bound in Theorem 4.2.7. For \(p\in (0,1)\) and large \(n\text{,}\) suppose that we let \(G\) be a graph on \(n\) vertices in which every edge of \(K_n\) is included in \(G\) with probability \(p\text{,}\) independent of all other edges. Then the expected number of edges in \(G\) is
\begin{equation*}
p\binom{n}{2}
\end{equation*}
and so, for \(n\) very large, we expect \(t(K_2,G)\approx p\text{.}\) Now, as we discussed before, if \(n\) is large, then the number of non-injective homomorphisms from \(C_4\) to \(G\) is \(O(n^3)\text{.}\) The expected number of injective homomorphisms is precisely
\begin{equation*}
p^4n(n-1)(n-2)(n-3)
\end{equation*}
and so we expect \(t(C_4,G)\approx p^4\) for large \(n\text{.}\) Thus, in expectation, the bound in Theorem 4.2.7 is approximately an equality for this graph. Thus, one way to interpret Theorem 4.2.7 is that the homomorphism density of \(C_4\) in a graph with a given \(K_2\) density is asymptotically minimized by a random graph of that density.
Here is a YouTube video related to supersaturation for 4-cycles:
