On stability of the Erdős-Rademacher Problem

Without loss of generality we can assume that $|V_{1}|\geq|V_{2}|\geq\ldots\geq|V_{r}|$. Now, let $x=|V_{1}|-\frac{n}{r}$. Then,

Thus, we can conclude

implying $x=O(1)$. Note that in the second to last inequality we used (2) and in the last inequality we used (3). We conclude $|V_{1}|=\frac{n}{r}+O(1)$. Similarly, we can conclude $|V_{r}|=\frac{n}{r}+O(1)$. ∎

Any copy of $K_{r+1}$ needs to contain at least one class-edge. There are exactly $(\frac{n}{r}+O(1))^{r-1}$ copies of $K_{r+1}$ containing one given class-edge but no others, since the other $r-1$ vertices need to be chosen from different classes. Since the number of missing cross-edges is $O(1)$, they do not have an impact in this counting. There are $s$ class-edges and thus we conclude that the number of copies of $K_{r+1}$ containing exactly one class-edge is

The number of copies containing at least two class-edges is $O(n^{r-2})$, because there are $O(1)$ ways to chose three vertices among the vertices being incident to the class-edges and at most $O(n^{r-2})$ ways to chose the remaining $r-2$ vertices. We conclude

Let $G$ be a graph on $n$ vertices and $t_{r}(n)+t$ edges such that $\tau_{r+1}(G)\geq s$ and $n$ is large enough. If $G$ is $2sr!e^{2r}$-far from being $r$-partite, then by applying Theorem 6, the number of copies of $K_{r+1}$ in $G$ is at least

where we used (3) to lower bound $t_{r}(n)$. By Lemma 5, $T_{r+1}(H)=(1+o(1))s(\frac{n}{r})^{r-1}$ for every $H\in\mathcal{H}$, and thus $T_{r+1}(H)\leq T_{r+1}(G)$. Hence, we can assume that $G$ is not $2sr!e^{2r}$-far from being $r$-partite. Then there exists a subgraph $G^{\prime}\subset G$ with $\chi(G^{\prime})\leq r$ and

Let $V(G^{\prime})=V_{1}\cup V_{2}\cup\ldots\cup V_{r}$ be a partition such that $V_{1},V_{2},\ldots,V_{r}$ are independent sets in $G^{\prime}$. By Lemma 4, the class sizes are roughly balanced, that is $|V_{i}|=\frac{n}{r}+O(1)$ for all $1\leq i\leq r$.

Since $G^{\prime}\subset G$, and $e(G^{\prime})>e(G)-2sr!e^{2r}$, the vertex partition $V(G)=V_{1}\cup V_{2}\cup\ldots\cup V_{r}$ contains at most $2sr!e^{2r}$ class-edges in $G$. If the number of class-edges in $G$ is less than $s$, then there is a $K_{r+1}$-covering set of size at most $s-1$, contradicting $\tau_{r+1}(G)\geq s$. If the number of class-edges is more than $s$, then by Lemma 5

for every $H\in\mathcal{H}$. Therefore, we can assume that the number of class-edges in $G$ is exactly $s$. These $s$ edges need to form a matching, otherwise there is a $K_{r+1}$-covering set of size $s-1$, contradicting $\tau_{r+1}(G)\geq s$. Further, $e^{c}(V_{1},\ldots,V_{r})\leq s-t$, because otherwise

Next, we assume that there is a missing cross-edge $uv\not\in E(G)$ not incident to any of the class-edges. Take a cross-edge $xy\in E(G)$ which is incident to exactly one class-edge. We will show that $T_{r+1}(G+uv-xy)<T_{r+1}(G)$. Adding $uv$ to $G$ increases the number of cliques of size $r+1$ by at most $sn^{r-3}$, because for each of the $s$ class-edges $e$ the number of cliques of size $r+1$ containing $e$ and $uv$ is increased by at most $n^{r-3}$. Removing $xy$ from $G+uv$ decreases the number of cliques of size $r+1$ by at least

where we used that in each class $V_{i}$ the number of vertices incident to no missing cross-edge is at least $|V_{i}|-s$. Thus, performing this edge flip decreases the number of cliques of size $r+1$, i.e. $T_{r+1}(G+uv-xy)<T_{r+1}(G)$. We repeat this process until we end up with a graph $\bar{G}$ such that $T_{r+1}(\bar{G})\leq T_{r+1}(G)$ and every missing cross-edge is incident to a class-edge.
If $\bar{G}$ has all class-edges in the same class, then $\bar{G}\in\mathcal{H}$. Thus, we can assume that $\bar{G}$ has the property that not all class-edges are in the same class and there is a missing cross-edge not adjacent to class-edges on both ends. Denote $G^{\prime}$ the graph constructed from $\bar{G}$ by adding all missing cross-edges. This graph satisfies

because for each class-edge $e$ and each added edge $e^{\prime}$, the number of cliques of size $r+1$ containing $e$ and $e^{\prime}$ increases by at most $\left(\frac{n}{r}+O(1)\right)^{r-2}$ if $e$ and $e^{\prime}$ share a vertex and by at most $n^{r-3}$ if $e$ and $e^{\prime}$ are disjoint.

