If number of occurrences of $C_{4}$ is $\frac{1}{2^{4}}n^{4}\pm o\left (n^{4}\right)$ in graph $G_n$ then $|\lambda_{2}\left(G_{n}\right)|=o(n)$

Question

I'm trying to solve the following question:

Let $\left\{ G_{n}\right\}$ be a series of graphs, where every $G_{n}$ is a $d(n)$-regular graph with degree $d(n)=\frac{1}{2}n\pm o(n)$. Let's denote by $C_{4}$ the simple circle on $4$ vertices. $C_{4}$ is said to appear as an uninduced subgraph in $G_{n}$ if there are distinct vertices $v_{1},\ldots,v_{4}\in V\left(G_{n}\right)$ for $\{i,j\}\in E\left(C_{4}\right)$ so $\left\{ v_{i},v_{j}\right\} \in E\left(G_{n}\right)$ (it is possible that $\left\{i.j\right\} \in E\left(C_{4}\right)$ although $\left\{ v_{i},v_{j}\right\} \in E\left(G\right)$). Prove that if the number of occurrences of $C_{4}$ as an uninduced subgraph in $G_{n}$ is $\frac{1}{2^{4}}n^{4}\pm o\left (n^{4}\right)$ then $|\lambda_{2}\left(G_{n}\right)|=o(n)$. (reminder $f=o(g)$ means that $(f/g)\to0$ holds When $n\to\infty$). Tutorial: Use the trace of the appropriate matrix.

In the solution they did (provided by a student but got full score from the professor):

Let $G_{n}=\left(V,E\right)$ be a $d(n)$-regular graph such that $d(n)=\frac{1}{2}n\pm o(n)$ holds. Suppose that the number of occurrences of $C_{4}$ as an uninduced subgraph in $G_{n}$ is $\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)$. Let $A\triangleq A\left(G_{n}\right)$ be the normalized adjacency matrix of the graph $G_{n}$ and let $\lambda_{1},\ldots,\lambda_{n}$ be its eigenvalues (which hold $\lambda_{1}\geq\ldots\geq\lambda_{n}$) which correspond to the objects $\vec{v}_{1},\ldots,\vec{v}_{n}$. According to a theorem, it follows that the eigenvectors of $A^{4}$ are the eigenvectors of $A$ and they correspond to the value $\lambda_{1}^{4},\ldots,\lambda_{n}^{4}$. The trace of a matrix is equal to the sum of its eigenvalues and therefore we will get: $$ \text{tr}\left(A^{4}\right)=\sum_{i=1}^{n}\lambda_{i}^{4} $$ For each $1\leq i\leq n$, we define $C_{4}^{i}$ to be the number of occurrences of a circle (not necessarily simple) of length $4$ over $i$ vertices in the graph $G$. According to a theorem it follows that $\left(A^{4}\right)_{i,j}$ is equal to the number of edges between $i$ and $j$ in the graph $G^{4}$, that is, to the number of different (not necessarily simple) paths, of length $4$ between $i$ and $j$ in the graph $G$. Therefore, we can conclude that The trace of the matrix $A^{4}$ is the number of circles of length $4$. Therefore, we can conclude that: $$ \text{tr}\left(A^{4}\right)=\sum_{i=1}^{4}C_{4}^{i} $$ Calculated according to cases:

• Count $C_{4}^{1}$: count the number of occurrences of a circle of length $4$ across $1$ vertices in graph $G$. Since graph $G$ is a simple graph, it follows that graph $G$ has no self-edges and therefore $C_{4}^{1 }=0$.
• Count $C_{4}^{2}$: Count the number of occurrences of a circle of length $4$ across $2$ vertices in graph $G$. Since graph $G$ is a simple graph, it follows that graph $G$ has no independent edges or multi edges. Therefore the circle must necessarily be of the form $u\to v\to u\to v\to u$. Since the graph $G$ has n vertices it follows that vertex $u$ has $n$ possibilities. Since the graph $G$ is $d$-regular, it follows that each vertex has $d$ neighbors and therefore vertex $v$ has $d$ options, so we get a total of $C_{4}^{2}=nd$.
• Count $C_{4}^{3}$: count the number of occurrences of a circle of length $4$ across $3$ vertices in graph $G$. Since graph $G$ is a simple graph, it follows that graph $G $has no independent edges or multi edges. Therefore the circle must necessarily be of the form $u\to v\to w\to v\to u$. We choose vertex $u$ in n options. Since the graph $G$ is $d$-regular it follows that each vertex has $d$ neighbors and therefore vertex $v$ has $d$ options. Since $u\neq w$ holds and also the graph $G$ is $d$-regular, it follows that vertex $w$ has $d-1$ possibilities. Since $d\leq n$ we get: $$ C_{4}^{3}=n\cdot(d-1)\cdot d\leq n\cdot(n-1)\cdot n=\Theta\left(n^{3}\right)=o\left(n^{4}\right) $$
• Count $C_{4}^{4}$: It's given that $C_{4}^{4}=\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)$.

