A tensor’s spectral bound on the clique number

Chunmeng Liu [email protected]/[email protected] Changjiang Bu [email protected] Academy for Advanced Interdisciplinary Studies, Northeast Normal University, Changchun 130024, PR China College of Mathematical Sciences, Harbin Engineering University, Harbin 150001, PR China

Abstract

In this paper, we study the spectral radius of the clique tensor $\mathcal{A}(G)$ associated with a graph $G$ . This tensor is a higher-order extensions of the adjacency matrix of $G$ . A lower bound of the clique number is given via the spectral radius of $\mathcal{A}(G)$ . It is an extension of Nikiforov’s spectral bound and tighter than the bound of Nikiforov in some classes of graphs. Furthermore, we obtain a spectral version of the Erdős-Simonovits stability theorem for clique tensors based on this bound.

keywords:

Tensor; Spectral radius; Clique number; Stability theorem
AMS classification: 05C50, 05C35

^†^†journal:

1 Introduction

The graphs considered throughout the paper are all simple. A clique is a subset of vertices within a graph that forms a complete subgraph. The clique number of a graph is defined as the size of its largest clique. A clique consisting of $t$ vertices is referred to as a $t$ -clique. The collection of all $t$ -cliques in a graph $G$ is represented by $C_{t}(G)$ , and the count of $t$ -cliques in $G$ is denoted by $|C_{t}(G)|$ .

1.1 Spectral radius and the clique number

For a graph $G$ , let $\rho(G)$ denote the largest eigenvalue of its adjacency matrix, which is also called the spectral radius of $G$ . The research on the matrix’s spectral bounds of clique numbers has yielded numerous significant results. For spectral bounds of the adjacency matrix, refer to [1, 2, 3]. For the Laplacian matrix’s spectral bounds, see [4] and for the signless Laplacian matrix’s spectral bounds, see [5]. In this paper, we obtain a bound for the clique number via the tensor’s spectra.

An order $m$ dimension $n$ complex tensor $\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{m}})$ is a multidimensional array comprising $n^{m}$ entries, where each index $i_{j}=1,2,\cdots,n$ for $j=1,2,\cdots,n$ . In 2005, Qi [6] and Lim [7] independently introduced the concept of eigenvalues for tensors. Recently, the authors [8] proposed the $t$ -clique tensor of a graph. Specifically, the $2$ -clique tensor is the adjacency matrix.

Definition 1.1.

[8] Let $G$ be an $n$ -vertex graph. An order $t$ and dimension $n$ tensor $\mathcal{A}(G)=(a_{i_{1}i_{2}\cdots i_{t}})$ is called the $t$ -clique tensor of $G$ , if

\displaystyle a_{i_{1}i_{2}\cdots i_{t}}=\begin{cases}\frac{1}{(t-1)!},&\{i_{1},\cdots,i_{t}\}\in C_{t}(G).\\ 0,&otherwise.\end{cases}

The maximum modulus of all eigenvalues of the $t$ -clique tensor of graph $G$ is referred to as the $t$ -clique spectral radius of $G$ , denoted by $\rho_{t}(G)$ . When $t=2$ , it simplifies to the spectral radius of the adjacency matrix of $G$ .

In this paper, we give a bound for the clique number in terms of $t$ -clique spectral radius. For two nonnegative integers $z$ and $s$ , let $\binom{z}{s}=\begin{cases}\frac{z!}{s!(z-s)!},&z\geq s.\\ 0,&z<s.\end{cases}$

Theorem 1.2.

For a graph $G$ , let $\omega$ be the clique number of $G$ . Then

\displaystyle\rho_{t}(G)\leq\frac{t}{\omega}\binom{\omega}{t}^{\frac{1}{t}}|C_{t}(G)|^{\frac{t-1}{t}}.

Moreover, if $G$ is a complete regular $\omega$ -partite graph for $\omega\geq t\geq 2$ , then the equality is achieved in the above inequality.

In the case of $t=2$ , Theorem 1.2 is a result of Nikiforov [9]. In Section 3, we will show that our bound tighter than Nikiforov’s bound in some classes of graphs and Theorem 1.2 implies that a Turán-type result of Erdős [10].

1.2 High-order spectral Turán problem

