# A note on extremal constructions
for the Erdős–Rademacher problem

Xizhi Liu Research was supported by ERC Advanced Grant 101020255 and
Leverhulme Research Project Grant RPG-2018-424. Email<EMAIL_ADDRESS>Mathematics Institute and DIMAP,
University of Warwick,
Coventry, CV4 7AL, UK  Oleg Pikhurko Research was supported by ERC Advanced
Grant 101020255 and Leverhulme Research Project Grant RPG-2018-424. Email:
<EMAIL_ADDRESS>Mathematics Institute and DIMAP,
University of Warwick,
Coventry, CV4 7AL, UK

###### Abstract

For given positive integers $r\geq 3$, $n$ and $e\leq\binom{n}{2}$, the famous
Erdős–Rademacher problem asks for the minimum number of $r$-cliques in a graph
with $n$ vertices and $e$ edges. A conjecture of Lovász and Simonovits from
the 1970s states that, for every $r\geq 3$, if $n$ is sufficiently large then,
for every $e\leq\binom{n}{2}$, at least one extremal graph can be obtained
from a complete partite graph by adding a triangle-free graph into one part.

In this note, we explicitly write the minimum number of $r$-cliques predicted
by the above conjecture. Also, we describe what we believe to be the set of
extremal graphs for any $r\geq 4$ and all large $n$, amending the previous
conjecture of Pikhurko and Razborov.

Keywords: Erdős–Rademacher problem, Lovász–Simonovits conjecture, Clique
density theorem.

##  1 Introduction

Given integers $n\geq r\geq 2$, let $T_{r}(n)$ denote the balanced complete
$r$-partite graph on $n$ vertices, and let $t_{r}(n)$ denote the number of
edges in $T_{r}(n)$. The celebrated Turán Theorem [24] (with the case $r=3$
proved earlier by Mantel [13]) states that, for $n\geq r\geq 3$, every
$n$-vertex graph with at least $t_{r-1}(n)+1$ edges contains a copy of an _$r$
-clique_ $K_{r}$, that is, a complete graph on $r$ vertices. An unpublished
result of Rademacher from 1941 (see [3]) states that, in fact, every
$n$-vertex graph with $t_{2}(n)+1$ edges contains at least $\left\lfloor
n/2\right\rfloor$ copies of $K_{3}$. The graph obtained from $T_{2}(n)$ by
adding one edge to the larger part shows that the bound $\left\lfloor
n/2\right\rfloor$ is tight. Rademacher’s theorem motivated Erdős [3] to
consider the following more general question, now referred to as the
_Erdős–Rademacher problem_ : determine

$\displaystyle g_{r}(n,e):=\min\Big{\\{}N(K_{r},G)\colon\text{$G$ is an
$(n,e)$-graph}\Big{\\}},$ (1)

where an _$(n,e)$ -graph_ means a graph with $n$ vertices and $e$ edges and
$N(K_{r},G)$ denotes the number of $r$-cliques in $G$.

This problem has attracted a lot of attention and has been actively studied
since it first appeared. Various results covering special ranges of $(n,e)$
were obtained (see e.g. [7, 4, 14, 20, 2, 11, 18, 19, 5, 6]) until Razborov
[22] determined the asymptotic value of $g_{3}(n,e)$ using flag algebras.
Later, using different methods, Nikiforov [17] determined the asymptotic value
of $g_{r}(n,e)$ for $r=4$ and Reiher [23] did this for all $r\geq 5$. For some
further related results, we refer the reader to [15, 16, 21, 8, 25, 10, 1].

Determining the exact value of $g_{r}(n,e)$ seems very challenging due to
multiple (conjectured) extremal constructions. Given $n$ and $e$ in
$\mathbb{N}:=\\{1,2,\dots\\}$ with $e\leq\binom{n}{2}$, let

$\displaystyle k=k(n,e):=\min\left\\{s\in\mathbb{N}\colon t_{s}(n)\geq
e\right\\},$ (2)

that is, $k$ is the smallest chromatic number that an $(n,e)$-graph can have.
Let $\mathcal{H}_{1}(n,e)$ (resp. $\mathcal{K}(n,e)$) denote the family of
$(n,e)$-graphs that can be obtained from a complete $(k-1)$-partite (resp.
complete multipartite) graph by adding a triangle-free graph into one part.
Note that the only difference between these two definitions is that we
restrict the number of parts to $k-1$ when defining $\mathcal{H}_{1}(n,e)$;
thus $\mathcal{H}_{1}(n,e)\subseteq\mathcal{K}(n,e)$. Lovász and Simonovits
[11] conjectured that for every integer $r\geq 3$ there exists $n_{0}$ such
that, for all positive integers $n\geq n_{0}$ and $e\leq\binom{n}{2}$, it
holds that

$\displaystyle g_{r}(n,e)=\min\Big{\\{}N(K_{r},H)\colon
H\in\mathcal{K}(n,e)\Big{\\}},$ (3)

that is, at least one $g_{r}(n,e)$-extremal graph is in $\mathcal{K}(n,e)$.
Note that (3) trivially holds for $e\leq t_{r-1}(n)$ when $g_{r}(n,e)=0$.

Erdős in [3] (resp. [4]) showed that (3) is true for $r=3$ when $e\leq
t_{2}(n)+3$ (resp. $e\leq t_{2}(n)+cn$ for some constant $c>0$). Lovász and
Simonovits [11] (see also Nikiforov and Khadzhiivanov [19]) extended the
result of Erdős to all $e$ satisfying $e\leq t_{2}(n)+\lfloor n/2\rfloor$.
Later, Lovász and Simonovits [12] proved (3) for $r\geq 3$ when
$e/\binom{n}{2}$ lies in a small upper neighborhood of $1-1/m$ for some
integer $m\geq r-1$. More recently, Liu, Pikhurko and Staden [9] determined
$g_{3}(n,e)$ for all positive integers $n$ when $e\leq(1-o(1))\binom{n}{2}$.
Determining the exact value of $g_{r}(n,e)$ for $r\geq 4$ is still wide open
in general.

Given $n,e\in\mathbb{N}$ with $e\leq\binom{n}{2}$, let
$\bm{a}^{\ast}=\bm{a}^{\ast}(n,e)\in\mathbb{N}^{k}$ be the unique vector such
that

$\displaystyle a_{k}^{\ast}:=\min\left\\{a\in\mathbb{N}\colon
a(n-a)+t_{k-1}(n-a)\geq e\right\\},$ $\displaystyle
a_{1}^{\ast}+\dots+a_{k-1}^{\ast}=n-a_{k}^{\ast},\quad\text{and}\quad
a_{1}^{\ast}\geq\dots\geq a_{k-1}^{\ast}\geq a_{1}^{\ast}-1,$

where $k=k(n,e)$ is as defined in (2). Thus $a_{k}^{\ast}$ is the smallest
possible part size that a $k$-partite $(n,e)$-graph can have. Also, let

$\displaystyle m^{\ast}=m^{\ast}(n,e)$
$\displaystyle:=\sum_{\\{i,j\\}\in\binom{[k]}{2}}a_{i}^{\ast}a_{j}^{\ast}-e,\quad\text{and}\quad$
$\displaystyle h^{\ast}_{r}(n,e)$
$\displaystyle:=\sum_{I\in\binom{[k]}{r}}\prod_{i\in
I}a_{i}^{\ast}-m^{\ast}\cdot\sum_{I^{\prime}\in\binom{[k-2]}{r-2}}\prod_{j\in
I^{\prime}}a_{j}^{\ast},$