There is a set $M$ of $e_{\bar{G}}^{c}(V_{1},V_{2},\ldots,V_{r})\leq s-1$ cross-edges such that each $e\in M$ is incident to class-edges on both endpoints and every class-edge is incident to edges from $M$ on at most one endpoint. Denote $H$ the graph constructed from $G^{\prime}$ by removing those edges. This graph satisfies $H\in\mathcal{H}$ and

completing the proof. ∎

By Theorem 3, we can assume that $G$ has a vertex partition $V(G)=A\cup B$ where $|A|\geq|B|$ with exactly $s$ class-edges forming a matching. Let $|A|=\lceil n/2\rceil+a,|B|=\lfloor n/2\rfloor-a$ for some $a\geq 0$. We have

and thus the number of missing cross-edges is

Let $M_{A}$ be the matching of class-edges inside $A$ and $M_{B}$ be the matching of class-edges inside $B$. Denote $G^{\prime}$ the graph constructed from $G$ by adding all missing cross-edges $e^{c}(A,B)$. The number of triangles in this graph is $|M_{A}||B|+|M_{B}||A|$.
Case 1: $|M_{B}|>0$.
The number of triangles in $G$ is at least $|M_{A}||B|+|M_{B}||A|-2e^{c}(A,B)$, because each missing cross-edge is in at most two triangles in $G^{\prime}$. Since $|A|\geq|B|$, we get

Case 2: $|M_{B}|=0$.
The number of triangles in $G$ is at least $|M_{A}||B|-e^{c}(A,B)$, because each missing cross-edge is in at most one triangle in $G^{\prime}$. Therefore

Let $G$ be an $n$-vertex graph with $t_{r}(n)+1$ edges satisfying $\tau_{r+1}(G)\geq 2$. By applying Theorem 3 for $s=2$ and $t=1$, we can assume without loss of generality that $G\in\mathcal{H}$ and thus has a vertex partition $V(G)=V_{1}\cup V_{2}\cup\ldots\cup V_{r}$ where $|V_{1}|\geq|V_{2}|\geq\ldots\geq|V_{r}|$ with exactly two class-edges $e_{1},e_{2}$ and at most one missing cross-edge. We have

This means we have two cases:

Case 1: $e^{c}(V_{1},V_{2},\ldots,V_{r})=0$.
In this case

by (5). Note that $|V_{1}|-|V_{r}|=2$, because if $|V_{1}|-|V_{r}|\geq 3$, then moving one vertex from $V_{1}$ to $V_{r}$ increases the sum $\sum_{1\leq i<j\leq r}|V_{i}||V_{j}|$ by at least two and thus

a contradiction. If $|V_{1}|-|V_{r}|\leq 1,$ then $\sum_{1\leq i<j\leq r}|V_{i}||V_{j}|=t_{r}(n)$, giving a contradiction as well. Thus, we have $|V_{1}|-|V_{r}|=2$. Similarly, $|V_{2}|-|V_{r-1}|\leq 1$, as otherwise (6) holds. Conclusively, there are only the following types of combination of class sizes. We list them depending on $\ell=n\mod r$. If $\ell\in\{0,1\}$, then

• •

  $|V_{1}|=\ldots=|V_{\ell+1}|=m+1$, $|V_{\ell+2}|=\ldots=|V_{r-1}|=m$, $|V_{r}|=m-1$.

If $\ell=2$, then

• •

  Type 1: $|V_{1}|=m+2$, $|V_{2}|=\ldots=|V_{r}|=m$,

• •

  Type 2: $|V_{1}|=|V_{2}|=|V_{3}|=m+1$, $|V_{4}|=\ldots=|V_{r-1}|=m$, $|V_{r}|=m-1$.

If $3\leq\ell\leq r-3$, then

• •

  Type 1: $|V_{1}|=m+2$, $|V_{2}|=\ldots=|V_{\ell-1}|=m+1$, $|V_{\ell}|=\ldots=|V_{r}|=m$,

• •

  Type 2: $|V_{1}|=\ldots=|V_{\ell+1}|=m+1$, $|V_{\ell+2}|=\ldots=|V_{r-1}|=m$, $|V_{r}|=m-1$.

If $\ell=r-2$, then

• •

  Type 1: $|V_{1}|=m+2$, $|V_{2}|=\ldots=|V_{r-3}|=m+1$, $|V_{r-2}|=\ldots=|V_{r}|=m$,

• •

  Type 2: $|V_{1}|=\ldots=|V_{r-1}|=m+1$, $|V_{r}|=m-1$.

If $\ell=r-1$, then

• •

  $|V_{1}|=m+2$, $|V_{2}|=\ldots=|V_{r-2}|=m+1$, $|V_{r-1}|=|V_{r}|=m$.

Denote the two class-edges $e_{1},e_{2}$. Let $1\leq\alpha\leq\beta\leq r$ such that $e_{1}\subset V_{\alpha}$ and $e_{2}\subset V_{\beta}$. The number of copies of $K_{r+1}$ containing $e_{1}$ but not $e_{2}$ is $\prod_{i\neq\alpha}|V_{i}|$. Similarly, the number of copies of $K_{r+1}$ containing $e_{2}$ but not $e_{1}$ is $\prod_{i\neq\beta}|V_{i}|$. Thus, the total number of copies of $K_{r+1}$ in $G$ is at least