# Turán Number of Subdivisions of Multipartite Graphs

Xiao-Chuan Liu  Instituto de Matemática Universidade Federal de Alagoas, Av.
Lourival Melo Mota, S/N, Maceió, Brasil<EMAIL_ADDRESS>,  Danni Peng
Center for Combinatorics and LMPC, Nankai University, Tianjing, 30071, China
<EMAIL_ADDRESS>and  Xu Yang  Instituto de Computação da Universidade
Federal de Alagoas, Av. Lourival Melo Mota, S/N, Maceió, Brasil
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we initiate the study of the extremal exponent for the
$1$-subdivisions of non-bipartite non-complete graphs. Let $K_{C_{k},1}$ be
the graph by connecting an additional vertex to every vertex of the cycle
$C_{k}$, $k\geq 4$. We show that for the $1$-subdivision of the tripartite
graph $K_{C_{k},1}^{\text{sub}}$, its Turán number is $\Theta(n^{4/3})$. Then
we obtain the upper bound for the extremal number of a family of graphs
consisting of (possibly degenerate) $1$-subdivisions of certain tripartite
graphs. We also obtain the same upper bound for the 1-subdivision of
$(K_{s+1,t}^{+})^{sub}$, where $K_{s+1,t}^{+}$ is a graph obtained by joining
$K_{s,t}$ with one new vertex $r$ by means of connecting $r$ with one vertex
in the $s$-part and all the vertices in the $t$-part.

Key words and phrases: Turán number, $1$-subdivision, non-bipartite graphs.

MSC subject classification code: 05C35.

##  1\. Introduction

One of the most fundamental problems in extremal graph theory is to determine
the Turán number of a graph $H$. By definition, let $\text{ex}(n,H)$ denote
the maximal number of edges of an $H$-free $n$-graph. The cornerstone in this
area is the classical Erdős-Stone-Simonovits theorem [8, 9], which says that

(1.1) $\text{ex}(n,H)=\big{(}1-\frac{1}{\chi(H)-1}+o(1)\big{)}{n\choose 2},$

where $\chi(H)$ is the chromatic number of $H$. However, when $H$ is a
bipartite graph, the above theorem only gives a crude bound $o(n^{2})$. In
fact, to understand the correct exponent of the extremal number of various
bipartite graphs is one of the central topics in extremal combinatorics. See
the recent survey [11] for more information about this rather huge topic.

In this paper, we will study this problem for the class of $1$-subdivisions of
graphs. For any graph $H$, its 1-subdivision $H^{\text{sub}}$ is obtained by
replacing each edge in $E(H)$ by a path of length two. Therefore,
$H^{\text{sub}}$ is a bipartite graph, whose vertex bipartition can be
regarded as $V(H)\cup E(H)$. In response to a conjecture made by Erdős in [7],
Conlon and Lee in [4] showed that the 1-subdivision of a complete graph always
has an extremal exponent strictly less than $\frac{3}{2}$. More precisely,

######  Theorem 1.1 ([4]).

For any integer $t\geq 3$,
$\text{ex}(n,K_{t}^{\text{sub}})=O(n^{3/2-1/{6^{t}}})$.

Then, Janzer in [13] improved this to

(1.2) $\text{ex}(n,K_{t}^{\text{sub}})=O(n^{\frac{3}{2}-\frac{1}{4t-6}}),$

which is expected to be correct exponent. In his proof, Janzer proposed a nice
scheme for upper bounding extremal numbers of 1-subdivisions of graphs.

Another related topic involving 1- subdivisions is the following conjecture
made by Kang, Kim and Liu in [15]: For any bipartite graph $H$, if
$\text{ex}(n,H)=O(n^{1+\alpha})$ for some $\alpha>0$, then
$\text{ex}(n,H^{\text{sub}})=O(n^{1+\frac{\alpha}{2}})$. In the same paper, it
was shown that the above conjecture implies the well-known rational exponent
conjecture by Erdős and Simonovits (see [6]), which states that for any
rational number $r\in[1,2]$, there exists a graph $H$ so that
$\text{ex}(n,H)=\Theta(n^{r})$.

Influenced by the subdivision conjecture, Conlon, Lee and Janzer in [5]
obtained the following result.

######  Theorem 1.2.

For any integers $2\leq s\leq t$,
$\text{ex}(n,K_{s,t}^{\text{sub}})=O(n^{3/2-1/{2s}})$.

When $t$ is sufficiently large, one can combine the recently developed random
polynomial method of Bukh and Conlon to see the exponent indeed gives the
correct order (see [1], [3] and [2]). More precisely, for any integer $s$ and
for any $t$ sufficiently large depending on $s$,

(1.3) $\text{ex}(n,K_{s,t}^{\text{sub}})=\Theta(n^{3/2-1/2s}).$

These papers inspired many works in this direction in recent years. However,
the current situation is still very unsatisfactory. For example, if the graph
$H$ itself is not bipartite, then there still exists no conjecture similar to
that of Kang, Kim and Liu. In other words, in general, if the chromatic number
of $H$ is $k\geq 3$, although its Turán number is of order $\Theta(n^{2})$,
there is no theory to even predict the Turán number for its $1$-subdivision
graph $H^{\text{sub}}$, with a single exceptional case of the complete graph
$K_{k}$, for which (1.2) provides an upper bound. In this paper, we contribute
to this topic by initiating the study of the extremal number for the
$1$-subdivisions of non-bipartite (and non-complete) graphs.

Our first result concerns the $1$-subdivision of a special type of tripartite
graph, namely $K_{1,2,2}^{\text{sub}}$. In fact, we see it as one of the
following family of graphs. Let $C_{k}$ be a cycle with $k\geq 3$. Then define
$K_{C_{k},1}$ to be the graph by connecting an additional vertex to every
vertex of the cycle $C_{k}$. Finally, we consider its subdivision
$K_{C_{k},1}^{\text{sub}}$. Note that when $k=3$, the graph
$K_{C_{3},1}^{\text{sub}}$ is just the graph $K_{4}^{\text{sub}}$.

######  Theorem 1.3.

Suppose $k\geq 4$. Then,

(1.4) $\text{ex}(n,K_{C_{k},1}^{\text{sub}})=\Theta(n^{4/3}).$

Note that when $k=4$, the graph $K_{C_{4},1}$, also known as $K_{1,2,2}$, has
one edge less than the graph $K_{1,1,1,2}$. Before Theorem 1.3, the only
previous result of $\text{ex}(n,K_{1,2,2}^{\text{sub}})$ is $O(n^{7/5})$,
indicated by $\text{ex}(n,K_{1,1,1,2}^{\text{sub}})$ in Theorem 4 of [13] (a
generalization of (1.2)). We improve the extremal number to matching upper and
lower bounds.

We also remark that in [17], Naor and Verstraëte gave an extremal number upper
bound of even cycles for bipartite graphs with non-equal parts. Then in [14],
Jiang, Ma and Yepremyan generalized this idea further to deal with more
general theta graphs. These results and their proofs are also relevant in our
proof of this theorem.

It is very interesting to ask if the same result holds for
$K_{1,2,t}^{\text{sub}}$. However, we suspect that at least for some large
$t$, the Turán exponent for $K_{1,2,t}^{\text{sub}}$ should be strictly larger
than $4/3$. But to ask for a better lower bound for this graph seems to be a
very difficult problem.

Next we turn to a tripartite graph $K_{1,s,t}$, with $t\geq s\geq 3$. Clearly,
the problem will become even harder. So, our next result is about a particular
family of graphs. Suppose we have a copy of complete bipartite graph
$K_{s,t}$, with the two vertex parts $\\{y_{1},\ldots,y_{s}\\}$ and
$\\{z_{1},\ldots,z_{t}\\}$. For any $i=1,\cdots,s$ and $j=1,\cdots,t$, we add
a new vertex $b_{ij}$ which joins both $y_{i}$ and $z_{j}$. This procedure
gives a copy of 1-subdivision of the $K_{s,t}$ which we write
$K_{s,t}^{\text{sub}}$. Then, let a bipartite graph be obtained as follows.
Firstly, add a distinct vertex $r$ to $K_{s,t}^{\text{sub}}$. Then, one by one
for each of the vertices $y_{1},\cdots,y_{s}$, $z_{1},\cdots,z_{t}$, either we
choose one of the vertices $b_{ij}$ defined above, or we add a new vertex $b$,
or we choose some previously used $b$, then we join this vertex to it and to
$r$. There are clearly finite ways to obtain such a graph. Finally, define
$\mathcal{F}_{1,s,t}$ to be the family of all bipartite graphs obtained this
way. In particular, the $1$-subdivision of the complete tripartite graph
$K_{1,s,t}$ belongs to this family, and is written as
$K_{1,s,t}^{\text{sub}}$. In Figure 1, we illustrate two examples. The first
one is $K_{1,2,3}^{sub}$. The other example is a degenerate example.

Figure 1. (1) is $K_{1,2,3}^{\text{sub}}$, a non-degenerate example. (2) is a
degenerate example. Here $ry_{1}$ is connected with a new vertex $b$. $rz_{1}$
used the same vertex $b$. $ry_{2}$ is connected with $b_{23}$. Finally,
$rz_{2}$ and $rz_{3}$ are both connected with the corresponding new vertices.

We are ready to state the next result of this paper.

######  Theorem 1.4.

For any integers $3\leq s\leq t$,
$\text{ex}(n,\mathcal{F}_{1,s,t})=O(n^{1+\frac{s^{2}+1}{2s+2s^{2}}})$.

Note that for all $s\geq 3$,
$\frac{s}{2s+2}<\frac{s^{2}+1}{2s+2s^{2}}<\frac{s}{2s+1}$, and
$\frac{s}{2s+1}$ was the best previous upper bound for this problem, given by
Janzer in [13]. Our result improves this upper bound. We suspect the same
upper bound is in fact true for the single interesting graph
$K_{1,s,t}^{\text{sub}}$ in this family, that is,