Let $\mathcal{F}$ denote a family of $n$ -vertex graphs that contain no isolated vertices. A graph is called $\mathcal{F}$ -free if it does not contain any graph from $\mathcal{F}$ as a subgraph. We denote by $ex(n,\mathcal{F})$ the maximum number of edges in an $\mathcal{F}$ -free graph on $n$ vertices. The study of $ex(n,\mathcal{F})$ is an important topic in extremal graph theory. There have been many classical results, such as Mantel’s theorem [11], Turán’s theorem [12], Erdős-Stone-Simonovits theorem [13, 14] and [15] for a survey.

We write $ex_{\rho}(n,\mathcal{F})$ for the maximum spectral radius over all $\mathcal{F}$ -free graphs on $n$ vertices. The problem of determining $ex_{\rho}(n,\mathcal{F})$ is referred to as the spectral version of the Turán problem. Many classical Turán-type results have been extended to their spectral versions, for example, spectral Mantel’s theorem [16], spectral Turán’s theorem [17], spectral Erdős-Stone-Bollobás theorem [18] and for some further results see [19, 20, 21, 22].

In this paper, we consider the high-order spectral Turán problem, which involves determining the maximum $t$ -clique spectral radius over all $\mathcal{F}$ -free graphs on $n$ vertices. In [8], the authors obtained the maximum $r$ -clique spectral radius over all $K_{r+1}$ -free graphs on $n$ vertices, which is the high-order spectral version of Mantel’s theorem. In [23], the authors provided an upper bound for $3$ -clique spectral radius of a $B_{k}$ -free and $K_{2,l}$ -free graph on $n$ vertices.

This paper concentrates on the stability result in the Turán-type problem. A structural stability theorem obtained by Erdős [24] and Simonovits [25], which is called Erdős-Simonovits stability theorem.

Theorem 1.3.

[24, 25] Let $H$ be a graph with the chromatic number $\chi(H)=r+1>2$ . For every $\epsilon>0$ , there exist $\delta>0$ and $n_{0}$ such that if $G$ is an $H$ -free graph on $n\geq n_{0}$ vertices and $|C_{2}(G)|\geq\left(1-\frac{1}{r}-\delta\right)\frac{n^{2}}{2}$ , then $G$ can be obtained from $T_{r}(n)$ by adding and deleting at most $\epsilon n^{2}$ edges.

In 2009, Nikiforov [26] proved a spectral version of Erdős-Simonovits stability theorem.

Theorem 1.4.

[26] Let $H$ be a graph with $\chi(H)=r+1>2$ . For every $\epsilon>0$ , there exist $\delta>0$ and $n_{0}$ such that if $G$ is an $H$ -free graph on $n\geq n_{0}$ vertices and $\rho(G)\geq\left(1-\frac{1}{r}-\delta\right)n$ , then $G$ can be obtained from $T_{r}(n)$ by adding and deleting at most $\epsilon n^{2}$ edges.

In this paper, we extend Theorem 1.4 to the $t$ -clique spectral version based on Theorem 1.2.

Theorem 1.5.

Let $H$ be a graph with $\chi(H)=r+1>t\geq 2$ . For every $\epsilon>0$ , there exist $\delta>0$ and $n_{0}$ such that if $G$ is an $H$ -free graph on $n\geq n_{0}$ vertices and $\rho_{t}(G)\geq\left(\binom{r-1}{t-1}\left(\frac{1}{r}\right)^{t-1}-\delta\right)n^{t-1}$ , then $G$ can be obtained from $T_{r}(n)$ by adding and deleting at most $\epsilon n^{2}$ edges.

The remainder of this paper is organized as follows: In Section 2, we introduce some definitions and lemmas required for the proofs. In Section 3, we present proofs of the conclusions of this paper along with some remarks.

2 Preliminaries

For an order $m$ dimensional $n$ complex tensor $\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{m}})$ , if there exist a complex number $\lambda$ and a nonzero complex vector $x=(x_{1},\ldots,x_{n})^{T}$ satisfy

\displaystyle\lambda x_{i}^{m-1}=\sum_{i_{2},\ldots,i_{m}=1}^{n}a_{ii_{2}\cdots i_{m}}x_{i_{2}}\cdots x_{i_{m}}\ (i=1,2,\cdots,n),

(1)

then $\lambda$ is called an eigenvalue of $\mathcal{A}$ and $x$ is called an eigenvector of $\mathcal{A}$ associated with $\lambda$ (refer to [6] for further details). A tensor $\mathcal{A}$ is termed symmetric if its entries remain invariant under any permutation of their indices. Furthermore, if all entries of a tensor $\mathcal{A}$ are nonnegative, then $\mathcal{A}$ is referred to as a nonnegative tensor.

