# On a conjecture of spectral extremal problems††thanks: This research was
partially supported by the National Nature Science Foundation of China (Nos.
11871329, 11971298)

Jing Wang, Liying Kang, Yisai Xue
Department of Mathematics, Shanghai University, Shanghai 200444, P.R. China
Corresponding author.
Email address<EMAIL_ADDRESS>(L. Kang<EMAIL_ADDRESS>(J. Wang),
<EMAIL_ADDRESS>(Y. Xue)

###### Abstract

For a simple graph $F$, let $\mathrm{Ex}(n,F)$ and $\mathrm{Ex_{sp}}(n,F)$
denote the set of graphs with the maximum number of edges and the set of
graphs with the maximum spectral radius in an $n$-vertex graph without any
copy of the graph $F$, respectively. The Turán graph $T_{n,r}$ is the complete
$r$-partite graph on $n$ vertices where its part sizes are as equal as
possible. Cioabă, Desai and Tait [The spectral radius of graphs with no odd
wheels, European J. Combin., 99 (2022) 103420] posed the following conjecture:
Let $F$ be any graph such that the graphs in $\mathrm{Ex}(n,F)$ are Turán
graphs plus $O(1)$ edges. Then $\mathrm{Ex_{sp}}(n,F)\subset\mathrm{Ex}(n,F)$
for sufficiently large $n$. In this paper we consider the graph $F$ such that
the graphs in $\mathrm{Ex}(n,F)$ are obtained from $T_{n,r}$ by adding $O(1)$
edges, and prove that if $G$ has the maximum spectral radius among all
$n$-vertex graphs not containing $F$, then $G$ is a member of
$\mathrm{Ex}(n,F)$ for $n$ large enough. Then Cioabă, Desai and Tait’s
conjecture is completely solved.

Key words: Spectral radius; Spectral extremal graph; Turán graph.

##  1 Introduction

Let $F$ be a simple graph. A graph $G$ is $F$-free if there is no subgraph of
$G$ isomorphic to $F$. The Turán type extremal problem is to determine the
maximum number of edges in a graph on $n$ vertices that is $F$-free, and the
maximum number of edges is called the Turán number, denoted by
$\mathrm{ex}(n,F)$. Such a graph with $\mathrm{ex}(n,F)$ edges is called an
extremal graph for $F$ and we denote by $\mathrm{Ex}(n,F)$ the set of all
extremal graphs on $n$ vertices for $F$. The Turán graph is the complete
$r$-partite graph on $n$ vertices where each partite set has either
$\lfloor\frac{n}{r}\rfloor$ or $\lceil\frac{n}{r}\rceil$ vertices and the edge
set consists of all pairs joining distinct parts, denoted by $T_{n,r}$. The
well-known Turán Theorem [26] states that the extremal graph corresponding to
Turán number $\mathrm{ex}(n,K_{r+1})$ is $T_{n,r}$, i.e.
$\mathrm{ex}(n,K_{r+1})=e(T_{n,r})$. Erdős, Stone and Simonovits [12, 11]
presented the following result

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

where $\chi(F)$ is the vertex-chromatic number of $F$. There are lots of
researches on Turán type extremal problems (such as [2, 13, 3, 17, 24, 16]).

In this paper we focus on spectral analogues of the Turán type problem for
graphs, which was proposed by Nikiforov [20]. The spectral Turán type problem
is to determine the maximum spectral radius instead of the number of edges
among all $n$-vertex $F$-free graphs. The graph which attains the maximum
spectral radius is called a spectral extremal graph. We denote by
$\mathrm{Ex_{sp}}(n,F)$ the set of all spectral extremal graphs for $F$.
Researches of the spectral Turán type problem have drawn increasing extensive
intersect (see [18, 1, 15, 22, 28]). Nikiforov [19] showed that if $G$ is a
$K_{r+1}$-free graph on $n$ vertices, then $\lambda(G)\leq\lambda(T_{n,r})$,
with equality if and only if $G=T_{n,r}$. This implies that if $G$ attains the
maximum spectral radius over all $n$-vertex $K_{r+1}$-free graphs for
sufficiently large $n$, then $G\in\mathrm{Ex}(n,K_{r+1})$. Cioabă, Feng, Tait
and Zhang [4] proved that the spectral extremal graph for $F_{k}$ belongs to
$\mathrm{Ex}(n,F_{k})$, where $F_{k}$ is the graph consisting of $k$ triangles
which intersect in exactly one common vertex. In addition, Chen, Gould,
Pfender and Wei [3] proved that $\mathrm{ex}(n,F_{k,r+1})=e(T_{n,r})+O(1)$,
where $F_{k,r+1}$ is the graph consisting of $k$ copies of $K_{r+1}$ which
intersect in a single vertex. Naturally, Cioabă, Desai and Tait [5] raised the
following conjecture.

######  Conjecture 1.1 (Cioabă et al. [5]).

Let $F$ be any graph such that the graphs in $\mathrm{Ex}(n,F)$ are Turán
graphs plus $O(1)$ edges. Then $\mathrm{Ex_{sp}}(n,F)\subset\mathrm{Ex}(n,F)$
for sufficiently large $n$.

The results of Nikiforov [19], Cioabă, Feng, Tait and Zhang [4], Li and Peng
[27], and Desai, Kang, Li, Ni, Tait and Wang [8] tell us that Conjecture 1.1
holds for $K_{r+1}$, $F_{k}$, $H_{s,k}$ and $F_{k,r}$, where $H_{s,k}$ is the
graph defined by intersecting $s$ triangles and $k$ odd cycles of length at
least $5$ in exactly one common vertex. In this paper, we shall prove the
following theorem which confirms Conjecture 1.1.

######  Theorem 1.2.

Let $r\geq 2$ be an integer, and $F$ be any graph such that the graphs in
$\mathrm{Ex}(n,F)$ are obtained from $T_{n,r}$ by adding $O(1)$ edges. For
sufficiently large $n$, if $G$ has the maximal spectral radius over all
$n$-vertex $F$-free graphs, then

$G\in\mathrm{Ex}(n,F).$

##  2 Notation and Preliminaries

In this section we introduce some notation and give the preparatory lemmas.

Let $G=(V(G),E(G))$ be a simple graph with vertex set $V(G)$ and edge set
$E(G)$. If $u,v\in V(G)$, and $uv\in E(G)$, then $u$ and $v$ are said to be
adjacent. For a vertex $v\in V(G)$, the neighborhood $N_{G}(v)$ (or simply
$N(v)$) of $v$ is $\\{u|\ uv\in E(G)\\}$, and the degree $d_{G}(v)$ (or simply
$d(v)$) of $v$ is $|N_{G}(v)|$. The minimum and maximum degrees are denoted by
$\delta(G)$ and $\Delta(G)$, respectively. For $S\subseteq V(G)$ and $v\in
V(G)$, let $d_{S}(v)=|N_{S}(v)|=|N_{G}(v)\cap S|$. For $V_{1},V_{2}\subseteq
V(G)$, $e(V_{1},V_{2})$ denotes the number of edges of $G$ between $V_{1}$ and
$V_{2}$. For $S\subseteq V(G)$, denote by $G\setminus S$ the graph obtained
from $G$ by deleting all vertices of $S$ and the incident edges. Denote by
$G[S]$ the graph induced by $S$ whose vertex set is $S$ and whose edge set
consists of all edges of $G$ which have both ends in $S$.

Let $G$ be a simple graph with $n$ vertices. The adjacent matrix of $G$ is
$A(G)=(a_{ij})_{n\times n}$ with $a_{ij}=1$ if $ij\in E(G)$, and $a_{ij}=0$
otherwise. The spectral radius of $G$ is the largest eigenvalue of $A(G)$,
denoted by $\lambda(G)$. Let $G_{1},\ldots,G_{s}$ be the components of $G$,
then $\lambda(G)=\max\\{\lambda(G_{i})|\ i\in[s]\\}$. For a connected graph
$G$, let $\mathbf{x}=(x_{1},\ldots,x_{n})^{\mathrm{T}}$ be an eigenvector of
$A(G)$ corresponding to $\lambda(G)$. Then $\mathbf{x}$ is a positive real
vector, and

$\lambda(G)x_{i}=\sum_{ij\in E(G)}x_{j},\text{ for any }i\in[n].$ (2)

The following Rayleigh quotient equation is very useful:

$\lambda(G)=\max_{\mathbf{x}\in\mathbb{R}^{n}_{+}}\frac{\mathbf{x}^{\mathrm{T}}A(G)\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}=\max_{\mathbf{x}\in\mathbb{R}^{n}_{+}}\frac{2\sum_{ij\in
E(G)}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}.$ (3)

We have the following two lemmas from Zhan [29].

######  Lemma 2.1 (Zhan [29]).

Let $A$ and $B$ be two nonnegative square matrices. If $B<A$ and $A$ is
irreducible, then $\lambda(B)<\lambda(A)$.

######  Lemma 2.2 (Zhan [29]).

Let $A$ be a nonnegative square matrix. If $B$ is a principal submatrix of
$A$, then $\lambda(B)\leq\lambda(A)$. If $A$ is irreducible and $B$ is a
proper principal submatrix of $A$, then $\lambda(B)<\lambda(A)$.

Let $A(G)$ be the adjacent matrix of graph $G$. Then $G$ is connected if and
only if $A(G)$ is irreducible. Combining with Lemmas 2.1 and 2.2, we have the
following result.

######  Lemma 2.3.

Let $G$ be a connected graph. If $G^{\prime}$ is a proper subgraph of $G$,
then $\lambda(G^{\prime})<\lambda(G)$.

Recall the classical stability theorem proved by Erdős [9, 10] and Simonovits
[23]:

######  Lemma 2.4 (Erdős [9, 10], Simonovits [23]).

For every $r\geq 2,\varepsilon>0$, and $(r+1)$-chromatic graph $F$, there
exists $\delta>0$ such that if a graph $G$ of order $n$ satisfies
$e(G)>(1-\frac{1}{r}-\delta)\frac{n^{2}}{2}$, then either $G$ contains $F$, or
$G$ differs form $T_{n,r}$ in at most $\varepsilon n^{2}$ edges.

Write $K_{r}(n_{1},\ldots,n_{r})$ for the complete $r$-partite graph with
classes of sizes $n_{1},\ldots,n_{r}$. Nikiforov [21] proved the spectral
version of Stability Lemma.

######  Lemma 2.5 (Nikiforov [21]).

Let $r\geq 2,1/\ln n<c<r^{-8(r+21)(r+1)},0<\varepsilon<2^{-36}r^{-24}$ and $G$
be a graph on $n$ vertices. If $\lambda(G)>(1-\frac{1}{r}-\varepsilon)n$, then
one of the following statements holds:
(a) $G$ contains a $K_{r+1}(\lfloor c\ln n\rfloor,\ldots,\lfloor c\ln
n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
(b) $G$ differs from $T_{n,r}$ in fewer than
$(\varepsilon^{1/4}+c^{1/(8r+8)})n^{2}$ edges.

From the above theorem, one can easily get the following result.

######  Corollary 2.6.

Let $F$ be a graph with chromatic number $\chi(F)=r+1$. 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 with
$\lambda(G)\geq(1-\frac{1}{r}-\delta)n$, then $G$ can be obtained from
$T_{n,r}$ by adding and deleting at most $\varepsilon n^{2}$ edges.

For $K_{r}(n_{1},n_{2},\ldots,n_{r})$, let $n=\sum_{i=1}^{r}n_{i}$. For
convenience, we assume that $n_{1}\geq n_{2}\geq\ldots\geq n_{r}>0$. It is
well-known [6, p. 74] or [7] that the characteristic polynomial of
$K_{r}(n_{1},n_{2},\ldots,n_{r})$ is given as

$\phi(K_{r}(n_{1},n_{2},\ldots,n_{r}),x)=x^{n-r}\left(1-\sum_{i=1}^{r}\frac{n_{i}}{x+n_{i}}\right)\prod_{j=1}^{r}(x+n_{j}).$

So the spectral radius $\lambda(K_{r}(n_{1},n_{2},\ldots,n_{r}))$ satisfies
the following equation:

$\sum_{i=1}^{r}\frac{n_{i}}{\lambda(K_{r}(n_{1},n_{2},\ldots,n_{r}))+n_{i}}=1$
(4)

Feng, Li and Zhang [14, Theorem 2.1] proved the following lemma, which can
also be seen in Stevanović, Gutnam and Rehman [25].

######  Lemma 2.7 (Feng et al. [14], Stevanović et al. [25]).

If $n_{i}-n_{j}\geq 2$, then

$\lambda(K_{r}(n_{1},\ldots,n_{i}-1,\ldots,n_{j}+1,\ldots,n_{r}))>\lambda(K_{r}(n_{1},\ldots,n_{i},\ldots,n_{j},\ldots,n_{r})).$

The following lemma was given in [4].

######  Lemma 2.8 (Cioabă et al. [4]).

Let $A_{1},\ldots,A_{p}$ be finite sets. Then

$|A_{1}\cap\ldots\cap
A_{p}|\geq\sum_{i=1}^{p}|A_{i}|-(p-1)\bigg{|}\bigcup_{i=1}^{p}A_{i}\bigg{|}.$

##  3 Proof of Theorem 1.2

Let $F$ be any graph such that the graphs in $\mathrm{Ex}(n,F)$ are Turán
graphs plus $O(1)$ edges. We may assume that the graphs in $\mathrm{Ex}(n,F)$
are obtained from $T_{n,r}$ by adding $a$ edges. Then
$\mathrm{ex}(n,F)=e(T_{n,r})+a$, which implies that $\chi(F)=r+1$ by (1) and
the fact $(1-\frac{1}{r})\frac{n^{2}}{2}-\frac{r}{8}\leq
e(T_{n,r})\leq(1-\frac{1}{r})\frac{n^{2}}{2}$. In the sequel, we always assume
that $G$ is a graph on $n$ vertices containing no $F$ as a subgraph and
attaining the maximum spectral radius. The aim of this section is to prove
that $G$ is obtained from $T_{n,r}$ by adding $a$ edges for $n$ large enough.

The sketch of our proof is as follows: Firstly, we give a lower bound on
$\lambda(G)$, and determine a partition $V(G)=V_{1}\cup\cdots\cup V_{r}$ such
that $\sum_{1\leq i<j\leq r}e(V_{i},V_{j})$ attains the maximum by using the
spectral version of Stability Lemma. Then we show that any vertex except at
most $2a$ vertices in $V_{i}$ is adjacent to all vertices in $V_{j}$ for any
$i,j\in[r]$ and $j\not=i$. Next, we prove that all vertices have eigenvector
entry very close to the maximum entry and show that the partition is balanced.
Finally, we prove $e(G)=\mathrm{ex}(n,F)$ by contradiction.

######  Lemma 3.1.

$G$ is connected.

###### Proof.

Suppose to the contrary that $G$ is not connected. Assume $G_{1},\ldots,G_{s}$
are the components of $G$ and $\lambda(G_{1})=\max\\{\lambda(G_{i})|\
i\in[s]\\}$, then $\lambda(G)=\lambda(G_{1})$ and $|V(G_{1})|\leq n-1$. For
any vertex $u\in V(G_{1})$, let $G^{\prime}$ be the graph obtained from
$G_{1}$ by adding a pendent edge $uv$ at $u$ and $n-1-|V(G_{1})|$ isolated
vertices. Then $\lambda(G^{\prime})>\lambda(G_{1})=\lambda(G)$ by Lemma 2.3.
This implies that $G^{\prime}$ contains a copy of $F$ as a subgraph, denote it
as $F_{1}$, then $uv$ is an edge of $F_{1}$. Next, we claim that
$d_{G_{1}}(u)<|V(F)|$. Otherwise, $d_{G_{1}}(u)\geq|V(F)|$. Then there exists
a vertex $w\in N_{G_{1}}(u)$ and $w\notin V(F_{1})$. Then $F_{1}-uv+uw$ is a
copy of $F$ in $G_{1}$, this is a contraction. Due to the arbitrary of vertex
$u$, $\Delta(G_{1})<|V(F)|$. Thus
$\lambda(G)=\lambda(G_{1})\leq\Delta(G_{1})<|V(F)|<\lambda(T_{n,r})$ and this
contradicts the fact that $G$ has the maximum spectral radius among all
$n$-vertex $F$-free graphs as $T_{n,r}$ is $F$-free. Therefore, $G$ is
connected. ∎

In the following, let $\lambda(G)$ be the spectral radius of $G$, $\mathbf{x}$
be a positive eigenvector corresponding to $\lambda(G)$ with $\max\\{x_{i}|\
i\in V(G)\\}=1$. Without loss of generality, we assume that $x_{z}=1$. If
there are multiple such vertices, we choose and fix $z$ arbitrarily among
them.

######  Lemma 3.2.

$\lambda(G)\geq\bigg{(}1-\frac{1}{r}\bigg{)}n-\frac{r}{4n}+\frac{2a}{n}.$

###### Proof.

Let $H$ be an $F$-free graph on $n$ vertices with maximum number of edges.
Since $G$ attains the maximum spectral radius over all $n$-vertex $F$-free
graphs, and $\mathrm{ex}(n,F)=e(T_{n,r})+a$, by the Rayleigh quotient
equation, we have

$\lambda(G)\geq\lambda(H)\geq\frac{\mathbf{1}^{T}A(H)\mathbf{1}}{\mathbf{1}^{T}\mathbf{1}}=\frac{2(e(T_{n,r})+a)}{n}\geq\frac{2}{n}\left(\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}-\frac{r}{8}+a\right)\geq\left(1-\frac{1}{r}\right)n-\frac{r}{4n}+\frac{2a}{n}.$

∎

Let $\ell$ be an integer satisfying $\ell\gg\max\\{a,|V(F)|\\}$.

######  Lemma 3.3.

For every $\epsilon>0$, there exists an integer $n_{0}$ such that if $n\geq
n_{0}$, then

$e(G)\geq e(T_{n,r})-\epsilon n^{2}.$

Furthermore, $G$ has a partition $V(G)=V_{1}\cup\ldots\cup V_{r}$ such that
$\sum_{1\leq i<j\leq r}e(V_{i},V_{j})$ attains the maximum, and

$\sum_{i=1}^{r}e(V_{i})\leq\epsilon n^{2},$

and for each $i\in[r]$,

$\left(\frac{1}{r}-3\sqrt{\epsilon}\right)n<|V_{i}|<\left(\frac{1}{r}+3\sqrt{\epsilon}\right)n.$

###### Proof.

From Lemma 3.2 and Corollary 2.6, it follows that $G$ is obtained from
$T_{n,r}$ by adding or deleting at most $\epsilon n^{2}$ edges for large
enough $n$. Then there is a partition of $V(G)=U_{1}\cup\ldots\cup U_{r}$ with
$\sum_{i=1}^{r}e(U_{i})\leq\epsilon n^{2}$, $\sum_{1\leq i<j\leq
r}e(U_{i},U_{j})\geq e(T_{n,r})-\epsilon n^{2}$ and
$\lfloor\frac{n}{r}\rfloor\leq|U_{i}|\leq\lceil\frac{n}{r}\rceil$ for each
$i\in[r]$. So $e(G)\geq e(T_{n,r})-\epsilon n^{2}$. Furthermore, $G$ has a
partition $V=V_{1}\cup\ldots\cup V_{r}$ such that $\sum_{1\leq i<j\leq
r}e(V_{i},V_{j})$ attains the maximum. In this case,
$\sum_{i=1}^{r}e(V_{i})\leq\sum_{i=1}^{r}e(U_{i})\leq\epsilon n^{2}$ and
$\sum_{1\leq i<j\leq r}e(V_{i},V_{j})\geq\sum_{1\leq i<j\leq
r}e(U_{i},U_{j})\geq e(T_{n,r})-\epsilon n^{2}$. Let
$s=\max\left\\{\left||V_{j}|-\frac{n}{r}\right|,j\in[r]\right\\}$. Without
loss of generality, we assume $\left||V_{1}|-\frac{n}{r}\right|=s$. Then

$\displaystyle e(G)$ $\displaystyle\leq$ $\displaystyle\sum_{1\leq i<j\leq
r}|V_{i}||V_{j}|+\sum_{i=1}^{r}e(V_{i})$ $\displaystyle\leq$
$\displaystyle|V_{1}|(n-|V_{1}|)+\sum_{2\leq i<j\leq r}|V_{i}||V_{j}|+\epsilon
n^{2}$ $\displaystyle=$
$\displaystyle|V_{1}|(n-|V_{1}|)+\frac{1}{2}\Big{(}(\sum_{j=2}^{r}|V_{j}|)^{2}-\sum_{j=2}^{r}|V_{j}|^{2}\Big{)}+\epsilon
n^{2}$ $\displaystyle\leq$
$\displaystyle|V_{1}|(n-|V_{1}|)+\frac{1}{2}(n-|V_{1}|)^{2}-\frac{1}{2(r-1)}(n-|V_{1}|)^{2}+\epsilon
n^{2}$ $\displaystyle<$
$\displaystyle-\frac{r}{2(r-1)}s^{2}+\frac{r-1}{2r}n^{2}+\epsilon n^{2},$

where the last second inequality holds by Hölder’s inequality, and the last
inequality holds since $\left||V_{1}|-\frac{n}{r}\right|=s$. On the other
hand,

$e(G)\geq e(T_{n,r})-\epsilon
n^{2}\geq\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}-\frac{r}{8}-\epsilon
n^{2}>\frac{r-1}{2r}n^{2}-2\epsilon n^{2},$

