# Generalized Turán results for intersecting cliques

Dániel Gerbner1 Balázs Patkós1,2
1 Alfréd Rényi Institute of Mathematics
2 Moscow Institute of Physics and Technology

###### Abstract

For fixed graphs $F$ and $H$, the generalized Turán problem asks for the
maximum number $\mathrm{ex}(n,H,F)$ of copies of $H$ that an $n$-vertex
$F$-free graph can have. In this paper, we focus on the case when $F$ is
$B_{r,s}$, the graph consisting of two cliques of size $r$ sharing $s$ common
vertices. We determine $\mathrm{ex}(n,K_{t},B_{r,0})$,
$\mathrm{ex}(n,K_{t},B_{r,1})$ and $\mathrm{ex}(n,K_{a,b},B_{3,1})$ for all
values of $a,b,r,t$ if $n$ is large enough.

##  1 Introduction

A central question in extremal graph theory, the so-called Turán problem asks
for the maximum number $\mathrm{ex}(n,F)$ of edges that an $n$-vertex graph
$G$ can have without containing $F$ as a subgraph. Graphs with this property
are called $F$-free. The asymptotics of $\mathrm{ex}(n,F)$ is given by the
celebrated Erdős-Stone-Simonovits theorem [10] if the chromatic number of $F$
is at least three. For results and open problems in the case when $F$ is
bipartite, see the survey by Füredi and Simonovits [13].

A natural generalization of this problem is to maximize the number of copies
of some other graph $H$ while forbidding $F$ as subgraph. This maximum is
denoted by $\mathrm{ex}(n,H,F)$. More precisely, we denote by
${\mathcal{N}}(H,G)$ the number of (unlabeled) copies of $H$ in $G$, and
$\mathrm{ex}(n,H,F):=\max\\{{\mathcal{N}}(H,G):G\text{ is an $F$-free graph on
$n$ vertices}\\}$. So the original problem is the $H=K_{2}$ case and
$\mathrm{ex}(n,F)=\mathrm{ex}(n,K_{2},F)$. More generally, for a family
${\mathcal{F}}$ of graphs, we denote by $\mathrm{ex}(n,H,{\mathcal{F}})$ the
maximum number of copies of $H$ in $n$-vertex graphs that do not contain any
member of ${\mathcal{F}}$. After some very interesting but sporadic results
[4, 21, 23], these so-called generalized Turán problems were first addressed
systematically by Alon and Shikhelman [2].

In this paper we study the case where $H$ consists of two cliques sharing some
vertices. Let us denote by $B_{r,s}$ the graph consisting of two $r$-cliques
sharing exactly $s$ vertices. We also call it a generalized book graph. We
call the vertices shared by the two $r$-cliques rootlet vertices, and the
other vertices of the book graph are page vertices. The page vertices are
partitioned into two pages, according to which of the two $r$-cliques they
belong to.

Let us denote by $G_{1}+G_{2}$ the graph consisting of a vertex disjoint pair
of copies of $G_{1}$ and $G_{2}$ and by $kG$ the graph consisting of $k$
vertex-disjoint copies of $G$. Let $T(m,s)$ denote the Turán graph, which is
the complete $s$-partite graph on $m$ vertices with each part having order
$\lfloor m/s\rfloor$ or $\lceil m/s\rceil$. For graphs $G_{1},G_{2}$, their
join $G_{1}\vee G_{2}$ denotes the graph obtained by taking vertex disjoint
copies of $G_{1},G_{2}$ and joining every pair $v_{1},v_{2}$ of vertices with
$v_{1}\in V(G_{1}),v_{2}\in V(G_{2})$. For a set $U\subset V(G)$, we denote by
$G[U]$ the subgraph of $G$ induced by $U$, i.e., the subgraph we obtain by
deleting the vertices not in $U$.

As it was observed by Clark, Entringer, McCanna, and Székely [6], the
celebrated 6-3 theorem of Ruzsa and Szemerédi [30] can be reformulated the
following way: the largest number of edges in an $n$-vertex graph where every
edge is contained in exactly one triangle is $o(n^{2})$ but at least
$n^{2-o(1)}$. This implies the same bounds on $\mathrm{ex}(n,K_{3},B_{3,2})$.
Gowers and Janzer [20] (motivated by a rainbow variant of generalized Turán
problems [17]) generalized this by showing that for $2\leq s<r$, we have
$n^{s-o(1)}<\mathrm{ex}(n,K_{r},\\{B_{r,s},B_{r,s+1},\dots,B_{r,r-1}\\})=o(n^{s})$.
Liu and Wang [26] initiated the study of $\mathrm{ex}(n,K_{r},B_{r,s})$. They
determined its value exactly for $s=0$ and $s=1$ in the case $n$ is large
enough, and gave bounds in the case of other values of $s$.

In this paper we extend these investigations to counting other graphs. Let us
first discuss other results that fit into this setting. If $s=0$, we forbid
two vertex-disjoint copies of $K_{r}$. Moon [29] showed that
$\mathrm{ex}(n,kK_{r})=|E(K_{k-1}\vee T(n-k+1,r-1))|$. Concerning generalized
Turán problems, $\mathrm{ex}(n,H,kG)$ was studied in [18], in particular the
order of magnitude of $\mathrm{ex}(n,K_{\ell},kK_{r})$ was determined there.