######  Conjecture 1.5.

For any integers $3\leq s\leq t$,

(1.5)
$\text{ex}(n,K_{1,s,t}^{\text{sub}})=O(n^{1+\frac{s^{2}+1}{2s+2s^{2}}}).$

In order to achieve this upper bound for a single graph from the family, more
ideas are needed. However, next we will look at $1$-subdivision of a
tripartite subgraph of $K_{1,s,t}$, for which the same upper bound can be
obtained.

######  Definition 1.6.

Let us denote by $K_{s+1,t}^{+}$ the graph obtained by a copy of complete
bipartite graph $K_{s,t}$ with one extra vertex $r$ which joins one vertex in
the $s$-part and joins all the vertices in the $t$-part. Then write
$(K_{s+1,t}^{+})^{\text{sub}}$ to denote the 1-subdivision graph of
$K_{s+1,t}^{+}$.

######  Theorem 1.7.

For any positive integers $s$ and $t$, $3\leq s\leq t-1$,

(1.6)
$\text{ex}(n,(K_{s+1,t}^{+})^{\text{sub}})=O(n^{1+\frac{s^{2}+1}{2s+2s^{2}}}).$

Below in Table 1 we list the results of the upper bounds of the extremal
exponents of some 1-subdivision of the graphs.

Table 1. Known and new results of the upper bound of the extremal exponents of 1-subdivision of some non-bipartite non-complete graphs.  $K^{\text{sub}}_{\underbrace{1,\ldots,1}_{s+1},t}$ | $\mathcal{F}_{1,s,t}$ | $(K_{s+1,t}^{+})^{\text{sub}}$ | $K^{\text{sub}}_{s+1,t}$
---|---|---|---
$1+\frac{s}{2s+1}$ | $1+\frac{s^{2}+1}{2s+2s^{2}}$ | $1+\frac{s^{2}+1}{2s+2s^{2}}$ | $1+\frac{s}{2s+2}$

For the last two theorems, we will generalize and simplify the proofs given by
Janzer in [13]. A variant of this method by Conlon, Lee and Janzer in [5]
helped to obtain a tight upper bound for the $1$-subdivision of complete
bipartite graphs.

The real difficulty in our problems is to avoid the degeneracy when we try to
embed the 1-subdivision of a non-bipartite non-complete graph. Specifically,
suppose we want to embed $K_{1,s,t}^{\text{sub}}$ in a bipartite graph $G$ on
the bipartition $A\cup B$. We choose a vertex $x\in A$ as the embedding image
of the part of size $1$. Then we study the set of all the vertices in $A$
which share some common neighbors with $x$, what we call the blue
neighbourhood of $x$ (see more details in Section 2). Then we have to embed
$K_{s,t}^{\text{sub}}$ into the bipartite graph formed by this blue
neighbourhood and $B$. However, even if we can do this, eventually we can only
obtain certain degenerate graphs (see Figure 1). Note that we still have
overcome this difficult in one special case as in Theorem 1.7.

Below, in Section 2, we include several standard reduction lemmas. Then we
will re-organize Janzer’s method for estimating subdivision extremal numbers.
We believe this exposition could be a bit easier to use than the original
formulation. Several useful counting lemmas are also introduced. In Section 3,
we prove Theorem 1.3. The proof employs certain embedding scheme which dates
back to the method of Faudree and Simonovits first appeared in [10]. In
Section 4, we prove Theorem 1.4. In Section 5, we prove Theorem 1.7. Both are
based on the method in [5].

##  2\. Preliminary Considerations

###  2.1. Standard Reductions

Hereafter, we only consider $n$ to be a sufficiently large integer.

######  Lemma 2.1.

  1. (a)

Let $G$ be a graph with average degree $d_{G}=2e(G)/v(G)$. Then there exists a
subgraph of $G$ which is bipartite and every vertex has degree at least
$d_{G}/4$. As a direct consequence, if $d_{G}=\omega(1)$, an arbitrary tree
with some fixed number of vertices embeds into $G$.

  2. (b)

Let $G$ be a bipartite graph with vertex bipartition $A\cup B$, write
$d_{A}=e(G)/|A|$ and $d_{B}=e(G)/|B|$. Then there exists a subgraph
$G^{\prime}$ of $G$, on some bipartition $A^{\prime}\cup B^{\prime}$, where
$A^{\prime}\subset A$ and $B^{\prime}\subset B$, so that each vertex $a\in
A^{\prime}$ has degree at least $d_{A}/4$ and each vertex $b\in B^{\prime}$
has degree at least $d_{B}/4$, and $e(G^{\prime})\geq e(G)/2$.

###### Proof.

The proof of this lemma is sort of folklore. For statement (a), we can color
all vertices uniformly at random, with the choice of two colors. The expected
number of edges whose two endpoints obtain distinct colors is exactly
$e(G)/2$. Therefore, there is one realization of the coloring so that one can
keep all such edges. This gives a bipartite graph. Then we delete all the
vertices whose degree is at most $d_{G}/4$. The deleting process must end,
since each step the average degree keeps increasing. When this process ends,
the resulting graph $G^{\prime}$ satisfies all the conditions. In the
resulting graph $G^{\prime}$, in order to embed an arbitrary tree of some
fixed number of vertices, a standard greedy embedding procedure is enough.

For statement (b), alternatively for parts $A$ and $B$, we delete all the
vertices which has degree at most $d_{A}/4$ and $d_{B}/4$, respectively, until
this procedure cannot be done anymore. This process must end because the
average degree for each side is always non-decreasing and when it ends, we
have deleted at most $e(G)/2$ edges. The conclusion follows. ∎

A graph $G$ is called $K$-almost regular, if every vertex $v$ has degree in
the interval $[\delta,K\delta]$, where $\delta$ is the minimum degree of the
graph $G$. A bipartite graph with bipartition $A\cup B$ is called balanced, if
$|A|/|B|\in[1/2,2]$. We will also need the following regularity lemma.

######  Lemma 2.2.

[Lemma 2.3 in [4]] Let $\alpha<1$ be a positive constant. For $n$ sufficiently
large, consider any graph $G$ on $n$ vertices with
$e(G)=\omega(n^{1+\alpha})$. Then $G$ contains a $K$-almost regular balanced
bipartite subgraph $G^{\prime}$ with $v(G^{\prime})\to\infty$ as $n$ tends to
infinity, and $e(G^{\prime})=\omega(v(G^{\prime})^{1+\alpha})$.

With the above lemma, we usually can simply assume the host graph $G$ is
$K$-almost regular, balanced bipartite graph on the vertex bipartition $A\cup
B$, where $|B|=n$ and $|A|=\Theta(n)$, and the degree of every vertex lies in
the interval $[\delta,K\delta]$. When $e(G)=\omega(n^{1+\alpha})$, we can
further assume $\delta=\omega(n^{\alpha})$.

###  2.2. Janzer’s Embedding Scheme for Graph Subdivisions

For $v_{1},\cdots,v_{k}\in A$, let $N_{G}(v_{1},\cdots,v_{k})\subset B$ be the
common neighborhood of $v_{1},\cdots,v_{k}$ in $G$.

######  Definition 2.3.

Fix a graph $H$ with $e(H)$ edges. Suppose $G$ is a bipartite graph on the
bipartition $A\cup B$. Relative to the graph $H$, in the graph $G$, define a
colored graph $G_{c}(A)$ on vertex set $A$. A pair $(u,v)\in A\times A$ forms
a _red edge_ if $|N_{G}(u,v)|\geq e(H)$. On the other hand, a pair $(u,v)$
forms a _blue edge_ if $1\leq|N_{G}(u,v)|\leq e(H)-1$. Finally, we call
$(u,v)$ an _uncoloured edge_ , if $|N_{G}(u,v)|=0$.

Moreover, in the colored graph $G_{c}(A)$, for any $v\in A$, let
$N_{b}(v)\subset A$ denote the blue neighborhood of $v$. Also denote by
$N_{b}(v_{1},\cdots,v_{k})$ the common blue neighborhood of
$v_{1},\cdots,v_{k}\in A$ in the colored graph $G_{c}(A)$.

The following definition provides a visual description of the embedding
process.

######  Definition 2.4.

Let $H_{c}$ be a colored copy of $H$ in $G_{c}(A)$. We call $H_{c}$ proper, if
all the edges of $H_{c}$ are blue or red, and one can choose pairwise distinct
common neighbors in $B$ for it, to successfully embed a copy of
$H^{\text{sub}}$ into the graph $G$.

Therefore, the embedding of the graph $H^{\text{sub}}$ into the graph $G$
becomes a matter of finding a proper copy $H_{c}$ of $H$ in $A$.

The next lemma guarantees enough blue edges in $G_{c}(A)$.

######  Lemma 2.5.

Fix a graph $H$ and suppose a bipartite graph $G$ on the bipartition $A\cup B$
is $H^{\text{sub}}$-free with minimum degree $\delta$ for vertices in $A$. Let
$K_{0}$ be a constant which is sufficiently large. Assume
$\delta\big{|}A\big{|}/\big{|}B\big{|}\geq 2K_{0}$, then there exist at least
$\Omega(\delta^{2}|A|^{2}/|B|)$ blue edges in $A$. Consequently, there exists
at least one vertex $x\in A$ such that $|N_{b}(x)|=\Omega(\delta^{2}|A|/|B|)$.

###### Proof.

The proof is essentially the same with Lemma 10 in [13]. We provide a
descriptive proof which might be a good alternative exposition of the original
computational proof.