as $n$ is large enough. Therefore, $\frac{r}{2(r-1)}s^{2}<3\epsilon n^{2}$,
which implies that
$s<\sqrt{\frac{6(r-1)\epsilon}{r}n^{2}}<\sqrt{6\epsilon}n<3\sqrt{\epsilon}n$.
The proof is completed. ∎

######  Lemma 3.4.

Let $\theta>0$ and $\epsilon>0$ be sufficiently small constants with
$\theta<\frac{1}{100r^{5}\ell}$ and $2\epsilon<\theta^{3}$. We denote

$W:=\cup_{i=1}^{r}\\{v\in V_{i}|\ d_{V_{i}}(v)\geq 2\theta n\\},$ (5)

and

$L:=\bigg{\\{}v\in V(G)|\
d(v)\leq\bigg{(}1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\bigg{)}n\bigg{\\}}.$
(6)

Then $|L|\leq\epsilon^{\frac{1}{3}}n$ and $W\subseteq L$.

###### Proof.

We first prove the following claims. Claim 1. $|W|<\theta n$

###### Proof.

It follows from Lemma 3.3 that $\sum_{i=1}^{r}e(V_{i})\leq\epsilon n^{2}$. On
the other hand, let $W_{i}:=W\cap V_{i}$ for all $i\in[r]$. Then

$2e(V_{i})=\sum_{u\in V_{i}}d_{V_{i}}(u)\geq\sum_{u\in W_{i}}d_{V_{i}}(u)\geq
2|W_{i}|\theta n$

Thus

$\sum_{i=1}^{r}e(V_{i})\geq\sum_{i=1}^{r}|W_{i}|\theta n=|W|\theta n.$

Therefore, we have that $|W|\theta n\leq\epsilon n^{2}$. This proves that
$|W|\leq\frac{\epsilon n}{\theta}<\theta n.$ ∎

Claim 2. $|L|\leq\epsilon^{\frac{1}{3}}n$.

###### Proof.

Suppose to the contrary that $|L|>\epsilon^{\frac{1}{3}}n$. Then there exists
a subset $L^{\prime}\subseteq L$ with
$|L^{\prime}|=\lfloor\epsilon^{\frac{1}{3}}n\rfloor$. Therefore,

$\begin{split}e(G[V\setminus L^{\prime}])\geq e(G)-\sum_{v\in
L^{\prime}}d(v)&\geq e(T_{n,r})-\epsilon
n^{2}-\epsilon^{\frac{1}{3}}n^{2}\bigg{(}1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\bigg{)}\\\
&>\frac{(n-\lfloor\epsilon^{\frac{1}{3}}n\rfloor)^{2}}{2}\bigg{(}1-\frac{1}{r}\bigg{)}+a\\\
&\geq e(T_{n^{\prime},r})+a=\mathrm{ex}(n^{\prime},F),\end{split}$

where $n^{\prime}=n-\lfloor\epsilon^{\frac{1}{3}}n\rfloor$ and $n$ is large
enough. However, $e(G[V\setminus L^{\prime}])>\mathrm{ex}(n^{\prime},F)$
implies that $G[V\setminus L^{\prime}]$ contains an $F$, which contradicts
that $G$ is $F$-free. ∎

Next, we prove that $W\subseteq L$. Otherwise, there exists a vertex $u_{0}\in
W$ and $u_{0}\notin L$. Without loss of generality, let $u_{0}\in V_{1}$.
Since $V(G)=V_{1}\cup\ldots\cup V_{r}$ is the partition such that $\sum_{1\leq
i<j\leq r}e(V_{i},V_{j})$ attains the maximum, $d_{V_{1}}(u_{0})\leq
d_{V_{i}}(u_{0})$ for each $i\in[2,r]$. Thus $d(u_{0})\geq rd_{V_{1}}(u_{0})$,
that is $d_{V_{1}}(u_{0})\leq\frac{1}{r}d(u_{0})$. On the other hand, since
$u_{0}\not\in L$, we get $d(u_{0})>(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}})n$.
Thus

