# New proofs of stability theorems on spectral graph problems††thanks: This
work was supported by NSFC (Grant No. 11931002). E-mail addresses:
<EMAIL_ADDRESS>cn (Yǒngtāo Lǐ<EMAIL_ADDRESS>(Yuèjiàn Péng,
corresponding author).

Yongtao Li, Yuejian Peng†
School of Mathematics, Hunan University
Changsha, Hunan, 410082, P.R. China

###### Abstract

Both the Simonovits stability theorem and the Nikiforov spectral stability
theorem are powerful tools for solving exact values of Turán numbers in
extremal graph theory. Recently, Füredi [J. Combin. Theory Ser. B 115 (2015)]
provided a concise and contemporary proof of the Simonovits stability theorem.
In this note, we present a unified treatment for some extremal graph problems,
including short proofs of Nikiforov’s spectral stability theorem and the
clique stability theorem proved recently by Ma and Qiu [European J. Combin. 84
(2020)]. Moreover, some spectral extremal problems related to the $p$-spectral
radius and signless Laplacian radius are also included.

Key words: Turán number; Extremal graph theory; Spectral radius; Graph
stability theorem.

2010 Mathematics Subject Classification. 05C50, 05C35.

##  1 Introduction

Extremal graph theory is one of the significant branches of discrete
mathematics and has experienced an impressive growth during the last few
decades. It deals usually with the problem of determining or estimating the
maximum or minimum possible size of a graph which satisfies certain
requirements, and further characterize the extremal graphs attaining the
bound. Such problems are related to other areas including theoretical computer
science, discrete geometry, information theory and number theory.

We say that a graph $G$ is $F$-free if it does not contain an isomorphic copy
of $F$ as a subgraph. For given $n$, the Turán number of a graph $F$, denoted
by $\mathrm{ex}(n,F)$, is the maximum number of edges in an $n$-vertex
$F$-free graph. An $F$-free graph on $n$ vertices with $\mathrm{ex}(n,F)$
edges is called an extremal graph for $F$.

Let $K_{r+1}$ be the complete graph on $r+1$ vertices. In 1941, Turán [48]
solved the natural question of determining $\mathrm{ex}(n,K_{r+1})$ for $r\geq
2$. Let $T_{r}(n)$ denote the complete $r$-partite graph on $n$ vertices where
its part sizes are as equal as possible. Turán [48] extended a result of
Mantel and obtained that if $G$ is a $K_{r+1}$-free graph on $n$ vertices,
then $e(G)\leq e(T_{r}(n))$, equality holds if and only if $G=T_{r}(n)$. There
are many extensions and generalizations on Turán’s result. In the language of
extremal number, the Turán theorem can be stated as

$\mathrm{ex}(n,K_{r+1})=e(T_{r}(n)).$ (1)

Moreover, we can easily see that
$(1-\frac{1}{r})\frac{n^{2}}{2}-\frac{r}{8}\leq
e(T_{r}(n))\leq(1-\frac{1}{r})\frac{n^{2}}{2}$. It is a cornerstone of
extremal graph theory to understand $\mathrm{ex}(n,F)$ for various graphs $F$;
see [15, 20, 46] for surveys. The problem of determining $\mathrm{ex}(n,F)$ is
usually called the Turán-type extremal problem. The most celebrated extension
of Turán’s theorem always attributes to a result of Erdős, Stone and
Simonovits, although it was proved first in [9], but indeed easily follows
from a result of Erdős and Stone [10].

######  Theorem 1.1 (Erdős–Stone–Simonovits, 1946/1966).

If $F$ is a graph with chromatic number $\chi(F)=r+1$, then

$\mathrm{ex}(n,F)=e(T_{r}(n))+o(n^{2})=\left(1-\frac{1}{r}+o(1)\right)\frac{n^{2}}{2}.$

The Turán theorem implies that every $n$-vertex graph with more than
$(1-\frac{1}{r})\frac{n^{2}}{2}$ edges contains a copy of $K_{r+1}$. The
Erdős–Stone–Simonovits theorem states that for any integer $t$ and
$\varepsilon>0$, then for sufficiently large $n$, every $n$-vertex graph with
at least $(1-\frac{1}{r})\frac{n^{2}}{2}+\varepsilon n^{2}$ edges not only
contains a copy of $K_{r+1}$, but also contains a copy of $K_{r+1}(t)$, the
complete $(r+1)$-partite graph with $t$ vertices in each part.

In 1966, Erdős [12, 13] and Simonovits [45] proved a stronger structural
theorem of Theorem 1.1 and discovered that this extremal problem exhibits a
certain stability phenomenon. Let $G_{1}$ and $G_{2}$ be two graphs which are
defined on the same vertex set. The edit-distance between $G_{1}$ and $G_{2}$,
denoted by $d(G_{1},G_{2})$, is the minimum integer $k$ such that $G_{1}$ can
be obtained from $G_{2}$ by adding or deleting a total number of $k$ edges.
The following structural stability theorem was proved by Erdős [12, 13] and
Simonovits in [45]. This result bounds the edit-distance between $G$ and
$T_{r}(n)$ when $G$ is $F$-free and $e(G)$ is close to
$(1-o(1))\mathrm{ex}(n,F)$.

######  Theorem 1.2 (Erdős–Simonovits, 1966).

Let $F$ be a graph with $\chi(F)=r+1\geq 3$. For every $\varepsilon>0$, there
exist $\delta>0$ and $n_{0}$ such that if $G$ is a graph on $n\geq n_{0}$
vertices, and $G$ is $F$-free such that
$e(G)\geq(1-\frac{1}{r}-\delta)\frac{n^{2}}{2}$, then the edit distance
$d(G,T_{r}(n))\leq\varepsilon n^{2}$.

Roughly speaking, if $G$ is an $n$-vertex $K_{r+1}$-free graph for which
$e(G)$ is close to $e(T_{r}(n))$, then the structure of $G$ must resemble the
Turán graph in an appropriate sense. Over the past twenty years, the stability
theorem has attracted wide public concern and plays an important role in the
development of extremal graph theory.

###  1.1 Spectral extremal graph problems

Let $G$ be a simple graph on $n$ vertices. The _adjacency matrix_ of $G$ is
defined as $A(G)=[a_{ij}]_{n\times n}$ where $a_{ij}=1$ if two vertices
$v_{i}$ and $v_{j}$ are adjacent in $G$, and $a_{ij}=0$ otherwise. We say that
$G$ has eigenvalues $\lambda_{1},\ldots,\lambda_{n}$ if these values are
eigenvalues of the adjacency matrix $A(G)$. Let $\lambda(G)$ be the maximum
value in absolute among the eigenvalues of $G$, which is known as the spectral
radius of graph $G$, that is,

$\lambda(G)=\max\\{|\lambda|:\text{$\lambda$ is an eigenvalue of $G$}\\}.$

By the Perron–Frobenius theorem, the spectral radius of a graph $G$ is
actually the largest eigenvalue of $G$ since the adjacency matrix $A(G)$ is
nonnegative. The spectral radius of a graph sometimes can give some
information about the structure of graphs.

In the classic extremal graph problem, we usually study the maximum or minimum
number of edges that the extremal graphs can have. Correspondingly, we can
study the extremal spectral problem. We define $\mathrm{ex}_{\lambda}(n,F)$ to
be the largest eigenvalue of the adjacency matrix in an $F$-free $n$-vertex
graph, that is,

$\mathrm{ex}_{\lambda}(n,F):=\max\bigl{\\{}\lambda(G):|G|=n~{}\text{and}~{}F\nsubseteq
G\bigr{\\}}.$

In 2007, Nikiforov [29] showed the spectral version of the Turán theorem.

$\mathrm{ex}_{\lambda}(n,K_{r+1})=\lambda(T_{r}(n)).$ (2)

By calculation, we can obtain that
$(1-\frac{1}{r})n-\frac{r}{4n}\leq\lambda(T_{r}(n))\leq(1-\frac{1}{r})n$. It
should be mentioned that the spectral version of the Turán theorem was early
studied independently by Guiduli in his PH.D. dissertation [17, pp. 58–61]
dating back to 1996 under the guidance of László Babai. We remark here that
the proof of Guiduli for the spectral Turán theorem is completely different
from that of Nikiforov [29]. The main idea in his proof [17] reduces the
problem of bounding the largest spectral radius among $K_{r+1}$-free graphs to
complete $r$-partite graphs, then one can show further that the balanced
complete $r$-partite graph attains the maximum value of the spectral radius.
The proof of Nikiforov is more algebraic and relies on a profound theorem from
[28] as well as an old theorem from [51] and [11].

A natural question we may ask is the following: what is the relation between
the spectral Turán theorem and the edge Turán theorem? Does the spectral bound
imply the edge bound of Turán’s theorem? This question was also proposed in
[32]. The answer is positive. It is well-known that
${e(G)}\leq\frac{n}{2}\lambda(G)$, with equality if and only if $G$ is
regular. Although the Turán graph $T_{r}(n)$ is sometimes not regular, but it
is nearly regular. Upon calculation, we can verify that
${e(T_{r}(n))}=\left\lfloor\frac{n}{2}\lambda(T_{r}(n))\right\rfloor$. With
the help of this observation, the spectral Turán theorem implies that

$e(G)\leq\left\lfloor\frac{n}{2}\lambda(G)\right\rfloor\leq\left\lfloor\frac{n}{2}\lambda(T_{r}(n))\right\rfloor=e(T_{r}(n)).$
(3)

Thus the spectral Turán theorem implies the classical Turán theorem.

In 2009, Nikiforov [33] proved the following theorem, which determined the
asymptotic maximum spectral radius of $F$-free graphs for arbitrary graph $F$.
Theorem 1.3 is a spectral analogue of the Erdős–Stone–Simonovits Theorem 1.1.

######  Theorem 1.3 (Nikiforov, 2009).

If $F$ is a graph with chromatic number $\chi(F)=r+1$, then

$\mathrm{ex}_{\lambda}(n,F)=\lambda(T_{r}(n))+o(n)=\left(1-\frac{1}{r}+o(1)\right)n.$

In the same year, Nikiforov [35] proved the corresponding spectral analogue of
the Erdős–Simonovits stability theorem.

######  Theorem 1.4 (Nikiforov, 2009).

Let $F$ be a graph with $\chi(F)=r+1\geq 3$. For every $\varepsilon>0$, there
exist $\delta>0$ and $n_{0}$ such that if $G$ is an $F$-free graph on $n\geq
n_{0}$ vertices and $\lambda(G)\geq(1-\frac{1}{r}-\delta)n$, then the edit
distance $d(G,T_{r}(n))\leq\varepsilon n^{2}$.

Since the Rayleigh formula gives $2e(G)/n\leq\lambda(G)$, the spectral theorem
of Nikiforov is a generalization of the Erdős–Stone–Simonovits theorem.
Moreover, the spectral stability theorem also generalizes the Simonovits
stability theorem. Just like the significance of the classical
Erdős–Simonovits stability theorem, with the development of spectral extremal
graph theory, we believe commonly that the spectral stability theorem will
also play a vital role in solving the spectral extremal problems; see, e.g.,
[5, 6, 24, 8] for recent progress.

###  1.2 Generalized extremal graph problems

Let $k_{s}(G)$ denote the number of copies of $K_{s}$ in $G$. In particular,
we have $k_{1}(G)=v(G)$ and $k_{2}(G)=e(G)$. In 1949, Zykov [51], and Erdős
[11] independently proved an extension of the Turán theorem, which states that
if $G$ is an $n$-vertex $K_{r+1}$-free graph, then $k_{s}(G)\leq
k_{s}(T_{r}(n))$ for every $s=2,3,\ldots,r$, equality holds if and only if $G$
is the Turán graph $T_{r}(n)$. For two graphs $T$ and $F$, the generalized
Turán number  $\mathrm{ex}(n,T,F)$ is defined as the maximum number of copies
of $T$ in an $F$-free graph on $n$ vertices. For example, setting $F=K_{2}$,
the extremal number $\mathrm{ex}(n,K_{2},F)$ is the classical function
$\mathrm{ex}(n,F)$. Under this definition, the result of Zykov and Erdős can
be written as

$\mathrm{ex}(n,K_{s},K_{r+1})=k_{s}(T_{r}(n)).$ (4)

In 2016, Alon and Shikhelman [1] systematically studied the function
$\mathrm{ex}(n,T,F)$ for many various combinations of $T$ and $F$. In
particular, they proved the following theorem.

######  Theorem 1.5 (Alon–Shikhelman, 2016).

If $F$ is a graph with chromatic number $\chi(F)=r+1$, then for every $2\leq
s\leq r$, we have

$\mathrm{ex}(n,K_{s},F)=k_{s}(T_{r}(n))+o(n^{s})=(1+o(1)){r\choose
s}\left(\frac{n}{r}\right)^{s}.$

The following clique version of the stability theorem was proved by Ma and Qiu
[27, Theorem 1.4]. Obviously, taking the case $s=2$, we can see that Theorems
1.5 and 1.6 reduce to Theorems 1.1 and 1.2 respectively.

######  Theorem 1.6 (Ma–Qiu, 2020).

Let $F$ be a graph with $\chi(F)=r+1\geq 3$. For every $\varepsilon>0$, there
exist $\delta>0$ and $n_{0}$ such that if $G$ is an $F$-free graph on $n\geq
n_{0}$ vertices and $k_{s}(G)\geq{r\choose s}(\frac{n}{r})^{s}-\delta n^{s}$
for some $2\leq s\leq r$, then the edit distance $d(G,T_{r}(n))\leq\varepsilon
n^{2}$.

The original proofs of both the classical stability theorem of Erdős and
Simonovits, the spectral stability theorem of Nikiforov and the clique
stability theorem of Ma and Qiu (Theorems 1.2, 1.4 and 1.6, respectively) are
based on the proficient graph structure analysis. In 2015, Füredi [16]
provided a concise and contemporary proof of Theorem 1.2 by applying a result
of Erdős, Frankl and Rödl [14], which is a direct consequence of the Szemerédi
regularity lemma. In 2021, Liu [25] presented short proofs to the stability
results of two extremal hypergraph problems.

In this paper, we study various stability theorems. Motivated by the works of
Füredi and Liu, we shall present an alternative proof of the spectral
stability theorem. Our method shows that the spectral stability theorem can be
deduced from the Erdős–Simonovits stability theorem. Moreover, we shall prove
that the clique stability theorem of Ma and Qiu can also be deduced from the
Erdős–Simonovits stability theorem. Although the spectral version and clique
version seem more stronger than the classical edge version, we show that these
three different versions are equivalent.

##  2 Preliminaries

In this section, we shall introduce some useful lemmas. The first lemma is a
celebrated result of Erdős, Frankl and Rödl [14, Theorem 1.5]. It is a direct
consequence of the Szemerédi regularity lemma and graph embedding lemma.

######  Lemma 2.1 (Erdős–Frankl–Rödl, 1986).

Let $F$ be a graph and $\varepsilon>0$ be an arbitrary number. There is
$n_{0}$ such that if $n\geq n_{0}$ and $G$ is an $n$-vertex $F$-free graph,
then we can remove at most $\varepsilon n^{2}$ edges from $G$ so that the
remaining graph is $K_{r}$-free, where $r=\chi(F)$.

Lemma 2.1 can be extended easily to hypergraphs as an implication of
hypergraph removal lemma. For a $k$-uniform hypergraph $H$, the $s$-blow-up of
$H$, denoted by $H(s)$, is a $k$-uniform hypergraph obtained from $H$ by
replacing each vertex $v\in V(H)$ by an independent set $I_{v}$ of $s$
vertices, say $x_{v}^{1},x_{v}^{2},\ldots,x_{v}^{s}$. If
$\\{v_{1},v_{2},\ldots,v_{k}\\}$ is an edge of $H$, then we define
$\\{x_{v_{1}}^{a_{1}},x_{v_{2}}^{a_{2}},\ldots,x_{v_{k}}^{a_{k}}\\}$ as an
edge of $H(s)$ for all $1\leq a_{1},\ldots,a_{k}\leq s$. That is, $H(s)$ is
obtained from $H$ by replacing each edge of $H$ by a complete $k$-partite
$k$-uniform hypergraph with each part of size $s$.

######  Theorem 2.2.

Let $H$ be a $k$-uniform hypergraph. For every $\varepsilon>0$ and $s\geq 1$,
there exists $n_{0}=n_{0}(H,\varepsilon,s)$ such that if $G$ is an $H(s)$-free
$k$-uniform hypergraph on $n\geq n_{0}$ vertices, then we can remove at most
$\varepsilon n^{k}$ edges from $G$ so that the remaining hypergraph is
$H$-free.

###### Proof.

The proof is a well application of the hypergraph removal lemma, which states
that for every $k$-graph $H$ and every $\varepsilon>0$, there is
$\delta=\delta_{H}(\varepsilon)>0$ such that any graph on $n$ vertices with at
most $\delta n^{h}$ copies of $H$ can be made $H$-free by removing at most
$\varepsilon n^{k}$ edges. Let $G$ be an $H(s)$-free $k$-uniform hypergraph.
First of all, we can see that the number of copies of $H$ is at most
$o(n^{h})$. Otherwise, applying a theorem of Erdős for $k$-partite $k$-graph,
we can prove that $\Omega(n^{h})$ copies of $H$ in $G$ lead to a copy of
$H(s)$ for sufficiently large $n$; see, e.g., [20, Theorem 2.2]. Next,
applying the hypergraph removal lemma, we can remove at most $o(n^{k})$ edges
from $H$ to make it $H$-free. ∎

The following lemma describes a relationship between the number of copies of
$K_{s}$ and $K_{t}$ in a $K_{r+1}$-free graph, where $s,t$ are two integers
less than $r+1$.

######  Lemma 2.3 (Khadzhiivanov [22]; Sós–Straus [47]).

Let $G$ be a $K_{r+1}$-free graph on $n$ vertices. For every $i\in[r]$, let
$k_{i}$ denote the number of copies of $K_{i}$ in $G$. Then

$\left(\frac{k_{r}}{{r\choose
r}}\right)^{1/r}\leq\left(\frac{k_{r-1}}{{r\choose
r-1}}\right)^{1/(r-1)}\leq\cdots\leq\left(\frac{k_{2}}{{r\choose
2}}\right)^{1/2}\leq\left(\frac{k_{1}}{{r\choose 1}}\right)^{1/1}.$

After finishing this paper, Nikiforov [42] told us that Lemma 2.3 was
rediscovered independently by many people in the literature; see [39] for a
short survey including a complete analytical proof and determining the cases
of equality.

Let $G$ be a graph on $n$ vertices with $m$ edges. Let $A$ be the adjacency
matrix of $G$. It is well-known that $2m/n\leq\lambda(G)\leq\sqrt{2m}$, which
is guaranteed by the Rayleigh inequality
$\lambda(G)\geq\bm{1}^{T}A\bm{1}/(\bm{1}^{T}\bm{1})=2m/n$ and
$\lambda(G)^{2}\leq\sum_{i=1}^{n}\lambda_{i}^{2}=\mathrm{tr}(A^{2})=\sum_{i=1}^{n}d_{i}=2m$.
Moreover, we can easily show that

$\lambda(G)\leq\sqrt{2m\left(1-\frac{1}{n}\right)}.$ (5)

Indeed, we observe first that $\sum_{i=1}^{n}\lambda_{i}={\rm tr}(A)=0$ and
$\sum_{i=1}^{n}\lambda_{i}^{2}={\rm tr}(A^{2})=\sum_{i=1}^{n}d_{i}=2m$.
Applying the Cauchy–Schwarz inequality, we obtain
$(2m-\lambda_{1}^{2})(n-1)=(\lambda_{2}^{2}+\cdots+\lambda_{n}^{2})(n-1)\geq(\lambda_{2}+\cdots+\lambda_{n})^{2}=\lambda_{1}^{2}$,
which implies $\lambda_{1}^{2}\leq 2m(1-\frac{1}{n})$.

In 2002, Nikiforov [28] proved a further improvement by applying the
Motzkin–Straus theorem. The conditions when equality holds in Lemma 2.4 was
later determined in [32].

######  Lemma 2.4 (Nikiforov, 2002).

Let $G$ be a graph with $m$ edges. Let $\omega$ be the clique number of $G$,
the size of a largest complete subgraph of $G$. Then

$\lambda(G)\leq\sqrt{2m\Bigl{(}1-\frac{1}{\omega}\Bigr{)}}.$

Moreover, the equality holds if and only if $G$ is a complete bipartite graph
for $r=2$, or a complete regular $r$-partite graph for $r\geq 3$ by adding
some isolated vertices.

Remark. Lemma 2.4 implies that if $G$ is a $K_{r+1}$-free graph with $m$
edges, then $\lambda(G)^{2}\leq{2m(1-\frac{1}{r})}$. On the one hand,
combining with $2m/n\leq\lambda(G)$, we get the Turán theorem
$m\leq(1-\frac{1}{r})\frac{n^{2}}{2}$. On the other hand, using
$m\leq(1-\frac{1}{r})\frac{n^{2}}{2}$, we have
$\lambda(G)\leq(1-\frac{1}{r})n$.

##  3 Main results

###  3.1 Alternative proofs

Nikiforov’s proof of Theorem 1.3 depends on two of his important theorems: the
first theorem investigated the relation between the number of cliques and the
spectral radisu [3], the second theorem states that every graph with many
$r$-cliques contains a large complete $r$-partite subgraph [30]. The proof of
Alon and Shikhelman for Theorem 1.5 applied the graph removal lemma and needed
a proposition [1, Proposition 2.1] to show that the number of copies of
$K_{r+1}$ in $G$ is at most $o(n^{r+1})$.

###### Alternative proof of Theorems 1.3 and 1.5.

Since $\chi(F)=r+1$, we know that the Turán graph $T_{r}(n)$ is $F$-free.
Moreover, we have $\lambda(T_{r}(n))\geq(1-\frac{1}{r})n-\frac{r}{4n}$ and for
$2\leq s\leq r$, $k_{s}(T_{r}(n))=\sum_{0\leq i_{1}\leq\cdots\leq i_{s}\leq
r-1}\prod_{t=1}^{s}\lfloor\frac{n+i_{t}}{r}\rfloor={r\choose
s}(\frac{n}{r})^{s}-o(n^{s})$. Thus the lower bounds in Theorems 1.3 and 1.5
can be witnessed by taking $T_{r}(n)$ as an example. Now, assume that $G$ is
an $n$-vertex $F$-free graph. By Lemma 2.1, we can remove $o(n^{2})$ edges
from $G$ and get a new graph $G^{*}$ which is $K_{r+1}$-free.

On the one hand, we claim that the removal of $o(n^{2})$ edges from $G$ can
only decrease $\lambda(G)$ by at most $o(n)$. Indeed, the Rayleigh inequality
gives $\lambda(G)\leq\lambda(G^{*})+\lambda(G\setminus G^{*})$ and the
inequality (5) implies $\lambda(G\setminus G^{*})\leq\sqrt{2e(G\setminus
G^{*})}=o(n)$. Since $G^{*}$ is $K_{r+1}$-free, the Nikiforov result (2)
implies
$\lambda(G^{*})\leq\mathrm{ex}_{\lambda}(n,K_{r+1})=\lambda(T_{r}(n))$. Thus,
we get $\lambda(G)\leq\lambda(T_{r}(n))+o(n)$. This completes the proof of
Theorem 1.3.

On the other hand, each edge of $G$ is contained in at most ${n-2\choose s-2}$
copies of $K_{s}$. This implies that the removal of $o(n^{2})$ edges from $G$
can merely remove at most $o(n^{2}){n-2\choose s-2}=o(n^{s})$ copies of
$K_{s}$, thus $k_{s}(G^{*})\geq k_{s}(G)-o(n^{s})$. Note that $G^{*}$ is
$K_{r+1}$-free, hence the Zykov result (4) gives
$k_{s}(G^{*})\leq\mathrm{ex}(n,K_{s},K_{r+1})=k_{s}(T_{r}(n))$. Therefore, we
obtain $k_{s}(G)\leq k_{s}(G^{*})+o(n^{s})\leq k_{s}(T_{r}(n))+o(n^{s})$. This
completes the proof of Theorem 1.5. ∎

Being an interesting property of extremal problems, the spectral stability
theorem also gives rise to a surprisingly useful tool for proving the exact
values of spectral Turán extremal problems. We note that the original proof of
Theorem 1.4 presented in [35] relies heavily on a spectral stability result of
large joint [34, Theorem 4] as well as a renowned result in [30, Theorem 1].
But the proof of the spectral stability result of large joint stated in [34]
seems complicated and needs a series of results from Nikiforov’s works in the
order [3, 30, 4, 36, 31]. In the sequel, we shall provide a new short proof of
Theorem 1.4. The line of proofs are quite different.

###### Alternative proof of Theorem 1.4.

Recall that $F$ is a graph with $\chi(F)=r+1\geq 3$. Let $\varepsilon>0$ be a
small fixed number. Let $G$ be an $F$-free graph on $n$ vertices such that
$\lambda(G)\geq(1-\frac{1}{r}-\delta)n$, where $n$ is a large enough number
and $\delta$ is a small enough number determined later. Applying the
Simonovits stability theorem (Theorem 1.2) to $K_{r+1}$, we know that there
exist $\delta(K_{r+1},\frac{\varepsilon}{2})>0$ and
$n_{0}=n_{0}(K_{r+1},\frac{\varepsilon}{2})$ such that if $H$ is an arbitrary
graph on $n\geq n_{0}$ vertices satisfying that $H$ is $K_{r+1}$-free and
$e(H)\geq\left(1-\frac{1}{r}-\delta(K_{r+1},\frac{\varepsilon}{2})\right)\frac{n^{2}}{2}$,
then the edit distance $d(H,T_{r}(n))\leq\frac{\varepsilon}{2}n^{2}$.

Let $\varepsilon_{0}\in(0,\frac{\varepsilon}{2}]$ be a sufficiently small
number determined later. Since $G$ is $F$-free, applying Lemma 2.1, we obtain
an integer $n_{1}=n_{1}(F,\varepsilon_{0})$ such that if $n\geq n_{1}$, then
we get a $K_{r+1}$-free subgraph by removing at most $\varepsilon_{0}n^{2}$
edges from $G$. We denote the resulting subgraph by $G^{*}$. Moreover, the
Rayleigh formula and inequality (5) give
$\lambda(G)\leq\lambda(G^{*})+\lambda(G\setminus
G^{*})<\lambda(G^{*})+\sqrt{2e(G\setminus G^{*})}$. This implies that
$\lambda(G^{*})>\lambda(G)-\sqrt{2\varepsilon_{0}}n\geq(1-\frac{1}{r}-\delta-\sqrt{2\varepsilon_{0}})n$.
Recall that $G^{*}$ is $K_{r+1}$-free. Applying the remark of Lemma 2.4 to
$G^{*}$, we have $\lambda(G^{*})^{2}\leq(1-\frac{1}{r})2e(G^{*})$, which
implies
$e(G^{*})\geq\left(1-\frac{1}{r}-2(\delta+\sqrt{2\varepsilon_{0}})\right)\frac{n^{2}}{2}$.
We choose sufficiently small $\varepsilon_{0}>0$, and sufficiently large
$n\geq\max\\{n_{0},n_{1}\\}$, then we can choose small $\delta>0$ such that
$2(\delta+\sqrt{2\varepsilon_{0}})\leq\delta(K_{r+1},\frac{\varepsilon}{2})$.
The Simonovits stability theorem gives
$d(G^{*},T_{r}(n))\leq\frac{\varepsilon}{2}n^{2}$. Thus $d(G,T_{r}(n))\leq
d(G,G^{*})+d(G^{*},T_{r}(n))\leq\varepsilon n^{2}$. ∎

We now give a short proof of Theorem 1.6.

###### Alternative proof of Theorem 1.6.

Let $G$ be an $F$-free graph on $n$ vertices such that $k_{s}(G)\geq{r\choose
s}(\frac{n}{r})^{s}-\delta n^{s}$, where $n$ is a large enough number and
$\delta$ is a small enough number determined later. By Theorem 1.2, we know
that for every $\varepsilon>0$, there exist
$\delta(K_{r+1},\frac{\varepsilon}{2})>0$ and
$n_{0}(K_{r+1},\frac{\varepsilon}{2})$ such that if $H$ is a graph on $n\geq
n_{0}$ vertices, and $H$ is $K_{r+1}$-free such that
$e(H)\geq\left(1-\frac{1}{r}-\delta(K_{r+1},\frac{\varepsilon}{2})\right)\frac{n^{2}}{2}$,
then the edit distance $d(H,T_{r}(n))\leq\frac{\varepsilon}{2}n^{2}$.

Let $\varepsilon_{0}>0$ be a sufficiently small number. Since $G$ is $F$-free,
applying Lemma 2.1, we obtain an integer $n_{1}=n_{1}(F,\varepsilon_{0})$ such
that if $n\geq n_{1}$, then we get a $K_{r+1}$-free subgraph by removing at
most $\varepsilon_{0}n^{2}$ edges from $G$. We denote the resulting subgraph
by $G^{*}$. Moreover, every edge of $G$ is contained in at most ${n-2\choose
s-2}$ copies of $K_{s}$. Thus the removal of $\varepsilon_{0}n^{2}$ edges from
$G$ can only destroy at most $\varepsilon_{0}n^{2}{n-2\choose
s-2}<\varepsilon_{0}n^{s}$ copies of $K_{s}$ in $G$. This implies that
$k_{s}(G^{*})\geq k_{s}(G)-\varepsilon_{0}n^{s}\geq{r\choose
s}(\frac{n}{r})^{s}-\delta n^{s}-\varepsilon_{0}n^{s}$. Note that $G^{*}$ is
$K_{r+1}$-free. Applying Lemma 2.3 to $G^{*}$, we have
$(k_{2}(G^{*})/{r\choose 2})^{1/2}\geq(k_{s}(G^{*})/{r\choose s})^{1/s}$,
which implies $e(G^{*})\geq{r\choose
2}\left((\frac{n}{r})^{s}-(\delta+\varepsilon_{0})n^{s}/{r\choose
s}\right)^{2/s}\geq(1-\frac{1}{r})\frac{n^{2}}{2}-t$, where $t={r\choose
2}\left((\delta+\varepsilon_{0})n^{s}/{r\choose s}\right)^{2/s}$. We choose
sufficiently small $\varepsilon_{0}>0$, and sufficiently large
$n\geq\max\\{n_{0},n_{1}\\}$, then we can choose $\delta>0$ small enough such
that $t\leq\delta(K_{r+1},\frac{\varepsilon}{2})\frac{n^{2}}{2}$. Thus the
Simonovits stability theorem implies $d(G,T_{r}(n))\leq
d(G,G^{*})+d(G^{*},T_{r}(n))\leq\varepsilon n^{2}$. ∎

###  3.2 Revisiting color-critical graphs

Let $e$ be an edge of graph $F$. We say that $e$ is a color-critical edge of
$F$ if $\chi(F-e)<\chi(F)$. We say that $F$ is color-critical if $F$ contains
a color-critical edge. There are many graphs that are color-critical. For
instance, the following graphs are color-critical. Every edge of the complete
graph $K_{r+1}$ is a color-critical edge. Then $K_{r+1}$ is color-critical
with $\chi(K_{r+1})=r+1$. Every edge of the odd cycle $C_{2k+1}$ is a color-
critical edge. So $C_{2k+1}$ is color-critical with $\chi(C_{2k+1})=3$. Let
$W_{n}=K_{1}\vee C_{n-1}$ be the wheel graph on $n$ vertices, a vertex that
joins all vertices of $C_{n-1}$. The even wheel graph $W_{2k}$ is color-
critical and $\chi(W_{2k})=4$. However, we can check that the odd wheel graph
$W_{2k+1}$ is not color-critical and $\chi(W_{2k+1})=3$. Let $B_{k}=K_{2}\vee
I_{k-2}$ be the book graph, that is, $k$ triangles sharing a common edge. Then
$B_{k}$ is color-critical and $\chi(B_{k})=3$.

In 1966, Simonovits [45] proved a celebrated result, which gives the exact
Turán number for all color-critical graphs.

######  Theorem 3.1 (Simonovits, 1966).

If $F$ is a graph with a critical edge and $\chi(F)=r+1$ where $r\geq 2$, then
there exists an $n_{0}=n_{0}(F)$ such that

$\mathrm{ex}(n,F)=e(T_{r}(n))$

holds for all $n\geq n_{0}$, and the unique extremal graph is the Turán graph
$T_{r}(n)$.

In 2009, Nikiforov [34, Theorem 2] proved the corresponding result in terms of
the spectral radius.

######  Theorem 3.2 (Nikiforov, 2009).

If $F$ is a graph with a critical edge and $\chi(F)=r+1$ where $r\geq 2$, then
there exists an $n_{0}=n_{0}(F)$ such that

$\mathrm{ex}_{\lambda}(n,F)=\lambda(T_{r}(n))$

holds for all $n\geq n_{0}$, and the unique extremal graph is $T_{r}(n)$.

Note that Theorem 3.2 implies Theorem 3.1 by applying (3). Indeed, assume that
$F$ is a color-critical graph with $\chi(F)=r+1$ and $G$ is $F$-free, Theorem
3.2 implies that for sufficiently large $n$, we have
$\lambda(G)\leq\lambda(T_{r}(n))$, which together with (3) yields $e(G)\leq
e(T_{r}(n))$.

Correspondingly, it was proved by Ma and Qiu [27] that for a color-critical
graph $F$ with $\chi(F)=r+1$ and sufficiently large $n$, the Turán graph
$T_{r}(n)$ is the unique graph attaining the maximum number of copies of
$K_{s}$ in an $n$-vertex $F$-free graph.

In what follows, we escape from the framework of the proof of Nikiforov and
give an alternative proof of Theorem 3.2 by applying the spectral stability
theorem (Theorem 1.4). The proof of Nikiforov [34] relies heavily on a series
of works stated in the order of [29, 36, 31, 3, 30]. Our proof is more
transparent and straightforward, we shall use some significant ideas and
techniques of the Szemerédi regularity lemma although we do not apply the
regularity lemma directly.

Let $G$ be an $n$-vertex graph and $G^{\prime}$ be an $r$-partite subgraph of
$G$ with partition $V(G^{\prime})=U_{1}\cup U_{2}\cup\cdots\cup U_{r}$. Let
$\varepsilon>0$ be a sufficiently small number. We say that $G^{\prime}$ is
$\varepsilon$-almost complete if for any $v\in U_{i}$ and any $j\neq i$, we
have $|N(v)\cap U_{j}|\geq|U_{j}|-\varepsilon n$. In other words, the number
of non-neighbors of $v$ in $U_{j}$ is at most $\varepsilon n$.

######  Lemma 3.3.

Let $F$ be a color-critical graph $\chi(F)=r+1$ where $r\geq 2$. Let
$\varepsilon>0$ be small enough. Let $G$ be an $n$-vertex $F$-free graph with
$n$ large enough. If $G$ contains an $\varepsilon$-almost complete $r$-partite
subgraph $G^{\prime}$ with $V(G^{\prime})=U_{1}\cup U_{2}\cup\cdots\cup
U_{r}$, and large enough $|U_{i}|$, then
(i) All parts $U_{1},U_{2},\ldots,U_{r}$ are independent sets in $G$.
(ii) For every $x\in V(G)\setminus V(G^{\prime})$, there exists a vertex set
$U_{i}$ such that $x$ has at most $\varepsilon rtn$ neighbors in $U_{i}$,
where $t$ is the number of vertices of $F$.

###### Proof.

(i) Since $F$ is a graph with a critical edge and $\chi(F)=r+1$, there is an
edge $\\{x,y\\}\in E(F)$ such that $F\setminus\\{x,y\\}$ is a subgraph of the
complete $r$-partite graph $K_{t,t,\ldots,t}=K_{r}(t)$. Without loss of
generality, we may assume on the contrary that $U_{1}$ contains an edge
$\\{u,v\\}$. We choose a vertex set $T_{1}\subseteq U_{1}$ satisfying
$|T_{1}|=t$ and $\\{u,v\\}\subseteq T_{1}$. Suppose we have obtained sets
$T_{1},T_{2},\ldots,T_{i}$ such that $|T_{i}|=t$ and
$T_{1},T_{2},\ldots,T_{i}$ form a complete $i$-partite graph $K_{i}(t)$. Note
that $G^{\prime}$ is $\varepsilon$-almost complete, so every $x\in
T_{1}\cup\cdots\cup T_{i}$ misses at most $\varepsilon n$ vertices in
$U_{i+1}$, i.e., excepting at most $it\varepsilon n$ vertices of $U_{i+1}$,
the remaining vertices of $U_{i+1}$ are adjacent to every vertex of
$T_{1}\cup\cdots\cup T_{i}$. Observe that $|U_{i+1}|-it\varepsilon n\geq t$.
Hence there exists a set $T_{i+1}\subseteq U_{i+1}$ with $|T_{i+1}|=t$ such
that the vertex sets $T_{1},\ldots,T_{i},T_{i+1}$ form a complete
$(i+1)$-partite graph $K_{i+1}(t)$. We can proceed this operation until we
find $r$ sets $T_{1},T_{2},\ldots,T_{r}$ satisfying $|T_{i}|=t$ and they form
a complete $r$-partite graph. Note that $\\{u,v\\}$ is an edge in $T_{1}$, it
corresponds to the edge $\\{x,y\\}$ of $F$. Thus $F$ is contained in
$G^{\prime}$, and so it is contained in $G$, a contradiction.

(ii) Suppose that $x$ has at least $\varepsilon rtn$ neighbors in set $U_{i}$
for every $i=1,2,\ldots,r$. Since $F$ is a fixed graph on $t$ vertices, we
know that $\varepsilon rtn\geq t$ holds for fixed small $\varepsilon$ and then
sufficiently large $n$. Setting $U_{i}^{\prime}=N(x)\cap U_{i}$ for every
$i=1,2,\ldots,r$. Firstly, we choose a set $T_{1}\subseteq U_{1}^{\prime}$
with $|T_{1}|=t$. Suppose that we have find sets $T_{1},T_{2},\ldots,T_{i}$
satisfying $T_{i}\subseteq U_{i}^{\prime},|T_{i}|=t$ and
$T_{1},T_{2},\ldots,T_{i}$ form a complete $i$-partite graph $K_{i}(t)$.
Observe that every $v\in T_{1}\cup\cdots\cup T_{i}$ misses at most
$\varepsilon n$ vertices of $U_{i+1}$, so it misses at most $\varepsilon n$
vertices of $U_{i+1}^{\prime}$. Note that $|U_{i+1}^{\prime}|\geq
rt\varepsilon n$, hence for sufficiently large $n$, we can find a set
$T_{i+1}\subseteq U_{i+1}^{\prime}$ such that $|T_{i+1}|=t$ and every vertex
of $T_{i+1}$ is adjacent to every vertex of $T_{1}\cup\cdots\cup T_{i}$. By
repeating this process, we can find $r$ sets $T_{1},T_{2},\ldots,T_{r}$ such
that $T_{i}\subseteq U_{i}^{\prime},|T_{i}|=t$ and $T_{1},T_{2},\ldots,T_{r}$
form a complete $r$-partite graph. Observe that $F$ is contained in the
complete $(r+1)$-partite graph formed by $\\{x\\},T_{1},\ldots,T_{r}$, so it
is contained in $G$, a contradiction. ∎

We now start our new proof of Theorem 3.2.

###### Alternative proof of Theorem 3.2.

Let $F$ be a graph with a critical edge and $\chi(F)=r+1$. Assume that $G$ is
an $n$-vertex $F$-free graph with $\lambda(G)\geq\lambda(T_{r}(n))$, our goal
is to show $G=T_{r}(n)$. Set $\varepsilon>0$ as a sufficiently small constant.
First of all, we claim that $\delta(G)\geq(1-\frac{1}{r}-\varepsilon)n$.
Otherwise, if there exists a vertex with degree less than
$(1-\frac{1}{r}-\varepsilon)n$,  then by a standard argument of successively-
vertex deletion [31, Theorem 5], we obtain a subgraph $G_{1}$ of $G$
satisfying $|G_{1}|=n_{1}\geq n/2$ vertices and one of the following
conditions:
(a) $\lambda(G_{1})>(1-\frac{1}{r}+\frac{\varepsilon}{4})n_{1}$; or
(b) $\delta(G_{1})\geq(1-\frac{1}{r}-\varepsilon)n_{1}$ and
$\lambda(G_{1})>\lambda(T_{r}(n_{1}))$.

If Condition (a) happens, then we can see that $G_{1}$ contains $F$ as a
subgraph by applying Theorem 1.3 for sufficiently large $n$. In what follows,
we consider Condition (b). In other words, $G$ has a subgraph $G_{1}$ on
$n_{1}>n/2$ vertices with $\lambda(G_{1})>\lambda(T_{r}(n_{1}))$ and the
minimum degree $\delta(G_{1})\geq(1-\frac{1}{r}-\varepsilon)n_{1}$.

Note that $\lambda(T_{r}(n_{1}))\geq(1-\frac{1}{r})n_{1}-\frac{r}{4n_{1}}$. By
the spectral stability Theorem 1.4, we have
$d(G_{1},T_{r}(n_{1}))\leq\varepsilon n_{1}^{2}$. Hence there exists an
$r$-partition of the vertex set of $G_{1}$, say $V(G_{1})=V_{1}\cup
V_{2}\cup\cdots\cup V_{r}$ such that $|V_{i}|=\lfloor n_{1}/r\rfloor$ or
$\lceil n_{1}/r\rceil$ for every $i=1,2,\ldots,r$, and
$\sum_{i=1}^{r}e(G_{1}[V_{i}])+e(T_{r}(n_{1}))-e(G_{1}[V_{1},V_{2},\ldots,V_{r}])\leq\varepsilon
n_{1}^{2}$, where $G_{1}[V_{i}]$ is the subgraph of $G_{1}$ induced by $V_{i}$
and $G_{1}[V_{1},V_{2},\ldots,V_{r}]$ is the $r$-partite subgraph of $G_{1}$
formed between sets $V_{1},V_{2},\ldots,V_{r}$. Note that
$e(T_{r}(n_{1}))-e(G_{1}[V_{1},V_{2},\ldots,V_{r}])$ is the number of edges of
$T_{r}(n)$ missing from $G_{1}$, i.e., the pair $\\{x,y\\}$ with $x\in
V_{i},y\in V_{j},i\neq j$ and $\\{x,y\\}\notin E(G_{1})$. For every
$i=1,2,\ldots,r$, we define $B_{i}$ as the set of vertices of $V_{i}$ missing
at least $\sqrt{\varepsilon}n_{1}$ edges from some $V_{j}$, that is,
$B_{i}=\\{v\in V_{i}:|N(v)\cap
V_{j}|\leq|V_{j}|-\sqrt{\varepsilon}n_{1}~{}\text{for some $j\neq i$}\\}$. We
call such vertex a bad vertex and denote $B=\cup_{i=1}^{r}B_{i}$. Then
$|B|\leq\frac{2\varepsilon
n_{1}^{2}}{\sqrt{\varepsilon}n_{1}}=2\sqrt{\varepsilon}n_{1}$. Let
$U_{i}=V_{i}\setminus B_{i}$ for every $i=1,\ldots,r$. Then
$|U_{i}|\geq|V_{i}|-|B|>\frac{n_{1}}{r}-3\sqrt{\varepsilon}n_{1}$. For every
$v\in U_{i}$ and $j\neq i$, we have $|N(v)\cap U_{j}|\geq|N(v)\cap
V_{j}|-|B|\geq(|V_{j}|-\sqrt{\varepsilon}n_{1})-2\sqrt{\varepsilon}n_{1}\geq|U_{j}|-3\sqrt{\varepsilon}n_{1}$.
Thus $G_{1}[U_{1},U_{2},\ldots,U_{r}]$ is a $3\sqrt{\varepsilon}$-almost
complete $r$-partite subgraph of $G_{1}$. By (i) of Lemma 3.3, we know that
$U_{1},U_{2},\ldots,U_{r}$ are independent sets.

If $B$ is non-empty, then for each bad vertex $x\in B$, by (ii) of Lemma 3.3,
there exists a set $U_{i}$ such that $|N(x)\cap U_{i}|\leq
3\sqrt{\varepsilon}rtn_{1}$. Now we add the bad vertex $x$ into the set
$U_{i}$, and get a new $r$-partition, say
$U_{1}^{\prime},\ldots,U_{i}^{\prime},\ldots,U_{r}^{\prime}$, where
$U_{i}^{\prime}=U_{i}\cup\\{x\\}$ and other $U_{j}^{\prime}=U_{j}$ for $j\neq
i$. We claim that the new partition
$G_{1}[U_{1}^{\prime},\ldots,U_{r}^{\prime}]$ is
$(7\sqrt{\varepsilon}rt)$-almost complete. Note that
$\delta(G_{1})\geq(1-\frac{1}{r}-\varepsilon)n_{1}$, so we have
$|N(x)\cap(\cup_{j\neq i}U_{j})|\geq d(x)-|B|-|N(x)\cap
U_{i}|\geq(1-\frac{1}{r}-\varepsilon)n_{1}-2\sqrt{\varepsilon}n_{1}-3\sqrt{\varepsilon}rtn_{1}\geq(1-\frac{1}{r})n_{1}-6\sqrt{\varepsilon}rtn_{1}$.
Note that $|\cup_{j\neq i}U_{j}|\leq|\cup_{j\neq i}V_{j}|\leq
n-\lfloor\frac{n_{1}}{r}\rfloor<(1-\frac{1}{r})n_{1}+\sqrt{\varepsilon}rtn_{1}$
for sufficiently large $n_{1}$. Thus we obtain $|N(x)\cap(\cup_{j\neq
i}U_{j})|\geq|\cup_{j\neq i}U_{j}|-7\sqrt{\varepsilon}rtn_{1}$. So the number
of non-neighbors of $x$ in set $\cup_{j\neq i}U_{j}$ is at most
$7\sqrt{\varepsilon}rtn_{1}$, which implies that the number of non-neighbors
of $x$ in each $U_{j}$ with $j\neq i$ is at most $7\sqrt{\varepsilon}rtn_{1}$.
Thus we get $|N(x)\cap U_{j}|\geq|U_{j}|-7\sqrt{\varepsilon}rtn_{1}$ for every
$j\neq i$. So we complete the proof of our claim. By (i) of Lemma 3.3, we know
that $U_{1}^{\prime},U_{2}^{\prime},\ldots,U_{r}^{\prime}$ are still
independent sets.

If $B\setminus\\{x\\}$ is non-empty, then for each bad vertex $y\in
B\setminus\\{x\\}$, by (ii) of Lemma 3.3, there exists a set $U_{i}^{\prime}$
such that $|N(y)\cap U_{i}^{\prime}|\leq(7\sqrt{\varepsilon}rt)\cdot rtn_{1}$.
We add the vertex $y$ to the set $U_{i}^{\prime}$, and obtain a new
$r$-partition. Repeating the above process, we can keep adding all bad
vertices of $B$ into our $r$-partition until $B=\varnothing$. At the end of
our process, we conclude that $G_{1}$ is an $r$-partite graph. Certainly,
$G_{1}$ is $K_{r+1}$-free, the spectral Turán theorem implies
$\lambda(G_{1})\leq\lambda(T_{r}(n_{1}))$. Recall that Condition (b) states
that $\lambda(G_{1})>\lambda(T_{r}(n_{1}))$, so we get a contradiction.

Hence, there are no vertices of $G$ with degree less than
$(1-\frac{1}{r}-\varepsilon)n$. We conclude that $G$ is an $F$-free graph on
$n$ vertices with $\lambda(G)\geq\lambda(T_{r}(n))$ and
$\delta(G)\geq(1-\frac{1}{r}-\varepsilon)n$. Now, replacing $G_{1}$ with $G$,
and repeating the above discussions, we can show that $G$ is an $r$-partite
graph. Keeping in mind that $\lambda(G)\geq\lambda(T_{r}(n))$, we obtain that
$G$ is a balanced complete $r$-partite graph on $n$ vertices. ∎

Our proof in above is a standard graph structure analysis. It is worth noting
that one can prove Theorem 3.1 by modifying slightly the above proof of the
spectral version. Generally speaking, the stability method has two steps.
First one need to prove a stability theorem, i.e., any construction of close
to maximum size is structurally close to the conjectured extremal graph. Armed
with this approximate structure, we can consider any supposed better
construction as being obtained from the extremal example by introducing a
small number of imperfections into the structure. The second step is to
analyze any possible imperfection and show that it must lead to a suboptimal
configuration, so in fact the conjectured extremal example must be optimal;
see [20, 26] for similar examples.

###  3.3 Making $K_{r+1}$-free graphs $r$-partite

In this subsection, we shall study the problem of how many edges needed to be
removed in a $K_{r+1}$-free graph to make its being $r$-partite. For integer
$r\geq 2$, let $D_{r}(G)$ denote the minimum number of edges which need to be
removed to make $G$ being $r$-partite. For cliques, the Erdős–Simonovits
theorem [45] states that for every $\varepsilon>0$, there exist $\delta>0$ and
$n_{0}$ such that if $G$ is a $K_{r+1}$-free graph on $n\geq n_{0}$ vertices
and $e(G)\geq e(T_{r}(n))-\delta n^{2}$, then $D_{r}(G)\leq\varepsilon n^{2}$.
In 2015, Füredi [16] provided an elegant proof of the result that every
$K_{r+1}$-free graph $G$ on $n$ vertices with at least $e(T_{r}(n))-t$ edges
satisfies $D_{r}(G)\leq t$. This provided a quantitative improvement of the
Erdős–Simonovits theorem. Very recently, Balogh, Clristian, Lavrov, Lidický
and Pfender [2] determined asymptotically a sharp bound on the number of edges
that are needed for small $t\in\mathbb{N}^{*}$.

######  Theorem 3.4 (Balogh–Clristian–Lavrov–Lidický–Pfender, 2021).

Let $r\geq 2$ be an integer. For all $n\geq 3r^{2}$ and $0\leq\delta\leq
10^{-7}r^{-12}$, the following holds. If $G$ is a $K_{r+1}$-free graph on $n$
vertices with $e(G)\geq e(T_{r}(n))-\delta n^{2}$, then
$D_{r}(G)\leq\bigl{(}\frac{2r}{3\sqrt{3}}+o_{\delta}(1)\bigr{)}\delta^{3/2}n^{2}$,
where $o_{\delta}(1)$ is a term converging to $0$ as $\delta$ tending to $0$.

In the sequel, we present the spectral version and clique version of Theorem
3.4.

######  Theorem 3.5.

Let $r\geq 2,n\geq 3r^{2}$ and $0\leq\delta\leq 10^{-7}r^{-12}$. If $G$ is an
$n$-vertex $K_{r+1}$-free graph such that
$\lambda(G)\geq(1-\frac{1}{r}-\delta)n$, then
$D_{r}(G)\leq\bigl{(}\frac{2r}{3\sqrt{3}}+o_{\delta}(1)\bigr{)}\delta^{3/2}n^{2}$.

###### Proof.

Since $G$ is $K_{r+1}$-free, applying the remark of Lemma 2.4, we have
$\lambda(G)^{2}\leq(1-\frac{1}{r})2e(G)$. Thus we have
$e(G)\geq\frac{1}{2}\lambda(G)^{2}/(1-\frac{1}{r})\geq\frac{n^{2}}{2}(1-\frac{1}{r}-\delta)^{2}/(1-\frac{1}{r})>\frac{n^{2}}{2}(1-\frac{1}{r}-2\delta)\geq
e(T_{r}(n))-\delta n^{2}$. The desired result follows immediately from Theorem
3.4. ∎

######  Theorem 3.6.

Given $r\geq 2$ and $s\geq 2$. Let $n$ be large and $\delta>0$ be sufficiently
small. If $G$ is a graph on $n$ vertices, and $G$ is $K_{r+1}$-free such that
$k_{s}(G)\geq{r\choose s}(\frac{n}{r})^{s}-\delta n^{s}$, then
$D_{r}(G)\leq\bigl{(}\frac{2r}{3\sqrt{3}}+o_{\delta}(1)\bigr{)}{r\choose
2}^{3/2}/{r\choose s}^{3/s}\cdot\delta^{3/s}n^{2}$.

###### Proof.

Note that $G$ is $K_{r+1}$-free. Applying Lemma 2.3, we get $e(G)\geq{r\choose
2}({k_{s}(G)}/{{r\choose s}})^{2/s}$, which together with the assumption
yields $e(G)\geq{r\choose 2}\left((\frac{n}{r})^{s}-\delta n^{s}/{r\choose
s}\right)^{2/s}\geq{r\choose 2}(\frac{n}{r})^{2}-{r\choose 2}/{r\choose
s}^{2/s}\cdot\delta^{2/s}n^{2}\geq e(T_{r}(n))-{r\choose 2}/{{r\choose
s}^{2/s}}\cdot\delta^{2/s}n^{2}$. By Theorem 3.4, we obtain the required
result
$D_{r}(G)\leq\bigl{(}\frac{2r}{3\sqrt{3}}+o_{\delta}(1)\bigr{)}{r\choose
2}^{3/2}/{r\choose s}^{3/s}\cdot\delta^{3/s}n^{2}$. ∎

Remark. The Rayleigh formula gives $2e(G)/n\leq\lambda(G)$. Thus Theorem 3.5
extends Theorem 3.4 slightly. In particular, the case $s=2$ in Theorem 3.6
reduces to Theorem 3.4. In addition, Theorem 3.6 is an improvement of a recent
result of Liu [25, Theorem 4.1].

For a positive integer $r\geq 2$, a graph $G$ is said to be
$K_{r+1}$-saturated (or maximal $K_{r+1}$-free) if it contains no copy of
$K_{r+1}$, but the addition of any edge from the complement $\overline{G}$
creates at least one copy of $K_{r+1}$. In 2018, Popielarz, Sahasrabudhe and
Snyder [43] proved the following stronger stability theorem for
$K_{r+1}$-saturated graphs.

######  Theorem 3.7 (Popielarz–Sahasrabudhe–Snyder, 2018).

Let $r\geq 2$ be an integer. For any $\varepsilon>0$, there exist $\delta>0$
and $n_{0}$ such that if $G$ is a $K_{r+1}$-saturated graph on $n\geq n_{0}$
vertices with $e(G)\geq(1-\frac{1}{r})\frac{n^{2}}{2}-\delta
n^{\frac{r+1}{r}}$, then $G$ contains a complete $r$-partite subgraph on
$(1-\varepsilon)n$ vertices.

The spectral version and clique version can be obtained similarly.

######  Theorem 3.8.

Let $r\geq 2$ be an integer. For any $\varepsilon>0$, there exist $\delta>0$
and $n_{0}$ such that if $G$ is a $K_{r+1}$-saturated graph on $n\geq n_{0}$
vertices with $\lambda(G)\geq(1-\frac{1}{r})n-\delta n^{\frac{1}{r}}$, then
$G$ contains a complete $r$-partite subgraph on $(1-\varepsilon)n$ vertices.

The following theorem extends Theorem 3.7 by setting $s=2$.

######  Theorem 3.9.

Let $r\geq 2$ and $s\geq 2$ be integers. For any $\varepsilon>0$, there exist
$\delta>0$ and $n_{0}$ such that if $G$ is a $K_{r+1}$-saturated graph on
$n\geq n_{0}$ vertices with $k_{s}(G)\geq{r\choose s}(\frac{n}{r})^{s}-\delta
n^{s\frac{r+1}{2r}}$, then $G$ contains a complete $r$-partite subgraph on
$(1-\varepsilon)n$ vertices.

###  3.4 Stability result for the $p$-spectral radius

The spectral radius of a graph is defined as the largest eigenvalue of its
adjacency matrix. By the Rayleigh theorem, we know that it is also equal to
the maximum value of $\bm{x}^{T}A(G)\bm{x}=2\sum_{\\{i,j\\}\in
E(G)}x_{i}x_{j}$ over all $\bm{x}\in\mathbb{R}^{n}$ with
$|x_{1}|^{2}+\cdots+|x_{n}|^{2}=1$. The definition of the spectral radius was
recently extended to the $p$-spectral radius. We denote the $p$-norm of
$\bm{x}$ by $\lVert\bm{x}\rVert_{p}=(|x_{1}|^{p}+\cdots+|x_{n}|^{p})^{1/p}$.
More precisely, the $p$-spectral radius of graph $G$ is defined as

$\lambda^{(p)}(G):=\max_{\lVert\bm{x}\rVert_{p}=1}2\sum_{\\{i,j\\}\in
E(G)}x_{i}x_{j}.$

We remark that $\lambda^{(p)}(G)$ is a versatile parameter. Indeed,
$\lambda^{(1)}(G)$ is known as the Lagrangian function of $G$,
$\lambda^{(2)}(G)$ is the spectral radius of its adjacency matrix, and

$\lim_{p\to+\infty}\lambda^{(p)}(G)=2e(G),$ (6)

which can be guaranteed by the following inequality

$2e(G)n^{-2/p}\leq\lambda^{(p)}(G)\leq(2e(G))^{1-1/p}.$ (7)

To some extent, the $p$-spectral radius can be viewed as a unified extension
of the classical spectral radius and the size of a graph. In addition, it is
worth mentioning that if $1\leq q\leq p$, then
$\lambda^{(p)}(G)n^{2/p}\leq\lambda^{(q)}(G)n^{2/q}$ and
$(\lambda^{(p)}(G)/2e(G))^{p}\leq(\lambda^{(q)}(G)/2e(G))^{q}$; see [39,
Proposition 2.13 and 2.14] for more details.

As commented by Kang and Nikiforov in [19, p. 3], linear-algebraic methods are
irrelevant for the study of $\lambda^{(p)}(G)$ in general, and in fact no
efficient methods are known for it. Thus the study of $\lambda^{(p)}(G)$ for
$p\neq 2$ is far more complicated than the classical spectral radius.

The extremal function for $p$-spectral radius is given as

$\mathrm{ex}_{\lambda}^{(p)}(n,{F}):=\max\\{\lambda^{(p)}(G):|G|=n~{}\text{and
$G$ is ${F}$-free}\\}.$

To some extent, the proof of results on the $p$-spectral radius shares some
similarities with the usual spectral radius when $p>1$; see [39, 19] for
extremal problems for the $p$-spectral radius. In 2014, Kang and Nikiforov
[19] extended the Turán theorem to the $p$-spectral version for $p>1$. They
proved that if $G$ is a $K_{r+1}$-free graph on $n$ vertices, then
$\lambda^{(p)}(G)\leq\lambda^{(p)}(T_{r}(n))$, equality holds if and only if
$G=T_{r}(n)$. In symbols, we have

$\mathrm{ex}_{\lambda}^{(p)}(n,K_{r+1})=\lambda^{(p)}(T_{r}(n)).$ (8)

######  Theorem 3.10.

If $F$ is a graph with chromatic number $\chi(F)=r+1$, then for every $p>1$,

$\mathrm{ex}_{\lambda}^{(p)}(n,F)=\lambda^{(p)}(T_{r}(n))+o(n^{2-(2/p)})=\left(1-\frac{1}{r}+o(1)\right)n^{2-(2/p)}.$

Theorem 3.10 extends both Theorem 1.1 and Theorem 1.3 by noting (6).

###### Proof.

The Turán graph $T_{r}(n)$ is $r$-partite, so $T_{r}(n)$ is an $F$-free graph.
Moreover, by inequality (7), we have $\lambda^{(p)}(T_{r}(n))\geq
2e(T_{r}(n))n^{-2/p}\geq(1-\frac{1}{r})n^{2-(2/p)}-\frac{r}{4n^{2/p}}$. Thus
$T_{r}(n)$ gives the lower bound
$\mathrm{ex}_{\lambda}^{(p)}(n,F)\geq\lambda^{(p)}(T_{r}(n))\geq(1-\frac{1}{r}+o(1))n^{2-(2/p)}$.
More precisely, we can obtain by detailed computation that
$\lambda^{(p)}(T_{r}(n))=(1+O(\frac{1}{n^{2}}))2e(T_{r}(n))n^{-2/p}=(1-O(\frac{1}{n^{2}}))(1-\frac{1}{r})n^{2-2/p}$,
where $O(\frac{1}{n^{2}})$ stands for a positive error term.

Now, assume that $G$ is an $n$-vertex $F$-free graph. By Lemma 2.1, we can
remove $o(n^{2})$ edges from $G$ and get a new graph $G^{*}$ which is
$K_{r+1}$-free. We claim that the removal of $o(n^{2})$ edges from $G$ can
only decrease $\lambda^{(p)}(G)$ by at most $o(n^{2-2/p})$. Indeed, we can see
from the definition that
$\lambda^{(p)}(G)\leq\lambda^{(p)}(G^{*})+\lambda^{(p)}(G\setminus G^{*})$,
and the inequality (7) implies $\lambda^{(p)}(G\setminus
G^{*})\leq(2e(G\setminus G^{*}))^{1-1/p}=o(n^{2-2/p})$. Since $G^{*}$ is
$K_{r+1}$-free, the Kang–Nikiforov result (8) implies
$\lambda^{(p)}(G^{*})\leq\mathrm{ex}_{\lambda}^{(p)}(n,K_{r+1})=\lambda^{(p)}(T_{r}(n))$.
Thus, we get $\lambda^{(p)}(G)\leq\lambda^{(p)}(T_{r}(n))+o(n^{2-2/p})$. This
completes the proof. ∎

Our unified treatment of Theorems 1.4 and 1.6 stated in Subsection 3.1 can
allow us to generalize the spectral stability theorem in terms of the
$p$-spectral radius.

######  Theorem 3.11.

Let $F$ be a graph with $\chi(F)=r+1\geq 3$. For every $p>1$ and
$\varepsilon>0$, there exist $\delta>0$ and $n_{0}$ such that if $G$ is a
graph on $n\geq n_{0}$ vertices, and $G$ is $F$-free such that
$\lambda^{(p)}(G)\geq(1-\frac{1}{r}-\delta)n^{2-(2/p)}$, then the edit
distance $d(G,T_{r}(n))\leq\varepsilon n^{2}$.

Theorem 3.11 extends both Theorem 1.2 and Theorem 1.4 by applying (6).

###### Proof.

The proof is short and similar. It is based on applying Theorem 1.2 and Lemma
2.1. There are two differences in the proof. The first is that
$\lambda^{(p)}(G)\leq\lambda^{(p)}(G^{*})+\lambda^{(p)}(G\setminus G^{*})$.
The second is an extension of Lemma 2.4, which states that
$\lambda^{(p)}(G)\leq(2m)^{1-1/p}(1-\frac{1}{r})^{1/p}$ whenever $G$ is an
$m$-edge $K_{r+1}$-free graph; see, e.g., [19, Theorem 3]. ∎

In the above, we established the stability theorem for $p$-spectral radius.
Under the similar line of our proof of Theorem 3.2, applying the $p$-spectral
stability theorem can allow us to extend Theorem 3.2 and prove the exact
$p$-spectral Turán function for every color-critical graph and real value
$p>1$. Moreover, it is possible to extend the usual spectral extremal results
to the $p$-spectral radius by applying the $p$-spectral stability result.

######  Theorem 3.12.

If $F$ is a graph with a critical edge and $\chi(F)=r+1$ where $r\geq 2$, then
for every real number $p>1$, there exists an $n_{0}=n_{0}(F,p)$ such that

$\mathrm{ex}_{\lambda}^{(p)}(n,F)=\lambda^{(p)}(T_{r}(n))$

holds for all $n\geq n_{0}$, and the unique extremal graph is the Turán graph
$T_{r}(n)$.

Remark. We remark that Kang and Nikiforov [19, Theorem 6], Keevash, Lenz and
Mubayi [21, Corollary 1.5] independently proved the same result with a
different method.

###  3.5 The minimum degree version

In this subsection, we shall consider the extremal graph problems in term of
the minimum degree. Recall that $\delta(G)$ is the minimum degree of $G$. We
define $\mathrm{ex}_{\delta}(n,F)$ to be the largest minimum degree in an
$n$-vertex graph that contains no copy of $F$, that is,

$\mathrm{ex}_{\delta}(n,F):=\max\bigl{\\{}\delta(G):|G|=n~{}\text{and}~{}F\nsubseteq
G\bigr{\\}}.$

First of all, we prove the degree version of Turán’s theorem.***We are not
sure whether Theorem 3.13 have already appeared in the literature, though we
have not yet found this theorem elsewhere, so we intend to present a proof
here for completeness.

######  Theorem 3.13.

If $G$ is an $n$-vertex graph containing no copy of $K_{r+1}$, then

$\delta(G)\leq\delta(T_{r}(n)).$

Moreover, the equality holds if and only if $G=T_{r}(n)$.

Before starting the proof, we show that the degree Turán theorem implies the
classical Turán theorem. Indeed, given an $n$-vertex $K_{r+1}$-free graph $G$,
the degree Turán Theorem 3.13 implies $\delta(G)\leq\delta(T_{r}(n))$. We
delete a vertex of minimum degree, and the resulting graph $G^{\prime}$ has
$n-1$ vertices with $e(G^{\prime})=e(G)-\delta(G)$ edges. Note that
$G^{\prime}$ has no copy of $K_{r+1}$. By the inductive hypothesis, we obtain
$e(G^{\prime})\leq e(T_{r}(n-1))$. Thus we have
$e(G)=e(G^{\prime})+\delta(G)\leq e(T_{r}(n-1))+\delta(T_{r}(n))=e(T_{r}(n))$.
Moreover, the equality holds if and only if $e(G^{\prime})=e(T_{r}(n-1))$ and
$\delta(G)=\delta(T_{r}(n))$. Hence the equality case of the degree Turán
theorem implies $G=T_{r}(n)$.

###### Proof.

Note that $\delta(T_{r}(n))=n-\lceil\frac{n}{r}\rceil$ and $\delta(G)\geq
n-\lceil\frac{n}{r}\rceil+1$. Suppose that $n=qr+s$, where $1\leq s\leq r$.
Hence $\delta(G)\geq n-(q+1)+1=n-q$. Let $u_{1},\ldots,u_{r}$ be $r$ distinct
vertices in $G$. Then we have
$|\cap_{i=1}^{r}N(u_{i})|\geq\sum_{i=1}^{r}|N(u_{i})|-(r-1)|\cup_{i=1}^{r}N(u_{i})|\geq
r(n-q)-(r-1)n=s\geq 1$, which implies that $G$ contains a copy of $K_{r+1}$. ∎

In what follows, we give another way to show the degree version. More
precisely, we shall show that the degree version for such extremal problem can
be deduced from the classical edge version.

###### Second proof.

Let $G$ be a $K_{r+1}$-free graph on $n$ vertices. By the Turán theorem, we
know that $e(G)\leq e(T_{r}(n))$. We assume on the contrary that
$\delta(G)\geq\delta(T_{r}(n))+1$. We assume that $s$ vertices of $T_{r}(n)$
have degree $\delta(T_{r}(n))$, and $t$ vertices have degree
$\delta(T_{r}(n))+1$, where $s+t=n$ and $0\leq t<n$. We have $2e(G)=\sum
d_{i}\geq n\delta(T_{r}(n))+n>n\delta(T_{r}(n))+t=2e(T_{r}(n))$, a
contradiction. Therefore, we get $\delta(G)\leq\delta(T_{r}(n))$. Moreover,
equality holds if and only if $e(G)=e(T_{r}(n))$, and then $G=T_{r}(n)$. So
the Turán theorem implies the degree version. On the other hand, the degree
version can deduce the Turán theorem by deleting a vertex with minimum degree,
we have $e(G)=e(G-v)+d(v)\leq e(T_{r}(n-1))+\delta(T_{r}(n))=e(T_{r}(n))$. ∎

As mentioned before the proof, we know that the degree version implies the
classical Turán theorem. The proof of Theorem 3.13 seems not complicated.
However, it is surprising that Theorem 3.13 seems not well-known in extremal
graph community. Moreover, the second proof reveals an interesting phenomenon
that both the degree version and the edge version of the Turán theorem are
equivalent.

Remark. For some extremal graph problems, if the extremal graph is regular or
nearly regular, then almost all degree version can imply the usual edge
version. For example, the extremal hypergraph Turán problem for the Fano
plane. Generally speaking, for some problems with the extremal graphs far from
being regular, these two versions can not be converted to each other. For
instance, the Erdős–Ko–Rado theorem and its degree version, the Hilton–Milner
theorem and its degree version.

For completeness, we next are going to present the degree versions of the
Erdős–Stone–Simonovits theorem and Erdős–Simonovits stability theorem. The
proofs can be given as a direct consequence of Theorems 1.1 and 1.2.

######  Theorem 3.14.

If $F$ is a graph with chromatic number $\chi(F)=r+1$, then

$\mathrm{ex}_{\delta}(n,F)=\delta(T_{r}(n))+o(n)=\left(1-\frac{1}{r}+o(1)\right)n.$

######  Theorem 3.15 (Degree stability theorem).

Let $F$ be a graph with $\chi(F)=r+1\geq 3$. For every $\varepsilon>0$, there
exist $\delta>0$ and $n_{0}$ such that if $G$ is a graph on $n\geq n_{0}$
vertices, and $G$ is $F$-free such that
$\delta(G)\geq(1-\frac{1}{r}-\delta)n$, then the edit distance
$d(G,T_{r}(n))\leq\varepsilon n^{2}$.

Applying the degree stability theorem and the techniques of the proof in
Subsection 3.2, we can similarly prove the following corresponding theorem for
all color-critical graphs.

######  Theorem 3.16.

If $F$ is a graph with a critical edge and $\chi(F)=r+1$ where $r\geq 2$, then
there exists an $n_{0}=n_{0}(F)$ such that

$\mathrm{ex}_{\delta}(n,F)=\delta(T_{r}(n))$

holds for all $n\geq n_{0}$, and the unique extremal graph is the Turán graph
$T_{r}(n)$.

###  3.6 The signless Laplacian spectral radius

Given a graph $G$, the signless Laplacian matrix of $G$ is defined as
$Q(G)=D(G)+A(G)$, where $D(G)=\mathrm{diag}(d_{1},\ldots,d_{n})$ is the degree
diagonal matrix and $A(G)$ is the adjacency matrix. We denote by $q(G)$ the
largest eigenvalue of $Q(G)$. Since $Q(G)$ is a positive semidefinite matrix,
its largest eigenvalue is actually the spectral radius. Hence we call $q(G)$
the signless Laplacian spectral radius of $G$.

A natural question is to extend the above-mentioned results on the adjacency
spectral radius to that of the signless Laplacian spectral radius. We define
$\mathrm{ex}_{q}(n,F)$ to be the largest eigenvalue of the signless Laplacian
matrix in an $n$-vertex graph that contains no copy of $F$. That is,

$\mathrm{ex}_{q}(n,F):=\max\bigl{\\{}q(G):|G|=n~{}\text{and}~{}F\nsubseteq
G\bigr{\\}}.$

Note that $Q(G)=D(G)-A(G)+2A(G)$ and $D(G)-A(G)$ is positive semidefinite. It
is known by the Weyl theorem for monotonicity of eigenvalues that
$2\lambda(G)\leq q(G)$. Thus any upper bound on $q(G)$ yields an upper bound
on $\lambda(G)$.

In 2013, He, Jin and Zhang [18] proved that if $G$ is an $n$-vertex
$K_{r+1}$-free graph, then $q(G)\leq q(T_{r}(n))$. Moreover, the equality
holds if and only if $G$ is a complete bipartite graph (not necessarily
balanced) for $r=2$ or $G=T_{r}(n)$ for $r\geq 3$. In other words, we have

$\mathrm{ex}_{q}(n,K_{r+1})=q(T_{r}(n)).$ (9)

It is worth noting that the extremal graphs for the case $r=2$ are not unique.
This phenomenon is surprisingly different from the extremal problem on the
adjacency spectral radius. Moreover, the signless Laplacian spectral Turán
theorem (9) also implies the classical Turán theorem (1); see [18, Corollary
2.5].

It is natural to consider the extremal problem for signless Laplacian radius
for general graphs. However, the Erdős–Stone–Simonovits type result and the
Erdős–Simonovits type stability result in terms of the signless Laplacian
spectral radius do not hold.

Remark. Let $F$ be a graph with chromatic number $\chi(F)=r+1$. The
Erdős–Stone type result
$\mathrm{ex}_{q}(n,F)=\left(1-\frac{1}{r}\right)2n+o(n)$ is not necessary to
be true.

The result is negative in the case $F=C_{2k+2}$ for every integer $k\geq 1$.

  * •

First of all, we take $F=C_{4}$ as a counter-example. When $n$ is odd, let
$F_{n}$ be the friendship graph of order $n$, that is,
$F_{n}=K_{1}\vee\frac{n-1}{2}K_{2}$; When $n$ is even, let $F_{n}$ be the
graph obtained from $F_{n-1}$ by hanging an extra edge to its center. In other
words, the $F_{n}$ can be viewed as a graph obtained from $K_{1,n-1}$ by
adding a maximum matching within the independent set. Note that $F_{n}$ is
$C_{4}$-free. Upon computation, we get
$q(F_{n})=\frac{n+2+\sqrt{n^{2}-4n+12}}{2}$ for odd $n$; and
$q(F_{n})=\frac{n+1+\sqrt{n^{2}-2n+9}}{2}$ for even $n$. Thus we have
$\mathrm{ex}_{q}(n,C_{4})\geq n+o(1)$. But $\chi(C_{4})=2$ and
$(1-\frac{1}{r})2n+o(n)=o(n)$.

  * •

For the case $k\geq 2$, let $S_{n,k}$ be the graph consisting of a clique on
$k$ vertices and an independent set on $n-k$ vertices in which each vertex of
the clique is adjacent to each vertex of the independent set. We can observe
that $S_{n,k}$ does not contain $C_{2k+2}$ as a subgraph. Furthermore, let
$S_{n,k}^{+}$ be the graph obtained from $S_{n,k}$ by adding an edge to the
independent set $I_{n-k}$. In the language of join of graphs, we have
$S_{n,k}^{+}=K_{k}\vee I_{n-k}^{+}$. Clearly, we can see that $S_{n,k}^{+}$ is
still $C_{2k+2}$-free and

$q(S_{n,k}^{+})>q(S_{n,k})=\frac{n+2k-2+\sqrt{(n+2k-2)^{2}-8k^{2}+8k}}{2}.$

Hence either the graph $S_{n,k}$ or $S_{n,k}^{+}$ can yield
$\mathrm{ex}_{q}(n,C_{2k+2})\geq n+o(n)$. However we have $\chi(C_{2k+2})=2$
and $(1-\frac{1}{r})2n+o(n)=o(n)$.

It is worth noting that Freitas, Nikiforov and Patuzzi [7] showed that
$\mathrm{ex}(n,C_{4})=q(F_{n})$ and $F_{n}$ is the unique extremal graph.
Moreover, Nikiforov and Yuan [40] proved
$\mathrm{ex}_{q}(n,C_{2k+2})=q(S_{n,k}^{+})$ for all $k\geq 2,n\geq 400k^{2}$
and $S_{n,k}^{+}$ is the unique extremal graph. It is a problem whether the
condition can be relax to $n\geq ck$ for some constant $c>0$. In addition, it
is meaningful to determine graphs $F$ satisfying
$\mathrm{ex}_{q}(n,F)=\left(1-\frac{1}{r}\right)2n+o(n)$.

For the signless Laplacian radius, one may make the following remark.

Remark. The following statement is not true: For any graph $F$ with
$\chi(F)=r+1$, $r\geq 2$ and $\varepsilon>0$, there exist $\delta>0$ and
$n_{0}$ such that if $n\geq n_{0}$ and $G$ is an $F$-free graph on $n$
vertices with $q(G)\geq(1-\frac{1}{r}-\delta)2n$, then the edit distance
$d(G,T_{r}(n))\leq\varepsilon n^{2}$.

Indeed, we now consider the case $F=C_{2k+1}$ or $F=F_{2k+1}$ for every $k\geq
2$, where $F_{2k+1}$ is defined as the graph consisting of $k$ triangles
intersecting in exactly one common vertex. Note that
$\chi(C_{2k+1})=\chi(F_{2k+1})=3$. If $G$ is $C_{2k+1}$-free (or
$F_{2k+1}$-free) with $q(G)\geq(\frac{1}{2}-o(1))2n$, then we can not get
$d(G,T_{2}(n))=o(n^{2})$. The reasons are stated as below. Recall that
$S_{n,k}$ is the graph consisting of a clique on $k$ vertices and an
independent set on $n-k$ vertices in which each vertex of the clique is
adjacent to each vertex of the independent set. Clearly, we can see that
$S_{n,k}$ does not contain $C_{2k+1}$ and $F_{2k+1}$ as a subgraph. Taking
$G=S_{n,k}$, we calculate that $q(S_{n,k})\sim
n+2k-2\geq(\frac{1}{2}-o(1))2n$. However, the fact $e(S_{n,k})={k\choose
2}+k(n-k)$, which together with $T_{2}(n)=\lfloor n^{2}/4\rfloor$ implies
$d(G,T_{2}(n))\geq\Omega(n^{2})$ for fixed integer $k$.

We mention here that for $k=1$, the $C_{3}$-free graphs attaining the maximum
signless Laplacian radius are complete bipartite graphs [18]. For $k\geq 2$,
the $C_{2k+1}$-free graph attains the maximum signless Laplacian radius is
uniquely the split graph $S_{n,k}=K_{k}\vee I_{n-k}$. This result was proved
by Freitas, Nikiforov and Patuzzi [7] for $k=2$ and $n\geq 6$, and by Yuan
[49] for $k\geq 3$ and $n\geq 110k^{2}$. In addition, the $T_{k}$-free graph
attains the maximum signless Laplacian radius is also the split graph
$S_{n,k}$. This result was recently proved by Zhao, Huang and Guo [50] for
$k\geq 2$ and $n\geq 3k^{2}-k-2$. It is interesting that whether these results
are valid for $n\geq ck$ for some $c>0$.

Remark. The above example for $F=C_{2k+1}$ implies that the following
statement is not true. If $F$ is a graph with a critical edge and
$\chi(F)=r+1$ where $r\geq 2$, then there exists an $n_{0}=n_{0}(F)$ such that
$\mathrm{ex}_{q}(n,F)=q(T_{r}(n))$ holds for all $n\geq n_{0}$, and the unique
extremal graph is the Turán graph $T_{r}(n)$.

##  4 Concluding remarks

We remark that the statement of Theorem 1.4 and Theorem 3.2 are
simplifications of [35, Theorem 2] and [34, Theorem 2], respectively.
Nikiforov’s original stability theorems (spectral and non-spectral) are a lot
more detailed and contain a lot more quantitative bound. The purpose was to
present theorems that can be used as tools in other theorems. It seems
impossible that his original stability theorems can be deduced from the
Erdős–Simonovits theorem, or by the Regularity Lemma.

Recall that $A(G)$ and $D(G)$ are the adjacency matrix and degree diagonal
matrix of $G$. The signless Laplacian matrix of $G$ is defined as
$Q(G)=D(G)+A(G)$. It was proposed by Nikiforov [41] to study the family of
matrices $A_{\alpha}$ defined for any real $\alpha\in[0,1]$ as

$A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G).$