where $[k]:=\\{1,\dots,k\\}$. Let $T:=K[A_{1}^{\ast},\ldots,A_{k}^{\ast}]$ be
the complete $k$-partite graph with parts $A_{1}^{\ast},\dots,A_{k}^{\ast}$
where $|A_{i}^{\ast}|=a_{i}^{\ast}$ for $i\in[k]$. Let
$H^{\ast}=H^{\ast}(n,e)$ be the graph obtained from $T$ by removing an
$m^{\ast}$-edge star whose centre lies in $A_{k}^{\ast}$ and whose leaves lie
in $A_{k-1}^{\ast}$. It is not hard to see (see e.g. the calculation in (10))
that $0\leq m^{\ast}\leq a_{k-1}^{\ast}-a_{k}^{\ast}$, so the graph $H^{\ast}$
is well-defined. Also, let $\mathcal{H}_{1}^{\ast}(n,e)$ be the family defined
as follows: If $m^{\ast}=0$, take all graphs obtained from $T$ by replacing,
for some $i\in[k-1]$, the bipartite graph $T[A_{i}^{\ast}\cup A_{k}^{\ast}]$
with an arbitrary triangle-free graph with $a_{i}^{\ast}a_{k}^{\ast}$ edges.
If $m^{\ast}>0$, take all graphs obtained from $T$ by replacing
$T[A_{k-1}^{\ast}\cup A_{k}^{\ast}]$ with an arbitrary triangle-free graph
with $a_{k-1}^{\ast}a_{k}^{\ast}-m^{\ast}$ edges. Observe that
$\mathcal{H}_{1}^{\ast}(n,e)\subseteq\mathcal{H}_{1}(n,e)$ and every graph in
$\mathcal{H}_{1}^{\ast}(n,e)$ has the same number of $r$-cliques (see Fact
2.2); also, the graph $H^{*}=H^{*}(n,e)$ is contained in
$\mathcal{H}_{1}^{\ast}(n,e)$.

Sharpening the Lovász–Simonovits Conjecture, Pikhurko and Razborov [21,
Conjecture 1.4] conjectured that, for $r\geq 4$ and sufficiently large $n$,
every $n$-vertex graph with $e\leq\binom{n}{2}$ edges and that contains the
minimum number of $K_{r}$ is in $\mathcal{K}(n,e)$. However, we show here that
this conjecture is false and present an amended version as follows.

First, we write explicitly the value of $g_{r}(n,e)$ predicted by the
Lovász–Simonovits Conjecture. (We also refer the reader to [9, Proposition
1.5] where similar results are proved for $r=3$.)

######  Theorem 1.1.

Suppose that $r,n,e\in\mathbb{N}$ satisfy $n\geq r\geq 3$ and
$e\leq\binom{n}{2}$. Then

$\displaystyle\min\Big{\\{}N(K_{r},G)\colon
G\in\mathcal{K}(n,e)\Big{\\}}=h_{r}^{\ast}(n,e).$ (4)

Moreover, if $r\geq 4$ and $e>t_{r-1}(n)$, then

$\displaystyle\Big{\\{}G\in\mathcal{K}(n,e)\colon
N(K_{r},G)=h_{r}^{\ast}(n,e)\Big{\\}}$
$\displaystyle=\mathcal{H}_{1}^{\ast}(n,e).$ (5)

Note that, since $\mathcal{H}_{1}^{\ast}(n,e)\subseteq\mathcal{H}_{1}(n,e)$,
Theorem 1.1 remains true if we replace $\mathcal{K}(n,e)$ by
$\mathcal{H}_{1}(n,e)$. In fact, the later version of the Lovász–Simonovits
Conjecture from [12] states that, for all sufficiently large $n\geq n_{0}(r)$,
at least one $g_{r}(n,e)$-extremal graph is in $\mathcal{H}_{1}(n,e)$. By (4),
these two conjectures are equivalent. One should be able to show with some
extra work that (5) also holds for $r=3$. Since our main focus is the case
$r\geq 4$, we do not pursue this strengthening here.

Given integers $n,e\in\mathbb{N}$ with $e\leq\binom{n}{2}$, we define the
family $\mathcal{H}_{2}^{\ast}(n,e)$ as follows (with
$k,\bm{a}^{\ast},m^{\ast}$ being as before). Take those graphs in
$\mathcal{H}_{1}^{\ast}(n,e)$ that are $k$-partite, along with the following
family. Take disjoint sets $A_{1},\ldots,A_{k}$ of sizes
$a_{1}^{\ast},\ldots,a_{k}^{\ast}$, respectively, and let $m:=m^{\ast}$. If
$m^{\ast}=0$ and $a_{1}^{\ast}\geq a_{k}^{\ast}+2$, then we also allow
$\left(|A_{1}|,\ldots,|A_{k}|\right)=\left(a_{2}^{\ast},\ldots,a_{k-1}^{\ast},a_{1}^{\ast}-1,a_{k}^{\ast}+1\right)$
and let $m:=a_{1}^{\ast}-a_{k}^{\ast}-1$. Take all graphs obtained from
$K[A_{1},\ldots,A_{k}]$ by removing $m$ edges, each connecting $B_{i}$ to
$A_{i}$ for some $i\in I$, where
$I:=\left\\{i\in[k-1]\colon|A_{i}|=|A_{k-1}|\right\\}$ and
$\left\\{B_{i}\colon i\in I\right\\}$ are some pairwise disjoint subsets of
$A_{k}$. Clearly, every graph in $\mathcal{H}_{2}^{\ast}(n,e)$ is an
$(n,e)$-graph.

######  Proposition 1.2.

Suppose that $n\geq r\geq 4$ and $t_{r-1}(n)<e\leq\binom{n}{2}$ are integers.
Then

$\displaystyle N(K_{r},G)=h_{r}^{\ast}(n,e),\quad\text{for every\
}G\in\mathcal{H}_{2}^{\ast}(n,e).$

Also, there are infinitely many pairs $(n,e)\in\mathbb{N}^{2}$ with
$t_{r-1}(n)<e\leq\binom{n}{2}$ such that
$\mathcal{H}_{2}^{\ast}(n,e)\setminus\mathcal{H}_{1}^{\ast}(n,e)\neq\emptyset$.

We propose the following amended conjecture.

######  Conjecture 1.3.

Let $r\geq 4$. For every sufficiently large integer $n$ and every integer $e$
with $t_{r-1}(n)<e\leq\binom{n}{2}$, it holds that

$\displaystyle\Big{\\{}G\colon\text{$G$ is an $(n,e)$-graph with
$N(K_{r},G)=g_{r}(n,e)$}\Big{\\}}=\mathcal{H}_{1}^{\ast}(n,e)\cup\mathcal{H}_{2}^{\ast}(n,e).$

For comparison with the case $r=3$, the exact result of Liu, Pikhurko and
Staden [9] valid for $e\leq(1-o(1))\binom{n}{2}$ states that the set of
$g_{3}(n,e)$-extremal graphs is exactly
$\mathcal{H}_{0}^{\ast}(n,e)\cup\mathcal{H}_{2}^{\ast}(n,e)$ for a certain
explicit family
$\mathcal{H}_{0}^{\ast}(n,e)\supseteq\mathcal{H}_{1}^{\ast}(n,e)$, where the
inclusion is strict for infinitely many pairs $(n,e)$. However, for $r\geq 4$
and $e>t_{r-1}(n)$, every graph in
$\mathcal{H}_{0}^{\ast}(n,e)\setminus\mathcal{H}_{1}^{\ast}(n,e)$ can be shown
to have more $K_{r}$’s than $H^{\ast}(n,e)$. (Basically, each such graph is
obtained from a complete $(k-1)$-partite graph by adding edges into more than
one parts and cannot minimise the number of $K_{r}$’s for $r\geq 4$ by Lemma
2.5.)

For the purposes of this paper (namely for Proposition 1.2), only the
difference $\mathcal{H}_{2}^{\ast}(n,e)\setminus\mathcal{H}_{1}^{\ast}(n,e)$
matters; we use the current definitions merely so that the families
$\mathcal{H}_{i}^{\ast}(n,e)$ and $\mathcal{H}_{i}(n,e)$ are the same as in
[9].

The rest of the paper of organised as follows. In the next section, we present
some definitions and preliminary results. As a step towards proving Theorem
1.1, we first find extremal graphs in a certain family $\mathcal{H}_{0}(n,e)$
in Section 3 (see Proposition 3.1 for the exact statement). We derive Theorem
1.1 in Section 4. The proof of Proposition 1.2 is presented in Section 5.