$\displaystyle d_{V_{2}}(u_{0})$ $\displaystyle\geq
d(u_{0})-d_{V_{1}}(u_{0})-(r-2)\left(\frac{1}{r}+3\sqrt{\epsilon}\right)n$
$\displaystyle\geq\left(1-\frac{1}{r}\right)d(u_{0})-(r-2)\left(\frac{1}{r}+3\sqrt{\epsilon}\right)n$
$\displaystyle>\frac{n}{r^{2}}-3(r-1)\epsilon^{\frac{1}{3}}n-3(r-2)\sqrt{\epsilon}n$
(7) $\displaystyle>\frac{n}{r^{2}}-6r\epsilon^{\frac{1}{3}}n.$

Recall from Claim 1 and Claim 2 that $|W|<{\theta}n$ and
$|L|\leq\epsilon^{\frac{1}{3}}n$, hence, for any $i\in[r]$ and sufficiently
large $n$, we have

$|V_{i}\setminus(W\cup
L)|\geq\left(\frac{1}{r}-3\sqrt{\epsilon}\right)n-\theta
n-\epsilon^{\frac{1}{3}}n\geq\ell.$

We claim that $u_{0}$ is adjacent to at most $a$ vertices in
$V_{1}\setminus(W\cup L)$. Otherwise, let $u_{1,1},u_{1,2},\ldots,u_{1,a+1}$
be the neighbors of $u_{0}$ in $V_{1}\setminus(W\cup L)$. Let
$u_{1,a+2},\ldots,u_{1,\ell}$ be another $\ell-a-1$ vertices in
$V_{1}\setminus(W\cup L)$. For any $j\in[\ell]$, since $u_{1,j}\not\in L$ and
$u_{1,j}\not\in W$, we have
$d(u_{1,j})>\left(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\right)n$, and
$d_{V_{1}}(u_{1,j})<2\theta n$. Thus,

$\displaystyle d_{V_{2}}(u_{1,j})$ $\displaystyle\geq
d(u_{1,j})-d_{V_{1}}(u_{1,j})-(r-2)\left(\frac{1}{r}+3\sqrt{\epsilon}\right)n$
$\displaystyle>\frac{n}{r}-3r\epsilon^{\frac{1}{3}}n-2\theta
n-3(r-2)\sqrt{\epsilon}n$ (8)
$\displaystyle>\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta n.$

By Lemma 2.8, we consider the common neighbors of
$u_{0},u_{1,1},\ldots,u_{1,\ell}$ in $V_{2}$,

$\displaystyle\left|N_{V_{2}}(u_{0})\cap N_{V_{2}}(u_{1,1})\cap\cdots\cap
N_{V_{2}}(u_{1,\ell})\setminus(W\cup L)\right|$ $\displaystyle\geq$
$\displaystyle
d_{V_{2}}(u_{0})+\sum_{j=1}^{\ell}d_{V_{2}}(u_{1,j})-\ell\left|V_{2}\right|-|W|-|L|$
$\displaystyle>$
$\displaystyle\frac{n}{r^{2}}-6r\epsilon^{\frac{1}{3}}n+\ell\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta
n\right)-\ell\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)-\theta
n-\epsilon^{\frac{1}{3}}n$ $\displaystyle>$
$\displaystyle\frac{n}{r^{2}}-16r\ell\epsilon^{\frac{1}{3}}n-(2\ell+1)\theta
n>\ell,$

for sufficiently large $n$. This implies that there exist $\ell$ vertices
$u_{2,1},u_{2,2},\ldots,u_{2,\ell}$ in $V_{2}\setminus(W\cup L)$ such that
$\\{u_{0},u_{1,1},\ldots,u_{1,\ell}\\}$ and $\\{u_{2,1},\ldots,u_{2,\ell}\\}$
induce a complete bipartite graph. For an integer $s$ with $2\leq s\leq r-1$,
suppose that for any $1\leq i\leq s$, there exist
$u_{i,1},u_{i,2},\ldots,u_{i,\ell}\in V_{i}\setminus(W\cup L)$ such that
$\\{u_{0},u_{1,1},\ldots,u_{1,\ell}\\}$, $\\{u_{2,1},\ldots,u_{2,\ell}\\}$,
$\ldots$, $\\{u_{s,1},\ldots,u_{s,\ell}\\}$ induce a complete $s$-partite
graph. We next consider the common neighbors of these vertices in $V_{s+1}$.
Similarly, by (7) and (8), we get that for each $i\in[s]$ and $j\in[\ell]$,

$\displaystyle d_{V_{s+1}}(u_{0})$
$\displaystyle>\frac{n}{r^{2}}-6r\epsilon^{\frac{1}{3}}n,$

and

$\displaystyle d_{V_{s+1}}(u_{i,j})$
$\displaystyle>\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta n.$

By Lemma 2.8 again, we can obtain

$\displaystyle\left|N_{V_{s+1}}(u_{0})\cap\left(\cap_{i\in[s],j\in[\ell]}N_{V_{s+1}}(u_{i,j})\right)\setminus(W\cup
L)\right|$ $\displaystyle\geq$ $\displaystyle
d_{V_{s+1}}(u_{0})+\sum_{i\in[s],j\in[\ell]}d_{V_{s+1}}(u_{i,j})-s\ell\left|V_{s+1}\right|-|W|-|L|$
$\displaystyle>$
$\displaystyle\frac{n}{r^{2}}-6r\epsilon^{\frac{1}{3}}n+s\ell\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta
n\right)-s\ell\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)-\theta
n-\epsilon^{\frac{1}{3}}n$ $\displaystyle>$
$\displaystyle\frac{n}{r^{2}}-16sr\ell\epsilon^{\frac{1}{3}}n-(2s\ell+1)\theta
n>\ell,$

where $n$ is sufficiently large. Hence there exist $\ell$ vertices
$u_{s+1,1},u_{s+1,2},\ldots,u_{s+1,\ell}\in V_{s+1}\setminus(W\cup L)$ such
that $\\{u_{0},u_{1,1},\ldots,u_{1,\ell}\\}$, $\ldots$, $\\{u_{s+1,1}$,
$\ldots$, $u_{s+1,\ell}\\}$ induce a complete $(s+1)$-partite graph. Thus, for
each $i\in[2,r]$, there exist $u_{i,1},u_{i,2},\ldots,u_{i,\ell}$ in
$V_{i}\setminus(W\cup L)$ such that $\\{u_{0},u_{1,1},\ldots,u_{1,\ell}\\}$,
$\\{u_{2,1},\ldots,u_{2,\ell}\\}$, $\ldots$, $\\{u_{r,1},\ldots,u_{r,\ell}\\}$
induce a complete $r$-partite graph. Let $G^{\prime}$ be the graph induced by
$\\{u_{0},u_{1,1},\ldots,u_{1,\ell}\\}$, $\ldots$,
$\\{u_{r,1},\ldots,u_{r,\ell}\\}$. Since $u_{0}$ is adjacent to
$u_{1,1},\ldots,u_{1,a+1}$, then $e(G^{\prime})>e(T_{r\ell+1,r})+a$, by the
definition of Turán number, $G^{\prime}$ contains an $F$, this is a
contradiction. Therefore $u_{0}$ is adjacent to at most $a$ vertices in
$V_{1}\setminus(W\cup L)$. Hence

$\displaystyle d_{V_{1}}(u_{0})$ $\displaystyle\leq$ $\displaystyle|W|+|L|+a$
$\displaystyle<$ $\displaystyle\theta n+\epsilon^{\frac{1}{3}}n+a$
$\displaystyle<$ $\displaystyle 2\theta n,$

for sufficiently large $n$. This is a contradiction to the fact that $u_{0}\in
W$. Hence $W\subseteq L$.

∎

######  Lemma 3.5.

For each $i\in[r]$,

$e(G[V_{i}\setminus L])\leq a.$

Furthermore, for each $i\in[r]$, there exists an independent set
$I_{i}\subseteq V_{i}\setminus L$ such that

$|I_{i}|\geq|V_{i}|-\epsilon^{\frac{1}{3}}n-a.$

###### Proof.

Suppose to the contrary that there exists an $i_{0}\in[r]$ such that
$e(G[V_{i_{0}}\setminus L])>a.$ Without loss of generality, we may assume that
$e(G[V_{1}\setminus L])>a.$ By Lemmas 3.3 and 3.4, we have $|V_{i}\setminus
L|\geq\left(\frac{1}{r}-3\sqrt{\epsilon}\right)n-\epsilon^{\frac{1}{3}}n\geq\ell$
for any $i\in[r]$. Let $u_{1,1},u_{1,2},\ldots,u_{1,\ell}$ be $\ell$ vertices
chosen from $V_{1}\setminus L$ such that the induced subgraph of
$\\{u_{1,1},u_{1,2},\ldots,u_{1,\ell}\\}$ in $G$ contains at least $a+1$
edges. For any $j\in[\ell]$, $u_{1,j}\notin L$ implies that $u_{1,j}\notin W$
by Lemma 3.4, thus
$d(u_{1,j})>\left(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\right)n$, and
$d_{V_{1}}(u_{1,j})<2\theta n$. Then we have

$\displaystyle d_{V_{2}}(u_{1,j})$ $\displaystyle\geq
d(u_{1,j})-d_{V_{1}}(u_{1,j})-(r-2)\left(\frac{1}{r}+3\sqrt{\epsilon}\right)n$
$\displaystyle>\frac{n}{r}-3r\epsilon^{\frac{1}{3}}n-2\theta
n-3(r-2)\sqrt{\epsilon}n$ (9)
$\displaystyle>\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta n.$

Applying Lemma 2.8, we get

$\displaystyle\left|N_{V_{2}}(u_{1,1})\cap N_{V_{2}}(u_{1,2})\cap\cdots\cap
N_{V_{2}}(u_{1,\ell})\setminus L\right|$ $\displaystyle\geq$
$\displaystyle\sum_{j=1}^{\ell}d_{V_{2}}(u_{1,j})-(\ell-1)\left|V_{2}\right|-|L|$
$\displaystyle\geq$
$\displaystyle\ell\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta
n\right)-(\ell-1)\left(\tfrac{1}{r}+3\sqrt{\epsilon}\right)n-\epsilon^{\frac{1}{3}}n$
$\displaystyle>$
$\displaystyle\frac{n}{r}-10r\ell\epsilon^{\frac{1}{3}}n-2\ell\theta n>\ell,$

for sufficiently large $n$. So there exist $\ell$ vertices
$u_{2,1},u_{2,2},\ldots,u_{2,\ell}\in V_{2}$ such that
$\\{u_{1,1},\ldots,u_{1,\ell}\\}$ and $\\{u_{2,1},\ldots,u_{2,\ell}\\}$ induce
a complete bipartite graph. For an integer $s$ with $2\leq s\leq r-1$, suppose
that for any $1\leq i\leq s$, there exist
$u_{i,1},u_{i,2},\ldots,u_{i,\ell}\in V_{i}\setminus L$ such that
$\\{u_{1,1},\ldots,u_{1,\ell}\\}$, $\\{u_{2,1},\ldots,u_{2,\ell}\\}$,
$\ldots$, $\\{u_{s,1},\ldots,u_{s,\ell}\\}$ induce a complete $s$-partite
subgraph in $G$. We next consider the common neighbors of these vertices in
$V_{s+1}$. Similarly, by (9), we get that for each $i\in[s]$ and $j\in[\ell]$,

$\displaystyle d_{V_{s+1}}(u_{i,j})$
$\displaystyle\geq\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta n.$

By Lemma 2.8 again, we can obtain

$\displaystyle\left|\left(\cap_{i\in[s],j\in[\ell]}N_{V_{s+1}}(u_{i,j})\right)\setminus
L\right|$ $\displaystyle\geq$
$\displaystyle\sum_{i\in[s],j\in[\ell]}d_{V_{s+1}}(u_{i,j})-(s\ell-1)\left|V_{s+1}\right|-|L|$
$\displaystyle\geq$ $\displaystyle
s\ell\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-2\theta
n\right)-(s\ell-1)\left(\tfrac{1}{r}+3\sqrt{\epsilon}\right)n-\epsilon^{\frac{1}{3}}n$
$\displaystyle>$
$\displaystyle\frac{n}{r}-10rs\ell\epsilon^{\frac{1}{3}}n-2s\ell\theta
n>\ell,$