So we get: $$ \begin{align*} \text{tr}\left(A^{4}\right)&=\sum_{i=1}^{4}C_{4}^{i}=C_{4}^{1}+C_{4}^{2}+C_{4}^{3}+C_{4}^{4}\\&=0+nd+o\left(n^{4}\right)+\left(\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)\right)\\&=nd+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right) \end{align*} $$ Since $\text{tr}\left(A^{4}\right)=\sum_{i=1}^{n}\lambda_{i}^{4}$, we get: $$ \begin{align*} \sum_{i=1}^{n}\lambda_{i}^{4}=nd+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)&\overset{(1)}{\Leftrightarrow}\lambda_{1}^{4}+\lambda_{2}^{4}+\sum_{i=3}^{n}\lambda_{i}^{4}=nd+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)\\&\overset{(1)}{\Leftrightarrow}\lambda_{2}^{4}=nd+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)-\lambda_{1}^{4}-\sum_{i=3}^{n}\lambda_{i}^{4}\\&\overset{(2)}{\Leftrightarrow}\lambda_{2}^{4}=nd+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)-\left(\frac{1}{2}n\pm o(n)\right)^{4}-\sum_{i=3}^{n}\lambda_{i}^{4}\\&\overset{(3)}{\Leftrightarrow}\lambda_{2}^{4}\leq n^{2}+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)-\left(\frac{1}{2}n\pm o(n)\right)^{4}-\sum_{i=3}^{n}\lambda_{i}^{4}\\&\overset{(4)}{\Leftrightarrow}\lambda_{2}^{4}\leq o\left(n^{4}\right)+o\left(n^{4}\right)+\frac{1}{2^{4}}n^{4}\pm o\left(n^{4}\right)-\left(\frac{1}{2^{4}}n^{2}\pm o\left(n^{4}\right)\right)\\&\overset{(5)}{\Leftrightarrow}\lambda_{2}^{4}\leq o\left(n^{4}\right)\\&\overset{(6)}{\Leftrightarrow}|\lambda_{2}|=o\left(n^{4}\right) \end{align*} $$

I have the following questions:

1. Regarding the case of "Count $C_{4}^{3}$" - is the calculation correct? I understand that in this case it's important to get $C_{4}^{3}=o\left(n^{4}\right)$, but is it $C_{4}^{3}=n\cdot(d-1)\cdot d$? Just want to make sure.

2. I don't get the ending. I understand that:

   • reason $(1)$: algebra.
   • reason $(2)$: $\lambda_{1}=d(n)=\frac{1}{2}n\pm o(n)$.
   • reason $(3)$: $d\leq n$.

   But I don't get $(4)$. It looks like that $(4)$ they said that $\left(\frac{1}{2}n\pm o(n)\right)^{4}\geq\left(\left(\frac{1}{2}n\right)^{4}\pm o\left(n^{4}\right)\right)$ and $\sum_{i=3}^{n}\lambda_{i}^{4}\geq0$. I agree with $\sum_{i=3}^{n}\lambda_{i}^{4}\geq0$ (Sum of values in even powers) but why $\left(\frac{1}{2}n\pm o(n)\right)^{4}\geq\left(\left(\frac{1}{2}n\right)^{4}\pm o\left(n^{4}\right)\right)$ is true? In wolfram I see that for every $a,b>0$ it's true that $(a+b)^4\geq a^4+b^4$ but $(a-b)^4\geq (a^4-b^4)$ only if $b>a$. If it's not true - could you please suggest a way to get to the requested output?

Please help me with those two questions.

Answer 1

1. First of all, your understanding is correct, we only need to have $o(n^4)$, regarding the detailed formula of $C_4^3$, what is your concern? To get a 3-node 4-cycle $u \to v \to w \to v \to u$, we have $n$ choices on $u$, then $d$ choices on $v$, then $d - 1$ choices on $w$ since we cannot go back to $u$ at this point, which gives $C_4^3 = nd(d-1)$ as written.

2. Regarding (4), $$(\frac{1}{2}n+o(n))^4 = ((\frac{1}{2}n)^4 + c_{31} (\frac{1}{2}n)^3 o(n) + c_{22} (\frac{1}{2}n)^2 (o(n))^2 + c_{13} (\frac{1}{2}n) (o(n))^3 + (o(n))^4 = (\frac{1}{2}n)^4 + o(n^4),$$ where $c_{ij}$'s are constants (combinatorial coefficients) in the expansion of $(x + y)^4$. I think the key point is that you should keep in mind that each $o(\cdot)$ notation is not a fixed value but it can be any value in the set $o(n^4)$, which might be confusing when you use $O(\cdot)$ or $o(\cdot)$ notations.

By the way, I think the $\Leftrightarrow$'s should be reviewed, maybe using $\Rightarrow$'s is better. Also, some typos can be seen in the question.