##  2 Preliminaries

Given $\ell$ pairwise disjoint sets $A_{1},\ldots,A_{\ell}$, we use
$K[A_{1},\ldots,A_{\ell}]$ to denote the complete ${\ell}$-partite graph with
parts $A_{1},\ldots,A_{\ell}$; if we care only about the isomorphism type of
this graph (i.e. only the sizes of the parts matter), we may instead write
$K_{a_{1},\ldots,a_{\ell}}$, where $a_{i}:=|A_{i}|$ for $i\in[\ell]$.

Let $G=(V,E)$ be a graph. By $|G|$ we denote the number of edges in $G$. Let
$\overline{G}:=\left(V,\binom{V}{2}\setminus E\right)$ denote the _complement_
of $G$. The subgraph of $G$ _induced_ by a set $A\subseteq V$ is
$G[A]:=\left(A,\binom{A}{2}\cap E\right)$. For disjoint $A,B\subseteq V$, we
use $G[A,B]$ to denote the induced bipartite graph with parts $A$ and $B$
(which consists of edges connecting $A$ to $B$).

In the remainder of this note, we assume unless it is stated otherwise that
$r,n,e\in\mathbb{N}$ satisfy $r\geq 3$ and $e\leq\binom{n}{2}$ (and we
minimise the number of $r$-cliques over $(n,e)$-graphs). Also, $k=k(n,e)$ is
defined in (2).

Given a family $\mathcal{F}$ of $(n,e)$-graphs, we use $\mathcal{F}^{\min}$ to
denote the collection of graphs $F\in\mathcal{F}$ with the minimum number of
$K_{r}$’s (over all graphs in $\mathcal{F}$). For convenience, we set
$N(K_{0},G):=1$ and $N(K_{-1},G):=0$ for all graphs $G$.

Let the family $\mathcal{H}_{0}(n,e)$ be the collection of all $(n,e)$-graphs
that can be obtained from an $n$-vertex complete $(k-1)$-partite graph by
adding a (possibly empty) triangle-free graph into each part. It is clear from
the definition that $\mathcal{H}_{1}(n,e)\subseteq\mathcal{H}_{0}(n,e)$.

The following fact follows from some simple calculations (with the argument
for Part (i) being the same as in (10)).

######  Fact 2.1.

Let $k,\bm{a}^{\ast},m^{\ast},H^{\ast}$, and $h_{r}^{\ast}(n,e)$ be as defined
in Section 1. Then it holds for all $r\geq 3$ that

  1. (i)

$0\leq m^{\ast}\leq a_{k-1}^{\ast}-a_{k}^{\ast}$,

  2. (ii)

$|K_{a_{1}^{\ast},\ldots,a_{k}^{\ast}}|-|K_{a_{1}^{\ast},\ldots,a_{k-2}^{\ast},a_{k-1}^{\ast}+1,a_{k}^{\ast}-1}|=a_{k-1}^{\ast}-a_{k}^{\ast}+1$,

  3. (iii)

$N(K_{r},H^{\ast})=h^{\ast}_{r}(n,e)\geq g_{r}(n,e)$.

We also need the following simple facts for counting $r$-cliques in some
special classes of graphs.

######  Fact 2.2.

Let $G$ be a graph, $S\subseteq V(G)$ be a vertex set, and
$\overline{S}:=V(G)\setminus S$. Suppose that the induced subgraph $G[S]$ is
triangle-free, and the induced bipartite graph $G[S,\overline{S}]$ is
complete. Then

$\displaystyle N(K_{r},G)=|G[S]|\cdot N(K_{r-2},G[\overline{S}])+|S|\cdot
N(K_{r-1},G[\overline{S}])+N(K_{r},G[\overline{S}]).$

######  Fact 2.3.

Suppose that $G$ is a graph obtained from $K[V_{1},\ldots,V_{\ell}]$ by adding
a triangle-free graph. Let $S:=V_{1}\cup V_{2}$ and
$\overline{S}:=V(G)\setminus S$. Then

$\displaystyle N(K_{r},G)\ =\ $ $\displaystyle|G[V_{1}]|\cdot|G[V_{2}]|\cdot
N(K_{r-4},G[\overline{S}])$
$\displaystyle+\left(|G[V_{1}]|\cdot|V_{2}|+|G[V_{2}]|\cdot|V_{1}|\right)\cdot
N(K_{r-3},G[\overline{S}])$ $\displaystyle+|G[S]|\cdot
N(K_{r-2},G[\overline{S}])+|S|\cdot
N(K_{r-1},G[\overline{S}])+N(K_{r},G[\overline{S}]).$

######  Fact 2.4.

Let $G$ be a graph, $S\subseteq V(G)$, and $\overline{S}:=V(G)\setminus S$.
Suppose that the induced subgraph $G[S]$ is $3$-partite, and the induced
bipartite subgraph $G[S,\overline{S}]$ is complete. Then

$\displaystyle N(K_{r},G)=N(K_{3},G[S])\cdot N(K_{r-3},G[\overline{S}])$
$\displaystyle+|G[S]|\cdot N(K_{r-2},G[\overline{S}])$ $\displaystyle+|S|\cdot
N(K_{r-1},G[\overline{S}])+N(K_{r},G[\overline{S}]).$

We will also use the following results.

######  Lemma 2.5.

Let $r\geq 4$ and let $n,e\in\mathbb{N}$ satisfy
$t_{r-1}(n)<e\leq\binom{n}{2}$. Suppose that $G\in\mathcal{H}^{\min}_{0}(n,e)$
is a graph with a vertex partition $V(G)=B_{1}\cup\ldots\cup B_{k-1}$ such
that $G$ is the union of $K[B_{1},\ldots,B_{k-1}]$ with a triangle-free graph.
Then $G$ contains at most one part $B_{i}$ which is _partially full_ , meaning
that $0<|G[B_{i}]|<t_{2}(|B_{i}|)$.

###### Proof.

Suppose to the contrary that $G$ contains two partially full parts $B_{i}$ and
$B_{j}$ for some $1\leq i<j\leq k-1$. Let $x:=|G[B_{i}]|$,
$\sigma:=|G[B_{i}]|+|G[B_{j}]|$ and $H:=G[V(G)\setminus(B_{i}\cup B_{j})]$.
Observe from Fact 2.3 that there exist constants $C_{2},C_{3},C_{4}$ depending
on $|B_{i}|$, $|B_{j}|$ and $H$ (but not on $x$) such that

$\displaystyle N(K_{r},G)=N(K_{r-4},H)\cdot
x(\sigma-x)+C_{2}x+C_{3}(\sigma-x)+C_{4}=:P(x).$

Let $G_{i}$ be the graph obtained from $G$ by moving one edge from $G[B_{j}]$
to $G[B_{i}]$ and rearranging the latter graph to be still $K_{3}$-free, which
is possible by Mantel’s theorem. Similarly, let $G_{j}$ be the graph obtained
from $G$ by moving one edge from $G[B_{i}]$ to $G[B_{j}]$. Note that
$N(K_{r},G_{i})=P(x+1)$ and $N(K_{r},G_{j})=P(x-1)$. Since $k\geq r$, we have

$P(x+1)+P(x-1)-2P(x)=-2N(K_{r-4},H)<0.$ (6)

Thus $\min\left\\{N(K_{r},G_{i}),N(K_{r},G_{j})\right\\}<N(K_{r},G)$,
contradicting the minimality of $G$.

The following simple inequality from [9] will be useful. For completeness, we
include its short proof here.

######  Lemma 2.6 ([9, Lemma 4.5]).

For all integers $a\geq 1$, $k\geq 2$, and $n\geq ak$, we have

$\displaystyle a(n-a)+t_{k-1}(n-a)>(a-1)(n-a+1)+t_{k-1}(n-a+1).$ (7)

###### Proof.