for sufficiently large $n$. Thus there exist $\ell$ vertices
$u_{s+1,1},u_{s+1,2},\ldots,u_{s+1,\ell}\in V_{s+1}\setminus L$ such that
$\\{u_{1,1},\ldots,u_{1,\ell}\\}$, $\\{u_{2,1},\ldots,u_{2,\ell}\\}$,
$\ldots$, $\\{u_{s+1,1},\ldots,u_{s+1,\ell}\\}$ induce a complete
$(s+1)$-partite subgraph in $G$. Therefore, for each $i\in[2,r]$, there exist
$u_{i,1},u_{i,2},\ldots,u_{i,\ell}$ in $V_{i}\setminus L$ such that
$\\{u_{1,1},\ldots,u_{1,\ell}\\}$, $\\{u_{2,1},\ldots,u_{2,\ell}\\}$,
$\ldots$, $\\{u_{r,1},\ldots,u_{r,\ell}\\}$ induce a complete $r$-partite
graph. Let $G^{\prime}$ be the graph induced by
$\\{u_{1,1},\ldots,u_{1,\ell}\\}$, $\ldots$,
$\\{u_{r,1},\ldots,u_{r,\ell}\\}$. Then $e(G^{\prime})>e(T_{r\ell,r})+a$,
which implies that $G^{\prime}$ contains a copy of $F$, this is a
contradiction. Thus for each $i\in[r]$, $e(G[V_{i}\setminus L])\leq a$.

Therefore, the subgraph obtained from $G[V_{i}\setminus L]$ by deleting one
vertex of each edge in $G[V_{i}\setminus L]$ contains no edges, which is an
independent set of $G[V_{i}\setminus L]$. Therefore, for each $i\in[r]$, there
exists an independent set $I_{i}\subseteq V_{i}$ such that

$\displaystyle|I_{i}|$ $\displaystyle\geq|V_{i}\setminus
L|-a\geq|V_{i}|-\epsilon^{\frac{1}{3}}n-a.$

∎

######  Lemma 3.6.

$L$ is empty and $e(G[V_{i}])\leq a$ for each $i\in[r]$.

###### Proof.

We first prove that $L=\varnothing$. Otherwise, let $v$ be a vertex in $L$.
Then $d(v)\leq(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}})n$. Recall that
$x_{z}=\max\\{x_{i}|\ i\in[n]\\}$, then
$\lambda(G)=\lambda(G)x_{z}=\sum_{wz\in E(G)}x_{w}\leq d(z)$. Hence

$d(z)\geq\lambda(G)\geq\left(1-\frac{1}{r}-\frac{r}{4n^{2}}+\frac{2a}{n^{2}}\right)n>\left(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\right)n,$

as $n$ is large enough. Hence $z\notin L$. Without loss of generality, we may
assume that $z\in V_{1}$. Let $G^{\prime}$ be the graph with
$V(G^{\prime})=V(G)$ and edge set
$E(G^{\prime})=E(G\setminus\\{v\\})\cup\\{vw|\ w\in
N(z)\cap(\cup_{i=2}^{r}I_{i})\\}$. We claim that $G^{\prime}$ is $F$-free.
Otherwise, $G^{\prime}$ contains a copy of $F$, denoted as $F^{\prime}$, as a
subgraph, then $v\in V(F^{\prime})$. Let $N_{G^{\prime}}(v)\cap
V(F^{\prime})=\\{w_{1},\ldots,w_{s}\\}$. Obviously, $w_{i}\notin V_{1}$ and
$w_{i}\notin L$ for any $i\in[s]$. If $z\notin V(F^{\prime})$, then
$(F^{\prime}\setminus\\{v\\})\cup\\{z\\}$ is a copy of $F$ in $G$, which is a
contradiction. Thus $z\in V(F^{\prime})$. For any $i\in[s]$,

$\displaystyle d_{V_{1}}(w_{i})$ $\displaystyle=d(w_{i})-d_{V\setminus
V_{1}}(w_{i})$
$\displaystyle\geq\left(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\right)n-a-\epsilon^{\frac{1}{3}}n-(r-2)\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)$
$\displaystyle>\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-a,$

where the last second inequality holds as $w_{i}\notin L$ and
$e(G[V_{j}\setminus L])\leq a$ for $w_{i}\in V_{j}$. Using Lemma 2.8, we get

$\displaystyle\Big{|}\bigcap_{i=1}^{s}N_{V_{1}}(w_{i})\setminus L\Big{|}$
$\displaystyle\geq$
$\displaystyle\sum_{i=1}^{s}d_{V_{1}}(w_{i})-(s-1)|V_{1}|-|L|$
$\displaystyle>$ $\displaystyle
s\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-a\right)-(s-1)\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)-\epsilon^{\frac{1}{3}}n$
$\displaystyle>$ $\displaystyle\frac{n}{r}-10sr\epsilon^{\frac{1}{3}}n-sa>1.$

Thus there exists $v^{\prime}\in V_{1}\setminus L$ such that $v^{\prime}$ is
adjacent to $w_{1},\ldots,w_{s}$. Then
$(F^{\prime}\setminus\\{v\\})\cup\\{v^{\prime}\\}$ is a copy of $F$ in $G$,
which is a contradiction. Thus $G^{\prime}$ is $F$-free.

By Lemma 3.5, we have $e(G[V_{1}\setminus L])\leq a$, then the maximum degree
in the induced subgraph $G[V_{1}\setminus L]$ is at most $a$. Combining this
with Lemma 3.4, we get

$d_{V_{1}}(z)=d_{{V_{1}}\cap L}(z)+d_{V_{1}\setminus
L}(z)\leq\epsilon^{\frac{1}{3}}n+a.$

Therefore, by Lemma 3.5, we have

$\displaystyle\lambda(G)$ $\displaystyle=$
$\displaystyle\lambda(G)x_{z}=\sum_{v\sim
z}x_{v}=\sum_{\begin{subarray}{c}v\in V_{1},v\sim
z\end{subarray}}x_{v}+\sum_{i=2}^{r}\left(\sum_{\begin{subarray}{c}v\in
V_{i},v\sim z\end{subarray}}x_{v}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}v\in V_{1},v\sim
z\end{subarray}}x_{v}+\sum_{i=2}^{r}\left(\sum_{\begin{subarray}{c}v\in
I_{i},v\sim z\end{subarray}}x_{v}+\sum_{\begin{subarray}{c}v\in V_{i}\setminus
I_{i},v\sim z\end{subarray}}x_{v}\right)$ $\displaystyle\leq$ $\displaystyle
d_{V_{1}}(z)+\sum_{i=2}^{r}\left(\sum_{\begin{subarray}{c}v\in I_{i},v\sim
z\end{subarray}}x_{v}\right)+\sum_{i=2}^{r}|V_{i}\setminus I_{i}|$
$\displaystyle\leq$
$\displaystyle\epsilon^{\frac{1}{3}}n+a+\sum_{i=2}^{r}\left(\sum_{\begin{subarray}{c}v\in
I_{i},v\sim z\end{subarray}}x_{v}\right)+(r-1)(\epsilon^{\frac{1}{3}}n+a).$

By Lemma 3.2, we have

$\sum_{i=2}^{r}\left(\sum_{\begin{subarray}{c}v\in I_{i},v\sim
z\end{subarray}}x_{v}\right)\geq\left(1-\frac{1}{r}\right)n-\frac{r}{4n}+\frac{2a}{n}-r\epsilon^{\frac{1}{3}}n-ra.$
(10)

By the Rayleigh quotient equation,

$\displaystyle\lambda(G^{\prime})-\lambda(G)$
$\displaystyle\geq\frac{\mathbf{x}^{T}\left(A(G^{\prime})-A(G)\right)\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}=\frac{2x_{v}}{\mathbf{x}^{T}\mathbf{x}}\left(\sum_{i=2}^{r}\left(\sum_{\begin{subarray}{c}w\in
I_{i},v\sim z\end{subarray}}x_{w}\right)-\sum_{uv\in E(G)}x_{u}\right)$
$\displaystyle\geq\frac{2x_{v}}{\mathbf{x}^{T}\mathbf{x}}\left(\left(1-\frac{1}{r}\right)n-\frac{r}{4n}+\frac{2a}{n}-r\epsilon^{\frac{1}{3}}n-ra-\left(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\right)n\right)>0,$

where the last second inequality holds since (10) and $\sum_{uv\in
E(G)}x_{u}\leq d(v)$, and the last inequality holds for $n$ large enough. This
contradicts the fact that $G$ has the largest spectral radius over all
$F$-free graphs, so $L$ must be empty. Furthermore, by Lemma 3.5, we have
$e(G[V_{i}])\leq a$ for each $i\in[r]$. ∎

######  Lemma 3.7.

For any $i\in[r]$, let $B_{i}=\\{u\in V_{i}|\ d_{V_{i}}(u)\geq 1\\}$ and
$C_{i}=V_{i}\setminus B_{i}$. Then

(1) $|B_{i}|\leq 2a$;

(2) For every vertex $u\in C_{i}$, $u$ is adjacent to all vertices of
$V\setminus V_{i}$.

###### Proof.

We prove the assertions by contradiction.

(1) If there exists a $j\in[r]$ such that $|B_{j}|>2a$, then $\sum_{u\in
B_{j}}d_{V_{j}}(u)>2a$. On the other hand, $e(G[V_{j}])\leq a$ by Lemma 3.6 .
Therefore,

$2a<\sum_{u\in B_{j}}d_{V_{j}}(u)=\sum_{u\in
V_{j}}d_{V_{j}}(u)=2e(G[V_{j}])\leq 2a,$

which is a contradiction.

(2) If there exists a vertex $v\in C_{i_{0}}$ such that there is a vertex
$w_{1}\notin V_{i_{0}}$ and $vw_{1}\notin E(G)$, where $i_{0}\in[r]$. Let
$G^{\prime}$ be the graph with $V(G^{\prime})=V(G)$ and
$E(G^{\prime})=E(G)\cup\\{vw_{1}\\}$. We claim that $G^{\prime}$ is $F$-free.
Otherwise, $G^{\prime}$ contains a copy of $F$, denoted as $F^{\prime}$, as a
subgraph, then $vw_{1}\in E(F^{\prime})$. Let $N_{G^{\prime}}(v)\cap
V(F^{\prime})=\\{w_{1},\ldots,w_{s}\\}$. Obviously, $w_{i}\notin V_{i_{0}}$
for any $i\in[s]$, then we have,

$\displaystyle d_{V_{i_{0}}}(w_{i})$ $\displaystyle=d(w_{i})-d_{V\setminus
V_{i_{0}}}(w_{i})$
$\displaystyle\geq\left(1-\frac{1}{r}-3r\epsilon^{\frac{1}{3}}\right)n-a-(r-2)\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)$
(11) $\displaystyle>\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-a,$

where the last second inequality holds as $L=\emptyset$, and $e(G[V_{j}])\leq
a$ for $w_{i}\in V_{j}$. Using Lemma 2.8, we consider the common neighbors of
$w_{1},\ldots,w_{s}$ in $C_{i_{0}}$,

$\displaystyle\Big{|}\bigcap_{i=1}^{s}N_{V_{i_{0}}}(w_{i})\setminus
B_{i_{0}}\Big{|}$ $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{s}d_{V_{i_{0}}}(w_{i})-(s-1)|V_{i_{0}}|-|B_{i_{0}}|$
$\displaystyle>$ $\displaystyle
s\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-a\right)-(s-1)\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)-2a$
$\displaystyle>$
$\displaystyle\frac{n}{r}-9rs\epsilon^{\frac{1}{3}}n-(s+2)a>1.$

Then there exists $v^{\prime}\in C_{i_{0}}$ such that $v^{\prime}$ is adjacent
to $w_{1},\ldots,w_{s}$. Then
$(F^{\prime}\setminus\\{v\\})\cup\\{v^{\prime}\\}$ is a copy of $F$ in $G$,
which is a contradiction. Thus $G^{\prime}$ is $F$-free. From the construction
of $G^{\prime}$, we see that $\lambda(G^{\prime})>\lambda(G)$, which
contradicts the assumption that $G$ has the maximum spectral radius among all
$F$-free graphs on $n$ vertices.

∎

######  Lemma 3.8.

For any $u\in V(G)$, $x_{u}\geq 1-\frac{20a^{2}r^{2}}{n}$.

###### Proof.

We will prove this lemma by contradiction. Suppose that there is a vertex
$v\in V(G)$ with $x_{v}<1-\frac{20a^{2}r^{2}}{n}$. Recall that
$x_{z}=\max\\{x_{i}|\ i\in V(G)\\}=1$. Without loss of generality, we may
assume that $z\in V_{1}$. Let $G^{\prime}$ be the graph with
$V(G^{\prime})=V(G)$ and $E(G^{\prime})=E(G\setminus\\{v\\})\cup\\{vw|\ w\in
N(z)\cap(\cup_{i=2}^{r}C_{i})\\}$. We claim that $G^{\prime}$ is $F$-free.
Otherwise, $G^{\prime}$ contains a copy of $F$, denoted by $F^{\prime}$, as a
subgraph, then $v\in V(F^{\prime})$. Let $N_{G^{\prime}}(v)\cap
V(F^{\prime})=\\{w_{1},\ldots,w_{s}\\}$. Obviously, $w_{i}\notin V_{1}$ for
any $i\in[s]$. If $z\notin V(F^{\prime})$, then
$(F^{\prime}\setminus\\{v\\})\cup\\{z\\}$ is a copy of $F$ in $G$, which is a
contradiction. Thus $z\in V(F^{\prime})$. By using the similar method as in
Lemma 3.7, we get