Since $\delta$ is the minimum degree for vertices in $A$, the total edge
number of $G$ is at least $\delta|A|$ which is at least $2K_{0}|B|$. On the
other hand, the total number of edges incident to a vertex in $B$ with degree
at most $K_{0}$, is at most $|B|K_{0}$, no more than half of the total edges.
So, we can only look at vertices in $B$ with degree at least $K_{0}$, which
provides at least half of the total edges.

On the other hand, for any vertex $v\in B$ with $N_{G}(v)\geq K_{0}$, every
pair of vertices in $N_{G}(v)$ either forms a red edge or a blue edge as $v$
is the one of the common neighbors. When $K_{0}$ is sufficiently large, we
apply Turán’s theorem for the extremal number of the complete graph
$K_{v(H)}$. Therefore, the number of red edges in $N_{G}(v)$ does not exceed
$e(T_{d_{G}(v),v(H)-1)})=(1-\varepsilon_{0}){d_{G}(v)\choose 2}$ for small
constant $\varepsilon_{0}$, because otherwise one finds a red copy $H_{c}$ of
$H$ which is proper and therefore $H^{\text{sub}}$ embeds, a contradiction.
So, there are at least $\Omega\left(d_{G}(v)^{2}\right)$ blue edges found in
$N_{G}(v)$, for any $v\in B$ with degree at least $K_{0}$. Then, this gives a
total count of

(2.1) $\displaystyle\Omega\left(\sum_{d_{G}(v)\geq K_{0},v\in
B}d_{G}(v)^{2}\right)\geq\Omega\left(\left(\sum_{d_{G}(v)\geq K_{0},v\in
B}d_{G}(v)\right)^{2}/|B|\right)\geq\Omega\left(\delta^{2}|A|^{2}/|B|\right),$

where the sum is over all $v\in B$ with degree at least $K_{0}$. Note the
first estimate is by Cauchy-Schwarz inequality.

Since each blue edge can be counted for at most $e(H)-1$ times, because it
corresponds to at most $e(H)-1$ vertices in $B$, there are
$\Omega\left(\delta^{2}|A|^{2}/|B|\right)$ blue edges in $G_{c}(A)$. ∎

We summarize one more idea from [13] as a proposition below. It is usually
used to embed an arbitrarily large number of vertices in the final stage of
the embedding. For a fixed graph $H$ and a constant integer $t$, let $K_{H,t}$
denote the graph formed by a copy of $H$ and an independent vertex set $T$
with $|T|=t$, where each pair $(h,t)\in H\times T$ joins an edge. Below red
edges and blue edges in $G_{c}(A)$ are defined with respect to the graph
$K_{H,t}$.

######  Proposition 2.6.

[See Theorem 4 of [13]] Suppose now the bipartite graph $G$ as in the previous
lemma is $K$-almost regular with minimum degree $\delta$. Suppose in the
colored graph $G_{c}(A)$ there is a proper blue copy of $H$, with vertex set
$V$. Assume that every pair of vertices in $V$ forms a non-red edge, and the
common blue neighborhood $N_{b}(V)$ has size $\omega(\delta)$. Then, we can
find $t$ vertices $z_{1},\cdots,z_{t}\in N_{b}(V)$, which together with $V$
form a proper blue copy of $K_{H,t}$ in $G_{c}(A)$.

###### Proof.

Suppose $|V|=s$, $Z=N_{b}(V)$ and write $V=\\{y_{1},\cdots,y_{s}\\}\subset A$
which is a non-red $s$-clique in $G_{c}(A)$, i.e., for any pair
$(y_{i},y_{j})$, $|N_{G}(y_{i},y_{j})|\leq e(K_{H,t})-1$. Then we observe the
union

(2.2) $B^{\prime}:=\bigcup_{1\leq i<j\leq s}N_{G}(y_{i},y_{j}),$

which has size at most ${s\choose 2}\times(e(K_{H,t})-1)$. It follows that the
total number of vertices in $Z$ which joins some vertex in $B$ is at most
$O(\delta)$, because $G$ is $K$-almost regular. Therefore, we can delete these
vertices from $Z$ and obtain $Z_{1}$ which still has size $\omega(\delta)$.
For any $z_{1}\in Z_{1}$, the neighborhood $N_{G}(z_{1})$ does not intersect
$B^{\prime}$. It follows that the graph obtained by the embedded $H$ with
added edges between $z_{1}$ and every vertex $y_{i}\in V$, is proper. In fact,
if it is not proper, it means for some choices of two vertices $y_{i}$ and
$y_{j}$, the pairs $(z_{1},y_{i})$ and $(z_{1},y_{j})$ must have some common
neighbour, say $b$. It implies $b$ belongs to $B^{\prime}$, which is a
contradiction.

In other words, we have found a proper blue copy of $K_{H,1}$ in $G_{c}(A)$.
Inductively, we can repeat the above argument until we have embedded $t$
vertices $z_{1},\cdots,z_{t}$, which means we can find a proper blue copy of
$K_{H,t}$. ∎

###  2.3. Several Counting Lemmas

Recall $G$ is a bipartite graph on the bipartition $A\cup B$, which is
$K$-almost balanced and regular. With respect to some fixed graph, we form the
colored graph $G_{c}(A)$ as in the Definition 2.3. In this context, we will
often need to count the total number of copies of proper blue $K_{s,1}$’s in a
certain subset of the colored graph $G_{c}(A)$. This is done in the following
general lemma. We write $K_{u_{1},\cdots,u_{s}}^{x}$ to denote a copy of
$s$-star centered at $x$.

The following lemma can be used to simplify a little the argument used in [5]
to show the upper bound of the extremal number of $1$-subdivision of complete
bipartite graphs.

######  Lemma 2.7.

Suppose in the colored graph $G_{c}(A)$, there is a vertex $y\in A$ and a
subset of its blue neighborhood $Y\subset N_{b}(y)$, with
$|Y|=\omega(\delta)$. Then the number of blue proper $s$-stars centered at $y$
whose leaves are all contained in $Y$ is $\Omega(|Y|^{s})$.

###### Proof.

We can list $N_{G}(y)=\\{b_{1},\cdots,b_{k}\\}$. Then we define
$W_{i}:=N_{G}(b_{i})\cap Y$ for each $1\leq i\leq k$. For simplicity, we
discard empty sets among this list, re-name the non-empty sets of them and
still call them $W_{i}$. Since each blue neighbor of $y$ shares at least one
common neighbor with $y$ in $B$, it belongs to some $N_{G}(b_{i})$. We have
$Y=\bigcup_{i=1}^{k}W_{i}$.

We claim that there exists a disjoint union $Y=\bigcup_{i=1}^{\ell}P_{i}$,
where each $|P_{i}|=\Theta(\delta)$, and $\ell=\Theta(|Y|/\delta)$, such that,
if $u_{1},u_{2},\cdots,u_{s}$ belong to $s$ distinct sets
$P_{i_{1}},P_{i_{2}},\cdots,P_{i_{s}}$, respectively, then the copy of
$s$-star, namely $K^{y}_{u_{1},\cdots,u_{s}}$, is proper.

To show the claim, we first update the sets by redefining $W_{1}=W_{1}$ and
$W_{i}=W_{i}\setminus\left(\bigcup_{j=1}^{i-1}W_{j}\right)$ for
$i=2,\cdots,k$. Then the disjoint union $Y=\bigcup_{i=1}^{k}W_{i}$ is a
partition of $Y$ with each part having size at most $K\delta$, since $G$ is
$K$-almost regular. Note every vertex $w_{i}\in W_{i}$ has the property that
it shares with $y$ some common neighbor which is not a common neighbor of $y$
and some vertex $w\in W_{i^{\prime}}$ for $i^{\prime}<i$. Then, we can find an
index $i_{1}$, such that the union $P_{1}=\bigcup_{j=1}^{i_{1}}W_{j}$ has size
$[\frac{1}{2}K\delta,\frac{3}{2}K\delta]$. Suppose for induction hypothesis
that we have found a union $\bigcup_{j=1}^{t}P_{j}$, where
$P_{j}=\bigcup_{i=i_{j-1}+1}^{i_{j}}W_{i}$ for some sequence $1\leq
i_{1}<\cdots<i_{t}<k$, and each $P_{j}$ has size
$|P_{j}|\in[\frac{1}{2}K\delta,\frac{3}{2}K\delta]$. If
$|Y\backslash\left(\bigcup_{j=1}^{t}P_{j}\right)|\leq\frac{1}{2}K\delta$, we
include it into $P_{t}$, and define $\ell=t$ to terminate the process. If not,
we can find $i_{t+1}<k$ such that $P_{t+1}=\bigcup_{j=i_{t}+1}^{i_{t+1}}W_{j}$
has size $[\frac{1}{2}K\delta,\frac{3}{2}K\delta]$. The process terminates
since there are only finitely many vertices to consider. Then we see
$|P_{i}|\in[\frac{1}{2}K\delta,2K\delta]$ is true for every $i$, and the claim
follows. Clearly $\ell=\Theta(|Y|/\delta)$.

Now we have ${\ell\choose s}$ ways to choose $s$ distinct $P_{i}$’s in the
above list. Then in each of these $P_{i}$’s, we have $\Theta(\delta)$ ways to
choose an arbitrary vertex. This gives a proper $s$-star. It follows the
number of such proper blue $s$-stars is at least
$\Omega\big{(}{|Y|/\delta\choose s}\times\delta^{s}\big{)}$, which is
$\Omega(|Y|^{s})$, and the proof is concluded. ∎

######  Proposition 2.8.

[cf. Corollary 4.6 in [5]] Suppose for some fixed integer $n_{0}$, the colored
graph $G_{c}(A)$ does not contain any red copy of $n_{0}$-clique. Suppose
$A^{\prime}\subset A$ has size $|A^{\prime}|=\omega(1)$, then the number of
$s$-tuples $\\{y_{1},\cdots,y_{s}\\}\subset A^{\prime}$ which form a non-red
clique in $A$ is at least $\Omega(|A^{\prime}|^{s})$.