Let $a_{1}\geq\dots\geq a_{k-1}$ denote the part sizes of $T_{k-1}(n-a)$. If
we increase its number of vertices by one, then the part sizes of the new
Turán graph, up to reordering, can be obtained by increasing $a_{k-1}$ by one.
Thus the difference between the expressions in (7) is

$\displaystyle|K_{a_{1},\ldots,a_{k-1},a}|-|K_{a_{1},\ldots,a_{k-2},a_{k-1}+1,a-1}|=a_{k-1}a-(a_{k-1}+1)(a-1)=a_{k-1}-a+1,$
(8)

which is positive since
$a_{k-1}\geq\left\lfloor(n-a)/(k-1)\right\rfloor\geq\left\lfloor(ak-a)/(k-1)\right\rfloor=a$.

##  3 Extremal graphs in $\mathcal{H}_{0}(n,e)$

As an intermediate step towards Theorem 1.1, we will first prove the following
result, which determines the extremal graphs in $\mathcal{H}^{\min}_{0}(n,e)$.

######  Proposition 3.1.

For all integers $n\geq r\geq 4$ and $t_{r-1}(n)<e\leq\binom{n}{2}$, we have
that $\mathcal{H}^{\min}_{0}(n,e)=\mathcal{H}^{\ast}_{1}(n,e)$.

We will use this result later to prove Theorem 1.1 by induction on the number
of parts in a graph in $\mathcal{K}(n,e)$. Note that, in general, none of
$\mathcal{K}(n,e)$ and $\mathcal{H}_{0}(n,e)$ is a subfamily of the other.
However, when we work on the structure of extremal graphs in
$\mathcal{K}(n,e)$ in the proof of Theorem 1.1, some intermediate graphs may
be in $\mathcal{H}_{0}(n,e)$.

We need some further preliminaries before we can prove Proposition 3.1.

Given a graph $G\in\mathcal{H}^{\min}_{0}(n,e)$ with partition
$B_{1},\ldots,B_{k-1}$, we apply the following modification to $G$ to obtain a
new graph $H^{\prime}=H^{\prime}(G)\in\mathcal{H}^{\min}_{0}(n,e)$. Note that,
in fact, these steps do not depend on $r$.

Step 1:

If there is a part $B_{i}$ that is partially full in $G$, then let $B:=B_{i}$
(by Lemma 2.5, such $B_{i}$ is unique if it exists). Otherwise, take an
arbitrary $i\in[k-1]$ with $|G[B_{i}]|=t_{2}(|B_{i}|)$ and let $B:=B_{i}$.
Since $|G|>t_{k-1}(n)$, the set $B$ is well-defined.

Step 2:

Note that $G-B$ is a complete multipartite graph. Let $A_{1},\ldots,A_{t-2}$
denote its parts. Let $a_{i}:=|A_{i}|$ for $i\in[t-2]$ and assume that
$a_{1}\geq\dots\geq a_{t-2}$. Note that each original part $B_{\ell}$ is
either $B$, some $A_{i}$, or the union of two parts $A_{i}$ and $A_{j}$.

Step 3:

Choose integers $a_{t-1}\geq a_{t}\geq 1$ such that

$\displaystyle
a_{t-1}+a_{t}=|B|\quad\text{and}\quad(a_{t-1}+1)(a_{t}-1)<|G[B]|\leq
a_{t-1}a_{t}.$

Note that this is possible by Mantel’s theorem since $G[B]$ is triangle-free.
Let $A_{t-1}\sqcup A_{t}=B$ be a partition with $|A_{t-1}|=a_{t-1}$ and
$|A_{t}|=a_{t}$. If $|G[B]|=t_{2}(|B|)$, then $a_{t-1}=\lceil|B|/2\rceil$ and
$a_{t}=\lfloor|B|/2\rfloor$ and we assume that $A_{t-1}\sqcup A_{t}=B$ is the
original partition of $G[B]$ with the two parts labelled so that
$|A_{t-1}|\geq|A_{t}|$.

Step 4:

Let $H^{\prime}$ be obtained from $K[A_{1},\ldots,A_{t}]$ by removing a star
whose centre lies in $A_{t}$ and $m^{\prime}$ leaves lie in $A_{t-1}$, where

$m^{\prime}:=\sum_{ij\in\binom{[t]}{2}}a_{i}a_{j}-e=a_{t-1}a_{t}-|G[B]|.$ (9)

This is possible because, by Step 3,

$\displaystyle 0\leq m^{\prime}=a_{t-1}a_{t}-|G[B]|\leq
a_{t-1}a_{t}-\left((a_{t-1}+1)(a_{t}-1)+1\right)=a_{t-1}-a_{t}.$ (10)

Notice that to obtain $H^{\prime}$ we only change the structure of $G$ on $B$
while keeping $|G[B]|=|H^{\prime}[B]|$. Thus
$H^{\prime}\in\mathcal{H}_{0}(n,e)$ and, since $G[B,V(G)\setminus B]$ is a
complete bipartite and $G[B]$ is triangle-free, it follows from Fact 2.2 that
$N(K_{r},H^{\prime})=N(K_{r},G)$, and hence,
$H^{\prime}\in\mathcal{H}_{0}^{\min}(n,e)$.

######  Lemma 3.2.

For all $r\geq 3$, integers $n$ and $e$ with $t_{r-1}(n)<e\leq\binom{n}{2}$
and $G\in\mathcal{H}_{0}^{\min}(n,e)$, the graph $H^{\prime}$ produced by
Steps 1–4 above is isomorphic to $H^{\ast}(n,e)$.

###### Proof.

To prove that $H^{\prime}\cong H^{\ast}(n,e)$, it suffices to show that $t=k$
and $(|A_{1}|,\ldots,|A_{t}|)=\bm{a}^{\ast}$, where $k$ and $\bm{a}^{\ast}$
are as defined in Section 1.

######  Claim 3.3.

If $m^{\prime}=0$, then $|H^{\prime}[A_{h}\cup A_{i}\cup
A_{j}]|>t_{2}(a_{h}+a_{i}+a_{j})$ for all $\\{h,i,j\\}\in\binom{[t]}{3}$. If
$m^{\prime}>0$, then $|H^{\prime}[A_{h}\cup A_{t-1}\cup
A_{t}]|>t_{2}(a_{h}+a_{t-1}+a_{t})$ for all $h\in[t-2]$.

###### Proof.

Let $S:=A_{h}\cup A_{i}\cup A_{j}$. Suppose to the contrary that
$|H^{\prime}[W]|\leq t_{2}(|W|)$. Then let $G_{1}$ be a new graph obtained
from $H^{\prime}$ by replacing $H^{\prime}[W]$ with a bipartite graph of the
same size. Note that the induced bipartite graph $H^{\prime}[W,\overline{W}]$
is complete. (Indeed, this is trivially true if $m^{\prime}=0$ as then
$H^{\prime}=K[A_{1},\ldots,A_{t}]$; if $m^{\prime}>0$, then the only non-
complete pair is $[A_{t-1},A_{t}]$, but both sets lie in $W$.) Since
$H^{\prime}$ is $t$-partite, the graph $G_{1}$ is $(t-1)$-partite (and with at
most one non-complete pair of parts). By Steps 2–3, we have $t\leq 2(k-1)$. So
we can represent $G_{1}$ as the union of a complete $(k-1)$-partite graph and
a triangle-free graph, which implies that $G_{1}\in\mathcal{H}_{0}(n,e)$. It
is easy to see from Fact 2.4 that $N(K_{r},G_{1})\leq N(K_{r},H^{\prime})$,
since $0=N(K_{3},G_{1}[W])\leq N(K_{3},H^{\prime}[W])$. So it follows from the
minimality of $H^{\prime}$ that $N(K_{3},H^{\prime}[W])=0$. If $\\{t-1,t\\}$
is not a subset of $\\{h,i,j\\}$, then $H^{\prime}[W]$ is a complete
$3$-partite graph and contains at least one traingle, contradicting
$N(K_{3},H^{\prime}[W])=0$. Therefore, $\\{t-1,t\\}\subseteq\\{h,i,j\\}$. By
symmetry, we may assume that $\\{t-1,t\\}=\\{i,j\\}$. Note that
$|H[A_{t-1},A_{t}]|\geq 1$, since otherwise, we would have $m^{\prime}\geq
a_{t-1}a_{t}>a_{t-1}-a_{t}$, contradicting (10). Note that each edge in
$H[A_{t-1},A_{t}]$ is in $|A_{h}|$ triangles in $H[W]$, contradicting
$N(K_{3},H^{\prime}[W])=0$.