$\displaystyle d_{V_{1}}(w_{i})>\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-a,$

for any $i\in[s]$. Using Lemma 2.8, we consider the common neighbors of
$w_{1},\ldots,w_{s}$ in $C_{1}$,

$\displaystyle\Big{|}\bigcap_{i=1}^{s}N_{V_{1}}(w_{i})\setminus B_{1}\Big{|}$
$\displaystyle\geq$
$\displaystyle\sum_{i=1}^{s}d_{V_{1}}(w_{i})-(s-1)|V_{1}|-|B_{1}|$
$\displaystyle>$ $\displaystyle
s\left(\frac{n}{r}-6r\epsilon^{\frac{1}{3}}n-a\right)-(s-1)\left(\frac{n}{r}+3\sqrt{\epsilon}n\right)-2a$
$\displaystyle>$
$\displaystyle\frac{n}{r}-9rs\epsilon^{\frac{1}{3}}n-(s+2)a>1.$

Then there exists $v^{\prime}\in C_{1}$ such that $v^{\prime}$ is adjacent to
$w_{1},\ldots,w_{s}$. Then $(F^{\prime}\setminus\\{v\\})\cup\\{v^{\prime}\\}$
is a copy of $F$ in $G$, which is a contradiction. Thus $G^{\prime}$ is
$F$-free.

By Lemma 3.6, $e(G[V_{1}])\leq a$, then $d_{V_{1}}(z)\leq a$. By (2), we have

$\displaystyle\lambda(G)x_{z}$ $\displaystyle=\sum_{w\thicksim
z}x_{w}=\sum_{w\thicksim z,w\in
V_{1}}x_{w}+\sum_{i=2}^{r}\Big{(}\sum_{w\thicksim z,w\in V_{i}}x_{w}\Big{)}$
$\displaystyle=\sum_{w\thicksim z,w\in
V_{1}}x_{w}+\sum_{i=2}^{r}\Big{(}\sum_{w\thicksim z,w\in
B_{i}}x_{w}+\sum_{w\thicksim z,w\in C_{i}}x_{w}\Big{)},$

which implies that

$\displaystyle\sum_{i=2}^{r}\Big{(}\sum_{w\thicksim z,w\in C_{i}}x_{w}\Big{)}$
$\displaystyle=\lambda(G)-\sum_{w\thicksim z,w\in
V_{1}}x_{w}-\sum_{i=2}^{r}\Big{(}\sum_{w\thicksim z,w\in B_{i}}x_{w}\Big{)}$
$\displaystyle\geq\lambda(G)-d_{V_{1}}(z)-\sum_{i=2}^{r}\Big{(}\sum_{w\in
B_{i}}1\Big{)}$ $\displaystyle\geq\lambda(G)-a-(r-1)2a,$ (12)
$\displaystyle=\lambda(G)-(2r-3)a,$

where (12) holds as $e(G[V_{1}])\leq a$, and $|B_{i}|\leq 2a$ for any
$i\in[r]$.

By Rayleigh quotient equation, we have

$\displaystyle\lambda(G^{\prime})-\lambda(G)$
$\displaystyle\geq\frac{\mathbf{x}^{T}(A(G^{\prime})-A(G))\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}$
$\displaystyle=\frac{2x_{v}}{\mathbf{x}^{T}\mathbf{x}}\left(\sum_{i=2}^{r}\Bigl{(}\sum_{w\thicksim
z,w\in C_{i}}x_{w}\Bigr{)}-\sum_{uv\in E(G)}x_{u}\right)$
$\displaystyle=\frac{2x_{v}}{\mathbf{x}^{T}\mathbf{x}}\left(\sum_{i=2}^{r}\Bigl{(}\sum_{w\thicksim
z,w\in C_{i}}x_{w}\Bigr{)}-\lambda(G)x_{v}\right)$
$\displaystyle>\frac{2x_{v}}{\mathbf{x}^{T}\mathbf{x}}\left(\lambda(G)-(2r-3)a-\lambda(G)\Bigl{(}1-\frac{20a^{2}r^{2}}{n}\Bigr{)}\right)$
$\displaystyle\geq\frac{2x_{v}}{\mathbf{x}^{T}\mathbf{x}}\left(\frac{r-1}{r}20a^{2}r^{2}-\frac{r}{4n}\frac{20a^{2}r^{2}}{n}+\frac{2a}{n}\frac{20a^{2}r^{2}}{n}-(2r-3)a\right)>0,$

where the last second inequality holds as (12), and the last inequality
follows by
$\lambda(G)\geq\left(1-\frac{1}{r}\right)n-\frac{r}{4n}+\frac{2a}{n}$. This
contradicts the assumption that $G$ has the maximum spectral radius among all
$F$-free graphs on $n$ vertices. Thus $x_{u}\geq 1-\frac{20a^{2}r^{2}}{n}$ for
any $u\in V(G)$.

∎

Let $G_{in}=\cup_{i=1}^{r}G[V_{i}]$. For any $i\in[r]$, let $|V_{i}|=n_{i}$,
$K=K_{r}(n_{1},n_{2},\ldots,n_{r})$ be the complete $r$-partite graph on
$V_{1},V_{2},\ldots,V_{r}$, and $G_{out}$ be the graph with $V(G_{out})=V(G)$
and $E(G_{out})=E(K)\setminus E(G)$.

######  Lemma 3.9.

$e(G_{in})-e(G_{out})\leq a.$

###### Proof.

Suppose to the contrary that $e(G_{in})-e(G_{out})>a.$ For each $i\in[r]$, let
$S_{i}$ be the vertex set satisfying $B_{i}\subseteq S_{i}\subseteq V_{i}$ and
$|S_{i}|=\ell$. Let $S=\cup_{i=1}^{r}S_{i}$, $G^{\prime}=G[S]$. By Lemma 3.7,
we have $e(G^{\prime})\geq
e(T_{r\ell,r})+e(G_{in})-e(G_{out})>e(T_{r\ell,r})+a,$ which implies that
$G^{\prime}$ contains an $F$, this is a contradiction. So
$e(G_{in})-e(G_{out})\leq a.$

∎

######  Lemma 3.10.

For any $1\leq i<j\leq r$, $\left|n_{i}-n_{j}\right|\leq 1$.

###### Proof.

We prove this lemma by contradiction. Without loss of generality, suppose that
$n_{1}\geq n_{2}\geq\ldots\geq n_{r}$. Assume that there exist $i_{0},j_{0}$
with $1\leq i_{0}<j_{0}\leq r$ such that $n_{i_{0}}-n_{j_{0}}\geq 2$.

Claim 1. There exists a constant $c_{1}>0$ such that
$\lambda(T_{n,r})-\lambda(K)\geq\frac{c_{1}}{n}$.

###### Proof.

Let
$K^{\prime}=K_{r}(n_{1},\ldots,n_{i_{0}}-1,\ldots,n_{j_{0}}+1,\ldots,n_{r}).$
Assume $K^{\prime}\cong
K_{r}(n^{\prime}_{1},n^{\prime}_{2},\ldots,n^{\prime}_{r})$, where
$n^{\prime}_{1}\geq n^{\prime}_{2}\geq\ldots\geq n^{\prime}_{r}$. By (4), we
have

$1=\sum_{i=1}^{r}\frac{n_{i}}{\lambda(K)+n_{i}}=\frac{n_{i_{0}}}{\lambda(K)+n_{i_{0}}}+\frac{n_{j_{0}}}{\lambda(K)+n_{j_{0}}}+\sum_{i\in[r]\setminus\\{i_{0},j_{0}\\}}\frac{n_{i}}{\lambda(K)+n_{i}},$
(13)

and

$1=\sum_{i=1}^{r}\frac{n^{\prime}_{i}}{\lambda(K^{\prime})+n^{\prime}_{i}}=\frac{n_{i_{0}}-1}{\lambda(K^{\prime})+n_{i_{0}}-1}+\frac{n_{j_{0}}+1}{\lambda(K^{\prime})+n_{j_{0}}+1}+\sum_{i\in[r]\setminus\\{i_{0},j_{0}\\}}\frac{n_{i}}{\lambda(K^{\prime})+n_{i}}.$
(14)

Subtracting (14) from (13), we get

$\displaystyle\frac{2(n_{i_{0}}-n_{j_{0}}-1)\lambda^{2}(K)+(n_{i_{0}}+n_{j_{0}})(n_{i_{0}}-n_{j_{0}}-1)\lambda(K)}{(\lambda(K)+n_{i_{0}}-1)(\lambda(K)+n_{i_{0}})(\lambda(K)+n_{j_{0}}+1)(\lambda(K)+n_{j_{0}})}$
$\displaystyle=$
$\displaystyle\sum_{i\in[r]\setminus\\{i_{0},j_{0}\\}}\frac{n_{i}(\lambda(K^{\prime})-\lambda(K))}{(\lambda(K)+n_{i})(\lambda(K^{\prime})+n_{i})}+\frac{(n_{i_{0}}-1)(\lambda(K^{\prime})-\lambda(K))}{(\lambda(K)+n_{i_{0}}-1)(\lambda(K^{\prime})+n_{i_{0}}-1)}$
$\displaystyle+\frac{(n_{j_{0}}+1)(\lambda(K^{\prime})-\lambda(K))}{(\lambda(K)+n_{j_{0}}+1)(\lambda(K^{\prime})+n_{j_{0}}+1)}$
$\displaystyle\leq$
$\displaystyle\frac{\lambda(K^{\prime})-\lambda(K)}{\lambda(K)+n^{\prime}_{r}}\Big{(}\sum_{i\in[r]\setminus\\{i_{0},j_{0}\\}}\frac{n_{i}}{\lambda(K^{\prime})+n_{i}}+\frac{n_{i_{0}}-1}{\lambda(K^{\prime})+n_{i_{0}}-1}+\frac{n_{j_{0}}+1}{\lambda(K^{\prime})+n_{j_{0}}+1}\Big{)}$
$\displaystyle=$
$\displaystyle\frac{\lambda(K^{\prime})-\lambda(K)}{\lambda(K)+n^{\prime}_{r}},$

where the inequality holds as
$n^{\prime}_{r}\leq\min\\{n_{1},\ldots,n_{i_{0}}-1,\ldots,n_{j_{0}}+1,\ldots,n_{r}\\}$,
and the last equality holds by (14). Combining with the assumption
$n_{i_{0}}-n_{j_{0}}\geq 2$, we obtain

$\displaystyle\frac{2\lambda^{2}(K)+(n_{i_{0}}+n_{j_{0}})\lambda(K)}{(\lambda(K)+n_{i_{0}}-1)(\lambda(K)+n_{i_{0}})(\lambda(K)+n_{j_{0}}+1)(\lambda(K)+n_{j_{0}})}\leq\frac{\lambda(K^{\prime})-\lambda(K)}{\lambda(K)+n^{\prime}_{r}}.$
(15)

In view of the construction of $K$, we see that

$n-\Big{(}\frac{n}{r}+3\sqrt{\epsilon}n\Big{)}\leq\delta(K)\leq\lambda(K)\leq\Delta(K)\leq
n-\Big{(}\frac{n}{r}-3\sqrt{\epsilon}n\Big{)},$

thus $\lambda(K)=\Theta(n)$. From (15), it follows that there exists a
constant $c_{1}>0$ such that
$\lambda(K^{\prime})-\lambda(K)\geq\frac{c_{1}}{n}$. Therefore, by Lemma 2.7,
$\lambda(T_{n,r})-\lambda(K)\geq\lambda(K^{\prime})-\lambda(K)\geq\frac{c_{1}}{n}$.

∎

Claim 2. There exists a constant $c_{2}>0$ such that
$\lambda(T_{n,r})-\lambda(K)\leq\frac{c_{2}}{n^{2}}$.

###### Proof.

According to the definition of $K$, we have $e(G)=e(G_{in})+e(K)-e(G_{out})$.
By Lemma 3.7, for any $i\in[r]$, and every vertex $u\in C_{i}$, $u$ is
adjacent to all vertices of $V\setminus V_{i}$. Thus

$e(G_{out})\leq\sum_{1\leq i<j\leq
r}|B_{i}||B_{j}|\leq\binom{r}{2}(2a)^{2}\leq 2a^{2}r^{2}.$

Therefore