Lemma 2.6.

[27] Let $\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{m}})$ be an order $m$ dimension $n$ symmetric nonnegative tensor. The spectral radius of $\mathcal{A}$ is equal to

\displaystyle\max\left\{\sum_{i_{1},i_{2},\cdots,i_{m}=1}^{n}a_{i_{1}\cdots i_{m}}x_{i_{1}}\cdots x_{i_{m}}:\sum_{i=1}^{n}x_{i}^{m}=1,(x_{1},x_{2},\cdots,x_{n})^{T}\in\mathbb{R}_{+}^{n}\right\},

where $\mathbb{R}_{+}^{n}$ denotes the set of all $n$ -dimensional vectors with nonnegative components.

Lemma 2.7.

[8] For a graph $G$ on $n$ vertices, we have

\displaystyle|C_{t}(G)|\leq\frac{n}{t}\rho_{t}(G).

(2)

Furthermore, if the number of $t$ -cliques containing vertex $i$ is the same for all $i\in V(G)$ , then equality holds in (2).

Lemma 2.8.

[28] Let $\epsilon$ be an arbitrary positive number, and let $G$ be an $H$ -free graph on $n$ vertices. There exists a positive number $n_{0}$ such that for $n>n_{0}$ , one can remove less than $\epsilon n^{2}$ edges from $G$ so that the remaining graph is $K_{r+1}$ -free, where $r+1=\chi(H)$ .

Lemma 2.9.

[29] Let $G$ be an $n$ -vertex $K_{r+1}$ -free graph and let $r\geq t\geq s\geq 1$ . Then

\displaystyle\left(\frac{|C_{t}(G)|}{\binom{r}{t}}\right)^{\frac{1}{t}}\leq\left(\frac{|C_{s}(G)|}{\binom{r}{s}}\right)^{\frac{1}{s}}.

In our proofs, we will use Hölder’s inequality, which is for two nonnegative vectors $x=(x_{1},\ldots,x_{n})^{T}$ and $y=(y_{1},\ldots,y_{n})^{T}$ . If the positive numbers $p$ and $q$ satisfy $\frac{1}{p}+\frac{1}{q}=1$ , then

\displaystyle\sum_{i=1}^{n}x_{i}y_{i}\leq\left(\sum_{i=1}^{n}x_{i}^{p}\right)^{\frac{1}{p}}\left(\sum_{i=1}^{n}y_{i}^{q}\right)^{\frac{1}{q}}

with equality holding if and only if $x$ and $y$ are proportional. And Maclaurin’s inequality, which states that for a nonnegative vector $x=(x_{1},\ldots,x_{n})^{T}$ , the following holds for each $k\in\{1,2,\ldots,n\}$ ,

\displaystyle\frac{x_{1}+\cdots+x_{n}}{n}\geq\left(\frac{\sum\limits_{1\leq i_{1}<\cdots<i_{k}\leq n}x_{i_{1}}\cdots x_{i_{k}}}{\binom{n}{k}}\right)^{\frac{1}{k}},

the equality holds if and only if $x_{1}=\cdots=x_{n}$ .

3 The proof of Theorem

To prove Theorem 1.2, we give the following conclusion, which is a high-order extension of the Motzkin-Straus theorem [30]. For a graph $G$ on $n$ vertices, let

\displaystyle\mu_{t}(G)=\max\left\{\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}:\sum_{i=1}^{n}x_{i}=1,(x_{1},\cdots,x_{n})^{T}\in\mathbb{R}_{+}^{n}\right\},

where $\mathbb{R}_{+}^{n}$ is the set of all $n$ -dimensional nonnegative vectors.

Lemma 3.10.

Let $G$ be a graph with clique number $\omega$ and let $t\leq\omega$ . Then

\displaystyle\mu_{t}(G)=\binom{\omega}{t}\omega^{-t}.

Proof.

Let $G$ be a graph consisting of an $\omega$ -clique and $n-\omega$ isolated vertices. Let $x_{1}=x_{2}=\cdots=x_{\omega}=\frac{1}{\omega}$ and $x_{\omega+1}=\cdots=x_{n}=0$ . Then

\displaystyle\mu_{t}(G)\geq\binom{\omega}{t}\omega^{-t}.