###### Proof.

Recall the Ramsey number $R(n_{0},s)$ is defined as the smallest integer
$n^{\ast}$ such that any red-blue colored graph on $n\geq n^{\ast}$ vertices
must contain either a red $n_{0}$-clique or a non-red $s$-clique. $R(n_{0},s)$
is a large constant only depending on $n_{0}$ and $s$ (see [12]). Since
$A^{\prime}\subset A$ does not contain a red $n_{0}$-clique, it follows that
each subset of $A^{\prime}$ with size $R(n_{0},s)$ contains a copy of non-red
$s$-clique. Note also that each non-red $s$-clique is contained in
${|A^{\prime}|-s\choose R(n_{0},s)-s}$ distinct $R(n_{0},s)$-subsets of
$A^{\prime}$. So we find a family $\mathcal{A}$ consisting of such non-red
$s$-cliques, and

(2.3) $|\mathcal{A}|\geq{|A^{\prime}|\choose
R(n_{0},s)}\Big{/}{|A^{\prime}|-s\choose
R(n_{0},s)-s}=\Omega(|A^{\prime}|^{s}).$

The proof is completed. ∎

##  3\. Proof of Theorem 1.3

In this section we prove Theorem 1.3. The main idea of the embedding process
is to deal with $C_{k}^{\text{sub}}=C_{2k}$ first, and then consider the third
part with one vertex.

The proof is based on a sort of old method of Faudree and Simnovits, firstly
appeared in [10]. The method was originally used to show upper bound for the
theta graphs. But it observes a sort of revival very recently, see for example
in [16], Liu and Yang used this method to obtain upper bound for generalized
theta graphs. Also, in [14], Jiang, Ma and Yepremyan also use this method to
obtain upper bound for a certain graph, which implies $7/5$ is a new Turán
exponent.

Now we state one result from [17], which is the extremal number of even cycles
for bipartite graphs with non-equal parts.

######  Lemma 3.1.

([17]) For $m\leq n$ and $k\geq 2$,

(3.1) $z(m,n,C_{2k})=\begin{cases}(2k-3)[(mn)^{\frac{k+1}{2k}}+m+n]&\mbox{if k
is odd,}\\\ (2k-3)[m^{\frac{k+2}{2k}}n^{\frac{1}{2}}+m+n]&\mbox{if k is
even,}\\\ \end{cases}$

where the asymmetric bipartite Turán number $z(m,n,H)$ is the maximum number
of edges in an $m$ by $n$ bipartite graph that is $H$-free.

###### Proof of the lower bound of Theorem 1.3. .

For lower bounds, note that the graph $K_{C_{k},1}^{\text{sub}}$ contains
copies of $C_{6}$, whose extremal number has order
$\text{ex}(n,C_{6})=\Theta(n^{4/3})$. Therefore, we have
$\text{ex}(n,K_{C_{k},1}^{\text{sub}})=\Omega(n^{4/3})$. ∎

Proof of the upper bound of Theorem 1.3. Let $k\geq 4$ be fixed. Assume the
graph $G^{\prime}$ on $n^{\prime}$ vertices is
$K_{C_{k},1}^{\text{sub}}$-free, and has $\omega(n^{\prime 4/3})$ edges. In
fact, we can reduce to the following situation with the help of Lemma 2.2. We
find a subgraph $G\subset G^{\prime}$ on $n$ vertices which is bipartite and
$K$-almost regular. $G$ is also $K_{C_{k},1}^{\text{sub}}$-free and it has the
following minimal degree condition.

(3.2) $\delta=\delta(G)=\omega(n^{1/3})$

Under these assumptions, we fix a starting vertex $r$ which we call the root.
Then for $i=0,1,2,3$, we define $L_{i}$ to be the set of vertices at distance
$i$ with $r$ in $G$. Therefore, $L_{0}=\\{r\\}$ and $|L_{1}|=\Theta(\delta)$.
The following simple observation is crucial.

######  Lemma 3.2.

Suppose in the bipartite subgraph $G[L_{1}\cup L_{2}]$, every vertex in
$L_{2}$ has at least $d$ neighbors in $L_{1}$, where $d$ is of order
$\omega(1)$. Suppose one can embed a copy of $C_{2k}$ into the bipartite
subgraph $G[L_{1}\cup L_{2}]$. Then, one can also embed
$K_{C_{k},1}^{\text{sub}}$ into $G$.

###### Proof.

By assumption, one can embed a copy of $C_{2k}$ into $G[L_{1}\cup L_{2}]$.
Note for each of the four vertices in this embedded image in $L_{2}$, it has
at least $q=q(n)$ neighbors in $L_{1}$. So, greedily, each of them, we can
choose a new vertex in $L_{1}$, which avoids all the previously used vertices
including the embedded image of $C_{2k}$. Therefore it connects to the root
$r$ via a distinct path of length $2$. This procedure eventually gives an
embedding of $K_{C_{k},1}^{\text{sub}}$ into $G$. ∎

######  Proposition 3.3.

(3.3) $|L_{2}|=\Theta(\delta^{2}).$

###### Proof.

Clearly $|L_{2}|=O(\delta^{2})$. Now suppose for contradiction that
$|L_{2}|=o(\delta^{2})$. Then we consider the induced bipartite graph
$H=G[L_{1}\cup L_{2}]$ on the bipartition $L_{1}\cup L_{2}$. We see that
$e(H)=\Theta(\delta^{2})$. Let $d_{L_{1}}=e(H)/|L_{1}|=\Theta(\delta)$ and
$d_{L_{2}}=e(H)/|L_{2}|=\omega(1)$. Applying Lemma 2.1 (b), we can find a
subgraph $H^{\prime}$ so that, for each remaining vertex $v\in L_{1}$, it has
$d_{L_{1}}/4$ neighbors in $L_{2}$, and for any remaining $w\in L_{2}$, it has
at least $d_{L_{2}}/4$ neighbors in $L_{1}$. We can modify $G$ such that
$G[L_{1}\cup L_{2}]=H^{\prime}$ and still call it $G$. Note that we still have
$|L_{1}|=\Theta(\delta)$.

By Lemma 3.2, we only need to show the graph $C_{2k}$ embeds in $G[L_{1}\cup
L_{2}]$ to get a contradiction with our assumption that the graph $G$ is
$K_{C_{k},1}^{\text{sub}}$-free.

Now we start with a vertex $x_{1}\in L_{1}$. In $G[L_{1}\cup L_{2}]$, we call
$U_{1}\subset L_{2}$ and $U_{2}\subset L_{1}\setminus\\{x_{1}\\}$ the set of
vertices which are at distance $1$ and $2$ with $x_{1}$, respectively. Then
clearly $|U_{1}|=\Theta(\delta)$. Moreover, $|U_{2}|=\Theta(\delta)$, because
$U_{2}$ is a subset of $L_{1}$. But since every vertex in $U_{1}$ has degree
$\Omega(d_{L_{2}})$, we see the average degree of the graph $G[U_{1}\cup
U_{2}]$ is at least $\Omega(d_{L_{2}})$. So by Lemma 2.1, the path $P_{2k-2}$
can be embedded into $G[U_{1}\cup U_{2}]$, together with $x_{1}$, which gives
an embedding of $C_{2k}$ into $G[L_{1}\cup L_{2}]$. Then we get a
contradiction, since Lemma 3.2 implies $K_{C_{k},1}^{\text{sub}}$ embeds. So
we have $|L_{2}|=\Theta(\delta^{2})$. ∎

In this context, we need the following technical lemma about extracting a
tree, which will be useful later. The proof is the same with Lemma 2.2 in
[16].

######  Definition 3.4.

Let $G$ be a bipartite graph on $n$ vertices and let
$d_{1}=d_{1}(n),d_{2}=d_{2}(n)$ be of order $\omega(1)$. Fix a vertex $r$. Let
$L_{1}$ and $L_{2}$ be the sets of vertices in $G$ which are at distance $1$
and $2$ to $r$, respectively. Suppose
$|L_{1}|=\Theta(d_{1}),|L_{2}|=\Theta(d_{1}d_{2})$, and every vertex $v\in
L_{1}$ has degree $d_{G}(v)=\Theta(d_{2})$. Then we define an essentially
regular tree $T\subset G[\\{r\\}\cup L_{1}\cup L_{2}]$ as a subgraph of $G$,
with vertex set $V(T)=\\{r\\}\cup T_{1}\cup T_{2}$, where $T_{1}\subset L_{1}$
and $T_{2}\subset L_{2}$, so that the following hold.

  1. (1)

$r$ is the root.

  2. (2)

The vertex set $T_{1}$ is called children of $r$, and it has size
$\Theta(d_{1})$.

  3. (3)

For each vertex $v\in T_{1}$, it has $\Theta(d_{2})$ children in $T_{2}$.

######  Lemma 3.5.

Let $G$ be a bipartite graph on $n$ vertices and let
$d_{1}=d_{1}(n),d_{2}=d_{2}(n)$ be of order $\omega(1)$. Fix a vertex $r$. Let
$L_{1}$ and $L_{2}$ be the sets of vertices in $G$ which are at distance $1$
and $2$ to $r$, respectively. Suppose
$|L_{1}|=\Theta(d_{1}),|L_{2}|=\Theta(d_{1}d_{2})$, and every vertex $v\in
L_{1}$ has degree $d_{G}(v)=\Theta(d_{2})$. Then we can extract an essentially
regular tree $T\subset G[\\{r\\}\cup L_{1}\cup L_{2}]$.

######  Proposition 3.6.

(3.4) $|L_{3}|=\Theta(\delta^{3}).$

###### Proof.