$\displaystyle\lambda(G)$
$\displaystyle=\frac{\mathbf{x}^{\mathrm{T}}A(G)\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle=\frac{2\sum_{ij\in
E(K)}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}+\frac{2\sum_{ij\in
E(G_{in})}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2\sum_{ij\in
E(G_{out})}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq\lambda(K)+\frac{2e(G_{in})}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2e(G_{out})(1-\frac{20a^{2}r^{2}}{n})^{2}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq\lambda(K)+\frac{2(e(G_{in})-e(G_{out}))}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}+\frac{e(G_{out})\frac{40a^{2}r^{2}}{n}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq\lambda(K)+\frac{2a}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}+\frac{\frac{80a^{4}r^{4}}{n}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}},$
(16)

where (16) holds by Lemma 3.9 and $e(G_{out})\leq 2a^{2}r^{2}.$

On the other hand, let $\mathbf{y}$ be an eigenvector of $T_{n,r}$
corresponding to $\lambda(T_{n,r})$, $k=n-r\lfloor\frac{n}{r}\rfloor$. Since
$T_{n,r}$ is a complete $r$-partite graph on $n$ vertices where each partite
set has either $\lfloor\frac{n}{r}\rfloor$ or $\lceil\frac{n}{r}\rceil$
vertices, we may assume
$\mathbf{y}=(\underbrace{y_{1},\ldots,y_{1}}_{k\lceil\frac{n}{r}\rceil},\underbrace{y_{2},\ldots,y_{2}}_{n-k\lceil\frac{n}{r}\rceil})^{\mathrm{T}}$.
Thus by (2), we have

$\displaystyle\lambda(T_{n,r})y_{1}=(r-k)\big{\lfloor}\frac{n}{r}\big{\rfloor}y_{2}+(k-1)\big{\lceil}\frac{n}{r}\big{\rceil}y_{1},$
(17)

and

$\displaystyle\lambda(T_{n,r})y_{2}=(r-k-1)\big{\lfloor}\frac{n}{r}\big{\rfloor}y_{2}+k\big{\lceil}\frac{n}{r}\big{\rceil}y_{1}.$
(18)

Combining (17) and (18), we obtain

$\Big{(}\lambda(T_{n,r})+\big{\lceil}\frac{n}{r}\big{\rceil}\Big{)}y_{1}=\Big{(}\lambda(T_{n,r})+\big{\lfloor}\frac{n}{r}\big{\rfloor}\Big{)}y_{2}.$

Without loss of generality, we assume that $y_{2}=1$. Then

$y_{2}\geq
y_{1}=\frac{\lambda(T_{n,r})+\lfloor\frac{n}{r}\rfloor}{\lambda(T_{n,r})+\lceil\frac{n}{r}\rceil}\geq
1-\frac{1}{\lambda(T_{n,r})+\lceil\frac{n}{r}\rceil}.$

Since $\lambda(T_{n,r})\geq\delta(T_{n,r})\geq n-\lceil\frac{n}{r}\rceil$,
$y_{1}\geq 1-\frac{1}{n}$. Let $H\in\mathrm{Ex}(n,F)$. Then
$e(H)=\mathrm{ex}(n,F)=e(T_{n,r})+a$. Therefore

$\displaystyle\lambda(G)$
$\displaystyle\geq\lambda(H)\geq\frac{\mathbf{y}^{\mathrm{T}}A(H)\mathbf{y}}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}$
$\displaystyle\geq\frac{\mathbf{y}^{\mathrm{T}}A(T_{n,r})\mathbf{y}}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}+\frac{2a}{\mathbf{y}^{\mathrm{T}}\mathbf{y}}\left(1-\frac{1}{n}\right)^{2}$
$\displaystyle\geq\lambda(T_{n,r})+\frac{2a}{n}\left(1-\frac{2}{n}\right).$
(19)

Combining (16), (19) and $\mathbf{x}^{\mathrm{T}}\mathbf{x}\geq
n(1-\frac{20a^{2}r^{2}}{n})^{2}\geq n-40a^{2}r^{2}$, we get

$\displaystyle\lambda(T_{n,r})-\lambda(K)$ $\displaystyle\leq$
$\displaystyle\frac{2a}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2a}{n}+\frac{4a}{n^{2}}+\frac{\frac{80a^{4}r^{4}}{n}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle\leq$
$\displaystyle\frac{2a}{n-40a^{2}r^{2}}-\frac{2a}{n}+\frac{4a}{n^{2}}+\frac{\frac{80a^{4}r^{4}}{n}}{n-40a^{2}r^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{80a^{3}r^{2}}{n(n-40a^{2}r^{2})}+\frac{4a}{n^{2}}+\frac{80a^{4}r^{4}}{n(n-40a^{2}r^{2})}$
$\displaystyle\leq$ $\displaystyle\frac{c_{2}}{n^{2}},$

where $c_{2}$ is a positive constant. ∎

Combining Claim 1 and Claim 2, we have

$\frac{c_{1}}{n}\leq\lambda(T_{n,r})-\lambda(K)\leq\frac{c_{2}}{n^{2}},$

which is a contradiction when $n$ is sufficiently large. Thus
$\left|n_{i}-n_{j}\right|\leq 1$ for any $1\leq i<j\leq r$.

∎

Proof of Theorem 1.2. Now we prove that $e(G)=\mathrm{ex}(n,F)$. Otherwise, we
assume that $e(G)\leq\mathrm{ex}(n,F)-1$. Let $H\in\mathrm{Ex}(n,F)$. Then
$|E(H)|=e(T_{n,r})+a$. By Lemma 3.10, we may assume that $V_{1}\cup\ldots\cup
V_{r}$ is a vertex partition of $H$. Let $E_{1}=E(G)\setminus E(H)$,
$E_{2}=E(H)\setminus E(G)$, then $E(H)=(E(G)\cup E_{2})\setminus E_{1}$, and

$|E(G)\cap E(H)|+|E_{1}|=e(G)<e(H)=|E(G)\cap E(H)|+|E_{2}|,$

which implies that $|E_{2}|\geq|E_{1}|+1$. Furthermore, by Lemma 3.7, we have

$\displaystyle|E_{2}|\leq a+\sum\limits_{1\leq i<j\leq r}|B_{i}||B_{j}|\leq
a+\binom{r}{2}(2a)^{2}\leq 3a^{2}r^{2}.$ (20)

According to (3) and (20), for sufficiently large $n$, we have

$\displaystyle\lambda(H)$
$\displaystyle\geq\frac{\mathbf{x}^{\mathrm{T}}A(H)\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle=\frac{\mathbf{x}^{\mathrm{T}}A(G)\mathbf{x}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}+\frac{2\sum_{ij\in
E_{2}}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}-\frac{2\sum_{ij\in
E_{1}}x_{i}x_{j}}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}$
$\displaystyle=\lambda(G)+\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}\sum_{ij\in
E_{2}}x_{i}x_{j}-\sum_{ij\in E_{1}}x_{i}x_{j}\Big{)}$
$\displaystyle\geq\lambda(G)+\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}|E_{2}|(1-\frac{20a^{2}r^{2}}{n})^{2}-|E_{1}|\Big{)}$
$\displaystyle\geq\lambda(G)+\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}|E_{2}|-\frac{40a^{2}r^{2}}{n}|E_{2}|-|E_{1}|\Big{)}$
$\displaystyle\geq\lambda(G)+\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}1-\frac{40a^{2}r^{2}}{n}|E_{2}|\Big{)}$
$\displaystyle\geq\lambda(G)+\frac{2}{\mathbf{x}^{\mathrm{T}}\mathbf{x}}\Big{(}1-\frac{40a^{2}r^{2}}{n}3a^{2}r^{2}\Big{)}$
$\displaystyle>\lambda(G),$

which contradicts the assumption that $G$ has the maximum spectral radius
among all $F$-free graphs on $n$ vertices. Hence $e(G)=\mathrm{ex}(n,F)$. ∎

## References

  * [1] L. Babai, B. Guiduli, Spectral extrema for graphs: the Zarankiewicz problem, Electron. J. Combin., 15 (2009) R123.
  * [2] B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978.
  * [3] G. Chen, R.J. Gould, F. Pfender, B. Wei, Extremal graphs for intersecting cliques, J. Combin. Theory Ser. B, 89 (2003) 159–171.
  * [4] S. Cioabă, L.H. Feng, M. Tait, X.D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin., 27 (4) (2020) P4.22.
  * [5] S. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin., 99 (2022) 103420.
  * [6] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980.
  * [7] C. Delorme, Eigenvalues of complete multipartite graphs, Discrete Math., 312 (2012) 2532-2535.
  * [8] D.N. Desai, L. Kang, Y. Li, Z. Ni, M. Tait, J. Wang, Spectral extremal graphs for intersecting cliques, arXiv:2108.03587v2, 2021.
  * [9] P. Erdős, Some recent results on extremal problems in graph theory (Results), in: Theory of Graphs (International Symposium Rome, 1966), Grodon and Breach, New York, Dunod, Paris, 1966, pp. 117–123.
  * [10] P. Erdős, On some new inequalities concerning extremal properties of graphs, in: Theory of Graphs (Proceedings of Colloquium, Tihany, 1966), Academic Press, New York, 1968, pp. 77-81.
  * [11] P. Erdős, M. Simonovits, A limit theorem in graph theory, Stud. Sci. Math. Hungar., 1 (1966) 51–57.
  * [12] P. Erdős, A.H. Stone, On the structure of linear graphs, Bull. Am. Math. Soc., 52 (1946) 1087–1091.
  * [13] P. Erdős, Z. Füredi, R.J. Gould, D.S. Gunderson, Extremal Graphs for Intersecting Triangles, J. Combin. Theory Ser. B, 64 (1995) 89–100.
  * [14] L.H. Feng, Q. Li, X.D. Zhang, Spectral radii of graphs with given chromatic number, Appl. Math. Lett., 20 (2007) 158–162.
  * [15] M. Fiedler, V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl., 432 (2010) 2170–2173.
  * [16] 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.
  * [17] P. Keevash, Hypergraph Turán problems, in Surveys in Combinatorics, Cambridge University Press, Cambridge, 2011, pp. 83–140.
  * [18] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput., 11 (2002) 179–189.
  * [19] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra Appl., 427 (2007) 183–189.
  * [20] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl., 432 (2010) 2243–2256.
  * [21] V. Nikiforov, Stability for large forbidden subgraphs, J. Graph Theory, 62 (4) (2009) 362–368.
  * [22] V. Nikiforov, Some new results in extremal graph theory, Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., 392, Cambridge University Press, Cambridge, 2011, pp. 141–181.
  * [23] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, In: Theory of Graphs (Proceedings of Colloquium, Tihany, 1966), Academic Press, New York, 1968, pp. 279–319.
  * [24] 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.
  * [25] D. Stevanović, I. Gutman, M. Rehman, On spectral radius and enery of complete multipartite graphs, Ars Math. Contemp., 9 (2015) 109–113.
  * [26] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok, 48 (1941) 436–452.
  * [27] Y. Li, Y. Peng, The spectral radius of graphs with no intersecting odd cycles, arXiv:2106.00587v1, 2021.
  * [28] M. Zhai, B. Wang, Proof of a conjecture on the spectral radius of $C_{4}$-free graphs, Linear Algebra Appl., 430 (2012) 1641–1647.
  * [29] X. Zhan, Matrix theory, Gradutate Studies in Mathematics. 147, American Mathematical Society, Providence, RI, 2013. x+253 pp.


# 2B or not 2B, a study of bottom-quark-philic semi-visible jets

Deepak Kar  Sukanya Sinha  School of Physics, University of Witwatersrand
Johannesburg, South Africa
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Semi-visible jets arise in strongly interacting dark sectors, resulting in
jets overlapping with missing transverse momentum direction. The
implementation of semi-visible jets is done using the Pythia Hidden Valley
module to mimic the QCD sector showering in so-called dark shower. In this
work, only heavy flavour Standard Model quarks are considered in dark shower,
resulting in a much less ambiguous collider signature of semi-visible jets
compared to the democratic production of all five quark flavours in dark
shower.

###### keywords:

Dark matter, semi-visible jets, heavy flavour

##  1 Introduction

Collider searches for Dark Matter (DM) have so far mostly focused on scenarios
where DM particles are produced in association with Standard Model (SM)
particles, typically termed mono-X searches, where X is the SM particle.
However, no evidence of DM has been observed so far. Several recent models [1,
2, 3] have been proposed that include a strongly-coupled dark sector, giving
rise to uncovered collider topologies. Semi-visible jets (SVJ) [4, 5, 6] is
one such example. In the $t$-channel production mode, a scalar bi-fundamental
mediator ($\Phi$) acts as a portal between the SM and dark sectors, resulting
in producing jets interspersed with dark hadrons. At leading order the two
SVJs are back-to-back and the direction of the missing transverse momentum is
aligned with one of the two reconstructed jets.