In particular, we can see that $A_{0}(G)=A(G)$ and $2A_{1/2}(G)=Q(G)$.
Nikiforov told us that he [41, Theorem 27] proved a unified extension of both
(2) and (9), which states that for every $r\geq 2$ and every $K_{r+1}$-free
graph $G$, if $0\leq\alpha<1-\frac{1}{r}$, then
$\lambda(A_{\alpha}(G))<\lambda(A_{\alpha}(T_{r}(n)))$, unless $G=T_{r}(n)$;
if $\alpha=1-\frac{1}{r}$, then $\lambda(A_{\alpha}(G))<(1-\frac{1}{r})n$,
unless $G$ is a complete $r$-partite graph; if $1-\frac{1}{r}<\lambda<1$, then
$\lambda(A_{\alpha}(G))<\lambda(A_{\alpha}(S_{n,r-1}))$, unless $G=S_{n,r-1}$,
where $S_{n,k}=K_{k}\vee I_{n-k}$. From this evidence, it is possible to
extend the results of our paper into the $A_{\alpha}$-spectral radius in the
range $\alpha\in[0,1-\frac{1}{r})$.

At the end of this paper, we propose a problem related to the recent progress
on stability type theorems. Let $f_{r}(n,t)$ be the smallest number such that
any $K_{r+1}$-free graph $G$ with $e(G)\geq e(T_{r}(n))-t$ edges can be made
$r$-partite by deleting at most $f_{r}(n,t)$ edges. The Erdős–Simonovits
stability theorem implies that $f_{r}(n,t)=o(n^{2})$ if $t=o(n^{2})$. Very
recently, Korándi, Roberts and Scott [23] proved that $f_{r}(n,t)$ is
witnessed by a pentagonal Turán graph if $t$ is small enough, which confirmed
a conjecture of Balogh, Clristian, Lavrov, Lidický and Pfender [2].