######  Claim 3.4.

If $m^{\prime}>0$, then $a_{t-2}\geq a_{t-1}$.

###### Proof.

Suppose to the contrary that $a_{t-2}\leq a_{t-1}-1$. Then let $G_{2}$ be a
new graph obtained from $H^{\prime}$ by moving edges from $[A_{t-2},A_{t}]$ to
$[A_{t-1},A_{t}]$ until this is no longer possible. Let $S:=A_{t-2}\cup
A_{t-1}\cup A_{t}$. If $A_{t-2}\cup A_{t}$ is an independent set in $G_{2}$
(i.e. if $m^{\prime}\geq a_{t-2}a_{t}$), then $|H^{\prime}[W]|=|G_{2}[W]|\leq
t_{2}(|W|)$, contradicting Claim 3.3. Thus $G_{2}[W]$ can be viewed as a graph
obtained from $K[A_{t-2},A_{t-1},A_{t}]$ by removing $m^{\prime}$ edges from
$K[A_{t-2},A_{t}]$. So $G_{2}\in\mathcal{H}_{0}(n,e)$. Note that

$\displaystyle
N(K_{3},G_{2}[W])-N(K_{3},H^{\prime}[W])=m^{\prime}\left(a_{t-2}-a_{t-1}\right)<0,$

which combined with Fact 2.4 implies that
$N(K_{r},G_{2})-N(K_{r},H^{\prime})<0$, contradicting the minimality of
$H^{\prime}$.

If $m^{\prime}>0$, let $C_{i}:=A_{i}$ for $i\in[t]$. If $m^{\prime}=0$, let
$C_{1},\ldots,C_{t}$ be a relabelling of $A_{1},\ldots,A_{t}$ so that the
sizes of the sets is non-increasing. Regardless of the value of $m^{\prime}$,
the following statements clearly hold:

  1. (i)

$c_{1}\geq\dots\geq c_{t}$, where $c_{i}:=|C_{i}|$ for $i\in[t]$,

  2. (ii)

$0\leq m^{\prime}\leq c_{t-1}-c_{t}$,

  3. (iii)

Claim 3.3 applies to all triples $\\{C_{i},C_{t-1},C_{t}\\}$ for $i\in[t-2]$.

The rest of the proof is written so that it works for both $m^{\prime}=0$ and
$m^{\prime}>0$.

######  Claim 3.5.

We have $c_{1}\leq c_{t-1}+1$.

###### Proof.

Let $S:=C_{1}\cup C_{t-1}\cup C_{t}$. Note that

$\displaystyle|K_{c_{1}-1,c_{t-1}+1,c_{t}}|-|H^{\prime}[S]|=m^{\prime}-c_{t-1}+c_{1}-1=:m^{\prime\prime}.$

Suppose to the contrary that $c_{1}\geq c_{t-1}+2$. Then $m^{\prime\prime}\geq
m^{\prime}+1$. Take a partition $C^{\prime}_{1}\cup C^{\prime}_{t-1}\cup
C^{\prime}_{t}=W$ of sizes $c_{1}-1,c_{t-1}+1,c_{t}$, respectively. Let
$H_{S}$ be the graph obtained from
$K[C^{\prime}_{1},C^{\prime}_{t-1},C^{\prime}_{t}]$ by removing
$m^{\prime\prime}$ edges between $C^{\prime}_{t-1}$ and $C^{\prime}_{t}$. This
is possible since $m^{\prime\prime}\leq(c_{t-1}+1)c_{t}$. (Indeed, otherwise
$|H^{\prime}[S]|\leq(c_{1}-1)(c_{t-1}+c_{t}+1)\leq t_{2}(|S|)$, contradicting
Claim 3.3.) We have $|H_{S}|=|H^{\prime}[S]|$. Let $H^{\prime\prime}$ be the
graph obtained from $H^{\prime}$ by replacing $H^{\prime}[W]$ with $H_{S}$.
Note that $H^{\prime\prime}\in\mathcal{H}_{0}(n,e)$. It follows from
$m^{\prime}\leq c_{t-1}-c_{t}$ that

$\displaystyle N(K_{3},H^{\prime}[W])-N(K_{3},H^{\prime\prime}[W])$
$\displaystyle=$ $\displaystyle\left(c_{1}c_{t-1}c_{t}-m^{\prime}c_{1}\right)$
$\displaystyle-$
$\displaystyle\left((c_{1}-1)(c_{t-1}+1)c_{t}-(m^{\prime}-c_{t-1}+c_{1}-1)(c_{1}-1)\right)$
$\displaystyle\geq$ $\displaystyle(c_{1}-c_{t})(c_{1}-c_{t-1}-2)+1\ \geq 1,$

which combined with Fact 2.4 implies that
$N(K_{r},H^{\prime})-N(K_{r},H^{\prime\prime})>0$, contradicting the
minimality of $H^{\prime}$.

######  Claim 3.6.

We have $t=k$.

###### Proof.

It suffices to show that $t_{t-1}(n)<e\leq t_{t}(n)$. The upper bound $e\leq
t_{t}(n)$ is trivial, since $H^{\prime}$ is $t$-partite. So it remains to show
that $e>t_{t-1}(n)$. Let $T:=H^{\prime}[C_{1}\cup\dots\cup C_{t-1}]$. It
follows form Claim 3.5 that $T\cong T_{t-1}(n-c_{t})$. Therefore,

$\displaystyle|H^{\prime}|-t_{t-1}(n-c_{t})=|H^{\prime}\setminus
T|=c_{t}(n-c_{t})-m^{\prime}.$ (11)

On the other hand, by viewing $T_{t-1}(n)$ as a graph obtained from
$T_{t-1}(n-c_{t})$ by adding $c_{t}$ new vertices into some parts, we obtain

$\displaystyle t_{t-1}(n)-t_{t-1}(n-c_{t})\leq c_{t}(n-c_{t-1}-1).$

By combining these two inequalities, we obtain

$\displaystyle|H^{\prime}|-t_{t-1}(n)\geq
c_{t}(c_{t-1}+1-c_{t})-m^{\prime}\geq(c_{t}-1)(c_{t-1}-c_{t})+c_{t}>0,$

proving that $e>t_{t-1}(n)$.

######  Claim 3.7.

The sequence $\left(|C_{1}|,\ldots,|C_{k}|\right)$ of part sizes is equal to
$\bm{a}^{\ast}=\bm{a}^{\ast}(n,e)$.

###### Proof.

Recall that $t=k$ and, by (11), we have that

$\displaystyle|H^{\prime}|-t_{k-1}(n-c_{k})=c_{k}(n-c_{k})-m^{\prime}\leq
c_{k}(n-c_{k}).$ (12)

Let us show that $c_{k}$ is the smallest nonnegative integer $a$ satisfying

$f(a):=a(n-a)+t_{k-1}(n-a)\geq e.$

This inequality holds for $a=c_{k}$ by (12). Note that $c_{k}\leq n/k$ as it
is the smallest among $c_{1}+\dots+c_{k}=n$. Thus, by Lemma 2.6, it is enough
to check that $a=c_{k}-1$ violates this condition. Notice that

$\displaystyle f(c_{k}-1)-f(c_{k})\leq
2c_{k}-n-1+(n-c_{k}-c_{k-1})=c_{k}-c_{k-1}-1.$

Therefore, it follows from $m^{\prime}\leq c_{k-1}-c_{k}$ that