Experimental results in the $s$-channel production mode has been presented by
the CMS collaboration [7] and preliminary results in the $t$-channel
production mode by ATLAS collaboration [8]. Recent works proposed way to
ascertain systematic uncertainties on SVJ production [9], use of jet
substructure observables to understand and discriminate SVJ [10, 11], using
machine learning methods to discriminate SVJ [12] or new signature of SVJ with
leptons [13]. The recent Snowmass whitepaper [14] presents a comprehensive
review. In this paper, we propose a signature of SVJ only being produced with
SM $b\text{-quarks}$ in the $t$-channel. However, some of the conclusions
derived here can also be applicable in a $s$-channel search.

##  2 SVJ with heavy flavour

The modelling of this final state signatures is performed using the Hidden
Valley (HV) [15] module of Pythia8 [16], which was designed in order to study
a sector which is decoupled from the Standard Model (SM). In HV module, the
Standard Model gauge group $G_{sm}$ is extended by a non-Abelian gauge group
$G_{d}$, where the SM particles are neutral under $G_{d}$, but new hidden
valley light particles are charged under $G_{d}$ and neutral under $G_{sm}$.
The interactions between SM fields and the HV particles are allowed by TeV-
scale operators. The simplest hidden valley model [17, 18, 19] assumes the
addition of a $U(1)$ x $SU(N_{d})$ gauge group, with couplings g’ and $g_{d}$,
with the $U(1)$ being broken by a scalar $<\phi>$. Assuming the addition of
two new quark flavours, and the presence of analogous neutral hidden valley
pions $\pi^{0}_{d}$, the $\pi^{0}_{d}$ can decay to SM hadrons via the Yukawa
coupling, $\kappa$. If $\pi^{0}_{d}$ are much lighter than the other hidden
valley hadrons of the theory, a helicity flipping suppression forces the
$\pi_{d}\rightarrow b\bar{b}$ to be dominant, provided the masses satisfy:
$2m_{b}<m_{\pi^{0}_{d}}<2m_{t}$. This is the same helicity flipping
suppression as is observed in the case of SM $\pi^{+}$ decaying to
$\mu^{+}\nu$ instead of $e^{+}\nu$. Hence, the b-philic mode of hidden valley
pion decay will be preferred unless there is a hierarchical $\kappa$ matrix
that opposes the mass enhancement.

The signal samples, at $\sqrt{s}=13$ TeV are generated by using a $t$-channel
simplified dark-matter model [20] in Madgraph5 [21] matrix element (ME)
generator, with and NNPDF2.3 LO PDF set [22], a mediator mass of 3000 GeV, and
a dark-matter candidate mass of 10 GeV. Different $R_{\textrm{inv}}$ fractions
result in somewhat different kinematics, so $R_{\textrm{inv}}$ values of 0.33
and 0.67 are studied. The MLM [23] jet matching scheme, with the matching
parameter set to 100 GeV, is employed to generate the signal with up to two
additional partons. In the HV module, as discussed above, only SM bottom quark
is considered. The multijet and $t\overline{t}$ proceses are generated with
Pythia8. As we are mostly concerned with the overall features, the lack of
higher order matrix element in background simulation is not a concern. For
these studies, the Rivet [24] analysis toolkit was used, with the Fastjet
package [25] for jet clustering.

##  3 Signal reconstruction

We start with the pre-selection used in recent ATLAS $t$-channel search [8].
In order to use $p_{\text{T}}^{\text{miss}}$ trigger, a minimum
$p_{\text{T}}^{\text{miss}}$ requirement of 200 GeV was needed. Jets are are
constructed using the anti-$k_{t}$ algorithm [26] with a radius parameter of
$R=0.4$, using both charged and neutral inputs. The leading jet
$p_{\mathrm{T}}$ was 250 GeV, while all the other jets were required to have
$p_{\mathrm{T}}$ of at least 30 GeV. Events needed to have at least two jets.
The jet closest to the $p_{\text{T}}^{\text{miss}}$ direction in azimuthal
angle was termed the SVJ candidate, and it was required be within
$\Delta\Phi<2.0$ of the $p_{\text{T}}^{\text{miss}}$ direction. It was seen
the the sub-leading jet was the SVJ candidate in most of the events. Events
with charged leptons having $p_{\mathrm{T}}$ of 7 GeV or more were vetoed.
Events with two or more $b\text{-tagged}$ jets were discarded as well, to
reduce the background from top quark initiated processes.

The pre-selection for the $b\text{-tagged}$ SVJ case follows the ATLAS pre-
selection. However, the 200 GeV $p_{\text{T}}^{\text{miss}}$ requirement
severely reduces the signal statistics, so in order to investigate the
strategies to increase the signal efficiency, we have removed
$p_{\text{T}}^{\text{miss}}$ requirement. At detector level, mis-measurement
of jets typically increase the $p_{\text{T}}^{\text{miss}}$, so this is not a
completely unrealistic assumption. However, for the actual analysis, we will
have to revert back to the 200 GeV $p_{\text{T}}^{\text{miss}}$ requirement,
assuming that the conclusions derived here hold. The lepton veto with the
lowest possible $p_{\mathrm{T}}$ was appropriate for the analysis dominated by
light-quark initiated jets, however semi-leptonic decays from
$b\text{-quarks}$ indicate the events will have leptons, so we have to
optimise that selection as well.

In order to arrive at an analysis strategy which can maximise the signal
efficiency for this specific final state, it is worthwhile to investigate
different jet reconstruction strategies. This final state offers a clean
playground, as the SVJs need to $b\text{-tagged}$, unlike for the democratic
production of all five flavours where the only handle we have is the azimuthal
separation from the $p_{\text{T}}^{\text{miss}}$ direction, which can
introduce ambiguities.

  * 1.

The ATLAS analysis uses jets with radius parameter of 0.4. The use of
$p_{\text{T}}^{\text{miss}}$ trigger does allow us to use jets of
$p_{\mathrm{T}}$ of 30 GeV, which would not be possible with lowest un-
prescaled single jet triggers, which currently in ATLAS requires a leading jet
$p_{\mathrm{T}}$ of 450 GeV [27].

  * 2.

As semi-visible jets tend be spread out with gaps in them, in our previous
work [11], we investigated the use of large-radius jets and jet substructure
observables. The jet energy calibration for large-radius jets with
anti-$k_{t}$ algorithm using a radius parameter of $1.0$ with trimming [28] as
used in ATLAS [29] typically require a minimum $p_{\mathrm{T}}$ of 200 GeV. We
would then require two $b\text{-tagged}$ large-radius jets with
$p_{\mathrm{T}}$ of at least 200 GeV. The $b\text{-tagging}$ of large-radius
jets in ATLAS are typically performed with associated track jets [30]. While
we can still use $p_{\text{T}}^{\text{miss}}$ trigger with large-radius jets,
the $p_{\mathrm{T}}$ requirement of 200 GeV for these jets remain.

  * 3.

Another possible option will be to use reclustered jets (RC) [31], as that
allows us to use lower $p_{\mathrm{T}}$ jets than usual large-radius jets, but
in the cases RC jets consist only one small-radius input jet, the experimental
jet mass calibration tends to be ill-defined. We have observed that this is
indeed the case for a significant number of events for radii of 0.8 to 1.5.
Since the radius is fixed, it is difficult to avoid this problem.

  * 4.

Jet reconstruction with a variable radius (VR) [32] was introduced to increase
the signal reconstruction efficiency for boosted resonance searches. The VR
algorithm needs the minimum and maximum allowed jet radius, as well $\rho$,
which is the mass parameter, resulting in the effective radius of the VR jets
to scale as $R~{}\rho/p_{\mathrm{T}}$. While different choices can be made for
input jets to VR algorithm, starting from trackjets (jets only with charged
particles at particle level) where going to much lower $p_{\mathrm{T}}$ is
feasible, we used anti-$k_{t}$ jets with radius parameter of $0.4$ with a
minimum $p_{\mathrm{T}}$ of 30 GeV as input to VR algorithm. The trackjets do
not capture the totality of the SVJ, which we saw leads to non-optimal
performance for signal to background discrimination later. The minimum radius
was kept at $0.4$ and the maximum was set to $1.5$ to stay well within the
central part of the detector. The suggested value of $\rho$ is
$<2p_{\mathrm{T}}$ in case of resonance searches, here we used 200 GeV. It was
checked that using a lower value did not affect the shape of kinematic
distributions, but reduced the acceptance. This can be understood from the
fact that SVJ indeed behaves like a multi-prong jet [11]. Since VR jet radius
adaptive compared to RC, we decided to use VR jets over RC jets. ATLAS has
used VT tracks jets in previous searches [33].

In order to compare the performance of the above mentioned jet reconstruction
strategies, we need to come up with a metric. As the pre-selection will
require a $b\text{-tagged}$ SVJ close to $p_{\text{T}}^{\text{miss}}$
direction, after requiring at least two $b\text{-tagged}$ SVJ, we demand at
least one of them must be within $\Delta\Phi<2.0$ of the
$p_{\text{T}}^{\text{miss}}$ direction, without requiring any higher leading
jet $p_{\mathrm{T}}$ threshold. Then in Figure 1, we look at the multiplicity
of $b\text{-tagged}$ jets for jets with radii 0.4 and 1.0, as well as of VR
jets.

Figure 1: The multiplicity of $b\text{-tagged}$ jets for radius 0.4 and radius
1.0 jets, as well as VR jets after $\Delta\Phi<2.0$ requirement, for signal
with $R_{\textrm{inv}}$ of 0.33 (left) and 0.67 (right).

The general trend is, use of large-radius jets decrease the signal efficiency,
however, using VR jets, even without any optimisation results in an
improvement, at least after $b\text{-jet}$ multiplicity requirement. In order
to understand the above mentioned signal efficiency gain with VR, we look at
the objects in $\eta-\phi$ plane for four representative events in Figure 2.
It is evident VR better reconstructs the SVJs better than jets with radius of
0.4, both in terms of containing all the decay products, as well as being
closer to the direction of missing transverse momentum. This is seen to be
true for both the signal points with rather different $R_{\textrm{inv}}$
fraction.

Figure 2: Various objects are plotted in $\eta-\phi$ plane for four
representative signal events with $R_{\textrm{inv}}$ of 0.33 (top row) and
0.67 (bottom row). The large hollow green circles represent the VR jets, the
filled gray circles represent anti-$k_{\textrm{t}}$ jets with R=0.4, the
magenta points represent dark hadrons, the blue points indicate stable
b-hadrond, and the orange line the direction of missing transverses momentum.

The next step is to optimise the pre-selections with VR jets to obtain further
improvement in signal efficiency, as well as to obtain a good signal to
background discrimination.

##  4 Search strategy

The pre-selections include discarding events with charged leptons having
$p_{\mathrm{T}}$ of 7 GeV or more. While that is reasonable for a mostly
light-flavour quark dominated signature, semi-leptonic decay of
$b\text{-quarks}$ produce a copious amount of charged leptons. Even in our
particle level study, this requirements leads to a loss of about 50% of signal
events with the 7 GeV $p_{\mathrm{T}}$ threshold, dropping to about 25% for a
higher $p_{\mathrm{T}}$ threshold of 30 GeV, which is highly non-ideal. To
recover events from lepton veto, two approaches can be adopted, either vetoing
events with charged leptons with a significantly higher $p_{\mathrm{T}}$
threshold, or requiring them to be close to the $b\text{-jet}$. In Figure 3,
the correlation between these two quantities are shown. It can be seen most
leptons have low $p_{\mathrm{T}}$ and are close to a $b\text{-tagged}$ jet.
Based on this, we decided to select leptons only with $p_{\mathrm{T}}>75$ GeV,
and further require they lie within $\Delta\Phi<0.1$ of a $b\text{-tagged}$
jet. This leads to no signal efficiency loss, but still rejects a large
fraction of background events with an isolated high $p_{\mathrm{T}}$ lepton.

Figure 3: The correlation of charged lepton $p_{\text{T}}$ against the
$\Delta\Phi$ distance from the closest $b\text{-tagged}$ jet is shown for the
signal a mediator mass of 3000 GeV and $R_{\textrm{inv}}$ of 0.33. Same trend
is observed for the signal with $R_{\textrm{inv}}$ of 0.67.

The leading background processes are multijet, and top quark pair production,
referred to as $t\overline{t}$. The semileptonic and dileptonic decay modes of
$t\overline{t}$ were seen to produce almost identical kinematic distributions
and yields, so we combined them together in non-hadronic. The jet closest in
azimuthal angle to the direction of the missing transverse momentum is termed
the SVJ candidate. The discriminating variables we looked at:

  * 1.

$H_{\text{T}}$, defined as the scalar sum of $p_{\mathrm{T}}$ of jets in the
event

  * 2.

Lead jet $p_{\mathrm{T}}$, the $p_{\mathrm{T}}$ of the leading jet

  * 3.