Suppose that $x=(x_{1},x_{2},\cdots,x_{n})^{T}$ is a vector chosen such that the expression

\displaystyle\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}

achieves its maximum value, and that $x$ contains the minimal number of nonzero entries among all such vectors. Let the vector $x$ have exactly $s$ nonzero entries. To prove that $s\leq\omega$ , we proceed by contradiction. Assuming that $s>\omega$ , there exist two nonzero entries $x_{i}$ and $x_{j}$ in $x$ such that the vertices $i$ and $j$ are not adjacent in $G$ . Otherwise, the subgraph induced by the nonzero entries of $x$ would form a clique larger than $\omega$ . Let $S_{G}(v,x)=\frac{\partial\left(\sum\nolimits_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}\right)}{\partial x_{v}}$ for $v=1,2,\cdots,n$ . Therefore, we have

\displaystyle\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}=x_{i}S_{G}(i,x)+x_{j}S_{G}(j,x)+M,

where the monomial in $M$ contains neither $x_{i}$ nor $x_{j}$ . Suppose that $S_{G}(i,x)\geq S_{G}(j,x)$ , the proof for the scenario where $S_{G}(i,x)<S_{G}(j,x)$ would follow a similar approach. Constructing the vector $y=(y_{1},y_{2},\cdots,y_{n})^{T}$ , where

\displaystyle y_{i}=x_{i}+x_{j},\ y_{j}=0,\ y_{m}=x_{m}\ (m\in\{1,2,\cdots,n\}\setminus\{i,j\}).

Obviously, we have $y_{1}+y_{2}+\cdots+y_{n}=1$ and

\displaystyle\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}y_{i_{1}}\cdots y_{i_{t}}-\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}=x_{j}\left(S_{G}(i,x)-S_{G}(j,x)\right).

By the assumption $x_{j}>0$ and $S_{G}(i,x)\geq S_{G}(j,x)$ , we obtain

\displaystyle\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}y_{i_{1}}\cdots y_{i_{t}}-\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}\geq 0.

(3)

If $\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}y_{i_{1}}\cdots y_{i_{t}}-\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}>0$ , this would contradict the choice of $x$ as the vector that maximizes the expression $\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}$ . And if the equality holds in (3), the vector $y$ has $s-1$ nonzero entries, this would contradict the assumption that vector $x$ has the least number of nonzero entries among all vectors that achieve the maximum value of the expression. Thus, we have $s\leq\omega$ . Suppose that $x_{1},x_{2},\cdots,x_{s}$ are all nonzero entries in $x$ . By Maclaurin’s inequality, we obtain

	$\displaystyle\mu_{t}(G)$	$\displaystyle=\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}\leq\sum_{1\leq i_{1}<i_{2}<\cdots<i_{t}\leq s}x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}\leq\binom{s}{t}\left(\frac{1}{s}\sum_{i=1}^{s}x_{i}\right)^{t}$
		$\displaystyle=\binom{s}{t}s^{-t}=\frac{1}{t!}\left(1-\frac{1}{s}\right)\left(1-\frac{2}{s}\right)\cdots\left(1-\frac{t-1}{s}\right)$
		$\displaystyle\leq\frac{1}{t!}\left(1-\frac{1}{\omega}\right)\left(1-\frac{2}{\omega}\right)\cdots\left(1-\frac{t-1}{\omega}\right)=\binom{\omega}{t}\omega^{-t}.$

The proof is complete. ∎

Next, we present the proof of Theorem 1.2.

Proof of Theorem 1.2.

For a graph $G$ , let $\mathcal{A}(G)=(a_{i_{1}i_{2}\cdots i_{t}})$ be the $t$ -clique tensor of $G$ . Let $x=(x_{1},x_{2},\cdots,x_{n})^{T}$ be an nonnegative eigenvector corresponding to $\rho_{t}(G)$ with $x_{1}^{t}+\cdots+x_{n}^{t}=1$ . Then

\displaystyle\rho_{t}(G)=\frac{\sum_{i_{1},\cdots,i_{t}=1}^{n}a_{i_{1}\cdots i_{t}}x_{i_{1}}\cdots x_{i_{t}}}{x_{1}^{t}+\cdots+x_{n}^{t}}=t\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}.

(4)

By Hölder’s inequality, we have

\displaystyle\rho_{t}(G)\leq t\left(\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}1^{\frac{t}{t-1}}\right)^{\frac{t-1}{t}}\left(\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}^{t}x_{i_{2}}^{t}\cdots x_{i_{t}}^{t}\right)^{\frac{1}{t}}.