If $s\geq 2$, then $B_{r,s}$ has a color-critical edge, i.e., an edge whose
deletion decreases the chromatic number. Simonovits [32] showed that for an
$r$-chromatic graph $F$ with a color-critical edge,
$\mathrm{ex}(n,F)=|E(T(n,r-1)|$. Ma and Qiu [28] showed that if $k<r$, then
$\mathrm{ex}(n,K_{k},F)={\mathcal{N}}(K_{k},T(n,r-1))$. Gerbner and Palmer
[19] and Gerbner [14] showed that we also have
$\mathrm{ex}(n,P_{3},F)={\mathcal{N}}(P_{3},T(n,r-1))$. Gerbner [15] presented
a theorem that determines the exact value of $\mathrm{ex}(n,H,B_{r,s})$ for a
class of graphs $H$ if $n$ is large enough.

In the case $s=1$, we have $\mathrm{ex}(n,B_{r,1})=|E(T(n,r-1)|+1$ and the
extremal construction is the Turán graph with an arbitrary additional edge.
This was proved in [7] for $r=3$ and in [5] for larger $r$. Gerbner and Palmer
[19] determined $\mathrm{ex}(n,C_{4},B_{3,1})$. $B_{r,1}$ has a color-critical
vertex, i.e., a vertex whose deletion decreases the chromatic number (from $r$
to $r-1$). Gerbner [15] determined $\mathrm{ex}(n,H,F)$ for every
$r$-chromatic graph $F$ with a color-critical vertex if $H$ is a complete
balanced $(r-1)$-partite graph $K_{a,\dots,a}$ with $a$ large enough. In
particular, this determines $\mathrm{ex}(n,K_{a,a},B_{3,1})$ for every $a$.

For a family of graphs ${\mathcal{H}}$, we denote by
$\mathrm{ex}(n,{\mathcal{H}},F)$ the largest value of
$\sum_{H\in{\mathcal{H}}}{\mathcal{N}}(H,G)$ $n$-vertex $F$-free graphs $G$.
The study of counting multiple graphs in generalized Turán problems was
initiated in [16]. Now we are ready to state our results.

######  Theorem 1.1.

For any $r$ and large enough $n$, we have the following:

(i) if $k<r$, then $\mathrm{ex}(n,K_{k},2K_{r})={\mathcal{N}}(K_{k},K_{1}\vee
T(n-1,r-1))$,

(ii) if $r\leq k<2r$, then
$\mathrm{ex}(n,\\{K_{k},K_{k+1},\dots,K_{2r-1}\\},2K_{r})={\mathcal{N}}(K_{k},K_{2k-2r+1}\vee
T(n-2k+2r-1,2r-k-1)$.

Note that the above theorem determines $\mathrm{ex}(n,K_{k},2K_{r})$ for every
pair of $s$ and $r$ if $n$ is large enough. The second statement gives a bit
more: if we count the copies of larger cliques in addition to $K_{k}$, then we
obtain the same bound. The extremal graph is the same for
$\mathrm{ex}(n,\\{K_{k},K_{k+1},\dots,K_{2r-1}\\},2K_{r})$ and
$\mathrm{ex}(n,K_{k},2K_{r})$, and it does not contain cliques of order more
than $k$.

######  Theorem 1.2.

For any $r\geq 3$, $1\leq s\leq r-1$, and $1\leq t<r-s$, we have

$\mathrm{ex}(n,K_{r+t},B_{r,s})=\Omega(n^{r-s-t-1}).$

For any $r\geq 3$, $2s+t+1<r$ and $n$ large enough, we have

$\mathrm{ex}(n,K_{r+t},B_{r,s})=\Theta(n^{r-s-t-1}).$

For any $t\geq 1$, $t+3<r$ and $n$ large enough, we have

$\mathrm{ex}(n,K_{r+t},B_{r,1})={\mathcal{N}}(K_{r+t},K_{2t+2}\vee
T(n-2t-2,r-t-2)).$

Observe that the above theorem determines $\mathrm{ex}(n,K_{k},B_{r,1})$ for
every $k>r$ and $n$ large enough. Consider now the case $k<r$. For $s=0$, the
value of $\mathrm{ex}(n,K_{k},B_{r,s})$ is determined exactly for sufficiently
large $n$ by Theorem 1.1. We have mentioned a result of Ma and Qiu [28]
earlier about graphs with a color-critical edge, which determines
$\mathrm{ex}(n,K_{k},B_{r,s})$ for sufficiently large $n$ if $k<r$ and $s\geq
2$. We now deal with the remaining case $s=1$. Let $T^{+}(n,r-1)$ denote the
graph we obtain from $T(n,r-1)$ by adding an edge to a smallest part.

######  Theorem 1.3.

If $k<r$ and $n$ is sufficiently large, then
$\mathrm{ex}(n,K_{k},B_{r,1})={\mathcal{N}}(K_{k},T^{+}(n,r-1))$.

In the case $r=3$, we can obtain a much more general result.

######  Theorem 1.4.

For any integers $a\leq b$ and $n$ large enough, we have that
$\mathrm{ex}(n,K_{a,b},B_{3,1})={\mathcal{N}}(K_{a,b},T)$ for some $n$-vertex
graph $T$ that is obtained from a complete bipartite graph by adding an edge.

For given $a$ and $b$, a straightforward optimization shows what $T$ is. In
the case $K_{a,b}$ is not a star, i.e., $a,b\geq 2$, the extra edge of $T$
cannot be in any copy of $K_{a,b}$, thus a complete bipartite graph
$K_{m,n-m}$ is also an extremal graph.

##  2 Forbidding $2K_{r}$ and counting cliques

In this section, we prove Theorem 1.1. First we gather some results that we
will use in the proof. A family ${\mathcal{F}}$ of sets is $t$-intersecting if
for any $F,F^{\prime}\in{\mathcal{F}}$ we have $|F\cap F^{\prime}|\geq t$. For
a set $X$ we denote by $\binom{X}{k}$ the family of all $k$-subsets of $X$.
The set $\\{1,2,\dots,n\\}$ of the first $n$ positive integers is denoted by
$[n]$, and we write $[a,b]$ for the interval $\\{s\in\mathbb{N}:a\leq s\leq
b\\}$.

We will use the following theorem of Frankl.

######  Theorem 2.1 (Frankl [11]).

Let ${\mathcal{F}}\subseteq\binom{[n]}{k}$ be $t$-intersecting with
$|\cap_{F\in{\mathcal{F}}}F|<t$. If $n$ is large enough, then
$|{\mathcal{F}}|\leq\max\\{|{\mathcal{F}}_{1}|,|{\mathcal{F}}_{2}|\\}$, where

${\mathcal{F}}_{1}=\left\\{F\in\binom{[n]}{k}:[t]\subset
F,F\cap[t+1,k+1]\neq\emptyset\right\\}\cup\binom{[k+1]}{k}$

and

${\mathcal{F}}_{2}=\left\\{F\in\binom{[n]}{k}:|F\cap[t+2]|\geq t+1\right\\}.$

Let us remark that later Ahlswede and Khachatrian [1] strengthened this result
by determining the maximum size of a $t$-intersecting family
${\mathcal{F}}\subset\binom{[n]}{k}$ with $|\cap_{F\in{\mathcal{F}}}F|<t$ for
any $n,k$, and $t$.

Another tool in the proof will be the following generalization of the Erdős-
Simonovits stability theorem [8, 32]. We say that two graphs $G$ and
$G^{\prime}$ have edit distance at most $x$ if we can obtain $G^{\prime}$ from
$G$ by adding and deleting $x$ edges

######  Theorem 2.2 (Ma, Qiu [28]).

Let $H$ be a graph with $\chi(H)=r+1>m\geq 2$. If $G$ is an $n$-vertex
$H$-free graph with
${\mathcal{N}}(K_{m},G)\geq{\mathcal{N}}(K_{m},T(n,r))-o(n^{m})$, then $G$ and
$T(n,r)$ have edit distance $o(n^{2})$.

We will also need the following two well-known results.

######  Theorem 2.3 (Zykov [34]).

For any $2\leq s<r\leq n$ we have

$\mathrm{ex}(n,K_{s},K_{r})={\mathcal{N}}(K_{s},T(n,r-1).$

######  Theorem 2.4 (Removal lemma, Erdős, Frankl, Rödl [9]).

For any graph $H$ on $h$ vertices and $\varepsilon>0$ there exists
$\delta=\delta(\varepsilon,H)$ such that if a graph $G=(V,E)$ on $n$ vertices
contains at most $\delta n^{h}$ copies of $H$, then there exists
$E^{\prime}\subset E$ with $|E^{\prime}|\leq\varepsilon n^{2}$ such that
$(V,E\setminus E^{\prime})$ is $H$-free.

###### Proof of Theorem 1.1.

Let $G=(V,E)$ be a $2K_{r}$-free graph on $n$ vertices.

Suppose first that $k<r$. Let $t$ be the minimum number such that there exists
a vertex subset $U\subset V$ of size $t$ such that $G[V\setminus U]$ is
$K_{r}$-free. Observe that $t\leq r$ as if $K$ is a copy of $K_{r}$, then
$G[V\setminus V(K)]$ must be $K_{r}$-free since $G$ is $2K_{r}$-free. By
Theorem 2.3, we have ${\mathcal{N}}(K_{k},G[V\setminus
U])\leq{\mathcal{N}}(K_{k},T(n-t,r-1))$. If $t\leq 1$, then this immediately
yields the statement of (i).

Assume $2\leq t\leq r$. Assume that
${\mathcal{N}}(K_{k},G)\geq{\mathcal{N}}(K_{k},T(n-t,r-1))$. Then the number
of $k$-cliques intersecting $U$ is at least ${\mathcal{N}}(K_{k},K_{1}\vee
T(n-1,r-1))-{\mathcal{N}}(K_{k},T(n-t,r-1))$. Observe that

${\mathcal{N}}(K_{k},K_{1}\vee T(n-1,r-1))-{\mathcal{N}}(K_{k},T(n-t,r-1))\\\
=(1+o(1))((t-1){\mathcal{N}}(K_{k-1},T(n\frac{r-2}{r-1},r-2))+{\mathcal{N}}(K_{k-1},T(n-1,r-1)).$

If $n$ is large enough, then

$\frac{{\mathcal{N}}(K_{k-1},T(n-1,r-1))}{{\mathcal{N}}(K_{k-1},T(n\frac{r-2}{r-1},r-2))}>c_{r}>1$

for some constant $c_{r}$ depending only on $r$. This means that the number of
$k$-cliques meeting $U$ is at least
$(t-1+c_{r}+o(1)){\mathcal{N}}(K_{k-1},T(n\frac{r-2}{r-1},r-2))$. As the
number of $k$-cliques containing at least two vertices of $U$ is $O(n^{k-2})$,
we obtain a contradiction by proving that for any $u\in U$, the number of
$k$-sets $S\subset V$ with $S\cap U=\\{u\\}$ and $G[S]=K_{k}$ is at most
$(1+o(1)){\mathcal{N}}(K_{k-1},T(n\frac{r-2}{r-1},r-2))$.

To this end, observe first that for any $u\in U$ the number of $(r-1)$-subsets
$A$ of $V\setminus U$ such that $\\{u\\}\cup A$ form a clique in $G$ is
$O(n^{r-2})$. Indeed, as $U$ is minimal, there exists an $r$-clique
$A^{\prime}$ with $u\notin A^{\prime}$, thus every such $(r-1)$-subset $A$
with $A\ni u$ must meet $A^{\prime}$ (as $G$ is $2K_{r}$-free), so their
number is at most $r\binom{n-2}{r-2}$. By Theorem 2.4, there exist a set
$E_{0}$ of $o(n^{2})$ edges whose deletion removes all these $K_{r-1}$s. The
number of $k$-cliques containing $u$ and at least one edge from $E_{0}$ is
$o(n^{k-1})$.

As the number of $k$-cliques in $G$ meeting $U$ is $O(n^{k-1})$, we must have
${\mathcal{N}}(K_{k},G[V\setminus
U])\geq{\mathcal{N}}(K_{k},T(n-t,r-1))-o(n^{k})$. Theorem 2.2 implies that
$V\setminus U$ can be partitioned into $r-1$ almost parts
$V_{1},V_{2},\dots,V_{r-1}$ such that $G[V\setminus U]$ has edit distance
$o(n^{2})$ from the Turán-graph on the $V_{i}$s as partite sets and each
$V_{i}$ has order either $\lfloor(n-t)/(r-1)\rfloor$ or
$\lceil(n-t)/(r-1)\rceil$.

We claim that there exists an $i$ such that $|N_{G}(u)\cap V_{i}|=o(n)$.
Indeed, otherwise we can pick $\Theta(n^{r-1})$ $(r-1)$-sets having exactly
one element in each $N_{G}(u)\cap V_{i}$. Only $o(n^{r-1})$ of these
$(r-1)$-sets contain a pair of vertices $v,v^{\prime}$ such that $vv^{\prime}$
is not an edge of $G$, since only $o(n^{2})$ edges between the sets $V_{i}$
($i\leq r-1$) are missing from $G$. Therefore, there are $\Theta(n^{r-1})$
copies of $K_{r-1}$s in the neighborhood of $u$, but we have already seen that
there are only $O(n^{r-2})$ of them.

Clearly, there are $o(n^{k-1})$ copies of $K_{k}$ containing $u$ and a vertex
from a $V_{i}$ with $|N_{G}(u)\cap V_{i}|=o(n)$. This implies that the number
of $k$-cliques containing $u$ is indeed at most
$o(n^{k-1})+{\mathcal{N}}(K_{k-1},T(n\frac{r-2}{r-1},r-2))$ as claimed. This
finishes the proof of (i).

Let us start the proof of (ii) with the special case when we only count copies
of $K_{k}$, i.e., we are interested in $\mathrm{ex}(n,K_{k},2K_{r})$. As
$r\leq k<2r-1$, any two copies $K^{1},K^{2}$ of $K_{k}$ must meet in at least
$2k-2r+1$ vertices, otherwise their union would contain at least $2r$ vertices
and thus a copy of $2K_{r}$. Therefore, the $k$-uniform hypergraph
$H=(V,{\mathcal{E}})$ with ${\mathcal{E}}=\\{S\in\binom{V}{k}:G[S]=K_{k}\\}$
is $(2k-2r+1)$-intersecting. Applying Theorem 2.1, we obtain that either all
the $k$-cliques of $G$ contain a fixed $(2k-2r+1)$-set, or
${\mathcal{N}}(K_{k},G)=o(n^{k-(2k-2r+1)})$. In the latter case, we are done,
since ${\mathcal{N}}(K_{k},K_{2k-2r+1}\vee
T(n-2k+2r-1,2r-s-1))=\Theta(n^{2r-k-1})$.

Therefore, we can assume that all the $k$-cliques of $G$ contain a fixed
$(2k-2r+1)$-set $K$. Then the vertices of $K$ are adjacent to all vertices
that are contained in a $K_{k}$ in $G$. Let $U$ denote the set of vertices
outside $K$ that are contained in at least one copy of $K_{k}$ in $G$, so
$|U|\leq n-(2k-2r+1)$. If $G[U]$ is $K_{2r-k}$-free, then

${\mathcal{N}}(K_{k},G)={\mathcal{N}}(K_{2r-k-1},G[U])\leq{\mathcal{N}}(K_{2r-k-1},T(n-2k+2r-1,2r-k-1))=\\\
{\mathcal{N}}(K_{k},K_{2k-2r+1}\vee T(n-2k+2r-1,2r-k-1)).$

. Finally, if $G[U]$ contains a copy $K^{\prime}$ of $K_{2r-k}$, then
$G[U\setminus[V(K^{\prime})]$ cannot contain a copy of $K_{2r-k-1}$ as such a
copy with $K$ and $K^{\prime}$ would contain a $2K_{r}$. Every copy of $K_{k}$
in $G$ must contain $K$ and intersect $U$ in a copy of $K_{2r-k-1}$, thus must
intersect $K^{\prime}$. Therefore, we have
${\mathcal{N}}(K_{k},G)=O(n^{2r-k-2})=o({\mathcal{N}}(K_{k},K_{2k-2r+1}\vee
T(n-2k+2r-1,2r-k-1))$.

Finally, let us consider the general case of (ii). Observe that similarly to
the special case above, the $(k+i)$-uniform hypergraph
$H_{i}=(V,{\mathcal{E}}_{i})$ with
${\mathcal{E}}_{i}=\\{S\in\binom{V}{k+i}:G[S]=K_{k+i}\\}$ is
$(2(k+i-r)+1)$-intersecting. Applying Theorem 2.1, we obtain that the number
of $(k+i)$-cliques is $O(n^{2r-k-i-1})$ and thus the number of cliques larger
than $k$ is $O(n^{2r-k-2})$. This means that

  * •

in order to contain $\Theta(n^{2r-k-1})$ cliques of size at least $k$, all the
$k$-cliques of $G$ must contain the same $2k-r+1$ vertices just as in the
special case,

  * •

as any vertex contained in an $(k+i)$-clique is also contained in a
$k$-clique, every clique of size at least $k$ is contained in $U$,

  * •

if $G[U]$ is $K_{2r-k}$-free, then there are no cliques of size larger than
$k$ in $G$, so the proof finishes as in the special case,

  * •

if $G[U]$ does contain a $k$-clique, then, just like in the special case,
there are $O(n^{2r-k-2})$ copies of $K_{k}$ in $G$. As the number of cliques
larger than $k$ is $O(n^{2r-k-2})$, we obtain the same conclusion.

∎

##  3 Forbidding $B_{r,s}$ and counting large cliques

In this section, we prove Theorem 1.2. Again, we begin by collecting the tools
we will use. The following is a simple corollary of Theorem 2.2.

######  Proposition 3.1.

For any $r\geq 3$ and large enough $n$, we have
$\mathrm{ex}(n,K_{r-1},K_{r}+K_{r-1})={\mathcal{N}}(K_{r-1},T(n,r-1))$.
Furthermore, if $G$ is an $n$-vertex $(K_{r}+K_{r-1})$-free graph with
${\mathcal{N}}(K_{r-1},G)={\mathcal{N}}(K_{r-1},T(n,r-1))-o(n^{r-1})$, then
$G$ has edit distance $o(n^{2})$ from $T(n,r-1)$.

###### Proof.

If an $n$-vertex graph $G$ contains a copy $K$ of $K_{r}$, then all the copies
of $K_{r-1}$ must meet $K$, so their number is
$O(n^{r-2})=o({\mathcal{N}}(K_{r-1},T(n,r-1))$. If $G$ is $K_{r}$-free, then
by Theorem 2.3, we have
${\mathcal{N}}(K_{r-1},G)\leq{\mathcal{N}}(K_{r-1},T(n,r-1))$ and the
furthermore part follows from Theorem 2.2. ∎

If $L$ is a set of non-negative integers, we say that a family ${\mathcal{F}}$
of sets is $L$-intersecting if for any distinct
$F,F^{\prime}\in{\mathcal{F}}$, we have $|F\cap F^{\prime}|\in L$.

######  Theorem 3.2 (Frankl, Füredi [12]).

Let ${\mathcal{F}}\subseteq\binom{[n]}{k}$ be a
$\\{0,1,\dots,\ell-1,k-\ell^{\prime},k-\ell^{\prime}+1,\dots,k-1\\}$-intersecting
family. Then the following statements hold.

(i) There exists a constant $d_{k}$ such that $|{\mathcal{F}}|\leq
d_{k}n^{\max\\{\ell,\ell^{\prime}\\}}$.

(ii) If $\ell^{\prime}>\ell$ and $n\geq n_{0}(k)$, then
$|{\mathcal{F}}|\leq\binom{n-k+\ell^{\prime}}{\ell^{\prime}}$ and equality
holds if and only if there exists a $(k-\ell^{\prime})$-subset $X$ of $[n]$
such that ${\mathcal{F}}=\\{F\in\binom{[n]}{k}:X\subset F\\}$.

(iii) If $\ell\geq\ell^{\prime}$ and $k-\ell$ has a primepower divisor $q$
with $q>\ell^{\prime}$, then
$|{\mathcal{F}}|\leq(1+o(1))\binom{n}{\ell}\frac{\binom{k+\ell^{\prime}}{\ell^{\prime}}}{\binom{k+\ell^{\prime}}{\ell}}$.

The result of Theorem 3.2 itself will not be sufficient for us, we will also
need some parts of the proof. In the following lemma, we gather the parts of
the Frankl-Füredi proof that we will use.

To state the lemma we need to define the $i$-shadow of a family
${\mathcal{F}}$ of sets as $\Delta_{i}({\mathcal{F}}):=\\{G:|G|=i,~{}\exists
F\in{\mathcal{F}}\text{ such that }G\subset F\\}$.

######  Lemma 3.3 (Lemma 6.1 and several propositions in [12]).

If $\ell<\ell^{\prime}$ and ${\mathcal{F}}\subseteq\binom{[n]}{k}$ is a
$\\{0,1,\dots,\ell-1,k-\ell^{\prime},k-\ell^{\prime}+1,\dots,k-1\\}$-intersecting
family, then ${\mathcal{F}}$ can be partitioned into
${\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}\cup\cdots\cup{\mathcal{F}}_{h}\cup{\mathcal{F}}_{h+1}$
such that

  * •

$|{\mathcal{F}}_{h+1}|=O(n^{\ell^{\prime}-1})$,

  * •

for every $1\leq j\leq h$ there exists a $(k-\ell^{\prime})$-set $A_{j}$ such
that ${\mathcal{F}}_{j}\subseteq\\{G\in\binom{[n]}{k}:A_{j}\subset G\\}$,

  * •

writing ${\mathcal{H}}_{j}=\\{F\setminus A_{j}:F\in{\mathcal{F}}_{j}\\}$ we
have that the $\ell$-shadows are pairwise disjoint, i.e., for every $1\leq
i<j\leq h$
$\Delta_{\ell}({\mathcal{H}}_{i})\cap\Delta_{\ell}({\mathcal{H}}_{j})=\emptyset$.

We will also use the Lovász version [27] of the Kruskal-Katona shadow theorem
[25, 24]. It states that if a family ${\mathcal{H}}$ of $k$-subsets has size
$\binom{x}{k}=\frac{x(x-1)\dots(x-k+1)}{k!}$ for some real $x$, then for any
$i\leq k$ we have $|\Delta_{i}({\mathcal{H}})|\geq\binom{x}{i}$.

We will also use a theorem of Andrásfai, Erdős, and Sós [3] that states that
an $n$-vertex $K_{r}$-free graph with chromatic number at least $r$ contains a
vertex of degree at most $(1-\frac{1}{(r-1)-4/3})n$.

For integers $n,r,s,t$ with $r>s+t+1$ and $n>2t+s+1$, let us define the
function

$f(n)=f_{r,s,t}(n)={\mathcal{N}}(K_{r+t},K_{s+2t+1}\vee
T(n-s-2t-1,r-s-t-1))=\prod_{i=0}^{r-s-t-2}\left\lfloor\frac{n-s-2t-1+i}{r-s-t-1}\right\rfloor.$

Observe that for fixed $r,s,t$, the function $f(n)$ is a polynomial of $n$ of
degree $r-s-t-1$. We will need the following simple properties of $f(n)$.

######  Proposition 3.4.

(i) For any pair $n_{1},n_{2}$ of positive integers $f(n_{1})+f(n_{2})\leq
f(n_{1}+n_{2})$ holds.

(ii) For any $\varepsilon>0$ there exists $\delta>0$ such that if $n$ is large
enough, then $f((1-\varepsilon)n)+f(\varepsilon n+o(n))<(1-\delta)f(n)$ holds.

(iii) If $r-s-t-1\geq 2$, $y=o(x)$ and $x=o(n)$, then
$f(n-x)+f(x+y)<f(n)-\Omega(xn^{r-s-t-2})$ holds.

Now we are ready to prove Theorem 1.2.

###### Proof of Theorem 1.2.

Each of the lower bounds is obtained from the following construction: let
$m=s+2t+1$ and $G$ be the join $K_{m}\vee T(n-m,r-s-t-1)$. As $m+r-s-t-1=r+t$,
we have
${\mathcal{N}}(K_{r+t},G)={\mathcal{N}}(K_{r-s-t-1},T(n-m,r-s-t-1))=(1+o(1))(\frac{n-m}{r-s-t-1})^{r-s-t-1}$.
To see that $G$ is $B_{r,s}$-free, observe that out of the $2r-s$ vertices of
a copy of $B_{r,s}$, at least $2r-s-m=2r-2s-2t-1$ vertices belong to
$T(n-m,r-s-t-1)$. Therefore at least $r-s-t$ vertices belong to the same
$K_{r}$ of $B_{r,s}$ in $T(n-m,r-s-t-1)$. As there is no clique of $r-s-t$
vertices in $T(n-m,r-s-t-1)$, the graph $G$ is indeed $B_{r,s}$-free.

For the general upper bound, let $G$ be a $B_{r,s}$-free graph on $n$
vertices. Define the $(r+t)$-uniform family
${\mathcal{F}}_{G}=\\{K\subseteq\binom{V(G)}{r+t}:G[K]=K_{r+t}\\}$. Observe
that ${\mathcal{F}}_{G}$ is
$\\{0,1,\dots,s-1,2t+s+1,2t+s+1,\dots,r+t-1\\}$-intersecting. Indeed, assume
that two cliques $K_{1},K_{2}$ each of size $r+t$ intersect in at least $s$,
but less than $(r+t)-(r-t-s-1)=2t+s+1$ vertices. Then the union of $K_{1}$ and
$K_{2}$ contains at least $2(r+t)-(2t+s)=2r-s$ vertices and their intersection
contains at least $s$ vertices, and thus $G$ contains a copy of $B_{r,s}$, a
contradiction. We can apply Theorem 3.2 (i) to show that
${\mathcal{N}}(K_{r+t},G)=O(n^{r-s-t-1})$.

Finally, we consider the case $s=1$. Let $k=r+t$, and $\ell^{\prime}=r-t-2$.
Suppose $G$ is such that ${\mathcal{N}}(K_{r+t},G)\geq f(n)$. By the
assumption $t+3<r$, we have $1<\ell^{\prime}$ and so by Lemma 3.3, we obtain a
partition
${\mathcal{F}}_{G}={\mathcal{F}}_{1}\cup\cdots\cup{\mathcal{F}}_{h}\cup{\mathcal{F}}_{h+1}$
and $m$-sets $A_{1},A_{2},\dots,A_{h}$ with the properties ensured by Lemma
3.3. We introduce positive reals $x_{1},\dots,x_{h}$ such that
$|{\mathcal{F}}_{i}|=|{\mathcal{H}}_{i}|=\binom{x_{i}}{\ell^{\prime}}$.
Without loss of generality, $x_{1}\geq x_{2}\geq\cdots\geq x_{h}$. Let
$M_{j}=\cup_{F\in{\mathcal{F}}_{j}}F$ and clearly, we have $|M_{j}|\geq
x_{j}$.

######  Claim 3.5.

There exists an integer $n_{0}$ and a constant $C$ such that if $n\geq n_{0}$,
then $\Delta_{1}({\mathcal{F}}_{1})\geq n-C$.

###### Proof.

By the Lovász version of the Kruskal-Katona shadow theorem, we know that
$|\Delta_{\ell}({\mathcal{H}}_{i})|\geq x_{i}$ and thus by Lemma 3.3 we have
$\sum_{i=1}^{h}x_{i}\leq n$. Also, $x_{i}\geq x_{j}$ implies
$\frac{\binom{x_{i}}{\ell^{\prime}}}{x_{i}}\geq\frac{\binom{x_{j}}{\ell^{\prime}}}{x_{j}}$.
Therefore,

$\sum_{j=i}^{h}|{\mathcal{F}}_{j}|=\sum_{j=i}^{h}|{\mathcal{H}}_{j}|=\sum_{j=i}^{h}x_{j}\frac{\binom{x_{j}}{\ell^{\prime}}}{x_{j}}\leq\frac{\binom{x_{i}}{\ell^{\prime}}}{x_{i}}\sum_{j=i}^{h}x_{j}\leq\frac{\binom{x_{i}}{\ell^{\prime}}}{x_{i}}n=O((x_{i}/n)^{\ell^{\prime}-1}n^{\ell^{\prime}}).$
(1)

Then $|M_{1}|\geq\varepsilon n$ for some fixed $\varepsilon>0$ as otherwise
$|{\mathcal{F}}|=o(n^{\ell^{\prime}})$, while
$f(n)=\Theta(n^{\ell^{\prime}})$. By Lemma 3.3, we have that the sets
$M_{j}\setminus A_{j}$ are pairwise disjoint and thus
$|M_{j}\setminus\cup_{j^{\prime}=1}^{j-1}M_{j^{\prime}}|\geq|M_{j}|-(j-1)m$.
Let $j_{1}$ be the largest index $j$ with $|M_{j}|\geq(m+1)n^{2/3}$. Then (1)
implies that
$\sum_{j=j_{1}+1}^{h}|{\mathcal{F}}_{j}|=O(n^{\ell^{\prime}-1/3})$, and Lemma
3.3 shows that $|{\mathcal{F}}_{h+1}|=O(n^{\ell^{\prime}-1})$. We claim that
$j_{1}\leq n^{1/3}$. Indeed, if not, then for $j\leq n^{1/3}$, we have
$|M_{j}\setminus\cup_{j^{\prime}=1}^{j-1}M_{j^{\prime}}|\geq|M_{j}|-jm>n^{2/3}$
and
$n\geq\sum_{j=1}^{n^{1/3}}|M_{j}\setminus\cup_{j^{\prime}=1}^{j-1}M_{j^{\prime}}|>n^{1/3}n^{2/3}$,
a contradiction. As a consequence, we also have

$\sum_{j=1}^{j_{1}}|M_{j}|\leq n+\sum_{j=1}^{j_{1}}(j-1)m\leq
n+j_{1}^{2}m=n+O(n^{2/3}).$

Observe that for every $j\leq h$, every vertex of $M_{j}$ is connected to
every vertex of $A_{j}$. This implies that $G[M_{j}\setminus A_{j}]$ is
$K_{r-t-1}+K_{r-t-2}$-free, and thus, by Proposition 3.1,
$|{\mathcal{F}}_{j}|={\mathcal{N}}(K_{r+t},G[M_{j}])\leq f(|M_{j}|)$. Using
Proposition 3.4 (i) and (1) we obtain

$\sum_{j=1}^{h+1}|{\mathcal{F}}_{j}|\leq
f(|M_{1}|)+f(n+j_{1}^{2}m-|M_{1}|)+O(n^{\ell^{\prime}-1/3})+O(n^{\ell^{\prime}-1}).$
(2)

Assume first that $|M_{1}|<n-n^{2/3}\log n$. Let $x=n^{2/3}\log n-j_{1}^{2}$
and $y=j_{1}^{2}$. Then Proposition 3.4 (iii) yields that
$f(|M_{1}|)+f(n+j_{1}^{2}-|M_{1}|)<f(n)-\Omega(xn^{\ell^{\prime}-1})$.
Therefore, the right hand side of (2) is less than
$f(n)-\Omega(xn^{\ell^{\prime}-1})+O(n^{\ell^{\prime}-1/3})+O(n^{\ell^{\prime}-1})<f(n)$,
a contradiction.

Suppose towards a contradiction that $r(n):=n-|M_{1}|$ tends to infinity. Let
us write $p(n):=(m+1)(r(n))^{2/3}$ and let $j^{*}$ be the largest index with
$|M_{j^{*}}|\geq p(n)$. Then by (1), we obtain
$\sum_{j=j^{*}+1}^{h+1}|{\mathcal{F}}_{j}|=O(n(p(n))^{\ell^{\prime}-1})=O(n^{\ell^{\prime}-1}p(n))$.
We claim that $j^{*}\leq(r(n))^{1/3}$. Indeed, we can argue similarly as for
the upper bound on $j_{1}$ earlier: if $(r(n))^{1/3}\leq j^{*}$, then for
$j\leq(r(n))^{1/3}$ we have
$|M_{j}\setminus\cup_{i=1}^{j-1}M_{i}|\geq|M_{j}|-j(1+m)\geq(r(n))^{2/3}$ and
$r(n)\geq\sum_{j=2}^{(r(n))^{1/3}}|M_{j}-\cup_{j^{\prime}=1}^{j-1}M_{j^{\prime}}|>(r(n))^{1/3}(r(n))^{2/3}$,
a contradiction. This implies that $\sum_{j=2}^{j^{*}}|M_{j}|\leq
r(n)+(1+m)p(n)$. Applying Proposition 3.4 (i) and (iii) with $x=r(n)$ and
$y=(1+m)p(n)$, we obtain that

${\mathcal{N}}(K_{r+t},G)=\sum_{j=1}^{h+1}|{\mathcal{F}}_{j}|\leq
f(|M_{1}|)+\sum_{j=2}^{j^{*}}f(M_{j})+O(n^{\ell^{\prime}-1}p(n))\leq\\\
f(n-r(n))+f(r(n)+(1+m)p(n))+O(n^{\ell^{\prime}-1}p(n))<f(n),$

a contradiction. ∎

By Claim 3.5, we may assume that $|M_{1}|\geq n-C$ for some constant $C$. By
Lemma 3.3, this implies ${\mathcal{N}}(K_{r+t},G)\leq
f(|M_{1}|)+O(n^{\ell^{\prime}-1})$. As ${\mathcal{N}}(K_{r+t},G)\geq f(n)$, we
must have ${\mathcal{N}}(K_{\ell^{\prime}},G[M_{1}\setminus A_{1}])\geq
f(|M_{1}|)-D(n^{\ell^{\prime}-1})$ for some constant $D$. Proposition 3.1
implies that $G[M_{1}\setminus A_{1}]$ is $K_{\ell^{\prime}+1}$-free and it
can be made $\ell^{\prime}$-partite by deleting $o(n^{2})$ edges. Let us
delete those edges and let $U_{1},U_{2},\dots,U_{\ell^{\prime}}$ be the
corresponding partition. We say that a vertex $v\in U_{i}$ is problematic if
there exists $j\neq i$ such that there are at least
$\frac{|U_{j}|}{(\ell^{\prime})^{2}}$ vertices in $U_{j}$ not adjacent to $v$.
A set of vertices $W\subset M_{1}\setminus A_{1}$ is good if it does not
contain any problematic vertices.

######  Claim 3.6.

There exists a set $X\subset M_{1}\setminus A_{1}$ with $|X|=O(1)$ such that
$M_{1}\setminus(A_{1}\cup X)$ is good.

###### Proof of Claim..

First we find a set $X_{1}$ of vertices whose removal from $G[M_{1}\setminus
A_{1}]$ makes the remaining graph $\ell^{\prime}$-partite such that
$|X_{1}|=O(1)$. Then we show that there are $O(1)$ problematic vertices in the
remaining $l^{\prime}$-partite graph.

Suppose first that $\chi(G[M_{1}\setminus A_{1}])\geq\ell^{\prime}+1$. Then by
a theorem of Andrásfai, Erdős, and Sós [3], there exists a vertex $v$ with
degree (in $G[M_{1}\setminus A_{1}]$) at most
$(1-\frac{1}{\ell^{\prime}-4/3}+o(1))|M_{1}\setminus A_{1}|$. As
$G[M_{1}\setminus A_{1}]$ is $K_{\ell^{\prime}+1}$-free,
$G[N_{G}(v)\cap(M_{1}\setminus A_{1})]$ is $K_{\ell^{\prime}}$-free and the
number of copies of $K_{r+t}$ in $G[M_{1}]$ containing $v$ is at most

${\mathcal{N}}(K_{\ell^{\prime}-1},G[N_{G}(v)\cap(M_{1}\setminus
A_{1}))\leq{\mathcal{N}}(K_{\ell^{\prime}-1},T((1-\frac{1}{\ell^{\prime}-4/3}+o(1))|M_{1}\setminus
A_{1}|,\ell^{\prime}-1)).$

Now observe that the difference between the number of copies of
$K_{\ell^{\prime}}$ in $T_{\ell^{\prime}}(|M_{1}\setminus A_{1}|)$ containing
a fixed vertex $u$ and this number is at least $\alpha n^{\ell^{\prime}-1}$
for some constant $\alpha$. So we remove $v$ and add it to $X_{1}$. If the
remaining graph is $\ell^{\prime}$-partite, then we are done with the first
step, otherwise we use the Adrásfai, Erdős, Sós theorem to find another vertex
of low degree, and so on. Observe that if $|X_{1}|\alpha$ is larger than $D$,
then ${\mathcal{N}}(K_{r+t},G)\leq f(n)$, so indeed we can guarantee that the
size of $X_{1}$ is bounded by a constant.

From now on, we can assume that the remaining graph $G[M_{1}\setminus
A_{1}\setminus X_{1}]$ is $\ell^{\prime}$-chromatic with partition
$U_{1},\dots,U_{\ell^{\prime}}$. If a vertex $u\in U_{i}$ is problematic, then
the number of copies of $K_{r+t}$ in $G[M_{1}]$ containing $v$ is at most
$(1-\frac{1}{(\ell^{\prime})^{2}})\prod_{j\neq i}|U_{j}|$, so again some
$\beta n^{\ell^{\prime}-1}$ smaller than in the appropriate Turán graph. We
remove problematic vertices one by one, let $X_{2}$ be the set of vertices
removed this way. As in the above paragraph, if $|X_{2}|\beta$ is larger than
$D$, then ${\mathcal{N}}(K_{r+t},G)\leq f(n)$, so indeed we can guarantee that
the size of $X_{2}$ is bounded by a constant. ∎

We claim that if an $(r+t)$-clique $W$ contains a vertex from $V\setminus
M_{1}$, then $W$ and $M_{1}\setminus X$ are disjoint. Indeed, assume to the
contrary that for a clique $W\not\subset M_{1}$ we have $|W\cap(M_{1}\setminus
X)|\geq 1$ and let $y$ be an element of $W\cap A_{1}$ if such an element exist
and $y\in W\cap M_{1}\setminus(A_{1}\cup X)$ otherwise.

Let us go through the indices $i$ with $y\notin U_{i}$ in an arbitrary order.
For each $i$, we pick a vertex $v_{i}\in U_{i}\setminus W$ that is connected
to $y$ and every vertex already picked. As the number of vertices picked this
way is at most $r-t-3$, at most $(r-t-3)|U_{i}|/(r-t-2)^{2}+o(n)$ vertices of
$U_{i}$ are forbidden, thus we can pick the desired vertex. Then we can add
the vertices of $A_{1}\cup|\\{y\\}$ to obtain a clique $W^{\prime}$ of size
$m+\ell^{\prime}=r+t$. Because $y$ is in both $W$ and $W^{\prime}$, we have
$|W\cap W^{\prime}|\geq 1$. We claim that $|W\cup W^{\prime}|\geq
m+2\ell^{\prime}+1=2r-1$. Indeed, as $W$ contains a vertex from $V\setminus
M_{1}$, we cannot have $A_{1}\subset W$ and thus by construction, we have
$|W\cap W^{\prime}|<m$. Observe that $1\leq|W\cap W^{\prime}|$ and $|W\cup
W^{\prime}|\geq 2r-1$ imply that $W\cup W^{\prime}$ contains a copy of
$B_{r,1}$. This contradiction shows that $W$ is indeed disjoint with
$M_{1}\setminus X$.

The number of $(r+t)$-cliques disjoint with $M_{1}\setminus X$ is

$\binom{|(V\setminus M_{1})\cup X|}{r+t}=O(1)=O(n^{\ell^{\prime}-2}).$

As a consequence we obtain that the number of $(r+t)$-cliques of $G$ meeting
$V\setminus M_{1}$ is $o(n^{\ell^{\prime}-1})$, while
$f(n)-f(n-C)=\Omega(n^{\ell^{\prime}-1})$ as long as $C$ is positive.
Therefore, we must have that $|M_{1}|=n$. As the sets $M_{i}\setminus A_{i}$
are pairwise disjoint, this implies that for any $F\in{\mathcal{F}}_{j}$, the
subset $F\setminus A_{j}$ be contained in $M_{1}\setminus A_{1}$, so their
total number is $O(n^{m})$. That means even with the exceptional sets from
${\mathcal{F}}_{h+1}$, the number of sets of
${\mathcal{F}}_{G}\setminus{\mathcal{F}}_{1}$ is $O(n^{\ell^{\prime}-1})$. If
there exists a set $F\in{\mathcal{F}}_{G}$ with $A_{1}\not\subset F$ and
$A_{1}\cap F\neq\emptyset$, then, as $G$ is $B_{r,1}$-free, every
$F_{1}\in{\mathcal{F}}_{1}$ must meet $F$ outside $A_{1}$, so
${\mathcal{F}}_{1}$ and ${\mathcal{F}}$ both have size
$O(n^{\ell^{\prime}-1})$, which contradicts $|{\mathcal{F}}|\geq f(n)$. If
${\mathcal{F}}$ contains a set $F$ disjoint with $A_{1}$, then, as $G$ is
$B_{r,1}$-free, every set $F_{1}\in{\mathcal{F}}_{1}$ is either disjoint with
$F$ or $|F\cap F_{2}|\geq 2$, so $|{\mathcal{F}}|\leq
f(n-S)+\binom{n}{\ell^{\prime}-2}+|\\{F\in{\mathcal{F}}:F\cap
A_{1}=\emptyset\\}$, where $S=|\cup_{F\in{\mathcal{F}},|A_{1}\cap F|=0}F|$. By
Proposition 3.4 (iii), $f(n)-f(n-S)=\Omega(n^{\ell^{\prime}-1})$, and so
$|{\mathcal{F}}|<f(n)$, a contradiction.

We have established that all $F\in{\mathcal{F}}_{G}$ must contain $A_{1}$, and
then we are done by Proposition 3.1. ∎

##  4 Forbidding $B_{r,1}$ and counting small cliques

In this section we prove Theorem 1.3. Recall that it states that for $k<r$ and
$n$ large enough,
$\mathrm{ex}(n,K_{k},B_{r,1})={\mathcal{N}}(K_{k},T^{+}(n,r-1))$. We will use
the asymptotic result
$\mathrm{ex}(n,K_{k},B_{r,1})=(1+o(1)){\mathcal{N}}(K_{k},T^{+}(n,r-1))=(1+o(1)){\mathcal{N}}(K_{k},T(n,r-1))$.
It follows from a theorem of Alon and Shikhelman [2] that states that if
$\chi(F)=r>k$, then
$\mathrm{ex}(n,K_{k},F)=(1+o(1)){\mathcal{N}}(K_{k},T(n,r-1))$.

###### Proof.

Let $G$ be a $B_{r,1}$-free graph on $n$ vertices. By Theorem 2.2, if $G$ has
at least ${\mathcal{N}}(K_{k},T(n,r-1))-o(n^{k})$ copies of $K_{k}$, then $G$
can be obtained from $T(n,r-1)$ by adding and removing at most $\varepsilon
n^{2}$ edges. We consider the $(r-1)$-partite subgraph $G^{\prime}$ of $G$
with the most number of edges. Let $V_{1},\dots,V_{r-1}$ be the parts of
$G^{\prime}$, then there are $o(n^{2})$ edges inside the parts $V_{i}$.
Moreover, each vertex is connected to at most as many vertices in its part as
in any other part. Also, every $V_{i}$ has size $(1-o(1))\frac{n}{r-1}$.

Let us pick $\alpha<(r-2)/(r-1)$, and assume first that every vertex has
degree at least $\alpha n$. We partition $V_{i}$ to $V_{i}^{\prime}$ and
$V_{i}^{\prime\prime}$ with $V_{i}^{\prime}$ containing those vertices of
$V_{i}$ that are connected to all but $o(n)$ vertices outside $V_{i}$. By the
assumption on the degrees, all $v\in V_{i}^{\prime\prime}$ are incident to
$\Omega(n)$ edges inside $V_{i}$. This implies $|V_{i}^{\prime\prime}|=o(n)$.

We will use that for any $i$, for any set $U\subset
V_{1}^{\prime}\cup\dots,V_{i}^{\prime}$ with $|U|=O(1)$, the common
neighborhood of the vertices of $U^{\prime}$ contains all but $o(n)$ vertices
from $V_{i+1}^{\prime}\cup\dots\cup V^{\prime}_{r-1}$. In particular, if we
take at most four vertices from $V_{1}$, we can find a copy $B_{r,1}$ or
$B_{r,0}$ in their common neighborhood by picking the necessary vertices from
the other parts one by one. Let $m$ be the largest number of edges inside a
$V_{i}$, without loss of generality there are $m$ edges inside $V_{1}$.

Consider first the case that $m>1$. We claim that there cannot be two edges
within $V_{1}^{\prime}$. Indeed, if $u,v,w$ is a path, then in the common
neighborhood of $u,v,w$ outside $V_{1}$, we can find two disjoint cliques
$K_{1},K_{2}$ each of size $r-2$, so $G[K_{1},\cup K_{2},\cup\\{u,v,w\\}]$
contains a copy of $B_{r,1}$. Similarly, if $uv$ and $wz$ are edges in
$V_{1}$, then in the common neighborhood of $u,v,w,z$ outside $V_{1}$ one can
find a copy $B$ of $B_{r-2,1}$, and $B$ together with $u,v,w,z$ form a copy of
$B_{r,1}$. These contradictions prove our claim.

The remaining possibility is that there exists a vertex $u\in
V_{1}^{\prime\prime}$ and thus $u$ has $n^{\prime}=\Omega(n)$ neighbors in
$V_{1}$. We also know that for any $i>1$, $u$ has at least $n^{\prime}$
neighbors in $V_{i}$, thus at least $n^{\prime}-o(n)\geq n^{\prime}/2$
neighbors in $V_{i}^{\prime}$. Let $U_{i}$ be an arbitrary set of $\lceil
n^{\prime}/2\rceil$ neighbors of $u$ in $V_{i}$, and
$U=U_{2}\cup\dots,U_{r-1}$. We can now count the copies of $K_{k}$. There are
$o(n^{k})$ copies containing an edge inside a $V_{i}$. Let $G^{\prime\prime}$
denote the complete $(r-1)$-partite graph with parts $V_{1},\dots,V_{r-1}$.
Now compare the number of copies of $K_{k}$ inside $G^{\prime}$ to the number
of copies of $K_{k}$ in $G^{\prime\prime}$. We claim that that $U$ is
$2K_{r-2}$-free. Indeed, if $K_{1},K_{2}$ were two cliques of each of size
$r-2$ in $U$, then the common neighborhood of the of the vertices of
$K_{1}\cup K_{2}$ would contain all but $o(n)$ vertices in $V_{1}$, in
particular all but $o(n)$ neighbors of $u$. So $K_{1},K_{2},u$ and two such
neighbors would form a $B_{r,1}$ in $G$. This contradiction proves our claim.

The $2K_{r-2}$-free property yields that the number of copies of $K_{k}$
containing a vertex of $V_{1}$ and a $K_{k-1}$ inside $U$ is less in
$G^{\prime}$ by $\Theta(n^{k})$ than in $G^{\prime\prime}$. Indeed, there are
at most
$|V_{1}|\mathrm{ex}(|U|,K_{k-1},2K_{r-2})=(1+o(1))|V_{1}|{\mathcal{N}}(K_{k},T(|U|,r-3))$
such copies of $K_{k}$ in $G^{\prime}$ and
$|V_{1}|{\mathcal{N}}(K_{k},T(|U|,r-2))$ such copies of $K_{k}$ in
$G^{\prime\prime}$. This implies that $G$ has less copies of $K_{k}$ than a
complete $(r-1)$-partite graph, which has no more copies of $K_{k}$ than the
Turán graph, completing the proof in this case.

Assume now that $m=1$, i.e. there is at most one edge inside each $V_{i}$. If
there are at least two such edges, say $uv\in V_{1}$ and $xy\in V_{2}$, then
we pick $U=\\{u_{1},u_{3},\dots,u_{r-1}\\}$ and
$U^{\prime}=\\{v_{2},u_{3},v_{4},\dots,v_{r-1}\\}$ with $u_{i},v_{i}\in
V_{i}$. If both $U\cup\\{x,y\\}$ and $U^{\prime}\cup\\{u,v\\}$ induce cliques,
then we find $B_{r,1}$, a contradiction. Thus there is a missing edge between
parts $V_{i}$ among these vertices, thus there are $\Omega(n)$ missing edges
between parts altogether. We can again compare the number of copies of $K_{k}$
inside $G^{\prime}$ to the number of copies of $K_{k}$ in the complete
$(r-1)$-partite graph with parts $V_{1},\dots,V_{r-1}$. The additional at most
$r-1$ edges inside parts create $O(n^{k-2})$ copies of $K_{k}$, while the
missing edges between parts are in $\Omega(n^{k-1})$ copies of $K_{k}$.

If there is only one edge $uv$ inside a part, say $V_{1}$, then we have to
show that the order of the parts is as balanced as possible. If we have
$|V_{i}|\geq|V_{j}|+2$, then we move a vertex from $V_{i}$ to $V_{j}$. The
number of copies of $K_{k}$ not containing $uv$ increases by
$\Theta(n^{k-2})$, while the number of copies of $K_{k}$ containing $uv$
increases by $O(n^{k-3})$, completing the proof in this case.

Assume now that there are vertices of degree less than $\alpha n$. We erase
such vertices one by one till we arrive to a graph $G_{0}$ with no such
vertices. Assume that we removed $\ell$ vertices. If $\ell<n/2$, then $G_{0}$
has sufficiently many vertices, thus at most
${\mathcal{N}}(K_{k},T^{+}(n-\ell,r-1))$ copies of $K_{k}$ by the above part
of the proof. We removed at most $\ell\mathrm{ex}(\alpha
n,K_{k-1},2K_{r-1})=(1+o(1))\ell{\mathcal{N}}(K_{k-1},T(\alpha n,r-2))$ copies
of $K_{k}$, using Theorem 1.1. If we add $\ell$ vertices to
$T^{+}(n-\ell,r-1))$ to form the $T^{+}(n,r-1))$ instead, then we add
$(1+o(1))\ell{\mathcal{N}}(K_{k-1},T((r-2)n/(r-1),r-2))$ copies of $K_{k}$,
thus we obtain more copies than in $G$, completing the proof.

If $\ell>n/2$, then we cannot apply the earlier part of the proof, since
$|V(G_{0})|$ may not be large enough. However, we removed at most
$\ell\mathrm{ex}(\alpha
n,K_{k-1},2K_{r-1})=(1+o(1))\ell{\mathcal{N}}(K_{k-1},T(\alpha
n,r-2))=\ell{\mathcal{N}}(K_{k-1},T((r-2)n/(r-1),r-2))-\Theta(n^{k})$ copies
of $K_{k}$, and the resulting graph $G_{0}$ has at most
$(1+o(1)){\mathcal{N}}(K_{k},T^{+}(n-\ell,r-1))$ copies of $K_{k}$ by the
known asymptotic bound, completing the proof.

∎

##  5 Forbidding $B_{3,1}$ and counting complete bipartite graphs

Let us start this section by describing the symmetrization method due to Zykov
[34]. He used it to show that
$\mathrm{ex}(n,K_{k},K_{r})={\mathcal{N}}(K_{k},T(n,r-1))$. We say that we
symmetrize a vertex $u$ to another vertex $v$ in a graph $G$ when we delete
all the edges incident to $u$ and for each edge $vw$, we add the edge $uw$. In
other words, we replace the neighborhood of $u$ by the neighborhood of $v$. We
apply this operation to non-adjacent vertices. One can show that if $G$ is
$K_{r}$-free for some $r$, then the graph $G^{\prime}$ we obtain by
symmetrizing $u$ to $v$ is also $K_{r}$-free.

Let $d(H,v)$ denote the number of copies of $H$ containing a vertex $v$.
Extending Zykov’s idea, Győri, Pach and Simonovits [22] showed that if $H$ is
a complete multipartite graph and $d(H,u)\leq d(H,v)$, then this
symmetrization does not decrease the total number of copies of $H$. Thus, for
any pair of non-adjacent vertices $(u,v)$ we can symmetrize one to the other
such that the total number of copies of $H$ does not decrease. We apply such
symmetrization steps as long as we can find two non-adjacent vertices with
different neighborhoods. At the end of the symmetrization process we obtain a
$K_{r}$-free complete multipartite graph with at least ${\mathcal{N}}(H,G)$
copies of $H$, which implies that $\mathrm{ex}(n,H,K_{r})$ is attained by a
complete $(r-1)$-partite graph (one also needs to show that this process
terminates).

In a sense, this is the most general application of Zykov symmetrization for
generalized Turán problems: if $F$ is any graph that is not a clique, then
symmetrization may ruin the $F$-free property. If $H$ is any graph that is not
complete multipartite, then it is possible that both symmetrizing $u$ to $v$
and symmetrizing $v$ to $u$ decreases the total number of copies of $H$.
However, Liu and Wang [26] introduced a restricted version of symmetrization
that avoids the first of these problems. Here we state the general version of
the basic idea.

######  Proposition 5.1.

Let $G$ be a $B_{r,s}$-free graph, $u$ and $v$ be non-adjacent vertices of
$G$, and assume that $v$ is not a rootlet vertex of any $B_{r,s+1}$ in $G$.
Let $G^{\prime}$ be the graph obtained from $G$ by symmetrizing $u$ to $v$.
Then $G^{\prime}$ is $B_{r,s}$-free.

###### Proof.

Assume that there is a copy $B$ of $B_{r,s}$ in $G^{\prime}$. Then $B$ has to
contain $u$, otherwise $B$ would be contained in $G$. If $B$ does not contain
$v$, then we can replace $u$ with $v$ to obtain a copy of $B_{r,s}$ that is
also present in $G$, a contradiction. If $B$ contains $v$, then, as $u$ and
$v$ are not adjacent in $G^{\prime}$, they are both page vertices of $B$, on
different pages. But they have the same neighborhood, thus $v$ is connected to
every vertex of $B$ but $u$. Then the $s$ rootlet vertices of $B$ with $v$
form the rootlet vertices of a copy $B^{\prime}$ of $B_{r,s+1}$ in $G$, where
the pages of $B^{\prime}$ are the pages of $B$ without $u$ and $v$. Thus $v$
is a rootlet vertex of a $B_{r,s+1}$ in $G$, contradicting our assumption. ∎

Let us repeatedly apply symmetrization on the vertices that are not rootlet
vertices of any $B_{r,s+1}$. Assume that the process terminates and let
$G_{0}$ be the resulting graph. Let $G_{1}$ be the subgraph of $G_{0}$ induced
by vertices that are not rootlet vertices of any $B_{r,s+1}$ in $G_{0}$. Then
the proposition above implies that $G_{1}$ is a complete multipartite graph.
Moreover, vertices of the same partite set of $G_{1}$ have the exact same
neighborhood in the other vertices of $G_{0}$.

Now we are ready to prove Theorem 1.4 which we restate for convenience.

######  Theorem.

For any integers $a\leq b$ and $n$ large enough, we have that
$\mathrm{ex}(n,K_{a,b},B_{3,1})={\mathcal{N}}(K_{a,b},T)$ for some $n$-vertex
graph $T$ that is obtained from a complete bipartite graph by adding an edge.

###### Proof.

Let $G$ be an $n$-vertex $B_{3,1}$-free graph with $\mathrm{ex}(n,H,B_{3,1})$
copies of $H=K_{a,b}$. Let $Q$ denote the set of vertices in $G$ that are not
rootlet vertices of a $B_{3,2}$. If there are two non-adjacent vertices $u$
and $v$ in $Q$ with $d(H,u)<d(H,v)$, then we symmetrize $u$ to $v$ and obtain
a $B_{3,1}$-free graph with more copies of $H$, a contradiction. Thus we can
assume that non-adjacent vertices in $Q$ have the same $d(H,v)$ value (and
also later, after any symmetrization). This means that for non-adjacent
vertices $u$ and $v$, we can choose whether we symmetrize $u$ to $v$ or $v$ to
$u$ and the total number of copies of $H$ will not change.

Recall that $B_{3,2}$ consists of two triangles sharing an edge. We call the
graph consisting of $k\geq 2$ triangles sharing an edge a book graph with $k$
pages. Observe that for any vertex $v\in Q$ there exists at most one book
$B_{v}$ of which $v$ is a page vertex. Indeed, the two books have at least 3
rootlet vertices. If the two books have four rootlet vertices, we find a
$B_{3,1}$. Thus the two books have at least 3 rootlet vertices $x,y,z$, each
connected to $u$, such that $xy$ and $yz$ are in $E(G)$. If these three
vertices and $v$ induce a $K_{4}$, then $v$ is a rootlet vertex of a
$B_{3,2}$, a contradiction. Otherwise, there is a fifth vertex $w$ in one of
the books, without loss of generality $w$ is joined to $x$ and $y$ with an
edge. Then $x,y,w$ and $y,z,v$ form triangles sharing exactly one vertex, a
contradiction.

Let $u$ and $v$ be page vertices from different copies of $B_{3,2}$ that are
not rootlet vertices of any $B_{3,2}$. If $B_{u}$ has more pages than $B_{v}$,
then we symmetrize $v$ to $u$. If they have the same number of pages, then we
symmetrize arbitrarily. If $u$ is the page vertex of a $B_{3,2}$ but $v$ is
not, then we symmetrize $v$ to $u$. We claim that after such a symmetrization,
the total number of pages in the largest $i$ books does not decrease for any
$i$ and increases for some $i$. Indeed, observe that if $B_{v}$ is among the
largest $i$ books, then so is $B_{u}$. We deleted at most one page containing
$v$, but added a page when we connected $v$ to the neighbors of $u$. This
proves the first part of the claim. Assume that there are $i-1$ books with
more pages than $B_{u}$. Those are unaffected by the symmetrization, and
$B_{u}$ has one more page, proving the second part of our claim.

Let us apply such symmetrization steps as long as we can. We claim that after
finitely many steps this process terminates. Indeed, for any $i$ the total
number of pages in the largest $i$ books can increase at most $in$ times.

Let $G_{0}$ be the resulting graph, $G_{1}$ be the subgraph induced on the
vertices that are not rootlet vertices of any $B_{3,2}$ and $G_{2}$ be the
subgraph induced by the other vertices. Note that the vertex set of $G_{1}$
might be different from $Q$, as symmetrization may destroy or create copies of
$B_{3,2}$. Non-adjacent vertices of $G_{1}$ have the same neighborhood, as
otherwise we would symmetrize one vertex to another. This means that $G_{1}$
is a complete $m$-partite graph for some $m$ with partite sets
$A_{1},\dots,A_{m}$. Observe that $m\leq 3$ because there are no rootlet
vertices in $G_{1}$.

Observe that in a page vertex of a $B_{3,2}$ can be a rootlet vertex of a
$B_{3,2}$ only if the book is actually a $K_{4}$, as otherwise one can easily
find a $B_{3,1}$. Furthermore, every vertex outside the $K_{4}$ can have at
most one neighbor inside that $K_{4}$. This implies that for every $i\leq m$,
we have that the vertices of $A_{i}$ have at most one neighbor in a $K_{4}$.
If $u$ and $v$ are the rootlet vertices of a $B_{3,2}$ that is not a $K_{4}$,
then its page vertices are in $G_{1}$, and belong to the same partite set
$A_{i}$. It is easy to see that if $u^{\prime}v^{\prime}$ is an edge in
$G_{2}$ and $\\{u^{\prime},v^{\prime}\\}\neq\\{u,v\\}$, then we cannot have
that $u^{\prime}$ and $v^{\prime}$ are both connected to a vertex $w\in
A_{i}$. Indeed, if $u,v,u^{\prime},v^{\prime}$ are four vertices, then they
form $B_{3,1}$ with $v$. If, say, $u=u^{\prime}$, then $u,v^{\prime},w$ and
$u,v,w^{\prime}$ for any page vertex $w^{\prime}$ from $B_{w}$ form two
triangles sharing exactly one vertex. In other words, the only copies of
$B_{3,2}$ with page vertices in $A_{i}$ are those with rootlet vertices $u$
and $v$.

Assume first that $m=3$. Then $G_{1}$ is a triangle because there are no
rootlet vertices in $G_{1}$. Then $G_{0}$ is the vertex-disjoint union of a
$K_{3}$ and several copies of $K_{4}$, with additional edges between these
subgraphs. However, every vertex $v$ is connected to at most one vertex in
every copy of $K_{4}$ and $K_{3}$ (except the one containing $v$). This means
that the degree of $v$ is at most $d:=2+(n+1)/4$. Then we can count the copies
of $K_{a,b}$ the following way. Assume that $a\neq b$; if $a=b$, then each of
our bounds are divided by 2 because of symmetry. Either we pick a vertex $v$,
$a$ of its neighbors and $b-1$ of their common neighbors other than $v$, or
pick $b$ neighbors of $v$ and $a-1$ of their common neighbors other than $v$.
This way we count every copy of $K_{a,b}$ exactly $a+b$ times, since we can
pick any vertex as the first vertex. Thus we obtain the upper bound
$n(\binom{d}{a}\binom{d}{b-1}+\binom{d}{b}\binom{d}{a-1})/(a+b)$. We can count
the copies of $K_{a,b}$ in $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ the same
way and we get
$n(\binom{d^{\prime}}{a}\binom{d^{\prime}}{b-1}+\binom{d^{\prime}}{b}\binom{d^{\prime}}{a-1})/(a+b)$
copies, where $d^{\prime}=\lfloor n/2\rfloor$. Clearly this is a larger number
if $n$ is large enough, a contradiction to our assumption that $G$ is
extremal.

Assume now that $m\leq 2$. We will handle together the cases $m=1$ and $m=2$;
in what follows $A_{2}$ may be empty. Observe that $G_{2}$ contains at most
two edges $uv$ and $u^{\prime}v^{\prime}$ such that $u,v$ are connected to the
vertices in $A_{1}$ and $u^{\prime},v^{\prime}$ are connected to the vertices
of $A_{2}$. $G_{2}$ also may contain several copies of $K_{4}$, with
additional edges between these subgraphs. However, at most one vertex of those
copies of $K_{4}$ can be connected to vertices in $A_{i}$ for every $i$. Also,
such a vertex can be connected to vertices of at most one of $A_{1}$ and
$A_{2}$ otherwise $G_{0}$ would contain a $K_{4}$ and a $K_{3}$ meeting in
exactly one vertex, thus a $B_{3,1}$.

Let us assume that there are $p\geq 1$ copies of $K_{4}$ in $G_{0}$ and let
$U$ be the set of their vertices. Recall that $G_{2}$ has at most 4 other
vertices: $u,v$ connected to the vertices in $A_{1}$ and
$u^{\prime},v^{\prime}$ are connected to the vertices of $A_{2}$. Let us
obtain $G_{0}^{\prime}$ the following way. For each vertex $w\in U$, we delete
the edges incident to $w$. If $w$ is connected to the vertices of $A_{1}$, we
add $w$ to $A_{2}^{\prime}$, and if $w$ is connected to the vertices of
$A_{2}$, we add $w$ to $A_{1}^{\prime}$. Then we add the remaining vertices of
$U$ to $A_{1}^{\prime}$ and $A_{2}^{\prime}$ such that for each $K_{4}$, 2 of
its vertices are in $A_{1}^{\prime}$ and 2 are in $A^{\prime}_{2}$. Finally,
we add $A_{1}$ to $A_{1}^{\prime}$ and $A_{2}$ to $A_{2}^{\prime}$. Then we
connect the vertices of $A_{1}^{\prime}$ to the vertices of $A_{2}^{\prime}$
and to $u$ and $v$, and similarly we connect the vertices of $A_{2}^{\prime}$
to $u^{\prime}$ and $v^{\prime}$. Clearly $G_{0}^{\prime}$ is $B_{3,1}$-free.

######  Claim 5.2.

$G_{0}^{\prime}$ contains more copies of $K_{a,b}$ than $G_{0}$.

###### Proof.

Assume first that $p\geq 4$. Then the degree of a vertex $w$ has not
decreased. If $w\in A_{1}\cup A_{2}$, then the edges incident to $w$ in
$G_{0}$ are also in $G_{0}^{\prime}$. Otherwise, $w$ was connected to at most
$p+2$ vertices of $U$ in $G_{0}$ and is connected to $2p$ vertices of $U$ in
$G_{0}^{\prime}$. Furthermore, if $w$ was connected to vertices in $G_{1}$,
those edges remain intact. Finally, $w$ was connected to at most 3 vertices
out of $u,v,u^{\prime},v^{\prime}$.

Consider a copy $H_{0}$ of $K_{a,b}$ in $G_{0}$ that intersects $G_{1}$ in a
non-empty set $X$ of vertices. If $X$ intersects both partite sets of $G_{1}$,
then $H_{0}$ is also in $G_{0}^{\prime}$, as the edges of $G_{0}$ that are
incident to vertices of $G_{1}$ are present in $G_{0}^{\prime}$. If $X$ is a
subset of $A_{1}$, then they belong to the same partite set of $H_{0}$ and the
other partite set of $H_{0}$ belongs to the set of vertices connected to
$A_{1}$ in $G_{0}$. Thus we have to pick the remaining vertices of $H_{0}$
from the common neighbors of these vertices; they have more common neighbors
in $G_{0}^{\prime}$, thus we can find more copies of $K_{a,b}$ this way in
$G_{0}^{\prime}$. This shows that there are more copies of $K_{a,b}$ in
$G_{0}^{\prime}$ intersecting $A_{1}\cup A_{2}$ than in $G_{0}$.

Finally, if a copy of $K_{a,b}$ does not intersect $G_{1}$, then we can pick
it the following way. We pick a vertex $w$, then we pick either $b$ of its (at
most $p+2$) neighbors in $G_{2}$ and $a-1$ of the at most $(p+2$) common
neighbors of those in $G_{2}$, or we pick $a$ of its neighbors and $b-1$ of
their common neighbors. We can pick more copies of $K_{a,b}$ in
$G_{0}^{\prime}$ the same way, as there are $2p$ neighbors of $w$ from
$V(G_{2})$ in $G_{0}^{\prime}$ and those have at least $2p$ common neighbors
from $V(G_{2})$ in $G_{0}^{\prime}$.

Assume now that $1\leq p\leq 3$. Observe that if $|A_{1}|=o(n)$ or
$|A_{2}|=o(n)$ then we have $o(n^{a+b})$ copies of $K_{a,b}$ in $G_{0}$, less
than in $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$, a contradiction. In a
$K_{4}$, at most two vertices are connected to vertices in $G_{1}$, and the
other at least two vertices have degree at most $4+p\leq 7$ in $G_{0}$. By
deleting the edges incident to them we removed $O(n^{b-1})$ copies of
$K_{a,b}$. By adding them to $A_{1}$ or $A_{2}$, we added $\Omega(n^{a+b-1})$
copies of $K_{a,b}$, a contradiction. ∎

The above claim finishes the proof if $p\geq 1$. Finally, if $p=0$, then
$G_{0}$ without $uv$ and $u^{\prime}v^{\prime}$ is a complete bipartite graph,
thus we are done if $m=1$ or if $u^{\prime}v^{\prime}$ does not exist. Observe
that a triangle on the vertices $u,v,u^{\prime},v^{\prime}$ would create a
$B_{3,1}$ with a vertex of $A_{1}$ or $A_{2}$. Thus, we can assume without
loss of generality that $uu^{\prime}$ and $vv^{\prime}$ are not edges of
$G_{0}$. Let $G_{0}^{\prime\prime}$ be the graph obtained by deleting from
$G_{0}$ the edge $u^{\prime}v^{\prime}$ and adding $uu^{\prime}$ and
$vv^{\prime}$. We have removed some copies of $K_{a,b}$ only if $a=b=2$ or if
$a=1$. In the first case, we removed only one copy, and we created more copies
of $K_{2,2}$. In the second case, the degree of every vertex remained the same
or (for two vertices) increased. Thus in both cases, the number of copies of
$K_{a,b}$ increased, a contradiction. ∎

Funding: Research supported by the National Research, Development and
Innovation Office - NKFIH under the grants KH 130371, SNN 129364, FK 132060,
and KKP-133819, and by the Ministry of Education and Science of the Russian
Federation in the framework of MegaGrant no. 075-15-2019-1926.

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, Journal of Combinatorial Theory, Series A, 76(1), (1996), 121–138.
  * [2] N. Alon, C. Shikhelman, Many $T$ copies in $H$-free graphs, Journal of Combinatorial Theory, Series B, 121, (2016) 146–172.
  * [3] B. Andrásfai, P. Erdős, V.T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Mathematics, 8(3), (1974), 205–218.
  * [4] B. Bollobás, E. Győri, Pentagons vs. triangles, Discrete Mathematics, 308(19), (2008), 4332–4336.
  * [5] G. Chen, R. J. Gould, F. Pfender, B. Wei, Extremal graphs for intersecting cliques, Journal of Combinatorial Theory Series B, 89, (2003) 159–171.
  * [6] L. H. Clark, R. C. Entringer, J. E. McCanna, L. A. Székely, Extremal problems for local properties of graphs, Australasian Journal of Combinatorics, 4, (1991), 25–32.
  * [7] P. Erdős, Z. Füredi, R.J. Gould, D. S. Gunderson, Extremal graphs for intersecting triangles. Journal of Combinatorial Theory, Series B, 64, (1995), 89–100.
  * [8] P. Erdős, On some new inequalities concerning extremal properties of graphs, in 1968 Theory of Graphs (Proc. Colloq., Tihany, 1966) 77–81.
  * [9] P. Erdős, P. Frankl, V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics, 2(1), (1986), 113–121.
  * [10] P. Erdős, M. Simonovits, A limit theorem in graph theory, Studia Scientarum Mathematicarum Hungarica 1, (1966), 51–57.
  * [11] P. Frankl, On intersecting families of finite sets. Journal of Combinatorial Theory, Series A, 24(2), (1978), 146–161.
  * [12] P. Frankl, Z. Füredi, Forbidding just one intersection, Journal of Combinatorial Theory, Series A, 39(2), (1985), 160–176.
  * [13] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, In Erdős Centennial, pp. 169–264. Springer, Berlin, Heidelberg, 2013.
  * [14] D. Gerbner, Generalized Turán problems for small graphs, arXiv preprint arXiv:2006.16150, 2020.
  * [15] D. Gerbner, On Turán-good graphs, Discrete Mathematics 344(8), (2021), 112445
  * [16] D. Gerbner, Counting multiple graphs in generalized Turán problems, arXiv preprint arXiv:2007.11645, 2020.
  * [17] D. Gerbner, T. Mészáros, A. Methuku, C. Palmer, Generalized rainbow Turán problems, arXiv preprint arXiv:1911.06642, 2019.
  * [18] D. Gerbner, A. Methuku, M. Vizer, Generalized Turán problems for disjoint copies of graphs, Discrete Mathematics, 342(11), (2019), 3130–3141.
  * [19] D. Gerbner, C. Palmer, Some exact results for generalized Turán problems, arXiv preprint arXiv:2006.03756, 2020.
  * [20] W.T. Gowers, B. Janzer, Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques. Combinatorics, Probability and Computing, 30(4), (2021), 1–18.
  * [21] A. Grzesik, On the maximum number of five-cycles in a triangle-free graph. Journal of Combinatorial Theory, Series B, 102(5), (2012), 1061–1066.
  * [22] E. Győri, J. Pach, M. Simonovits, On the maximal number of certain subgraphs in $K_{r}$-free graphs, Graphs and Combinatorics, 7(1), (1991), 31–37.
  * [23] H. Hatami, J. Hladký, D. Král’, S. Norine, A. Razborov, On the number of pentagons in triangle-free graphs, Journal of Combinatorial Theory, Series A, 120(3), (2013), 722–732.
  * [24] G. O. H. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq. Tihany, 1966, pp. 187–207, Akad. Kiadó, Budapest, 1968.
  * [25] J. B. Kruskal, The number of simplices in a complex, in: Math. Optimization Techniques, pp. 251–278, Univ. of Calif. Press, Berkeley, 1963.
  * [26] E.L. Liu, J. Wang, The Generalized Turán Problem of Two Intersecting Cliques, arXiv preprint arXiv:2101.08004, 2021.
  * [27] L. Lovász, Combinatorial problems and exercises, Amsterdam: North-Holland. 1993.
  * [28] J. Ma, Y. Qiu, Some sharp results on the generalized Turán numbers, European Journal of Combinatorics, 84, (2020), 103026.
  * [29] J. W. Moon, On independent complete subgraphs in a graph, Canadian Journal of Mathematics, 20, (1968), 95–102.
  * [30] I. Z. Ruzsa E. Szemerédi, Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18, (1978), 939–945.
  * [31] Richard H. Schelp, Andrew Thomason, A Remark on the Number of Complete and Empty Subgraphs. Comb. Probab. Comput. 7(2), (1998), 217–219.
  * [32] M. Simonovits, A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 279–319. 1968.
  * [33] V.T. Sós, Remarks on the connection of graph theory, finite geometry and block designs. Téorie Combinatorie 2, (1976), 223–233.
  * [34] A. A. Zykov, On some properties of linear complexes, Matematicheskii sbornik, 66(2), (1949), 163–188.