$\phi_{\textrm{MET},\textrm{closest-jet}}$, defined as the $\Delta\Phi$ of the
jet closest to the direction of the missing transverse momentum

  * 4.

$|\phi_{\textrm{max}}-\phi_{\textrm{min}}|$, defined as the azimuthal angle
between the closest jet ($j_{1}$) and farthest jet ($j_{2}$) from
$p_{\text{T}}^{\text{miss}}$

  * 5.

$p_{\mathrm{T}}^{\textrm{bal}}$, $p_{\mathrm{T}}$ balance between the $j_{1}$
$j_{2}$, defined as,

$p_{\mathrm{T}}^{\textrm{bal}}=\frac{|\vec{p_{\mathrm{T}}}(j_{1})+\vec{p_{\mathrm{T}}}(j_{2})|}{|\vec{p_{\mathrm{T}}}(j_{1}|+|\vec{p_{\mathrm{T}}}(j_{2})|}$.

Previously we found the last two of the observable to be most different
between signal and most background processes [8], so at the first step, we
tried to look at the other observables in Figure 4.

Figure 4: The distributions of $H_{\text{T}}$ (top left), leading jet
$p_{\mathrm{T}}$ (top right) and $\phi_{\textrm{MET},\textrm{closest-
jet}}$(bottom) for two signal (corresponding to a mediator mass of 3000 GeV
and $R_{\textrm{inv}}$ of 0.33 and 0.67) and all leading background processes
after only jet multiplicity and lepton angle requirements.

Based on these distributions, we decided to require the leading jet
$p_{\mathrm{T}}$ to be at least 80 GeV, $\phi_{\textrm{MET},\textrm{closest-
jet}}$of 0.5 or smaller. Finally, the signal region (SR) can be defined with
$H_{\text{T}}$ of more than 400 GeV. in Figure 4. After these requirements,
the distributions of $|\phi_{\textrm{max}}-\phi_{\textrm{min}}|$ and
$p_{\mathrm{T}}^{\textrm{bal}}$ are shown in Figure 5. Unfortunately, it
appears the former is not very helpful in this case, but the latter is a good
discriminating variable, and can be used in the search.

Figure 5: The distributions of $|\phi_{\textrm{max}}-\phi_{\textrm{min}}|$
(left) and $p_{\mathrm{T}}^{\textrm{bal}}$(right) for two signal
(corresponding to a mediator mass of 3000 GeV and $R_{\textrm{inv}}$ of 0.33
and 0.67) and all leading background processes after all requirements in the
SR defined by $H_{\text{T}}>400$ GeV.

For completeness, we also provide a cutflow in Table 1 summarising the above
steps. As we can see, the simple selections we used are already rather
effective in defining a signal-enriched region, with
$p_{\mathrm{T}}^{\textrm{bal}}$ being a sensitive observable. A detector level
search will also have a requirement on $p_{\text{T}}^{\text{miss}}$, typically
at least 200 GeV to reach the trigger efficiency plateau, which might further
help in enhancing the signal over the background.

Requirement | Selection efficiency reduction in $\%$:
---|---
| Signal (3000,33) | Signal (3000, 67) | Multijet | Hadronic $t\overline{t}$ | Semileptonic $t\overline{t}$ | Dilpetonic $t\overline{t}$
DiBjet | 51 | 20 | 1 | 49 | 49 | 47
Lepton angle | 49 | 19 | 1 | 49 | 41 | 34
$\phi_{\textrm{MET},\textrm{closest-jet}}$ | 37 | 13 | 0 | 22 | 13 | 9.
Leading jet $p_{\mathrm{T}}$ | 36 | 13 | 0 | 20 | 11 | 7
$H_{\text{T}}$ SR | 25 | 8 | 0 | 4 | 1 | 1
Table 1: The numbers represent the percentage of events remaining after each
requirement. The individual requirements are mentioned in the text. The signal
corresponds to a mediator mass of 3000 GeV and $R_{\textrm{inv}}$ of 0.33 and
0.67, as indicated in the parenthesis.

##  5 Summary

A feasibility study for a collider search for SVJ produced in association with
only heavy flavour quarks is presented. While this is theoretically well
motivated scenario, no search has been performed yet, but we show that it is a
rather promising search channel. The additional requirement of SVJs being
$b\text{-tagged}$ acts as a powerful tool to isolate signal-like events, while
the use of VR jets improves signal acceptance.

## Acknowledgements

DK is funded by the National Research Foundation (NRF), South Africa. SS
thanks University of Witwatersrand Research Council for Sellschop grant and
NRF for Extension Support Doctoral Scholarship. We would like to thank Tim
Cohen and Matt Strassler for useful inputs. We also thank Suvam Maharana for
additional discussions.

## References

  * [1] P. Schwaller, D. Stolarski, A. Weiler, Emerging Jets, JHEP 05 (2015) 059.  arXiv:1502.05409, doi:10.1007/JHEP05(2015)059.
  * [2] H. Beauchesne, E. Bertuzzo, G. Grilli Di Cortona, Dark matter in Hidden Valley models with stable and unstable light dark mesons, JHEP 04 (2019) 118.  arXiv:1809.10152, doi:10.1007/JHEP04(2019)118.
  * [3] E. Bernreuther, F. Kahlhoefer, M. Krämer, P. Tunney, Strongly interacting dark sectors in the early Universe and at the LHC through a simplified portal, JHEP 01 (2020) 162.  arXiv:1907.04346, doi:10.1007/JHEP01(2020)162.
  * [4] T. Cohen, M. Lisanti, H. K. Lou, Semivisible Jets: Dark Matter Undercover at the LHC, Phys. Rev. Lett. 115 (17) (2015) 171804.  arXiv:1503.00009, doi:10.1103/PhysRevLett.115.171804.
  * [5] T. Cohen, M. Lisanti, H. K. Lou, S. Mishra-Sharma, LHC Searches for Dark Sector Showers, JHEP 11 (2017) 196.  arXiv:1707.05326, doi:10.1007/JHEP11(2017)196.
  * [6] H. Beauchesne, E. Bertuzzo, G. Grilli Di Cortona, Z. Tabrizi, Collider phenomenology of Hidden Valley mediators of spin 0 or 1/2 with semivisible jets, JHEP 08 (2018) 030.  arXiv:1712.07160, doi:10.1007/JHEP08(2018)030.
  * [7] CMS Collaboration, Search for resonant production of strongly coupled dark matter in proton–proton collisions at $13\,\text{TeV}$ (2021).  arXiv:2112.11125.
  * [8] ATLAS Collaboration, Search for non-resonant production of semi-visible jets using Run 2 data in ATLAS, ATLAS-CONF-2022-038 (2022).
URL https://atlas.web.cern.ch/Atlas/GROUPS/PHYSICS/CONFNOTES/ATLAS-
CONF-2022-038/

  * [9] T. Cohen, J. Doss, M. Freytsis, Jet Substructure from Dark Sector Showers, arXiv:2004.00631 (4 2020).  arXiv:2004.00631.
  * [10] M. Park, M. Zhang, Tagging a jet from a dark sector with Jet-substructures at colliders, Phys. Rev. D 100 (11) (2019) 115009.  arXiv:1712.09279, doi:10.1103/PhysRevD.100.115009.
  * [11] D. Kar, S. Sinha, Exploring Jet Substructure in Semi-visible jets, SciPost Phys. 10 (2021) 84.  doi:10.21468/SciPostPhys.10.4.084.
URL https://scipost.org/10.21468/SciPostPhys.10.4.084

  * [12] E. Bernreuther, T. Finke, F. Kahlhoefer, M. Krämer, A. Mück, Casting a graph net to catch dark showers, SciPost Phys. 10 (2) (2021) 046.  arXiv:2006.08639, doi:10.21468/SciPostPhys.10.2.046.
  * [13] C. Cazzaniga, A. de Cosa, Leptons lurking in semi-visible jets at the LHC (6 2022).  arXiv:2206.03909.
  * [14] G. Albouy, et al., Theory, phenomenology, and experimental avenues for dark showers: a Snowmass 2021 report (3 2022).  arXiv:2203.09503.
  * [15] L. Carloni, T. Sjostrand, Visible Effects of Invisible Hidden Valley Radiation, JHEP 09 (2010) 105.  arXiv:1006.2911, doi:10.1007/JHEP09(2010)105.
  * [16] T. Sjöstrand, S. Ask, J. R. Christiansen, R. Corke, N. Desai, P. Ilten, S. Mrenna, S. Prestel, C. O. Rasmussen, P. Z. Skands, An Introduction to PYTHIA 8.2, Comput. Phys. Commun. 191 (2015) 159–177.  arXiv:1410.3012, doi:10.1016/j.cpc.2015.01.024.
  * [17] M. J. Strassler, K. M. Zurek, Echoes of a hidden valley at hadron colliders, Phys. Lett. B 651 (2007) 374–379.  arXiv:hep-ph/0604261, doi:10.1016/j.physletb.2007.06.055.
  * [18] M. J. Strassler, On the Phenomenology of Hidden Valleys with Heavy Flavor (6 2008).  arXiv:0806.2385.
  * [19] S. Renner, P. Schwaller, A flavoured dark sector, JHEP 08 (2018) 052.  arXiv:1803.08080, doi:10.1007/JHEP08(2018)052.
  * [20] Dmsimp model, https://github.com/smsharma/SemivisibleJets, accessed: 2020-11-10.
  * [21] J. Alwall, R. Frederix, S. Frixione, V. Hirschi, F. Maltoni, O. Mattelaer, H. S. Shao, T. Stelzer, P. Torrielli, M. Zaro, The automated computation of tree-level and next-to-leading order differential cross sections, and their matching to parton shower simulations, JHEP 07 (2014) 079.  arXiv:1405.0301, doi:10.1007/JHEP07(2014)079.
  * [22] P. Skands, S. Carrazza, J. Rojo, Tuning PYTHIA 8.1: the Monash 2013 Tune, Eur. Phys. J. C74 (8) (2014) 3024.  arXiv:1404.5630, doi:10.1140/epjc/s10052-014-3024-y.
  * [23] M. L. Mangano, M. Moretti, F. Piccinini, M. Treccani, Matching matrix elements and shower evolution for top-quark production in hadronic collisions, JHEP 01 (2007) 013.  arXiv:hep-ph/0611129, doi:10.1088/1126-6708/2007/01/013.
  * [24] C. Bierlich, et al., Robust Independent Validation of Experiment and Theory: Rivet version 3, SciPost Phys. 8 (2020) 026.  arXiv:1912.05451, doi:10.21468/SciPostPhys.8.2.026.
  * [25] M. Cacciari, G. P. Salam, G. Soyez, FastJet User Manual, Eur. Phys. J. C72 (2012) 1896.  arXiv:1111.6097, doi:10.1140/epjc/s10052-012-1896-2.
  * [26] M. Cacciari, G. P. Salam, G. Soyez, The anti-$k_{t}$ jet clustering algorithm, JHEP 04 (2008) 063.  arXiv:0802.1189, doi:10.1088/1126-6708/2008/04/063.
  * [27] ATLAS Collaboration, Performance of the ATLAS trigger system in 2015, Eur. Phys. J. C 77 (2017) 317.  arXiv:1611.09661, doi:10.1140/epjc/s10052-017-4852-3.
  * [28] D. Krohn, J. Thaler, L.-T. Wang, Jet Trimming, JHEP 02 (2010) 084.  arXiv:0912.1342, doi:10.1007/JHEP02(2010)084.
  * [29] ATLAS Collaboration, Optimisation of large-radius jet reconstruction for the ATLAS detector in $13\,\text{TeV}$ proton–proton collisions, Eur. Phys. J. C 81 (2020) 334.  arXiv:2009.04986, doi:10.1140/epjc/s10052-021-09054-3.
  * [30] ATLAS Collaboration, Identification of boosted Higgs bosons decaying into $b$-quark pairs with the ATLAS detector at $13\,\text{TeV}$, Eur. Phys. J. C 79 (2019) 836.  arXiv:1906.11005, doi:10.1140/epjc/s10052-019-7335-x.
  * [31] B. Nachman, P. Nef, A. Schwartzman, M. Swiatlowski, C. Wanotayaroj, Jets from Jets: Re-clustering as a tool for large radius jet reconstruction and grooming at the LHC, JHEP 02 (2015) 075.  arXiv:1407.2922, doi:10.1007/JHEP02(2015)075.
  * [32] D. Krohn, J. Thaler, L.-T. Wang, Jets with Variable R, JHEP 06 (2009) 059.  arXiv:0903.0392, doi:10.1088/1126-6708/2009/06/059.
  * [33] ATLAS Collaboration, Search for dark matter produced in association with a Standard Model Higgs boson decaying into b-quarks using the full Run 2 dataset from the ATLAS detector, JHEP 11 (2021) 209.  arXiv:2108.13391, doi:10.1007/JHEP11(2021)209.