######  Theorem 4.1 (Korándi–Roberts–Scott, 2021).

For every $r\geq 2$, there is a $\delta_{r}>0$ such that if $G$ is a
$K_{r+1}$-free graph on $n$ vertices with $e(G)\geq
e(T_{r}(n))-\delta_{r}n^{2}$ edges, then there is a pentagonal Turán graph
$G^{*}$ on $n$ vertices with $e(G^{*})\geq e(G)$ and $D_{r}(G^{*})\geq
D_{r}(G)$.

It is natural to consider the corresponding spectral problem.

######  Problem 4.2.

For every $r\geq 2$, there is a $\delta_{r}>0$ such that if $G$ is a
$K_{r+1}$-free graph on $n$ vertices with
$\lambda(G)\geq\lambda(T_{r}(n))-\delta_{r}n$, then there is a pentagonal
Turán graph $G^{*}$ on $n$ vertices with $\lambda(G^{*})\geq\lambda(G)$ and
$D_{r}(G^{*})\geq D_{r}(G)$.

### Acknowledgements

This paper is dedicated to Vladimir Nikiforov whose beautiful works on
spectral graph theory inspire the author. The first author would like to thank
Prof. Lihua Feng, who introduced and encouraged him to the study of
fascinating spectral graph theory when he was a graduate student at Central
South University. Thanks also go to Prof. Vladimir Nikiforov for valuable
comments and for pointing out references [51, 22].