By the degree condition, clearly, $|L_{3}|=O(\delta^{3})$. Assume for
contradiction that $|L_{3}|=o(\delta^{3})$.

Recall our standing assumption that $G$ is $K_{C_{k},1}^{\text{sub}}$-free and
every vertex has degree of order $\Theta(\delta)$. By Proposition 3.3, we know
$|L_{2}|=\Theta(\delta^{2})$. Now we consider the subset $B\subset L_{2}$ in
which every vertex has $\Theta(\delta)$ neighbors in $L_{1}$. Since the total
number of edges between $L_{1}$ and $L_{2}$ is $\Theta(\delta^{2})$, it
follows that $|B|=O(\delta)=o(\delta^{2})$. Let $A\subset L_{1}$ be a subset
in which every vertex $v\in A$ has degree $o(\delta)$ in $L_{2}\setminus B$.
That is, any vertex $v\in L_{1}\setminus A$ has degree $\Theta(\delta)$ in
$L_{2}\setminus B$. Since in $G[L_{1}\cup(L_{2}\setminus B)]$, there are
$\Theta(\delta^{2})$ edges, we can see that in $G[(L_{1}\setminus
A)\cup(L_{2}\setminus B)]$ there are still $\Theta(\delta^{2})$ edges and
hence $|L_{1}\setminus A|=\Theta(\delta)$. Then we can update
$L_{1}=L_{1}\setminus A$ and $L_{2}=L_{2}\setminus B$, which still have sizes
$\Theta(\delta)$ and $\Theta(\delta^{2})$, respectively. Now we use Lemma 3.5
to obtain an essentially regular tree. After the reduction (which we still
call $G$), the induced subgraph $G[\\{r\\}\cup L_{1}\cup L_{2}]$ is an
essentially regular tree. Note that now every vertex $w\in L_{2}$ has
$\Theta(\delta)$ neighbors in $L_{3}$, as $w$ has only $o(\delta)$ neighbors
in $L_{1}$ after updating $L_{2}$.

To sum up, we have cleaned the graph $G$, so that the following properties are
satisfied.

  1. (1)

$G[\\{r\\}\cup L_{1}\cup L_{2}]$ is a tree.

  2. (2)

$|L_{1}|=\Theta(\delta)$. For each $v\in L_{1}$, it has degree
$\Theta(\delta)$ in $L_{2}$. Let $Q_{v}\subset L_{2}$ denote the set of
children of $v$. These $Q_{v}$’s form a partition of $L_{2}$.

  3. (3)

Every vertex $w\in L_{2}$ has $\Theta(\delta)$ neighbors in $L_{3}$.

Now we take a vertex $v_{1}\in L_{1}$, and consider the sets $U_{1}^{v}\subset
L_{2}$ and $U_{2}^{v}\subset L_{3}$, which are the sets of vertices that are
at distance $1$ and $2$ with $v_{1}$, respectively. By previous properties, we
see $G[U_{1}^{v}\cup U_{2}^{v}]$ has an edge number of order
$\Theta(\delta^{2})$. By Proposition 3.3, regarding $v_{1}$ as the root this
time, we conclude that $|U_{2}^{v}|=\Theta(\delta^{2})$. Then we apply Lemma
3.5 to extract a tree structure from $G[\\{v_{1}\\}\cup U_{1}^{v}\cup
U_{2}^{v}]$ via deleting some vertices and edges. Note that after the
deletion, $v_{1}$ still has $\Theta(\delta)$ children in $U_{1}^{v}$ and
$G[U_{1}^{v}\cup U_{2}^{v}]$ has edges of order $\Theta(\delta^{2})$. In fact
the above procedure can be done for every vertex $v\in L_{1}$. We still call
the resulting graph $G$, and update $L_{2}$, $L_{3}$ as the set of vertices
left after the above deletion process, respectively. The graph $G$ now
satisfies that $G[\\{r\\}\cup L_{1}\cup L_{2}]$ is an essentially regular tree
rooted at $r$. For each $v\in L_{1}$, $G[\\{v\\}\cup U_{1}^{v}\cup U_{2}^{v}]$
is also an essentially regular tree rooted at $v$.

Consequently, $G$ satisfies the following nice properties.

  1. (1)

The total number of edges in $G[L_{2}\cup L_{3}]$ is of order
$\Theta(\delta^{3})$.

  2. (2)

For each vertex $w\in L_{3}$, all its neighbors in $L_{2}$ belong to the
children sets of pairwise distinct vertices in $L_{1}$.

Now recall our assumption that $|L_{3}|=o(\delta^{3})$ (this order can not be
increased after all the deletion we have done). Applying Lemma 3.1, let one
part have size $a=|L_{2}|=\Theta(\delta^{2})$ and the other part have size
$b=|L_{3}|=o(\delta^{3})$. Take $k\geq 4$. If $b=O(\delta^{2})$, the
asymmetric bipartite Turán number has an upper bound
$O(\delta^{2+\frac{2}{k}})+O(\delta^{2})=o(\delta^{3})$. If
$b=\omega(\delta^{2})$, then $a$ is the smaller part and
$a+b=O(b)=o(\delta^{3})$. Since $(ab)^{\frac{k+1}{2k}}$ and
$a^{\frac{k+2}{2k}}b^{\frac{1}{2}}$ are bounded by $o(\delta^{3})$, we have

(3.5) $\displaystyle
z(a,b,C_{2k})=O\left((ab)^{\frac{k+1}{2k}}+a^{\frac{k+2}{2k}}b^{\frac{1}{2}}\right)+O\left(a+b\right)=o(\delta^{3}).$

In both cases, the asymmetric bipartite Turán number has order
$o(\delta^{3})$. Then one can embed a copy of $C_{2k}$ in $G[L_{2}\cup L_{3}]$
since it has $\Theta(\delta^{3})$ edges.

In fact, we need a stronger statement as follows. We need to ensure that one
can embed $C_{2k}$ in such a way so that in the embedded image, the $k$
vertices in $L_{2}$ belong to $k$ distinct children set of vertices in
$L_{1}$. When directly applying Lemma 3.1, it does not give this, but one can
check the following. In the original proof of Lemma 3.1, we keep in mind our
condition that each vertex $w\in L_{3}$ has its neighbours in $L_{2}$ belong
to the children set of distinct vertices in $L_{1}$. Therefore, every time
when we are embedding a tree greedily into $G[L_{2}\cup L_{3}]$, and at each
step when we embed one vertex into $L_{2}$, we can always avoid certain
forbidden parts. The full details will be mostly a repetition of the original
proof, and are therefore omitted (see also Lemma 3.5 of [16]).

Thus, with this embedded image of $C_{2k}$, one can trace back to the root $r$
in order to give an embedding of $K_{C_{k},1}^{\text{sub}}$ which is a
contradiction to the assumption. This concludes the proof of the proposition.
∎

End of proof of the upper bound for Theorem 1.3. Recall that we have assumed
that $\delta=\omega(n^{1/3})$. By Proposition 3.6, we see
$|L_{3}|=\Theta(\delta^{3})=\omega(n)$, which is a contradiction, since $n$ is
the total number of vertices in the graph $G$. The proof of Theorem 1.3 is
finished.

##  4\. The family Formulation

In this section we prove Theorem 1.4.

Fix $s\geq 3$. Noticing Lemma 2.2, we can assume that the host graph $G$ is
bipartite on $A\cup B$, $K$-almost regular, balanced, $\mathcal{F}$-free, and
minimum degree satisfying

(4.1) $\delta=\omega(n^{(s^{2}+1)/(2s+2s^{2})}).$

We will apply Lemma 2.5 twice. Firstly, there exists a vertex $x$ whose blue
neighborhood $A_{1}$ has size $|A_{1}|=\Theta(\delta^{2})$, where the lower
bound follows from Lemma 2.5 and the upper bound follows from the fact that
$G$ is $K$-almost regular. Then for the bipartite graph on the bipartition
$A_{1}\cup B$, the average degree condition for $A_{1}$ is again satisfied
since $\delta|A_{1}|/|B|=\Omega(\delta^{3}/n)=\omega(1)$. Applying Lemma 2.5
again, it follows that the number of blue edges with vertices inside $A_{1}$
is $\Omega(\delta^{6}/n)$.

The condition that $G$ is $\mathcal{F}_{1,s,t}$-free implies that in
$G_{c}(A_{1})$ there is no proper copy of $K_{s,t}$, with the color of each
edge either red or blue. For any $u_{1},\cdots,u_{s}\in A_{1}$, we write

(4.2) $P_{u_{1},\cdots,u_{s}}(A_{1}):=\\{y\in
A_{1}\big{|}K_{u_{1},\cdots,u_{s}}^{y}\text{ is a proper blue star}\\}.$

In other words, $|P_{u_{1},\cdots,u_{s}}(A_{1})|$ counts the number of proper
blue $s$-stars associated to a certain fixed $s$-tuple in $A_{1}$.

######  Lemma 4.1.

(4.3) $\sum_{u_{1},\cdots,u_{s}\in
A_{1}}|P_{u_{1},\cdots,u_{s}}(A_{1})|=\Omega(\delta^{4s+2}/n^{s}).$

###### Proof.

Recall the number of blue edges with vertices in $A_{1}$ is
$\Omega(\delta^{6}/n)$. We use $d_{b}^{A_{1}}(y)=|N_{b}(y)\cap A_{1}|$ to
denote the number of blue neighbors of $y$ in $A_{1}$. So we have

(4.4) $\sum_{y\in A_{1}}d_{b}^{A_{1}}(y)=\Omega(\delta^{6}/n),$