$\displaystyle f(c_{k}-1)\leq
f(c_{k})-(m^{\prime}+1)\leq|H^{\prime}|+m^{\prime}-(m^{\prime}+1)<|H^{\prime}|,$

as desired.

Thus $c_{k}=a_{k}^{\ast}$ and (since $t=k$ by Claim 3.6) we have
$(c_{1},\dots,c_{k})=\bm{a}^{\ast}$ by Claim 3.5, as desired.

Also, it follows from the definitions that $m^{\prime}=m^{\ast}$ and thus
$H^{\prime}$ is isomorphic to $H^{\ast}(n,e)$. This completes the proof of
Lemma 3.2.

Now we are ready to prove Proposition 3.1.

###### Proof of Proposition 3.1.

Let $G\in\mathcal{H}^{\min}_{0}(n,e)$ be arbitrary. Let $B_{1},\ldots,B_{k-1}$
be a vertex partition such that $G$ is the union of $K[B_{1},\ldots,B_{k-1}]$
with a triangle-free graph $J$. Let $b_{i}:=|B_{i}|$ for $i\in[k-1]$. Apply
Steps 1–4 to $G$ to obtain a $k$-partite graph $H^{\prime}$ with parts
$A_{1},\ldots,A_{k}$. By Lemma 3.2, we have $H^{\prime}\cong
H^{\ast}:=H^{\ast}(n,e)$. Assume that $|A_{i}|=a^{\ast}_{i}$ for $i\in[k]$ and
that all missing edges of $H^{\prime}$ (if any exist) go between $A_{k-1}$ and
$A_{k}$.

The following claim follows from the definitions of Steps 1–4.

######  Claim 3.8.

If $i\in[k-1]$ satisfies $|G[B_{i}]|\in\left\\{0,t_{2}(b_{i})\right\\}$, then
$H^{\prime}[B_{i}]=G[B_{i}]$.

Since $H^{\prime}$ is $k$-partite, it follows from the definitions of Steps
1–4 that exactly one part $B_{p}$ of $G$ is divided into $A_{q}\cup A_{s}$ in
Steps 2–3, where, say, $1\leq q<s\leq k$, while the remaining parts of $G$
correspond to the remaining parts of $H^{\prime}$. In particular,
$b_{p}=a_{q}^{\ast}+a_{s}^{\ast}$.

######  Claim 3.9.

We have $|G[B_{p}]|>0$.

###### Proof.

It follows from $m^{\ast}\leq a_{k-1}^{\ast}-a_{k}^{\ast}$ that

$\displaystyle|H^{\prime}[B_{p}]|=a_{q}^{\ast}a_{s}^{\ast}-m^{\ast}\geq
a_{q}^{\ast}a_{s}^{\ast}-(a_{k-1}^{\ast}-a_{k}^{\ast})>0.$

Combined with Claim 3.8, we see that $|G[B_{p}]|>0$.

Suppose first that $m^{\ast}=0$. Then $H^{\prime}=K[A_{1},\ldots,A_{k}]$, and
$G$ can be obtained from $H^{\prime}$ by replacing $H^{\prime}[A_{q}\cup
A_{s}]$ with $G[B_{p}]$. Moreover, $G[B_{p}]$ is a triangle-free graph with
$a^{\ast}_{q}+a^{\ast}_{s}$ vertices and $a^{\ast}_{q}a^{\ast}_{s}$ edges. If
$a^{\ast}_{s}=a^{\ast}_{k}$, then it follows from the definition of
$\mathcal{H}_{1}^{\ast}(n,e)$ that $G\in\mathcal{H}_{1}^{\ast}(n,e)$.
Otherwise, $|a^{\ast}_{q}-a^{\ast}_{s}|\leq 1$ (by the definition of
$\bm{a}^{\ast}$), and hence, $G\cong T_{2}(a^{\ast}_{q}+a^{\ast}_{s})$. This
implies that $G$ does not contain any partially full part, and hence,
$G=H^{\prime}\in\mathcal{H}_{1}^{\ast}(n,e)$.

Suppose that $m^{\ast}>0$. Since $G[A_{i},A_{j}]$ is complete for all
$\\{i,j\\}\neq\\{q,s\\}$ and $H^{\prime}[A_{i},A_{j}]$ is complete iff
$\\{i,j\\}\neq\\{k-1,k\\}$, we have $\\{q,s\\}=\\{k-1,k\\}$. Thus $G$ can be
obtained from $K[A_{1},\ldots,A_{k}]$ by replacing $K[A_{k-1}\cup A_{k}]$ with
a triangle-free graph with $a^{\ast}_{k-1}a^{\ast}_{k}-m^{\ast}$ edges. This
gives $G\in\mathcal{H}_{1}^{\ast}(n,e)$. We conclude that
$\mathcal{H}^{\min}_{0}(n,e)\subseteq\mathcal{H}^{\ast}_{1}(n,e)$. Since
$\mathcal{H}^{\ast}_{1}(n,e)\subseteq\mathcal{H}_{0}(n,e)$ and every graph in
$\mathcal{H}^{\ast}_{1}(n,e)$ contains the same number of $K_{r}$’s, we have
$\mathcal{H}^{\min}_{0}(n,e)=\mathcal{H}^{\ast}_{1}(n,e)$.

##  4 Proof of Theorem 1.1

With Proposition 3.1 in hand, we are now ready to prove Theorem 1.1.

###### Proof of Theorem 1.1.

Fix integers $n\geq r\geq 3$ and $e\leq\binom{n}{2}$. Notice that (4) can be
reduced to $\min\big{\\{}N(K_{r},G)\colon G\in\mathcal{K}(n,e)\big{\\}}\geq
h_{r}^{\ast}(n,e)$, since the other direction is trivially true. Suppose that
$G\in\mathcal{K}^{\min}(n,e)$ is a graph obtained from a complete
$\ell$-partite graph by adding a triangle-free graph to one part. We aim to
show that $N(K_{r},G)\geq h_{r}^{\ast}(n,e)$ when $r\geq 3$ and, in addition,
$G\in\mathcal{H}_{1}^{\ast}(n,e)$ when $r\geq 4$ and $e>t_{r-1}(n)$. We prove
this statement by induction on $\ell+r$. Notice that if $\ell=k-1$ (where
$k=k(n,e)$) and $r\geq 4$, then $G\in\mathcal{H}_{0}(n,e)$, and it follows
from Proposition 3.1 that $G\in\mathcal{H}_{1}^{\ast}(n,e)$, as desired. If
$\ell=k-1$ and $r=3$, then $G\in\mathcal{H}_{0}(n,e)$, and it follows from [9,
Proposition 1.5] that $N(K_{3},G)\geq h_{3}^{\ast}(n,e)$. So the statement is
true for all pairs $(\ell,r)$ with $\ell=k-1$ and $r\geq 3$, and this serves
as our base case.

Assume that $\ell\geq k$ and $r\geq 3$. Let $U_{1}\cup\dots\cup U_{\ell}=V(G)$
be a partition such that $G$ is obtained from the complete $\ell$-partite
graph $K[U_{1},\ldots,U_{\ell}]$ by adding a triangle-free graph into
$U_{\ell}$. We can assume that $U_{\ell}$ is not an independent set (otherwise
consider instead the $(\ell-1)$-partition of $V(G)$ where $U_{\ell-1}$ and
$U_{\ell}$ are merged together).

First, we prove (4). Assume that $\ell\geq r-1$, as otherwise
$h_{r}^{\ast}(n,e)=0$ and there is nothing to do. Note that $U_{\ell}$ is as
large as any other part: if some part $U_{i}$ has strictly larger size then by
moving all edges from $U_{\ell}$ to $U_{i}$ (by $|U_{i}|>|U_{\ell}|$ there is
enough space for this) we strictly decrease the number of $r$-cliques (since
$\ell\geq r-1$), a contradiction. By relabelling parts
$U_{1},\ldots,U_{\ell-1}$, we may assume that $U_{1}$ is of smallest size
among $U_{1},\ldots,U_{\ell-1}$. Let $\hat{G}$ denote the induced subgraph of
$G$ on $U_{2}\cup\dots\cup U_{\ell}$. Let $\hat{n}:=n-|U_{1}|$ and
$\hat{e}:=|\hat{G}|$. Let $\hat{k}:=k(\hat{n},\hat{e})$ be as defined in (2)
(while we reserve $k$ for $k(n,e)$).