## References

  * [1] N. Alon, C. Shikhelman, Many $T$ copies in $H$-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172.
  * [2] J. Balogh, F.C. Clemen, M. Lavrov, B. Lidický, F. Pfender, Making $K_{r+1}$-free graphs $r$-partite, Combin. Probab. Comput. 30 (4) (2021) 609–618.
  * [3] B. Bollobás, V. Nikiforov, Cliques and the spectral radius, J. Combin. Theory Ser. B 97 (2007) 859–865.
  * [4] B. Bollobás, V. Nikiforov, Joints in graphs, Discrete Math. 308 (2008) 9–19.
  * [5] S. Cioabă, L.H. Feng, M. Tait, X.-D. Zhang, The spectral radius of graphs with no intersecting triangles, Electron. J. Combin. 27 (4) (2020) P4.22.
  * [6] S. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin. 99 (2022) 103420.
  * [7] M.A.A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the $Q$-index: forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra 26 (2013) 905–916.
  * [8] D.N. Desai, L. Kang, Y. Li, Z. Ni, M. Tait, J. Wang, Spectral extremal graphs for intersecting cliques, 18 pages, (2021), arXiv: 2108.03587v2. See https://arxiv.org/abs/2108.03587v2
  * [9] P. Erdős, M. Simonovits, A limit theorem in graph theory, Stud. Sci. Math. Hungar. 1 (1966) 51–57.
  * [10] P. Erdős, A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087–1091.
  * [11] P. Erdős, On the number of complete subgraphs contained in certain graphs, Magy. Tud. Akad. Mat. Kut. Intéz. Közl. 7 (1962) 459–474.
  * [12] 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.
  * [13] P. Erdős, On some new inequalities concerning extremal properties of graphs, In: Theory of Graphs (Proceedings of the Colloquium, Tihany, 1966), Academic Press, New York, 1968, pp. 77–81.
  * [14] 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.
  * [15] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdős Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, pp. 169–264.
  * [16] Z. Füredi, A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity, J. Combin. Theory Ser. B 115 (2015) 66–71.
  * [17] B.D. Guiduli, Spectral extrema for graphs, Ph. D. Thesis, University of Chicago, December 1996. See http://people.cs.uchicago.edu/~laci/students/guiduli-phd.pdf
  * [18] B. He, Y.-L. Jin, X.-D. Zhang, Sharp bounds for the signless Laplacian spectral radius in terms of clique number, Linear Algebra Appl. 438 (2013) 3851–3861.
  * [19] L. Kang, V. Nikiforov, Extremal problem for the $p$-spectral radius of graphs, Electronic J. Combin. 21 (3) (2014) 87–101.
  * [20] P. Keevash, Hypergraph Turán problems, in Surveys in Combinatorics, Cambridge University Press, Cambridge, 2011, pp. 83–140.
  * [21] P. Keevash, J. Lenz, D. Mubayi, Spectral extremal problems for hypergraphs, SIAM J. Discrete Math. 28 (4) (2014) 1838–1854.
  * [22] N. Khadzhiivanov, Inequalities for graphs (in Russian), C. R. Acad. Sci. Bul. 30 (1977) 793–796.
  * [23] D. Korándi, A. Roberts, A. Scott, Exact stability for Turán theorem, Advances in Combinatorics (9) 2021, 17pp. See https://doi.org/10.19086/aic.31079.
  * [24] Y. Li, Y. Peng, The spectral radius of graphs with no intersecting odd cycles, 22 pages, Discrete Math. (2022), to appear, arXiv: 2106.00587. See https://arxiv.org/abs/2106.00587.
  * [25] X. Liu, New short proofs to some stability theorems, European J. Combin. 96 (2021) 103350.
  * [26] J. Ma, X. Yu, Some notes on Extremal Combinatorics, a lecture notes for Tianyuan Mathematics Foundation 2018 Summer School on Graph Theory.
  * [27] J. Ma, Y. Qiu, Some sharp results on the generalized Turán numbers, European J. Combin. 84 (2020) 103026.
  * [28] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189.
  * [29] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra Appl. 427 (2007) 183–189.
  * [30] V. Nikiforov, Graphs with many $r$-cliques have large complete $r$-partite subgraphs, Bull. London Math. Soc. 40 (2008) 23–25.
  * [31] V. Nikiforov, A spectral condition for odd cycles in graphs, Linear Algebra Appl. 428 (2008) 1492–1498.
  * [32] V. Nikiforov, More spectral bounds on the clique and independence numbers, J. Combin. Theory Ser. B 99 (6) (2009) 819–826.
  * [33] V. Nikiforov, A spectral Erdős–Stone–Bollobás theorem, Combin. Probab. Comput. 18 (2009) 455–458.
  * [34] V. Nikiforov, Spectral saturation: inverting the spectral Turán theorem, Electron. J. Combin. 16 (1) (2009) R 33.
  * [35] V. Nikiforov, Stability for large forbidden subgraphs, J. Graph Theory 62 (4) (2009) 362–368.
  * [36] V. Nikiforov, Turán’s theorem inverted, Discrete Math. 310 (1) (2010) 125–131.
  * [37] V. Nikiforov, Some new results in extremal graph theory, Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011, pp. 141–181.
  * [38] V. Nikiforov, An extension of Maclaurin’s inequality, 7 pages, Preprint, 2006/2013, arXiv: math/0608199v3. See https://arxiv.org/abs/math/0608199v3.
  * [39] V. Nikiforov, Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455–535.
  * [40] V. Nikiforov, X. Yuan, Maxima of the $Q$-index: Forbidden even cycles, Linear Algebra Appl. 471 (2015) 636–653.
  * [41] V. Nikiforov, Merging the $A$\- and $Q$-spectral theories, Appl. Anal. Discrete Math. 11 (1) (2017) 81–107.
  * [42] V. Nikiforov, Private communication, December 28, 2021.
  * [43] K. Popielarz, J. Sahasrabudhe, R. Snyder, A stability theorem for maximal $K_{r+1}$-free graphs, J. Combin. Theory Ser. B 132 (2018) 236–257.
  * [44] V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, Random Structures Algorithms 28 (2) (2006) 180–194.
  * [45] 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.
  * [46] M. Simonovits, Paul Erdős’ influence on Extremal graph theory, in The Mathematics of Paul Erdős II, R.L. Graham, Springer, New York, 2013, pp. 245–311.
  * [47] 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.
  * [48] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), pp. 436–452. (in Hungarian).
  * [49] X. Yuan, Maxima of the $Q$-index: Forbidden odd cycles, Linear Algebra Appl. 458 (2014) 207–216.
  * [50] Y. Zhao, X.Y. Huang, H. Guo, The signless Laplacian spectral radius of graphs with no intersecting triangles, Linear Algebra Appl. 618 (2021) 12–21.
  * [51] A.A. Zykov, On some properties of linear complexes (in Russian), Mat. Sbornik N.S. 24 (66) (1949) 163–188.