Since $x_{1}^{t}+\cdots+x_{n}^{t}=1$ , by Lemma 3.10, we obtain

\displaystyle\rho_{t}(G)\leq t|C_{t}(G)|^{\frac{t-1}{t}}\left(\binom{\omega}{t}\omega^{-t}\right)^{\frac{1}{t}}=\frac{t}{\omega}\binom{\omega}{t}^{\frac{1}{t}}|C_{t}(G)|^{\frac{t-1}{t}}.

Let $G$ be a complete regular $\omega$ -partite graph for $\omega\geq t\geq 2$ . The number of $t$ -cliques in $G$ is $|C_{t}(G)|=\omega^{t}\binom{\omega}{t}$ , then

\displaystyle\frac{t}{\omega}\binom{\omega}{t}^{\frac{1}{t}}|C_{t}(G)|^{\frac{t-1}{t}}=\omega^{t-1}\binom{\omega-1}{t-1}.

And each vertex is contained in $\omega^{t-1}\binom{\omega-1}{t-1}$ $t$ -cliques. Thus, we have

\displaystyle\rho_{t}(G)=\omega^{t-1}\binom{\omega-1}{t-1}.

∎

Remark 1.

In [9], Nikiforov prove that

\displaystyle 2|C_{2}(G)|\frac{\omega-1}{\omega}\geq\rho^{2}(G).

(5)

Let $F$ be a unicyclic graph with girth $3$ . The graph $F$ contains a subgraph isomorphic to $K_{3}$ , then $\rho(F)\geq 2$ . By (5), we have the following inequality for the clique number $\omega(F)$ of $F$ ,

\displaystyle\omega(F)\geq 1+\frac{2}{|C_{2}(F)|-2}.

(6)

For the graph $F$ , the $3$ -clique spectral radius $\rho_{3}(F)=1$ . By Theorem 1.2, we get

\displaystyle\omega(F)\geq 3.

(7)

Obviously, the inequality (7) is tighter than (6) when $|C_{2}(F)|$ is larger than $3$ .

In addition, for a $K_{r+1}$ -free graph $F^{\prime}$ on $n$ vertices, by Theorem 1.2 and Lemma 2.7, we have

\displaystyle|C_{t}(F^{\prime})|\leq\frac{n}{t}\frac{t}{r}\binom{r}{t}^{\frac{1}{t}}|C_{t}(F^{\prime})|^{\frac{t-1}{t}}.

Then

\displaystyle|C_{t}(F^{\prime})|\leq\frac{n^{t}}{r^{t}}\binom{r}{t}.

Theorem 1.2 and Lemma 2.7 imply that an upper bound on the number of $t$ -cliques in a $K_{r+1}$ -free graph, a conclusion established in [10].

Proof of Theorem 1.5.

For a graph $H$ with $\chi(H)=r+1\geq 3$ , let $G$ be an $H$ -free graph on $n$ vertices. Let $x=(x_{1},x_{2},\cdots,x_{n})^{T}$ be a nonnegative eigenvector corresponding to $\rho_{t}(G)$ with $x_{1}^{t}+\cdots+x_{n}^{t}=1$ . By (4), we have

\displaystyle\rho_{t}(G)=t\sum_{\{i_{1},i_{2},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}.

For an arbitrary positive number $\epsilon>0$ , let $\epsilon^{\prime}\in\left(0,\min\left\{\frac{\epsilon}{2},\left((t-1)!\epsilon\right)^{\frac{t}{t-1}}\right\}\right]$ . By Lemma 2.8, for a sufficiently large $n$ , we can get a $K_{r+1}$ -free graph $G^{\prime}$ from $G$ by removing less than $\epsilon^{\prime}n^{2}$ edges. This process implies that the number of $t$ -cliques removed from $G$ is at most $\epsilon^{\prime}n^{2}\binom{n-2}{t-2}$ . Let $\hat{G}$ be an $n$ -vertex graph with $C_{t}(\hat{G})=C_{t}(G)\setminus C_{t}(G^{\prime})$ . Then

\displaystyle t\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G)}x_{i_{1}}\cdots x_{i_{t}}=t\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(G^{\prime})}x_{i_{1}}\cdots x_{i_{t}}+t\sum_{\{i_{1},\cdots,i_{t}\}\in C_{t}(\hat{G})}x_{i_{1}}\cdots x_{i_{t}}.