Choose a small constant $\varepsilon$, and consider only vertices
$y_{1},\cdots,y_{\ell}\in A_{1}$, so that each of them has at least
$\varepsilon\delta^{4}/n$ blue neighbors in $A_{1}$. Since
$|A_{1}|=\Theta(\delta^{2})$, if $\varepsilon$ is sufficiently small, the
vertices whose degrees smaller than $\varepsilon_{0}\delta^{4}/n$ only
contribute $o(\delta^{6}/n)$ blue edges. Therefore by ignoring these items, we
see

(4.5) $\sum_{i=1}^{\ell}d_{b}^{A_{1}}(y_{i})=\Omega(\delta^{6}/n).$

Since $d_{b}^{A_{1}}(y_{i})\geq\varepsilon_{0}\delta^{4}/n=\omega(\delta)$ for
each $i=1,\cdots,\ell$, by Lemma 2.7, each $y_{i}$ is the center of at least
$\Omega\big{(}(d_{b}^{A_{1}}(y_{i}))^{s}\big{)}$ copies of proper blue
$s$-stars in $A_{1}$. By Jensen’s inequality, it follows that, the total
number of proper blue $s$-stars is at least

(4.6)
$\Omega\Big{(}\sum_{i=1}^{\ell}d_{b}^{A_{1}}(y_{i})^{s}\Big{)}\geq\Omega\Big{(}\ell\times(\frac{1}{\ell}\sum_{i=1}^{\ell}d_{b}^{A_{1}}(y_{i}))^{s}\Big{)}=\Omega(\delta^{4s+2}/n^{s}),$

where we also observed that $\ell\leq|A_{1}|=O(\delta^{2})$. The proof is
completed. ∎

Observing in the context of Proposition 2.6, if we find a non-red $s$-clique
in $A_{1}$, whose common blue neighborhood inside $A_{1}$ has size
$\omega(\delta)$, then we can find a proper copy of $K_{s,t}$ in
$G_{c}(A_{1})$ for any large constant $t$. In particular, this implies that
$G$ has a copty of $\mathcal{F}_{1,s,t}$, which is a contradiction with the
assumption. Indeed, the proof of Theorem 1.4 reduces to the following
proposition.

######  Proposition 4.2.

Suppose that $A_{1}$ is the blue neighborhood of $x\in A$. There exist
distinct vertices $v_{1},\cdots,v_{s}\in A_{1}$ satisfying the following
properties.

  1. (1)

each pair $(v_{i},v_{j})$ with $1\leq i<j\leq s$ is a non-red edge in
$G_{c}(A_{1})$.

  2. (2)

the number of vertices $z\in A_{1}$ which makes $K_{v_{1},\cdots,v_{s}}^{z}$ a
blue star is of order $\omega(\delta)$.

###### Proof.

Recall that $|A_{1}|=\Theta(\delta^{2})$. By Lemma 4.1, the number of blue and
proper $s$-stars in $G_{c}(A_{1})$ is
$\Omega\big{(}\delta^{4s+2}/n^{s}\big{)}$, and it is written as a sum
$\sum_{u_{1},\cdots,u_{s}\in A_{1}}|P_{u_{1},\cdots,u_{s}}(A_{1})|$. In this
sum, we can ignore some terms which are too small. More precisely, let us take
a sufficiently large constant $K_{0}$, to be determined later, and delete from
the above sum the $s$-tuples $(u_{1},\cdots,u_{s})$ for which
$|P_{u_{1},\cdots,u_{s}}(A_{1})|<K_{0}$. Note by doing so, the total number of
blue proper $s$-stars that were not counted is at most
$O(\delta^{2s})=o(\delta^{4s+2}/n^{s})$. Let $U$ be the collection of
$s$-tuples in $A_{1}$ with $|P_{u_{1},\cdots,u_{s}}(A_{1})|\geq K_{0}$. It
follows that summing only over $u_{1},\cdots,u_{s}$ for which
$|P_{u_{1},\cdots,u_{s}}(A_{1})|\geq K_{0}$, we still have the total sum to be
equal to $\Omega(\delta^{4s+2}/n^{s})$.

Now we look at one fixed $s$-tuple $(u_{1},\cdots,u_{s})\in U$. Since $G$ is
$\mathcal{F}_{1,s,t}$-free, there exists no proper $K_{s,t}$ in
$G_{c}(A_{1})$. So we can find a maximal subset $Y=\\{y_{1},\cdots,y_{p}\\}$
in $P_{u_{1},\cdots,u_{s}}(A_{1})$ with $|Y|=p<t$, such that the copy of
colored complete bipartite graph $K_{s,p}$, which is formed by the vertex sets
$\\{u_{1},\cdots,u_{s}\\}$, $\\{y_{1},\cdots,y_{p}\\}$ and all blue edges
between them, is proper. Therefore, for any $y\in
P_{u_{1},\cdots,u_{s}}(A_{1})\backslash Y$, it must share a common neighbor
with some pair of vertices $(u_{i},y_{j})$ from the above list. Therefore, by
pigeonhole principle, there exists a set $X\subset
P_{u_{1},\cdots,u_{s}}(A_{1})$, of size
$(|P_{u_{1},\cdots,u_{s}}(A_{1})|-p)/sp=\Omega(|P_{u_{1},\cdots,u_{s}}(A_{1})|)$,
and one $u_{k}$ for some $1\leq k\leq s$, and some $b\in B$, such that
$X\cup\\{u_{k}\\}\subset N_{G}(b)$.

Note again that the existence of a red $(s+t)$-clique in $A_{1}$ would
contradict the assumption that $G$ is $\mathcal{F}_{1,s,t}$-free. Thus, we
apply Proposition 2.8 by taking $n_{0}=s+t$, and $A^{\prime}=X$. It follows
the total number of non-red $s$-cliques is at least $\Omega(|X|^{s})$, which
is at least $\frac{1}{C_{0}}|P_{u_{1},\cdots,u_{s}}(A_{1})|^{s}$, by
specifying some constant $C_{0}>0$.

Now we decide to choose the constant $K_{0}$ to be much larger than $C_{0}$.
Then for each $s$-tuple $(u_{1},\cdots,u_{s})\in U$, we can obtain
$\frac{1}{C_{0}}|P_{u_{1},\cdots,u_{s}}(A_{1})|^{s}$ many $s$-tuples, each of
which, written down as $(v_{1},\cdots,v_{s})$, forms a non-red clique in
$G_{c}(A_{1})$, which is Condition (1) in this proposition. Caution that each
edge in this clique has color blue or is uncolored. It can be the case that
this $s$-clique has no blue edges. Also, they satisfy that each $v_{i}$ is a
blue neighbour of every $u_{j}$ for $j=1,\cdots,s$. Furthermore, for the
vertex $b\in B$ and $u_{k}$ with $1\leq k\leq s$ fixed earlier, one has
$\\{v_{1},\cdots,v_{s}\\}\cup\\{u_{k}\\}\subset N_{G}(b)$. Then we make the
following estimate. The total number of such $2s$-tuples
$\\{u_{1},\cdots,u_{s},v_{1},\cdots,v_{s}\\}$ is at least

$\displaystyle\Omega\big{(}\sum_{U}|P_{u_{1},\cdots,u_{s}}(A_{1})|^{s}\big{)}$
$\displaystyle\geq\Omega\big{(}|U|\times\big{(}\frac{1}{|U|}\sum_{U}|P_{u_{1},\cdots,u_{s}}(A_{1})|\big{)}^{s}\big{)}$
$\displaystyle\geq\Omega\big{(}(\delta^{4s+2}/n^{s})^{s}/(\delta^{2s})^{s-1})=\Omega(\delta^{2s^{2}+4s}/n^{s^{2}}\big{)}.$

Here we have used Jensen’s inequality.

Next we do a double counting. First we can choose one position $k$ in $s$
ways. Then we can choose $b\in B$ in at most $n$ ways. Next, we can choose the
values of the coordinates $v_{1},\cdots,v_{s},u_{k}$ in $O(\delta^{s+1})$
ways, because they all are neighbors of the chosen vertex $b$. So we obtain
$O(n\delta^{s+1})$ ways to choose so far.

The degree condition $\delta=\omega(n^{(s^{2}+1)/(2s+2s^{2})})$ implies that

(4.7) $\delta^{2s^{2}+4s}/n^{s^{2}}=\omega(\delta^{s-1}n\delta^{s+1}).$

Therefore, for some choice of $k,v_{1},\cdots,v_{s},u_{k}$ as above, there are
at least $\omega(\delta^{s-1})$ ways to choose more coordinates, resulting in
a $2s$-tuple satisfying all these conditions described as above. Since there
are exactly $(s-1)$-coordinates to be decided, we conclude that there are at
least $\omega(\delta)$ distinct vertices showing up in these coordinates.
Therefore, the conclusion of the proposition follows. Hence the proof of
Theorem 1.4 is also completed by applying Proposition 2.6. ∎

##  5\. $K_{s+1,t}^{+}$ subdivision

In this section we prove Theorem 1.7. Now again, assume $G$ is a $K$-almost
regular balanced bipartite graph on the bipartition $A\cup B$, and
$(K_{s+1,t}^{+})^{\text{sub}}$-free. Also assume the minimum degree

(5.1) $\delta=\omega(n^{(s^{2}+1)/(2s+2s^{2})}).$

We fix a vertex $x\in A$ and its blue neighborhood $A_{1}=N_{b}(x)$. As in the
previous section, we will apply Lemma 2.5 twice. With $G$ being
$(K_{s+1,t}^{+})^{\text{sub}}$-free, Lemma 2.5 implies that
$|A_{1}|=\Theta(\delta^{2})$. Applying Lemma 2.5 again, we can conclude that
$G_{c}(A_{1})$ contains $\Omega(\delta^{6}/n)$ blue edges. The following lemma
gives the correct order for blue and proper $s$-stars
$K^{y}_{u_{1},\cdots,u_{s}}$ in $G_{c}(A_{1})$ which also satisfy that
$K^{x}_{u_{1},\cdots,u_{s}}$ is blue and proper. Note since this time we
requires more conditions to be satisfied, the proof of the following lemma is
a variant of the combination of the proof of Lemma 2.7 and Lemma 4.1.

