Supersaturation for Even Cycles

Section 4.3 Supersaturation for Even Cycles

Our next goal is to prove a generalization of Theorem 4.2.7 to all even cycles. As it turns out, the proof that we gave for \(4\)-cycles does not easily generalize to all even cycles (c.f. Challenge Problem 1 in Section 3.7). Instead, we will establish a link between the number of cycles of even length in a graph \(G\) and the eigenvalues of its adjacency matrix and apply some basic linear algebra.

“Spectrum.”

Definition 4.3.1.

Let \(G\) be a graph with vertices \(v_1,\dots,v_n\text{.}\) The adjacency matrix of \(G\text{,}\) denoted \(A_G\text{,}\) is an \(n\times n\) matrix in which the entry in the \(i\)th row and \(j\)th column is \(1\) if \(v_iv_j\in E(G)\) and \(0\) otherwise.

Note that the adjacency matrix of \(G\) depends on the labelling of the vertices. So, it is not unique; i.e. a given graph \(G\) may have many different adjacency matrices.

Figure 4.3.2. A graph \(G\) with vertices labelled \(v_1,,v_5\) and the adjacency matrix of \(G\) with respect to this labelling.

The adjacency relation is symmetric; i.e., if \(u\) is adjacent to \(v\text{,}\) then \(v\) is adjacent to \(u\text{.}\) This implies that adjacency matrices are symmetric, in the sense that \(A_G^T=A_G\) where \(A^T\) is the transpose of a matrix \(A\text{.}\) All of the statements in the following lemma are usually proven in a standard course on linear algebra. Let tr(A) denote the trace of a square matrix \(A\text{;}\) i.e. the sum of its diagonal entries. Given a square matrix \(A\text{,}\) let \(A^1=A\) and \(A_k=A A^{k-1}\) for \(k\geq2\text{.}\) Let \(\langle\cdot,\cdot\rangle\) be the standard inner product on \(\mathbb{R}^n\text{.}\)

Lemma 4.3.3.

Let \(A\) be an \(n\times n\) matrix over \(\mathbb{R}\text{.}\) Let \(\lambda_1,\dots,\lambda_n\in \mathbb{C}\) be the eigenvalues of \(A\text{.}\)

If \(A\) is symmetric, then \(\lambda_1,\dots,\lambda_n\) are real.
(Min-Max Theorem): If \(A\) is symmetric, then \(\lambda_1=\frac{\max_{\vec{v}\neq \vec{0}}\langle \vec{v},A\vec{v}\rangle}{\langle \vec{v},\vec{v}\rangle}\) where \(\lambda_1\) is the largest eigenvalue of \(A\text{.}\)
For \(k\geq1\text{,}\) \(\lambda_1^k,\dots,\lambda_n^k\) are the eigenvalues of \(A^k\text{.}\)
\(\tr(A) = \sum_{i=1}^n\lambda_i\text{.}\)

The key connection between the eigenvalues of \(A_G\) and cycles in \(G\) is given by the following lemma and the corollary which follows it. For \(k\geq1\text{,}\) walk of length \(k\) in a graph is a sequence \(w_1,w_2,\dots,w_{k+1}\) of vertices such that any two consecutive vertices are adjacent.

Lemma 4.3.4.

For all \(k\geq1\text{,}\) and for all \(1\leq i,j\leq n\text{,}\) the \((i,j)\) entry of \(A_G^k\) is equal to the number of walks of length \(k\) in \(G\) which start at \(v_i\) and end at \(v_j\text{.}\)

Proof.

We proceed by induction on \(k\text{.}\) For \(k=1\text{,}\) the result is trivial as there is a walk of length \(1\) from \(v_i\) to \(v_j\) if and only if they are adjacent.

Now, for \(k\geq2\text{,}\) the \((i,j)\) entry of \(A_G^k\) is the sum over all \(1\leq \ell\leq n\) of the \((i,\ell)\) entry of \(A_G^{k-1}\) multiplied by the \((\ell,j)\) entry of \(A_G\text{.}\) Thus, by induction, the \(\ell\)th term counts the number of walks of length \(k-1\) from \(v_i\) to \(v_\ell\) times the number of walks of length \(1\) from \(v_\ell\) to \(v_j\text{.}\) That is, it counts walks of length \(k\) from \(v_i\) to \(v_j\) in which the penultimate vertex is \(v_\ell\text{.}\) Therefore, the sum of this quantity over all \(\ell\) counts all walks of length \(k\) from \(v_i\) to \(v_j\) and we are done.

Denote the vertex set of the cycle \(C_k\) by \(\{u_1,\dots,u_k\}\) where the vertices are listed in the order that they come on the cycle.

Corollary 4.3.5.

For \(k\geq3\text{,}\) the \(i\)th diagonal entry of \(A_G^k\) is equal to the number of homomorphisms \(f\) from \(C_k\) to \(G\) such that \(f(u_1)=v_i\text{.}\)

Proof.

For \(k\geq3\text{,}\) the number of walks of length \(k\) that start and end at \(v_i\) is precisely the number of homomorphisms \(f\) from \(C_k\) to \(G\) such that \(f(u_1)=v_i\text{.}\) Therefore, the result follows from Lemma 4.3.4.

Corollary 4.3.6.

If \(G\) is a graph on \(n\) vertices and \(\lambda_1,\dots,\lambda_n\) are the eigenvalues of its adjacency matrix, then, for every \(k\geq3\text{,}\)

\begin{equation*} t(C_k,G)=\sum_{i=1}^n\left(\frac{\lambda_i}{n}\right)^k\text{.} \end{equation*}

Proof.

By Corollary 4.3.5, we have that

\begin{equation*} \tr(A_G^k)=\hom(C_k,G)\text{.} \end{equation*}

The result now follows by part c and part d of Lemma 4.3.3 and the fact that \(t(C_k,G)=\frac{\hom(C_k,G)}{n^k}\text{.}\)

The key thing about even cycles is that any real number raised to an even exponent is non-negative. Therefore, by Lemma 4.3.3 part a, to get a lower bound on \(t(C_k,G)\text{,}\) it suffices to lower bound the largest eigenvalue. Let’s put this observation into practice.

Theorem 4.3.7. Sidorenko [264].

Let \(k\geq2\text{.}\) For every graph \(G\text{,}\)

\begin{equation*} t(C_{2k},G)\geq t(K_2,G)^{2k}\text{.} \end{equation*}

Proof.

By Corollary 4.3.6,

\begin{equation*} t(C_{2k},G)= \sum_{i=1}^n\left(\frac{\lambda_i}{n}\right)^{2k}\text{.} \end{equation*}

By Lemma 4.3.3 part a, the eigenvalues of \(A_G\) are real. Therefore, since \(2k\) is even, we have

\begin{equation*} t(C_{2k},G)\geq (\lambda_1/n)^{2k}\text{.} \end{equation*}

Let \(\vec{1}=(1,\dots,1)\) be the all-ones vector in \(\mathbb{R}^n\text{.}\) By Lemma 4.3.3 part b,

\begin{equation*} \lambda_1\geq \frac{\langle \vec{1},A_G\vec{1}\rangle}{\langle \vec{1},\vec{1}\rangle} = \frac{2|E(G)|}{n} = t(K_2,G)n\text{.} \end{equation*}

This completes the proof.

Here are a couple of YouTube videos related to supersaturation for even cycles:

Prev Top Next