######  Claim 4.1.

We have $\hat{k}\leq k$.

###### Proof.

Let $H^{\ast}=H^{\ast}(n,e)$ be the $k$-partite graph as defined in Section 1.
Assume that $A_{1}^{\ast},\ldots,A_{k}^{\ast}$ are the corresponding parts of
$H^{\ast}$ of sizes $a_{1}^{\ast}\geq\dots\geq a_{k}^{\ast}$, respectively. It
is clear that $|A_{1}^{\ast}|\geq\frac{n}{k}$. It follows from the minimality
of $U_{1}$ that
$|U_{1}|\leq\frac{n-|U_{\ell}|}{\ell-1}<\frac{n}{k}\leq|A_{1}^{\ast}|$. Let
$W_{1}\subseteq A_{1}^{\ast}$ be a set of size $|U_{1}|$ and let $H^{\prime}$
be the induced subgraph of $H^{\ast}$ on $V(H)\setminus W_{1}$. Observe that
$H^{\prime}$ is still a $k$-partite graph and $|H^{\prime}|\geq|\hat{G}|$. So
it follows from the definition that $\hat{k}\leq k$.

Note that $\hat{G}$ can be viewed as a graph obtained from a complete
$(\ell-1)$-partite graph by adding a triangle-free graph into one part; in
particular, $\hat{G}\in\mathcal{K}(\hat{n},\hat{e})$. Let $\hat{H}$ be
$H^{\ast}(\hat{n},\hat{e})$ and let $G^{\prime}$ be the graph obtained from
$G$ by replacing $\hat{G}$ with $\hat{H}$. It follows from the inductive
hypothesis that

$\displaystyle N(K_{r},\hat{H})=h_{r}^{\ast}(\hat{n},\hat{e})\leq
N(K_{r},\hat{G})\quad\text{and}\quad N(K_{r-1},\hat{H})\leq
N(K_{r-1},\hat{G}).$

Hence,

$\displaystyle h_{r}^{\ast}(n,e)\leq N(K_{r},G^{\prime})$
$\displaystyle=N(K_{r},\hat{H})+|U_{1}|\cdot N(K_{r-1},\hat{H})$
$\displaystyle\leq N(K_{r},\hat{G})+|U_{1}|\cdot
N(K_{r-1},\hat{G})=N(K_{r},G),$

finishing the inductive step for proving (4).

Now suppose that that $r\geq 4$ and $e>t_{r-1}(n)$, and suppose for
contradiction that $G\not\in\mathcal{H}_{1}^{\ast}(n,e)$. Reusing the notation
introduced above, let us first derive a contradiction from assuming that
$\hat{G}\not\in\mathcal{H}_{1}^{\ast}(\hat{n},\hat{e})$.

If $\hat{e}>t_{r-1}(\hat{n})$, then it follows from the inductive hypothesis
that

$\displaystyle N(K_{r},\hat{H})<N(K_{r},\hat{G})\quad\text{and}\quad
N(K_{r-1},\hat{H})\leq N(K_{r-1},\hat{G}).$

Therefore,

$\displaystyle N(K_{r},G^{\prime})$
$\displaystyle=N(K_{r},\hat{H})+|U_{1}|\cdot N(K_{r-1},\hat{H})$
$\displaystyle<N(K_{r},\hat{G})+|U_{1}|\cdot N(K_{r-1},\hat{G})=N(K_{r},G),$
(13)

contradicting the minimality of $G$.

So suppose that $\hat{e}\leq t_{r-1}(\hat{n})$. We have that $\ell\geq k\geq
r$. Recall that $\hat{G}$ is a graph obtained from an $(\ell-1)$-partite graph
by adding a non-empty triangle-free graph. Thus, we have
$N(K_{r},\hat{H})=0<N(K_{r},\hat{G})$. In addition, by (4), we have
$N(K_{r-1},\hat{H})=h_{r-1}^{\ast}(\hat{n},\hat{e})\leq N(K_{r-1},\hat{G})$.
But then the same calculation as in (13) gives a contradiction to the
minimality of $G$.

Thus we have that $\hat{G}\in\mathcal{H}_{1}^{\ast}(\hat{n},\hat{e})$. Let
$\hat{A}_{1}^{\ast}\cup\ldots\cup\hat{A}_{\hat{k}}^{\ast}=V(\hat{G})$ be the
partition of $\hat{G}$ as in the definition of
$\mathcal{H}_{1}^{\ast}(\hat{n},\hat{e})$. Let
$B_{1}:=U_{1}\cup\hat{A}_{1}^{\ast}$, $B_{i}:=\hat{A}_{i}^{\ast}$ for $2\leq
i\leq\hat{k}-2$, and
$B_{\hat{k}-1}:=\hat{A}_{\hat{k}-1}\cup\hat{A}_{\hat{k}}$. We can view $G$ as
a graph obtained from $K[B_{1},\ldots,B_{\hat{k}-1}]$ by adding triangle-free
graphs into two parts, namely $G[B_{1}]$ and $G[B_{\hat{k}-1}]$. Since
$\hat{k}\leq k$ by Claim 4.1, it holds that $G\in\mathcal{H}_{0}(n,e)$.
Therefore, it follows from Proposition 3.1 that
$G\in\mathcal{H}_{1}^{\ast}(n,e)$, finishing the proof of Theorem 1.1.

Let us remark that if we replace the family $\mathcal{K}(n,e)$ in Theorem 1.1
by the larger family $\mathcal{K}^{\prime}(n,e)$ that consists of all graphs
obtained from a complete partite graph by adding a triangle-free graph (that
is, we allow to add edges into more than one part) then the theorem will
remain true. Indeed, for $r\geq 4$, the proof of Lemma 2.5 (which in fact
works for any number of parts) shows that every extremal graph
$\mathcal{K}^{\prime}(n,e)$ has at most one partially full part and thus
belongs to $\mathcal{K}(n,e)$. For $r=3$, the equality in (4), will also
remain true (again by the proof of Lemma 2.5 except the inequality in (6)
becomes equality).

##  5 Proof of Proposition 1.2

###### Proof of Proposition 1.2.

First, we prove that $N(K_{r},H)=h_{r}^{\ast}(n,e)$ for all
$H\in\mathcal{H}_{2}^{\ast}(n,e)$. Fix $H\in\mathcal{H}_{2}^{\ast}(n,e)$.

First consider the case when $(|A_{1}|,\dots,|A_{k}|)=\bm{a}^{\ast}$, where
the sets $A_{1},\dots,A_{k}$ are as in the definition of
$\mathcal{H}_{2}^{\ast}(n,e)$. Let $K:=K[A_{1},\ldots,A_{k}]$, and
$m_{i}^{\ast}:=|\overline{H}[B_{i},A_{i}]|$ for $i\in
I:=\left\\{j\in[k-1]\colon|A_{j}|=|A_{k-1}|\right\\}$. Note from the
definition of $I$ that for all $i\in I$, we have that

$\displaystyle
N(K_{r-2},K[A_{1},\ldots,A_{i-1},A_{i+1},\dots,A_{k-1}])=N(K_{r-2},K[A_{1},\ldots,A_{k-2}]),$

because we count $r$-cliques in two isomorphic graphs. Therefore,

$\displaystyle N(K_{r},K)-N(K_{r},H)$ $\displaystyle=\sum_{i\in
I}m_{i}^{\ast}\cdot N(K_{r-2},K[A_{1},\ldots,A_{i-1},A_{i+1},\dots,A_{k-1}])$
$\displaystyle=\sum_{i\in I}m_{i}^{\ast}\cdot
N(K_{r-2},K[A_{1},\ldots,A_{k-2}])$ $\displaystyle=m^{\ast}\cdot
N(K_{r-2},K[A_{1},\ldots,A_{k-2}])=N(K_{r},K)-N(K_{r},H^{\ast}).$ (14)