By Lemma 2.6, we obtain

\displaystyle\rho_{t}(G)\leq\rho_{t}(G^{\prime})+\rho_{t}(\hat{G}).

For the graph $\hat{G}$ , since $|C_{t}(\hat{G})|\leq\epsilon^{\prime}n^{2}\binom{n-2}{t-2}$ and by Theorem 1.2,

\displaystyle\rho_{t}(\hat{G})\leq\frac{t}{n}\binom{n}{t}^{\frac{1}{t}}|C_{t}(\hat{G})|^{\frac{t-1}{t}}\leq\left(\frac{t^{t}}{n^{t}}\frac{n^{t}}{t!}\right)^{\frac{1}{t}}\left(\epsilon^{\prime}\frac{n^{t}}{(t-2)!}\right)^{\frac{t-1}{t}}\leq\frac{(\epsilon^{\prime})^{\frac{t-1}{t}}}{(t-1)!}n^{t-1}\leq\epsilon n^{t-1}.

Thus, we get

\displaystyle\rho_{t}(G^{\prime})\geq\rho_{t}(G)-\epsilon n^{t-1}.

For a $K_{r+1}$ -free graph $F$ , by Theorem 1.3, for a positive number $\epsilon^{\prime\prime}\in(0,\frac{\epsilon}{2}]$ , there exist $\delta^{\prime}>0$ and a sufficiently large natural number $n$ such that if $F$ is a graph on $n$ vertices and satisfies $|C_{2}(F)|\geq\left(1-\frac{1}{r}-\delta^{\prime}\right)\frac{n^{2}}{2}$ , then $F$ can be obtained from $T_{r}(n)$ by adding and deleting at most $\epsilon^{\prime\prime}n^{2}$ edges. Let $\delta=\left(\frac{\binom{r-1}{t-1}}{r(r-1)}\delta^{\prime}\right)^{\frac{t-2}{2}}-\epsilon$ . Assume $n$ is a natural number that is sufficiently large such that

\displaystyle\rho_{t}(G^{\prime})\geq\left(\binom{r-1}{t-1}\left(\frac{1}{r}\right)^{t-1}-\delta\right)n^{t-1}.

Then

\displaystyle\rho_{t}(G^{\prime})\geq\left(\binom{r-1}{t-1}\left(\frac{1}{r}\right)^{t-1}-\delta\right)n^{t-1}-\epsilon n^{t-1}=\left(\binom{r-1}{t-1}\left(\frac{1}{r}\right)^{t-1}-\delta-\epsilon\right)n^{t-1}.

The graph $G^{\prime}$ is $K_{r+1}$ -free, by Theorem 1.2, we obtain

\displaystyle\frac{t}{r}\binom{r}{t}^{\frac{1}{t}}|C_{t}(G^{\prime})|^{\frac{t-1}{t}}\geq\rho_{t}(G^{\prime})\geq\left(\binom{r-1}{t-1}\left(\frac{1}{r}\right)^{t-1}-\delta-\epsilon\right)n^{t-1}.

By Lemma 2.9, we have

\displaystyle\frac{t}{r}\binom{r}{t}\left(\frac{|C_{2}(G^{\prime})|}{\binom{r}{2}}\right)^{\frac{t-1}{2}}\geq\frac{t}{r}\binom{r}{t}^{\frac{1}{t}}|C_{t}(G^{\prime})|^{\frac{t-1}{t}}\geq\left(\binom{r-1}{t-1}\left(\frac{1}{r}\right)^{t-1}-\delta-\epsilon\right)n^{t-1}.

Then

	$\displaystyle\|C_{2}(G^{\prime})\|$	$\displaystyle\geq\left(\left(\frac{1}{r}\right)^{t-1}\binom{r}{2}^{\frac{t-1}{2}}-\frac{r}{t}\binom{r}{t}^{-1}\binom{r}{2}^{\frac{t-1}{2}}(\delta+\epsilon)\right)^{\frac{2}{t-1}}n^{2}$
		$\displaystyle\geq\left(\left(\frac{1}{r}\right)^{2}\binom{r}{2}-\binom{r-1}{t-1}^{-1}\binom{r}{2}(\delta+\epsilon)^{\frac{2}{t-1}}\right)n^{2}$
		$\displaystyle=\left(1-\frac{1}{r}-\binom{r-1}{t-1}^{-1}r(r-1)(\delta+\epsilon)^{\frac{2}{t-1}}\right)\frac{n^{2}}{2}=\left(1-\frac{1}{r}-\delta^{\prime}\right)\frac{n^{2}}{2}.$