######  Lemma 5.1.

Define $\mathcal{P}$ to be the family of $(s+1)$-tuples, consisting of
$(y,u_{1},\cdots,u_{s})\in A_{1}^{s+1}$ with the following properties.

  1. (i)

$K^{y}_{u_{1},\cdots.u_{s}}$ is a blue and proper $s$-star.

  2. (ii)

$K^{x}_{u_{1},\cdots,u_{s}}$ is a blue and proper $s$-star.

Then $|\mathcal{P}|=\Omega(\delta^{4s+2}/n^{s})$.

###### Proof.

Recall $\delta=\omega(n^{\frac{s^{2}+1}{2s+2s^{2}}})$. Let
$d_{b}^{A_{1}}(y)=|N_{b}(y)\cap A_{1}|$ denote the size of the blue
neighborhood of $y$ in $G_{c}(A_{1})$. We know the number of blue edges in
$G_{c}(A_{1})$ can be expressed as $\sum_{y\in
A_{1}}d_{b}^{A_{1}}(y)=\Omega(\delta^{6}/n)$. Since
$|A_{1}|=\Theta(\delta^{2})$, by ignoring vertices in $A_{1}$ whose blue
neighborhood in $G_{c}(A_{1})$ is $o(\delta^{4}/n)$, only at most
$o(\delta^{6}/n)$ blue edges are ignored. Therefore, for some small constant
$\varepsilon$, we write

(5.2) $I=\\{y\in A_{1}\big{|}d_{b}^{A_{1}}(y)\geq\varepsilon\delta^{4}/n\\}.$

Then we still have the same order for the total number of blue edges joined to
them, that is,

(5.3) $\sum_{y\in I}d_{b}^{A_{1}}(y)=\Omega(\delta^{6}/n).$

The argument is a little sketchy, because it is simply a repetition of
previous section, with no essential changes. Next, for each $y\in I$, instead
of applying Lemma 2.7 directly, we need to use the arguments in its proof to
find enough $s$-tuples satisfying both conditions (i) and (ii).

For any $y\in I$, let $N_{b}(x,y)$ denote the common blue neighborhood of $x$
and $y$ in $A$ and we know that
$|N_{b}(x,y)|=d_{b}^{A_{1}}(y)=\Omega(\delta^{4}/n)=\omega(\delta)$. We are
going to look for $s$-tuples $(u_{1},\cdots,u_{s})$ which, together with $y$,
will make both $(i)$ and $(ii)$ hold. We list both
$N_{G}(x)=\\{b_{x,1},\cdots,b_{x,k_{x}}\\}$ and
$N_{G}(y)=\\{b_{y,1},\cdots,b_{y,k_{y}}\\}$, such that, the common neighbors
of $x$ and $y$ appear at the beginning in both lists. In other words, there
exists some $k^{\ast}\leq\min\\{k_{x},k_{y}\\}$ such that, for
$i=1,\cdots,k^{\ast}$, $b_{x,i}=b_{y,i}$. Then for each $(i,j)$, we consider
the family $\mathcal{W}$ consisting of sets $W_{i,j}=\big{(}N_{G}(b_{x,i})\cup
N_{G}(b_{y,j})\big{)}\cap N_{b}(x,y)$. Up to deleting some duplicate sets and
empty sets, and then re-ordering the remaining sets $W_{i,j}$, we simply
rewrite this family as

(5.4) $\mathcal{W}=\\{U_{1},\cdots,U_{k}\\},\ k\geq k^{\ast}$

satisfying that for each $i\leq k^{\ast}$, $U_{i}=N_{G}(b_{x,i})\cap
N_{b}(x,y)=N_{G}(b_{y,i})\cap N_{b}(x,y)$. Note that, since each vertex in
$N_{b}(x,y)$ has at least one common neighbor with both $x$ and $y$ in $G$, it
belongs to some $N_{G}(b_{x,i})$ or some $N_{G}(b_{y,j})$, thus
$N_{b}(x,y)=\bigcup_{i=1}^{k}U_{i}$.

We claim that one can make a partition $N_{b}(x,y)=\bigcup_{j=1}^{\ell}P_{j}$
with the following properties.

  1. (1)

$\ell=\Theta(d_{b}^{A_{1}}(y)/\delta)$.

  2. (2)

for each $1\leq j\leq\ell$, $|P_{j}|=\Theta(\delta)$.

  3. (3)

for any $u_{1},\cdots,u_{s}$ taken from sets $P_{i_{1}},\cdots,P_{i_{s}}$,
with $1\leq i_{1}<\cdots<i_{s}\leq\ell$, both $K^{x}_{u_{1},\cdots,u_{s}}$ and
$K^{y}_{u_{1},\cdots,u_{s}}$ are proper.

We show the claim via an induction process, similar to the proof of Lemma 2.7.
First we observe that each element in the family $\mathcal{W}$ is a set with
size at most $2K\delta$, since it is a union of the neighborhoods of two
vertices in $B$. Update the definition of these sets by setting $U_{1}=U_{1}$
and $U_{i}=U_{i}\setminus\left(\bigcup_{j=1}^{i-1}U_{j}\right)$ for
$i=2,\cdots,k$. Then $\bigcup_{i=1}^{k}U_{i}$ is a partition of $N_{b}(x,y)$
with the size of each part at most $2K\delta$.

We can choose some $k_{1}$ such that $P_{1}=\bigcup_{j=1}^{k_{1}}U_{j}$ has
size $[\frac{1}{2}K\delta,\frac{5}{2}K\delta]$. Now any vertex $v\in
N_{b}(x,y)\backslash P_{1}$ joins some $b\in B$ which is not the common
neighbor of any vertex in $P_{1}$ and $x$ (or $y$). Inductively, suppose we
have found disjoint sets $P_{1},\cdots,P_{t}$ such that each of them has size
in the interval $[\frac{1}{2}K\delta,\frac{5}{2}K\delta]$,
$\bigcup_{i=1}^{t}P_{i}=\bigcup_{i=1}^{k_{t}}U_{i}$ for some $k_{t}$, and any
$u_{1}\in P_{i_{1}},\cdots,u_{s}\in P_{i_{s}}$ for any sequence $1\leq
i_{1}<\cdots<i_{s}\leq t$ make both $K^{x}_{u_{1}\cdots,u_{s}}$ and
$K^{y}_{u_{1},\cdots,u_{s}}$ proper. Now we are dealing with two cases,
namely, $k_{t}\leq k^{\ast}$ or $k_{t}>k^{\ast}$. However, there is no
difference in both cases, that is, any vertex
$z_{t}\in\bigcup_{j=k_{t}+1}^{k}U_{j}=N_{b}(x,y)\backslash\bigcup_{j=1}^{t}P_{j}$
does not share any common neighbor with any vertex in
$\bigcup_{j=1}^{t}P_{j}$.

Now we can find some $k_{t+1}$ such that the set
$P_{t+1}=\bigcup_{i=k_{t}+1}^{k_{t+1}}U_{i}$ has size in
$[\frac{1}{2}K\delta,\frac{5}{2}K\delta]$. If the number of the rest vertices
is at most $\frac{1}{2}K\delta$, we include all the rest vertices into
$P_{t+1}$, define $\ell=t+1$, and the process terminates. If the rest of the
vertices is more than $\frac{1}{2}K\delta$, we continue with the process.
Eventually we will terminate since there are only finitely many vertices. It
is easy to check that all properties (1), (2) and (3) hold.

After the claim, we count. We can choose $s$ pairwise disjoint sets
$P_{i_{1}},\cdots,P_{i_{s}}$ from the above list in $\ell\choose s$ ways, and
then in each of these $s$ sets, we choose arbitrarily an element $u_{i}\in
P_{i}$. Therefore, we find $\Omega\Big{(}{\ell\choose
s}\times\delta^{s}\Big{)}=\Omega\big{(}(d_{b}^{A_{1}}(y))^{s}\big{)}$ many
$s$-tuples $(u_{1},\cdots,u_{s})$ making both $K^{x}_{u_{1},\cdots,u_{s}}$ and
$K^{y}_{u_{1},\cdots,u_{s}}$ proper.

To sum up, we have shown that for each $y\in I$, the total number of
$s$-tuples satisfying (i) and (ii) is
$\Omega\big{(}(d_{b}^{A_{1}}(y))^{s}\big{)}$. Recalling (5.2) and (5.3), and
applying Jensen’s inequality, it follows that the number of $(s+1)$-tuples
$(y,u_{1},\cdots,u_{s})$ satisfying both (i) and (ii) is

(5.5) $\Omega(\sum_{y\in
I}d_{b}^{A_{1}}(y)^{s})\geq\Omega\Big{(}|I|\Big{(}\frac{1}{|I|}\sum_{y\in
I}d_{b}^{A_{1}}(y)\Big{)}^{s}\Big{)}=\Omega(\delta^{4s+2}/n^{s}).$

The proof is completed. ∎

Below, for any $s$-tuple $(u_{1},\cdots,u_{s})\in A_{1}^{s}$, let
$P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})$ be the set of vertices $y\in A_{1}$
such that both properties (i) and (ii) in Lemma 5.1 hold true.

######  Lemma 5.2.

Suppose there is no proper copy of $K_{s+1,t}^{+}$ in $G_{c}(A)$ and an
$s$-tuple $(u_{1},\cdots,u_{s})\in A_{1}^{s}$ has size
$|P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})|=\omega(1)$. Then we can find a
vertex $b\in B$ and a family $\mathcal{V}$ of $s$-tuples in $A_{1}^{s}$ with
$|\mathcal{V}|=\Omega(|P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})|^{s})$, such
that every $\\{v_{1},\cdots,v_{s}\\}\subset\mathcal{V}$ forms a non-red
$s$-clique, and one of the following two cases happens.

  1. (1)