It follows that $N(K_{r},H)=N(K_{r},H^{\ast})=h^{\ast}(n,e)$, as desired.

Now suppose that $(|A_{1}|,\dots,|A_{k}|)\not=\bm{a}^{\ast}$. Recall that then
$m^{\ast}=0$,
$(|A_{1}|,\ldots,|A_{k}|)=(a_{2}^{\ast},\ldots,a_{k-1}^{\ast},a_{1}^{\ast}-1,a_{k}^{\ast}+1)$,
$m=a_{1}^{\ast}-a_{k}^{\ast}+1$, and $H$ is a graph obtained form
$K[A_{1},\ldots,A_{k}]$ by removing some $m$ edges. We may assume that these
$m$ edges were removed from parts $[A_{k-1},A_{k}]$, since this does not
affect the value of $N(K_{r},H)$ by the calculation in (5). Now, by viewing
$H$ as a graph obtained from $K[A_{1},\ldots,A_{k}]$ by replacing
$K[A_{k-1},A_{k}]$ with a triangle-free graph, we see that
$H\in\mathcal{H}_{1}^{\ast}(n,e)$, and hence, $N(K_{r},H)=h^{\ast}(n,e)$.

Next, we show that there are infinitely many pairs $(n,e)\in\mathbb{N}^{2}$
with $t_{r-1}(n)<e\leq\binom{n}{2}$ such that
$\mathcal{H}_{2}^{\ast}(n,e)\setminus\mathcal{H}_{1}^{\ast}(n,e)\neq\emptyset$.
It is enough to chose $(n,e)$ so that $a_{k-2}^{\ast}=a_{k-1}^{\ast}$ and
$m^{\ast},a_{k}^{\ast}\geq 2$; the choice that we use (in (15) below) is
rather arbitrary.

Take any integers $p\geq r-1$, $q\geq 100$, and $2\leq m\leq q$. Let
$n:=2pq+q$ and $e:=\binom{p}{2}(2q)^{2}+2pq^{2}-m$. Note that $e+m$ is the
number of edges in the complete $(p+1)$-partite graph $K_{2q,\dots,2q,q}$ with
$p$ parts of size $2q$ and one part of size $q$. The choice of $(p,q,m)$
ensures that

$\displaystyle
e=\binom{p}{2}(2q)^{2}+2pq^{2}-m>\binom{p}{2}\left(\frac{2pq+q}{p}\right)^{2}\geq
t_{p}(n).$

By $e\leq e+m\leq t_{p}(n)$, we have that $k(n,e)=p$.

Let us show that $a_{p}^{\ast}=q$. By Lemma 2.6, it is enough to show that
$(q-1)(n-q-1)+t_{k-1}(n-q-1)<e$. The left-hand side here is the size of the
graph obtained from the complete partite graph $K_{2q,\dots,2q,q}$ by moving a
vertex from the part of size $q$ into one of size $2q$. This results in losing
$q+1>m$ edges, giving the required. Thus

$\displaystyle a_{1}^{\ast}=\dots=a^{\ast}_{p-1}=2q,\quad
a_{p}^{\ast}=q,\quad\text{and}\quad m^{\ast}=m.$ (15)

Let $V_{1}\cup\dots\cup V_{p+1}=[n]$ be a partition such that
$|V_{1}|=\dots=|V_{p}|=2q$ and $|V_{p+1}|=q$. Fix $m$ distinct vertices
$v_{1},\ldots,v_{m}\in V_{p+1}$, and choose a vertex $u_{i}\in V_{i}$ for
every $i\in[m]$. Let $G$ be the graph obtained from $K[V_{1},\ldots,V_{p-1}]$
by removing pairs in $\\{\\{v_{i},u_{i}\\}\colon i\in[m]\\}$. It is easy to
see that
$G\in\mathcal{H}_{2}^{\ast}(n,e)\setminus\mathcal{H}_{1}^{\ast}(n,e)$, proving
Proposition 1.2.

## References

  * [1] J. Balogh and F. C. Clemen.  On stability of the Erdős-Rademacher problem.  Illinois J. Math., 67(1):1–11, 2023.
  * [2] B. Bollobás.  On complete subgraphs of different orders.  Math. Proc. Cambridge Philos. Soc., 79(1):19–24, 1976.
  * [3] P. Erdős.  Some theorems on graphs.  Riveon Lematematika, 9:13–17, 1955.
  * [4] P. Erdős.  On a theorem of Rademacher-Turán.  Illinois J. Math., 6:122–127, 1962.
  * [5] D. C. Fisher.  Lower bounds on the number of triangles in a graph.  J. Graph Theory, 13(4):505–512, 1989.
  * [6] M. Goldwurm and M. Santini.  Clique polynomials have a unique root of smallest modulus.  Inform. Process. Lett., 75(3):127–132, 2000.
  * [7] A. W. Goodman.  On sets of acquaintances and strangers at any party.  Amer. Math. Monthly, 66:778–783, 1959.
  * [8] J. Kim, H. Liu, O. Pikhurko, and M. Sharifzadeh.  Asymptotic structure for the clique density theorem.  Discrete Anal., pages Paper No. 19, 26, 2020.
  * [9] H. Liu, O. Pikhurko, and K. Staden.  The exact minimum number of triangles in graphs with given order and size.  Forum Math. Pi, 8:e8, 144, 2020.
  * [10] X. Liu and D. Mubayi.  On a generalized Erdős-Rademacher problem.  J. Graph Theory, 100(1):101–126, 2022.
  * [11] L. Lovász and M. Simonovits.  On the number of complete subgraphs of a graph.  In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), volume No. XV of Congress. Numer., pages 431–441. Utilitas Math., Winnipeg, MB, 1976.
  * [12] L. Lovász and M. Simonovits.  On the number of complete subgraphs of a graph. II.  In Studies in pure mathematics, pages 459–495. Birkhäuser, Basel, 1983.
  * [13] W. Mantel.  Problem 28.  Wiskundige Opgaven, 10(60-61):320, 1907.
  * [14] J. W. Moon and L. Moser.  On a problem of Turán.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 7:283–286, 1962\.
  * [15] D. Mubayi.  Counting substructures I: color critical graphs.  Adv. Math., 225(5):2731–2740, 2010.
  * [16] D. Mubayi.  Counting substructures II: Hypergraphs.  Combinatorica, 33(5):591–612, 2013.
  * [17] V. Nikiforov.  The number of cliques in graphs of given order and size.  Trans. Amer. Math. Soc., 363(3):1599–1618, 2011.
  * [18] V. S. Nikiforov.  On a problem of P. Erdős.  Annuaire Univ. Sofia Fac. Math. Méc., 71(2):157–160, 1976/77.
  * [19] V. S. Nikiforov and N. G. Khadzhiivanov.  Solution of the problem of P. Erdős on the number of triangles in graphs with $n$ vertices and $[n^{2}/4]+l$ edges.  C. R. Acad. Bulgare Sci., 34(7):969–970, 1981.
  * [20] E. A. Nordhaus and B. M. Stewart.  Triangles in an ordinary graph.  Canadian J. Math., 15:33–41, 1963.
  * [21] O. Pikhurko and A. Razborov.  Asymptotic structure of graphs with the minimum number of triangles.  Combin. Probab. Comput., 26(1):138–160, 2017.
  * [22] A. A. Razborov.  On the minimal density of triangles in graphs.  Combin. Probab. Comput., 17(4):603–618, 2008.
  * [23] C. Reiher.  The clique density theorem.  Ann. of Math. (2), 184(3):683–707, 2016.
  * [24] P. Turán.  On an external problem in graph theory.  Mat. Fiz. Lapok, 48:436–452, 1941.
  * [25] C. Xiao and G. O. H. Katona.  The number of triangles is more when they have no common vertex.  Discrete Math., 344(5):Paper No. 112330, 6, 2021.