By Theorem 1.3, the graph $G^{\prime}$ can be obtained from $T_{r}(n)$ by adding and deleting at most $\epsilon^{\prime\prime}n^{2}$ edges. Since we removed $\epsilon^{\prime}n^{2}$ edges from $G$ to $G^{\prime}$ , the graph $G$ can be derived from $T_{r}(n)$ by adding and deleting at most $\epsilon^{\prime}n^{2}+\epsilon^{\prime\prime}n^{2}\leq\epsilon n^{2}$ edges. ∎

Acknowledgement

This work is supported by the National Natural Science Foundation of China (No. 12071097, 12371344), the Natural Science Foundation for The Excellent Youth Scholars of the Heilongjiang Province (No. YQ2022A002) and the Fundamental Research Funds for the Central Universities.

References

[1] H. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B 40 (1986) 113-117.
[2] B. Bollobás, V. Nikiforov, Cliques and the spectral radius, J. Combin. Theory Ser. B 97 (2007) 859-865.
[3] V. Nikiforov, More spectral bounds on the clique and independence numbers, J. Combin. Theory Ser. B 99 (2009) 819-826.
[4] M. Lu, H. Lin, F. Tian, Laplacian spectral bounds for clique and independence numbers of graphs, J. Combin. Theory Ser. B 97 (2007) 726-732.
[5] B. He, Y. Jin, X. Zhang, Sharp bounds for the signless Laplacian spectral radius in terms of clique number, Linear Algebra Appl. 438 (2013) 3851-3861
[6] L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005) 1302-1324.
[7] L.H. Lim, Singular values and eigenvalues of tensors: A variational approach, in: 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005, pp. 129-132.
[8] C. Liu, C. Bu, On a generalization of the spectral Mantel’s theorem, J. Comb. Optim. 46 (2023) 14.
[9] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179-189.
[10] P. Erdős, On the number of complete subgraphs contained in certain graphs, M. Tud. Akad. Mat. Kut. Intéz. Közl. 7 (1962) 459-474.
[11] W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60-61.
[12] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452 (in Hungarian).
[13] P. Erdős, A. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087-1091.
[14] P. Erdős, M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51-57.
[15] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in: Erdős Centennial, Springer, 2013, pp. 169-264.
[16] E. Nosal, Eigenvalues of Graphs, Master’s Thesis, University of Calgary, 1970.
[17] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra Appl. 427 (2007) 183-189.
[18] V. Nikiforov, A spectral Erdős-Stone-Bollobás theorem, Comb. Probab. Comput. 18 (2009) 455-458.
[19] M. Zhai, J. Shu, A spectral version of Mantel’s theorem, Discrete Math. 345 (2022) 112630.
[20] S. Cioabă, D.N. Desai, M. Tait, A spectral Erdős-Sós theorem, SIAM J. Discrete Math. 37 (3) (2023) 2228-2239.
[21] Y. Li, L. Lu, Y. Peng, A spectral Erdős-Rademacher theorem, Adv. in Appl. Math. 158 (2024) 102720.
[22] V. Nikiforov, Some new results in extremal graph theory, in: Surveys in Combinatorics, in: London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 141-181.
[23] C. Liu, J. Zhou, C. Bu, The high order spectral extremal results for graphs and their applications, Discrete Appl. Math. 357 (2024) 209-214.
[24] P. Erdős, Some recent results on extremal problems in graph theory (Results), In: Theory of Graphs (International Symposium Rome, 1966), Gordon and Breach, New York, Dunod, Paris, 1966, pp. 117-123.
[25] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc. Colloq. Tihany, 1966, Academic Press, New York, 1968, pp. 279-319.
[26] V. Nikiforov, Stability for large forbidden subgraphs, J. Graph Theory 62 (4) (2009) 362-368.
[27] L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl. 439 (2013) 228-238.
[28] P. Erdős, P. Frankl, V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (2) (1986) 113-121.
[29] V. Sós, E. Straus, Extremals of functions on graphs with applications to graphs and hypergraphs, J. Combin. Theory Ser. B 32 (1982) 246-257.
[30] T.S. Motzkin, E.G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965) 533-540.