Reducing the number of factors/components is the same as reducing the size of
the space in which the primary variables are represented.

  * •

Based on the Pythagorean theorem, it is possible to analyze the standard
deviations and variance of individual original variables by analyzing the
lengths and squares of the lengths of the respective vector components.

  * •

Clustering of primary variables due to their mutual similarity, and also due
to the similarity to factors in factor analysis, and also due to the
similarity to principal components in principal component analysis, can be
performed by clustering vectors (points) due to their mutual similarity and
because of the similarity to the factors/components.

In addition to the practical aspects considered in the article, it is also
worth noting an aspect that probably has no practical significance, but is
somewhat surprising. This is true for the artifact that has been observed for
the vector representation of the primary variables in both PCA and FA. By
multiplying the matrix of row vectors representing the primary variables by
the transposition of the matrix of eigenvectors $U^{T}$, a symmetric matrix
was obtained. In this context, questions arose about the cause of the
phenomenon and about the possibility of its use. There is no answer to the
second question. The article found an algebraic answer to the first question.

## Acknowledgments

The author expresses his gratitude to Andrzej Ptasznik for making the Weather
Data available for analysis.

## References

  * [1] Z. Gniazdowski, “New Interpretation of Principal Components Analysis,” _Zeszyty Naukowe WWSI_ , vol. 11, no. 16, pp. 43–65, 2017. [Online]. Available: https://www.doi.org/10.26348/znwwsi.16.43
  * [2] P. Francuz and R. Mackiewicz, _Liczby nie wiedzą, skąd pochodzą. Przewodnik po metodologii i statystyce nie tylko dla psychologów_. Lublin: Wydawnictwo KUL, 2007.
  * [3] Z. Gniazdowski, “Geometric interpretation of a correlation,” _Zeszyty Naukowe WWSI_ , vol. 7, no. 9, pp. 27–35, 2013. [Online]. Available: https://www.doi.org/10.26348/znwwsi.9.27
  * [4] J. Legras, _Praktyczne metody analizy numerycznej_. Wydawnictwa Naukowo-Techniczne, 1974.
  * [5] D. T. Larose, _Data mining methods & models_. John Wiley & Sons, 2006.
  * [6] E. Mooi, M. Sarstedt, and I. Mooi-Reci, “Principal Component and Factor Analysis,” in _Market Research: The Process, Data, and Methods Using Stata_. Singapore: Springer Singapore, 2018, pp. 265–311. [Online]. Available: https://doi.org/10.1007/978-981-10-5218-7_8
  * [7] B. Thompson, _Exploratory and confirmatory factor analysis: Understanding concepts and applications_. Washington, DC: American Psychological Association, 2004.
  * [8] R. A. Fisher, “The use of multiple measurements in taxonomic problems,” _Annals of eugenics_ , vol. 7, no. 2, pp. 179–188, 1936. [Online]. Available: https://doi.org/10.1111/j.1469-1809.1936.tb02137.x
  * [9] S. Ertel, _Factor analysis-Healing an ailing model_. Universitätsverlag Göttingen, 2013.
  * [10] C. F. Hofacker, _Mathematical marketing_. New South Network Services, 2007.
  * [11] A. Phakiti, “Exploratory factor analysis,” in _The Palgrave handbook of applied linguistics research methodology_. Springer, 2018, pp. 423–457.
  * [12] H. F. Kaiser, “The varimax criterion for analytic rotation in factor analysis,” _Psychometrika_ , vol. 23, no. 3, pp. 187–200, 1958. [Online]. Available: https://doi.org/10.1007/BF02289233
  * [13] H. Abdi, “Factor rotations in factor analyses,” in _Encyclopedia for Research Methods for the Social Sciences_. Thousand Oaks, CA: Sage, 2003, pp. 792–795.
  * [14] M. Loève, “Elementary Probability Theory,” in _Probability Theory I_. New York, NY: Springer New York, 1977, pp. 1–52. [Online]. Available: https://doi.org/10.1007/978-1-4684-9464-8_1
  * [15] R. K. Pace and R. Barry, “Sparse spatial autoregressions,” _Statistics & Probability Letters_, vol. 33, no. 3, pp. 291–297, 1997. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S016771529600140X
  * [16] ——, “Data from: Sparse spatial autoregressions,” 1999. [Online]. Available: http://lib.stat.cmu.edu/datasets/houses.zip
  * [17] Z. Gniazdowski and D. Kaliszewski, “On the clustering of correlated random variables,” _Zeszyty Naukowe WWSI_ , vol. 12, no. 18, pp. 45–114, 2018. [Online]. Available: https://www.doi.org/10.26348/znwwsi.18.45
  * [18] J. W. Poelstra, N. Vijay, M. Hoeppner, and J. B. Wolf, “Transcriptomics of colour patterning and coloration shifts in crows,” _Molecular ecology_ , vol. 24, no. 18, pp. 4617–4628, 2015.
  * [19] J. W. Poelstra, N. Vijay, M. P. Höppner, and J. B. W. Wolf, “Data from: Transcriptomics of colour patterning and colouration shifts in crows,” 2015. [Online]. Available: https://doi.org/10.5061/dryad.hv333
  * [20] J. Gerritsma, R. Onnink, and A. Versluis, “Yacht Hydrodynamics,” UCI Machine Learning Repository, 2013. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/YachtHydrodynamics
  * [21] O. Akbilgic, “Istanbul Stock Exchange,” UCI Machine Learning Repository, 2013\. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/ISTANBULSTOCKEXCHANGE