either $\\{v_{1},\cdots,v_{s},x\\}\subset N_{G}(b)$,

  2. (2)

or there is a $k\in\\{1,\cdots.s\\}$, such that
$\\{v_{1},\cdots,v_{s},u_{k}\\}\subset N_{G}(b)$.

###### Proof.

Let’s define a maximal subset $\\{y_{1},\cdots,y_{r}\\}\subset
P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})$ such that, together with $\\{x\\}$ and
$\\{u_{1},\cdots,u_{s}\\}$, they form a proper copy of $K_{s+1,r}^{+}$,
denoted by $H$. More precisely, the edge set $E(H)$ consists of $(x,u_{1})$,
$\\{(x,y_{i})\\}_{1\leq i\leq r}$, and $\\{(u_{i},y_{j})\\}_{1\leq i\leq
s,1\leq j\leq r}$. Because $H$ is proper, for each $e\in E(H)$, we can find
one distinct vertex $b\in B$ such that it is a common neighbor of both
vertices of the edge $e$. Let $B_{used}$ be the set of these vertices. Note
that $|B_{used}|=1+(s+1)r$. Since $G$ is $(K_{s+1,t}^{+})^{\text{sub}}$-free,
we must have $0\leq r<t$, where $r=0$ means that the maximal subset could be
an empty set.

For any $y\in
P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})\backslash\\{y_{1},\cdots,y_{r}\\}$, by
maximality of the set $\\{y_{1},\cdots,y_{r}\\}$, there exists some $b\in
B_{used}$ such that $y\in N_{G}(b)$. By pigeonhole principle, there exists a
certain vertex $b^{\ast}\in B_{used}$ which is joined by at least
$\Omega(|P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})|)$ vertices. Note that either
$b^{\ast}\in N_{G}(x)$, or there is some $1\leq k\leq s$ such that
$b^{\ast}\in N_{G}(u_{k})$, which will lead to the dichotomy in the statement
of this lemma. Applying Proposition 2.8, there exist at least
$\Omega(|P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})|^{s})$ many non-red $s$-tuples
$\\{v_{1},\cdots,v_{s}\\}$ satisfying either (1) or (2). Let $\mathcal{V}$
denote the family of $s$-tuples. So the proof is complete. ∎

The proof of Theorem 1.7 reduces to the following proposition.

######  Proposition 5.3.

Suppose $G$ is $(K_{s+1,t}^{+})^{\text{sub}}$-free. Then there exists
$\\{y_{1},\cdots,y_{s}\\}\subset A_{1}$ which forms a non-red clique, and the
common blue neighbourhood of $\\{y_{1},\cdots,y_{s}\\}$ in $G_{c}(A_{1})$ has
size $\omega(\delta)$.

###### Proof.

We start from Lemma 5.1, and notice that the total number does not drop if we
only sum over all the $s$-tuples $u_{1},\cdots,u_{s}$ with
$|P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})|=\omega(1)$. Then by Lemma 5.2, for
each such $s$-tuple, we can obtain $b\in B$, and a family $\mathcal{V}$ of
$s$-tuples forming non-red $s$-cliques, with
$|\mathcal{V}|=\Omega(|P^{\prime}_{u_{1},\cdots,u_{s}}(A_{1})|^{s})$, such
that

  1. (i)

either $\\{v_{1},\cdots,v_{s}\\}\in\mathcal{V}$ implies
$\\{v_{1},\cdots,v_{s},x\\}\subset N_{G}(b)$,

  2. (ii)

or there exists some $u_{k}$ such that
$\\{v_{1},\cdots,v_{s}\\}\in\mathcal{V}$ implies
$\\{v_{1},\cdots,v_{s},u_{k}\\}\subset N_{G}(b)$.

Recall that $|A_{1}|=\Theta(\delta^{2})$, by Lemma 5.1 and Jensen’s
inequality, the total number of $2s$-tuples
$(u_{1},\cdots,u_{s},v_{1},\cdots,v_{s})$ with the above properties is at
least
$\Omega\big{(}(\delta^{2})^{s}\times(\delta^{2s+2}/n^{s})^{s}\big{)}=\Omega(\delta^{4s+2s^{2}}/n^{s^{2}})$.
Then, at least one of the above dichotomies will be satisfied by at least
$\Omega(\delta^{4s+2s^{2}}/n^{s^{2}})$ many $s$-tuples. In both cases, we will
do double counting, with the degree condition (5.1) at hand.

If assertion (i) is satisfied by $\Omega(\delta^{4s+2s^{2}}/n^{s^{2}})$ many
$2s$-tuples, we can choose $b\in B$ in $n$ ways, then we choose
$v_{1},\cdots,v_{s}\in N_{G}(b)$ in $\delta^{s}$ ways. We note the degree
condition implies that $\delta^{4s+2s^{2}}/n^{s^{2}}=\omega(\delta^{2s}n).$
Therefore, by pigeonhole principle, given by a certain one particular such
choice of $b,v_{1},\cdots,v_{s}$, there will be at least $\omega(\delta^{s})$
ways to extend this choice to find $2s$-tuple to satisfy assertion (i). Since
there are $s$ coordinates to consider, we conclude that the total number of
vertices showing up in these $s$-coordinates is at least $\omega(\delta)$.

If assertion (ii) is satisfied by $\Omega(\delta^{4s+2s^{2}}/n^{s^{2}})$ many
$2s$-tuples, we can choose $b\in B$ in $n$ ways, and then choose $1\leq k\leq
s$, and then choose $v_{1},\cdots,v_{s},u_{k}$ in $\delta^{s+1}$ ways. Use the
degree condition again, we see
$\delta^{4s+2s^{2}}/n^{s^{2}}=\omega(\delta^{s-1}n\delta^{s+1})$. So by
pigeonhole principle, there is a certain choice of
$b,u_{k},v_{1},\cdots,v_{s}$, which extends in at least $\omega(\delta^{s-1})$
ways to a different $2s$-tuple satisfying assertion (ii). Since there are
$s-1$ coordinates to consider, we conclude that the total number of vertices
showing up in these $(s-1)$-coordinates is at least $\omega(\delta)$. Now the
proof of the Proposition is completed. ∎

###### End of Proof of Theorem 1.7.

Note Proposition 5.3 provides with an $s$-subset of vertices
$\\{v_{1},\cdots,v_{s}\\}\subset A_{1}$, which, together with the vertex $x$,
forms a non-red $(s+1)$-clique. Let $H$ be the graph that consists of vertex
set $\\{x,v_{1},\cdots,v_{s}\\}$ and only one edge $(x,v_{1})$. So in
$G_{c}(A)$, there is a proper and blue copy of $H$. Then we apply Proposition
2.6 to find a proper copy of $K_{s+1,t}^{+}$ in $G_{c}(A)$, and the proof is
completed. ∎

## ACKNOWLEDGMENTS

When the first draft of this paper was obtained, X-C. Liu was supported by
Fapesp Pós-Doutorado grant (Grant Number 2018/03762-2).

## References

  * [1] B. Bukh.  Random algebraic construction of extremal graphs.  Bulletin of the London Mathematical Society, 47(6):939–945, 2015\.
  * [2] B. Bukh and D. Conlon.  Rational exponents in extremal graph theory.  Journal of the European Mathematical Society, 20(7):1747–1757, 2018\.
  * [3] D. Conlon.  Graphs with few paths of prescribed length between any two vertices.  Bulletin of the London Mathematical Society, 51(6):1015–1021, 2019\.
  * [4] D. Conlon and J. Lee.  On the extremal number of subdivisions.  International Mathematics Research Notices, 2021(12):9122–9145, 2021.
  * [5] D. Conlon, J. Lee, and O. Janzer.  More on the extremal number of subdivisions.  Combinatorica, 41(4):1–30, 2021.
  * [6] P. Erdős.  On the combinatorial problems which I would most like to see solved.  Combinatorica, 1(1):25–42, 1981.
  * [7] P. Erdős.  Problems and results in combinatorial analysis and graph theory.  Discrete Mathematics, 72(1–3):81–92, 1988.
  * [8] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  In Studia Sci. Math. Hung. Citeseer, 1965.
  * [9] P. Erdős and A. H. Stone.  On the structure of linear graphs.  Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946.
  * [10] R. Faudree and M. Simonovits.  On a class of degenerate extremal graph problems.  Combinatorica, 3(1):83–93, 1983.
  * [11] Z. Füredi and M. Simonovits.  The history of degenerate (bipartite) extremal graph problems.  In Erdős Centennial, pages 169–264. Springer, 2013.
  * [12] R. L. Graham, B. L. Rothschild, and J. H. Spencer.  Ramsey theory, volume 20.  John Wiley & Sons, 1991.
  * [13] O. Janzer.  Improved bounds for the extremal number of subdivisions.  The Electronic Journal of Combinatorics, 26(3), 2019.
  * [14] T. Jiang, J. Ma, and L. Yepremyan.  On turán exponents of bipartite graphs.  Combinatorics, Probability and Computing, 31(2):333–344, 2022.
  * [15] D. Y. Kang, J. Kim, and H. Liu.  On the rational Turán exponents conjecture.  Journal of Combinatorial Theory, Series B, 148:149–172, 2021.
  * [16] X.-C. Liu and X. Yang.  On turan number for generalized theta graph.  arXiv preprint arXiv:2103.10200, 2021.
  * [17] A. Naor and J. Verstraëte.  A note on bipartite graphs without 2k-cycles.  Combinatorics, Probability and Computing, 14(5-6):845–849, 2005\.