2. Notation

Let G be a graph. We define V(G) to be the vertex set of G and E(G) to be the edge set of G. Let $X \subseteq V(G)$ . Then G[X] is the graph induced by X on G and has vertex set X and edge set $E(G[X]) \,{:\!=}\, \{xy \in E(G)\,{:}\, x,y \in X\}$ . For each $x \in V(G)$ , we define the neighbourhood of x in G to be $N_G(x)\,{:\!=}\, \{y\in V(G)\,{:}\, xy \in E(G)\}$ and define $d_G(x) \,{:\!=}\, |N_G(x)|$ .

We write $0 < a \ll b \ll c < 1$ to mean that we can choose the constants a,b,c from right to left. More precisely, there exist non-decreasing functions $f\,{:}\,(0,1] \to (0,1]$ and $g\,{:}\,(0,1] \to (0,1]$ such that for all $a \leq f(b)$ and $b \leq g(c)$ our calculations and arguments in our proofs are correct. Larger hierarchies are defined similarly.

3. The extremal constructions for Theorem 1.4 and Theorem 1.6

In this section, we will give the extremal constructions that match the upper bounds in Theorems 1.4 and 1.6. First, let us consider those for Theorem 1.4.

Observe that

\begin{equation*}e(EX_1(n,t,r)) = \binom{n}{2} - \binom{\frac{n+t}{r} + 1}{2}\end{equation*}

and

\begin{equation*}e(EX_2(n,t,r)) = \binom{n}{2} - \binom{k}{2} - k(n - k - (r - 2 - q)).\end{equation*}

Hence,

\begin{align*}&\quad \max\left\{\binom{n}{2} - \binom{\frac{n+t}{r} + 1}{2}, \binom{n}{2} - \binom{k}{2} - k(n - k - (r - 2 - q))\right\} \\[3pt] &= \max\left\{e(EX_1(n,t,r)), e(EX_2(n,t,r))\right\}.\end{align*}

Next we show that $EX_1(n,t,r)*K_t$ and $EX_2(n,t,r)*K_t$ do not contain $K_r$ -factors, that is, they are extremal graphs for Theorem 1.4.

Proof. First, let us consider $EX_1(n,t,r)*K_t$ . For a contradiction, assume that $EX_1(n,t,r)*K_t$ contains a $K_r$ -factor $\mathcal T$ . Then each vertex in V(A) belongs to a different copy of $K_r$ in $\mathcal T$ . This implies $\frac{n+t}{r} = |\mathcal T| \geq |V(A)| = \frac{n+t}{r} + 1$ , a contradiction. Hence, $EX_1(n,t,r)*K_t$ does not contain a $K_r$ -factor.

Now let us consider $EX_2(n,t,r)*K_t$ . For a contradiction, assume that $EX_2(n,t,r)*K_t$ contains a $K_r$ -factor $\mathcal T$ . Then every vertex of B belongs to a different copy of $K_r$ in $\mathcal T$ . Thus, by construction, the copies of $K_r$ in $\mathcal T$ covering B must cover at least

\begin{align*} & \left\lceil\frac{t+1}{r-1}\right\rceil \cdot (r-1) = \left(\frac{t-q}{r-1} + 1\right) \cdot (r-1) = t - q + r - 1 > t + |C|\end{align*}

vertices in the copy of $K_t$ and C, a contradiction. Hence, $EX_2(n,t,r)*K_t$ does not contain a $K_r$ -factor.

We now give the extremal constructions which, excluding error terms, match the upper bounds given in Theorem 1.6.

One can see that the extremal examples in Definition 3.3 have the same construction to those in Definition 3.1 for $r = 2$ , except that in Definition 3.3 we omit the condition $2|(n+t)$ and add the condition that $\left\lceil\frac{n+t}{2}\right\rceil < n$ (in order for $EX_1(n,t)$ to be well-defined).

Observe that $e(EX_1(n,t))$ and $e(EX_2(n,t))$ asymptotically match the upper bounds given in Theorem 1.6. Indeed,

\begin{equation*}e(EX_1(n,t)) = \binom{n}{2} - \binom{\left\lceil\frac{n+t}{2}\right\rceil + 1}{2} \ \ \text{ and } \ \ e(EX_2(n,t)) = \binom{n}{2} - \left(t(n-1) - \binom{t}{2}\right).\end{equation*}

We conclude this section by showing that $EX_1(n,t)*K_t$ and $EX_2(n,t)*K_t$ do not contain certain $(n+t)$ -vertex bipartite graphs H.

For example, the Hamilton cycle (when $n+t$ is even), the disjoint union of an isolated vertex and a cycle on $n+t-1$ vertices (when $n+t$ is odd) and $K_{s,s}$ -factors (for any fixed $s \in \mathbb N$ ) belong to $\mathcal{H}_1$ ; the Hamilton cycle (when $n+t$ is even), $K_{s,s}$ -factors (for any fixed $s \in \mathbb N$ so that s does not divide t) and any bipartite graph with minimum degree at least $t+1$ belong to $\mathcal{H}_2$ .

Proof. First, let us consider $EX_1(n,t)*K_t$ . Since $EX_1(n,t)$ contains an independent set of size $\left\lceil\frac{n+t}{2}\right\rceil + 1$ , any bipartite graph from $\mathcal{H}_1$ cannot be in $EX_1(n,t)$ .

Now let us consider $EX_2(n,t)*K_t$ . Since $EX_2(n,t)$ has a set of t isolated vertices and $|K_t| = t$ , we require that any bipartite graph H spanning $EX_2(n,t)*K_t$ must have a tripartition (A,B,C) of V(H) such that $|A| = n-t$ , $|B| = |C| = t$ and every vertex in C is only adjacent to vertices in B, where $B = V(K_t)$ and C is the set of t isolated vertices in $EX_2(n,t)$ . Hence $EX_2(n,t)*K_t$ does not contain any graph in $\mathcal{H}_2$ .

4. Proof of Theorem 1.4

The proof of Theorem 1.4 follows an inductive argument on the number of vertices n of G. Given a graph G such that $G*K_t$ does not contain a $K_r$ -factor, we apply an appropriate vertex-modification procedure which, roughly speaking, allows us to assume G is locally isomorphic to one of the two extremal examples. This allows us to remove such local structure from G and apply induction.

The vertex-modification procedures are described by the following two structural lemmas regarding graphs G with the property that $G*K_t$ does not contain a $K_r$ -factor. Lemma 4.1 allows us to assume that the degree of a vertex is either $n-1$ (which is the degree of all vertices in $V(EX_1(n,t,r))\setminus A$ and $C\subset V(EX_2(n,t,r))$ ) or at most $n-1-\left\lceil\frac{t+1}{r-1}\right\rceil$ (which is the degree of all vertices in $V(EX_2(n,t,r))\setminus(B\cup C)$ ). Lemma 4.2 allows us to assume that either each edge of G belongs to some r-clique or there is a vertex with degree $n-1$ .

Proof. Suppose that there exists a vertex $v\in V(G)$ such that

\begin{equation*}n-1-\left\lceil\frac{t+1}{r-1}\right\rceil<d_G(v)<n-1.\end{equation*}

Let $G^{\prime}$ be the graph obtained from G by adding every possible edge incident to v, that is, $d_{G^\prime}(v) = n-1$ . Since e(G) is maximal with respect to $G*K_t$ not containing a $K_r$ -factor, we must have that $G^\prime*K_t$ contains a $K_r$ -factor $\mathcal{T^\prime}$ . Using $\mathcal{T^\prime}$ , we will now construct a $K_r$ -factor $\mathcal{T}$ in $G*K_t$ , giving us a contradiction.

Let $K^v$ be the copy of $K_r$ in $\mathcal{T^\prime}$ covering v. If $K^v \subseteq G*K_t$ then we can take $\mathcal{T}: = \mathcal{T'}$ . Hence assume $K^v \nsubseteq G*K_t$ . If there exists a copy $K^{\prime}$ of $K_r$ in $\mathcal{T'}$ that lies entirely in $K_t$ , then, for any $u \in V(K')$ , we can take

\begin{equation*}\mathcal{T} \,{:\!=}\, \left(\mathcal{T'}\setminus\{K^v, K'\}\right) \cup \left\{(G*K_t)[\{u\} \cup \left(V(K^v)\setminus \{v\}\right)], (G*K_t)[\{v\} \cup \left(V(K')\setminus \{u\}\right)]\right\}.\end{equation*}

Hence, assume no such copy of $K_r$ in $\mathcal{T'}$ exists. Since $K^v \nsubseteq G*K_t$ and no copy of $K_r$ in $\mathcal T'$ lies entirely in $K_t$ , the number of copies of $K_r$ in $\mathcal{T'}$ which cover some vertex of $\{v\} \cup V(K_t)$ in $G'*K_t$ is at least $\left\lceil\frac{t+1}{r-1}\right\rceil$ . But $d_G(v) > n-1 - \left\lceil\frac{t+1}{r-1}\right\rceil$ , hence there exists a copy $\hat{K}$ of $K_r$ in $\mathcal{T'}$ which intersects $\{v\} \cup V(K_t)$ and whose vertices are all neighbours of v in $G*K_t$ or v itself. Now, if $v \in V(\hat{K})$ , then $K^v=\hat{K} \subseteq G*K_t$ , a contradiction to our previous assumption. Hence, $V(\hat{K}) \cap V(K_t) \neq \emptyset$ and, for any $u \in V(\hat{K}) \cap V(K_t)$ , we can take

\begin{equation*}\mathcal{T} \,{:\!=}\, (\mathcal{T'}\setminus\{K^v, \hat{K}\}) \cup \big\{(G*K_t)[\{u\} \cup \left(V(K^v)\setminus \{v\}\right)] , (G*K_t)[\{v\} \cup (V(\hat{K})\setminus \{u\})]\big\}.\end{equation*}

Proof. Let xy be an edge in G which is not contained in any copy of $K_r$ . Let Q be a clique of maximal size containing xy and set $\ell \,{:\!=}\, |V(Q)|$ . Observe that every vertex in G has at most $\ell-1$ neighbours in Q as otherwise xy would lie in an $(\ell+1)$ -clique. Thus,

\begin{equation*}\sum_{v\in V(Q)} d_G(v) \leq n(\ell-1).\end{equation*}

Let $G^{\prime}$ be the graph obtained by deleting all edges between x and vertices in $V(G)\setminus V(Q)$ and, subsequently, adding any missing edge incident to any vertex in $V(Q)\setminus\{x\}$ . Note that Q is still an $\ell$ -clique in $G^{\prime}$ and

\begin{equation*}\sum_{v\in V(Q)} d_{G^\prime}(v) = n(\ell-1).\end{equation*}

Hence, $e(G)\leq e(G^\prime)$ . Also, $G^{\prime}$ is a graph on n vertices and $d_{G^\prime}(y) = n-1$ . It remains to show that $G'*K_t$ does not contain a $K_r$ -factor. Suppose, for a contradiction, that $G'*K_t$ does contain a $K_r$ -factor $\mathcal{T'}$ . We will now use $\mathcal{T}'$ to construct a new $K_r$ -factor $\mathcal{T}$ in $G'*K_t$ which does not contain any edge vw where $v \in V(Q)$ and $w \in V(G')\setminus V(Q)$ . Such a $K_r$ -factor $\mathcal{T}$ is also a $K_r$ -factor in $G*K_t$ , giving us a contradiction.

Suppose that the copy $K^x$ of $K_r$ in $\mathcal{T'}$ covering x has exactly s vertices in $K_t$ . Then $K^x$ has exactly $r-s$ vertices in Q. Thus, there are $\ell-r+s$ remaining vertices in $V(Q)\setminus V(K^x)$ . Note that $\ell-r+s\leq s$ , hence there is an injection $f \,{:}\, V(Q)\setminus V(K^x) \to V(K^x)\cap V(K_t)$ . We construct our $K_r$ -factor $\mathcal{T}$ as follows: for every copy of $K_r$ in $\mathcal{T}'$ intersecting Q other than $K^x$ , we substitute all vertices lying in its intersection with Q with their images under f. Finally, we take the copy of $K_r$ formed by the $\ell$ -clique Q and the $s - (\ell - r + s) = r-\ell$ vertices in $V(K^x)\cap V(K_t)$ which do not appear in the image of f. Observe that $\mathcal{T}$ does not use any edge vw where $v \in V(Q)$ and $ w \in V(G)\setminus V(Q)$ , and we are done.

Before proceeding to the proof of Theorem 1.4, we prove the following technical lemma.Footnote 1

Lemma 4.3. Let $n,t,r \in \mathbb N$ such that the following holds: $n,r \geq 3$ ; $r-1$ divides $t+1$ ; r divides $n+t$ ; $t+1<(r-1)(n-1)$ . If

(1) \begin{equation}e(EX_1(n-1,t+1,r)) < e(EX_2(n-1,t+1,r))\end{equation}

then

(2) \begin{equation}e(EX_2(n-1,t+1,r)) + (n-1) \leq e(EX_2(n,t,r)).\end{equation}

Proof. Let $k\,{:\!=}\,\frac{t+1}{r-1}$ . Since $r-1$ divides $t+1$ , we can compute $e(EX_2(n,t,r))$ and $e(EX_2(n-1,t+1,r))$ explicitly:

\begin{equation*}e(EX_2(n,t,r)) = \binom{n}{2}- \binom{k}{2} - k(n-k),\end{equation*}

\begin{equation*}e(EX_2(n-1,t+1,r)) = \binom{n-1}{2}- \binom{k+1}{2} - (k+1)(n-k-r).\end{equation*}

It follows that

\begin{equation*}e(EX_2(n,t,r))- e(EX_2(n-1,t+1,r))=(n-1) + k +(n-k-r)-kr.\end{equation*}

Rearranging this, one obtains that (2) holds precisely when

\begin{equation*} t \leq n - r - \frac{n}{r} \,{=\!:}\, g(n,r).\end{equation*}

Further, one can calculate that $e(EX_2(n-1,t+1,r)) \leq e(EX_1(n-1,t+1,r))$ precisely when

(3) \begin{equation} f_1(n,r) \,{:\!=}\, \frac{n(r-1)}{(2r^2 - 2r + 1)} - r \leq t \leq n(r-1) - r^2 \,{=\!:}\, f_2(n,r).\end{equation}

Since (1) holds, we have that (3) implies that $t < f_1(n,r)$ or $t > f_2(n,r)$ . Observe that $f_1(n,r) \leq g(n,r)$ . Thus, if $t < f_1(n,r)$ then $t < g(n,r)$ and the claim holds.

Suppose $t > f_2(n,r)$ . We will show that in this case the hypothesis of the lemma cannot actually hold. In particular, under the assumptions that $r-1$ divides $t+1$ , r divides $n+t$ and $t > f_2(n,r)$ , $EX_2(n-1,t+1,r)$ is undefined. Indeed, for a contradiction let us assume that $EX_2(n-1,t+1,r)$ is well-defined in this case, thus the inequality $t+1<(r-1)(n-1)$ must hold. By assumption, t satisfies the following modular equations:

(4) \begin{equation} t\equiv -1 \quad(\text{mod}\; r-1)\quad\text{and}\quad t\equiv -n\quad(\text{mod}\; r).\end{equation}

For n and r fixed, the solution of (4) is unique modulo $r(r-1)$ by the Chinese Remainder Theorem, since r and $r-1$ are coprime. Note that $t'=(r-1)(n-1)-1$ is a solution of (4), hence $t=(r-1)(n-1)-1-kr(r-1)$ for some integer k. The constraint $t+1<(r-1)(n-1)$ forces $k\geq 1$ , hence

\begin{equation*}t\leq (r-1)(n-1)-1-r(r-1)=n(r-1)-r^2=f_2(n,r).\end{equation*}

This contradicts the assumption that $t > f_2(n,r)$ .

Proof of Theorem 1.4. We prove Theorem 1.4 by induction on n. If $n=2$ then $e(G) \in \{0, 1\}$ . Since $t < 2(r-1)$ and $r |(n+t)$ , we must have $t = r-2$ . If $e(G) = 1$ then $G*K_t$ is a copy of $K_r$ , contradicting our choice of G. Thus $e(G) = 0$ . Observe that $k = \left\lceil\frac{t+1}{r-1}\right\rceil = 1$ and $q = r-2$ . Thus,

\begin{equation*}\max\left\{\binom{n}{2} - \binom{\frac{n+t}{r} + 1}{2}, \binom{n}{2} - \binom{k}{2} - k(n - k - (r - 2 - q))\right\} = \max\{0,0\} = 0.\end{equation*}

Thus, Theorem 1.4 holds for $n = 2$ .

For the inductive step, we may assume without loss of generality that G is a graph on n vertices such that e(G) is maximal with respect to the property that $G*K_t$ does not contain a $K_r$ -factor.

Case (i): G contains an isolated vertex v. If $t < r-2$ , then one could add a single edge to v and G would still not contain a $K_r$ -factor, contradicting our choice of G. Hence, $t \geq r-2$ . If $t = r - 2$ , then $k = \left\lceil\frac{t+1}{r-1}\right\rceil= 1$ and $q = r-2$ . Hence

\begin{align*} &\max\left\{\binom{n}{2} - \binom{\frac{n+t}{r} + 1}{2}, \binom{n}{2} - \binom{k}{2} - k(n - k - (r - 2 - q))\right\} \\= &\max\left\{\binom{n}{2} - \binom{\frac{n-2}{r} + 2}{2}, \binom{n-1}{2}\right\}.\end{align*}

Since G contains at least one isolated vertex,

\begin{equation*}e(G) \leq \binom{n-1}{2} \leq \max\left\{\binom{n}{2} - \binom{\frac{n-2}{r} + 2}{2}, \binom{n-1}{2}\right\},\end{equation*}

and we are done. If $t \geq r-1$ , consider the graph ${G}^{\prime}$ obtained by deleting v from G. Since $G*K_t$ does not contain a $K_r$ -factor, $G^\prime*K_{t-r+1}$ does not contain a $K_r$ -factor. Thus, by our inductive hypothesis

\begin{equation*}e(G^\prime)\leq\max\{e(EX_1(n-1,t-r+1,r)), e(EX_2(n-1,t-r+1,r))\}.\end{equation*}

It follows from $e(G)=e(G^\prime)$ and $e(EX_i(n-1,t-r+1,r))\leq e(EX_i(n,t,r))$ Footnote 2 for $i=1,2$ that $e(G)\leq\max\{e(EX_1(n,t,r)), e(EX_2(n,t,r))\}$ .

Case (ii): G contains a vertex of degree $n-1$ . Consider the graph ${G}^{\prime}$ obtained by deleting such a vertex from G. Note that $G*K_t=G^\prime*K_{t+1}$ . If $t+1\geq (r-1)(n-1)$ , then trivially $G^\prime*K_{t+1}$ contains a $K_r$ -factor, a contradiction. So we must have that $t+1< (r-1)(n-1)$ and hence by induction

\begin{equation*} e(G^\prime)\leq\max\{e(EX_1(n-1,t+1,r)), e(EX_2(n-1,t+1,r))\}.\end{equation*}

Observe that $e(G)=e(G^\prime)+n-1$ . We aim to show that

(5) \begin{equation} e(G)\leq\max\{e(EX_1(n,t,r)), e(EX_2(n,t,r))\}.\end{equation}

If $e(G^\prime)\leq e(EX_1(n-1,t+1,r)$ , then

\begin{equation*}e(G*K_t) = e(G^\prime*K_{t+1}) \leq e(EX_1(n-1,t+1,r)*K_{t+1}) = e(EX_1(n,t,r)*K_t)\end{equation*}

and thus

\begin{equation*}e(G) \leq e(EX_1(n,t,r)).\end{equation*}

Similarly, if $e(G^\prime)\leq e(EX_2(n-1,t+1,r)$ and $r-1$ does not divide $t+1$ then

\begin{equation*}e(G*K_t) = e(G^\prime*K_{t+1}) \leq e(EX_2(n-1,t+1,r)*K_{t+1}) = e(EX_2(n,t,r)*K_t)\end{equation*}

and thus

\begin{equation*}e(G) \leq e(EX_2(n,t,r)).\end{equation*}

It remains to check that (5) holds in the case when $(r-1)|(t+1)$ and

\begin{equation*} e(EX_1(n-1,t+1,r)) < e(EX_2(n-1,t+1,r)).\end{equation*}

In this case, Lemma 4.3 implies that

\begin{equation*}e(G)=e(G^\prime)+ n - 1 \leq e(EX_2(n-1,t+1,r)) + (n-1) \leq e(EX_2(n,t,r)),\end{equation*}

as desired.

Case (iii): G contains no vertex of degree 0 or $n-1$ . If G contains an edge which is not contained in any copy of $K_r$ , then by Lemma 4.2 there exists a graph ${G}^{\prime}$ on n vertices such that $G^\prime*K_t$ does not contain a $K_r$ -factor, $e(G)\leq e(G^\prime)$ and $G^{\prime}$ has a vertex of degree $n-1$ . The argument from Case (ii) then implies that $e(G) \leq e(G^\prime) \leq \max\{e(EX_1(n,t,r)), e(EX_2(n,t,r))\}$ .

We may therefore assume every edge of G is contained in some copy of $K_r$ . Moreover, as no vertex in G has degree 0, every vertex in G is contained in a copy of $K_r$ . Let w be a vertex of smallest degree in G. If $d_{G}(w) \geq n-\frac{n+t}{r}$ , then

\begin{equation*}\delta(G*K_t) \geq n-\frac{n+t}{r}+t=\frac{r-1}{r}(n+t).\end{equation*}

Hence, by Theorem 1.2, we have that $G*K_t$ contains a $K_r$ -factor, a contradiction.

Thus, $d_{G}(w)<n-\frac{n+t}{r}$ . Let K be a copy of $K_r$ in G containing w. Consider the graph ${G}^{\prime}$ obtained by removing K and all its vertices from G. Then, $G^\prime*K_t$ does not contain a $K_r$ -factor; this implies that $t<(r-1)(n-r)$ . Hence, by our inductive hypothesis, we have

\begin{equation*}e(G^\prime)\leq\max\{e(EX_1(n-r,t,r)), e(EX_2(n-r,t,r))\}.\end{equation*}

If $e(G^\prime)\leq e(EX_1(n-r,t,r))$ , then $d_{G}(w)<n-\frac{n+t}{r}$ implies $e(G)\leq e(EX_1(n,t,r))$ , as desired: this follows from the fact that $EX_1(n-r,t,r)$ can be obtained by removing a clique Q of size r from $EX_1(n,t,r)$ where Q has one vertex of degree $n-\frac{n+t}{r}-1$ . By Lemma 4.1, we have that $\Delta(G)\leq n-1-\left\lceil\frac{t+1}{r-1}\right\rceil$ since we assumed G contains no vertices of degree $n-1$ and e(G) is maximal with respect to the property that $G*K_t$ does not contain a $K_r$ -factor. Thus, if $e(G^\prime)\leq e(EX_2(n-r,t,r))$ , then applying this observation yields that $e(G)\leq e(EX_2(n,t,r))$ , as desired: similarly as before, this follows from the fact that $EX_2(n-r,t,r)$ can be obtained by removing a clique Q of size r from $EX_2(n,t,r)$ where all vertices in Q have degree $n-1-\left\lceil\frac{t+1}{r-1}\right\rceil$ .

5. Proof of Theorem 1.6

In the proof of Theorem 1.6, we will make use of the following theorem of Knox and Treglown [Reference Knox and Treglown10].

Theorem 5.1 (Knox and Treglown [Reference Knox and Treglown10]). Given any $\Delta \in \mathbb N$ and any $\gamma >0$ , there exists constants $\beta >0$ and $n_0 \in \mathbb N$ such that the following holds. Suppose that H is a bipartite graph on $n \geq n_0$ vertices with $\Delta (H) \leq \Delta$ and bandwidth at most $\beta n$ . Let G be a graph on n vertices with degree sequence $d_1\leq \dots \leq d_n$ . If

\begin{equation*}d_{i} \geq i+\gamma n \ \text{ for all } \ i < n/2,\end{equation*}

then G contains a copy of H.

In fact, Knox and Treglown proved a more general result for robust expanders (see [Reference Knox and Treglown10, Theorem 1.8]). We use Theorem 5.1 in a similar way to how Chvátal’s theorem [Reference Chvátal4] is used in the proof of Theorem 1.1 in [Reference Nenadov, Sudakov and Wagner13].

Proof. Let $\Delta \in \mathbb{N}$ and $\varepsilon > 0$ . Define $\gamma > 0$ such that $\gamma \ll \varepsilon, 1/\Delta$ . Apply Theorem 5.1 with $\Delta$ and $\gamma$ to produce constants $\beta > 0$ and $n_0 \in \mathbb{N}$ such that

\begin{equation*} 0 < \frac{1}{n_0} \ll \beta \ll \gamma \ll \varepsilon, \frac{1}{\Delta}.\end{equation*}

Let $t \in \mathbb N$ , $n \geq n_0$ and H be an $(n+t)$ -vertex graph as in the statement of the theorem. Suppose that G is a graph on n vertices such that $G*K_t$ does not contain H. Let m(G) denote the number of missing edges in G, that is, $m(G) \,{:\!=}\, \binom{n}{2} - e(G)$ . Then proving Theorem 1.6 is equivalent to proving the following bound on m(G):

(6) \begin{align} m(G) \geq \begin{cases} t(n-1) - \binom{t}{2} - \varepsilon n^2\ \ \mbox{if} \ \ t \leq \dfrac{n}{5} \\[0.5em] \binom{\lceil (n+t)/2 \rceil + 1}{2} - \varepsilon n^2 \ \ \mbox{if} \ \ t > \dfrac{n}{5}. \end{cases}\end{align}

Let $G^\prime \,{:\!=}\, G*K_t$ and label the vertices of $G^{\prime}$ as $v_1, \ldots, v_{n+t}$ such that $d_{G^\prime}(v_i) \,{:\!=}\, d_i$ is the degree of vertex $v_i$ and $d_1 \leq d_2 \leq \ldots \leq d_{n+t}$ . Since $G^{\prime}$ does not contain H as a subgraph, it does not satisfy the degree sequence condition of Theorem 5.1. Moreover, $\delta(G^\prime) \geq t$ , hence there must exist $t - \gamma(n+t) < i \leq \left\lceil(n+t)/2\right\rceil - 1$ such that $d_i < i + \gamma(n+t)$ . From $d_1 \leq \ldots \leq d_i < i + \gamma(n+t) $ we deduce that the number of edges missing from $G^{\prime}$ is at least

(7) \begin{align} m(G^\prime) \geq \sum_{j=1}^i(n+t-1-d_j) - \binom{i}{2} & > i(n+t-1-i-\gamma(n+t)) - \binom{i}{2}\nonumber \\ & \geq i((1 - 2\gamma)(n + t) - i) - \binom{i}{2} \,{=\!:}\, f(i).\end{align}

Set $u \,{:\!=}\, \left\lceil(n+t)/2\right\rceil - 1$ . Now f(i) is a quadractic in i and $\frac{d^2(f(i))}{di^2} < 0$ . Also, note that $m(G) = m(G^\prime)$ . Hence, as $t - \gamma(n+t) < i \leq u$ , we have from (7) that

(8) \begin{equation} m(G) \geq \min\{f(t - \gamma(n+t) ), f(u)\}.\end{equation}

One can calculate that

(9) \begin{equation} f(t - \gamma(n+t) ) \leq f(u) \ \ \mbox{if and only if} \ \ t \leq \begin{cases} \dfrac{n - 2\gamma n + 8}{5 + 2\gamma} \ \ \mbox{if $n + t$ is even} \\ \\[-7pt] \dfrac{n - 2\gamma n + 5}{5 + 2\gamma} \ \ \mbox{if $n + t$ is odd}. \end{cases}\end{equation}

As $\frac{1}{n} \ll \gamma \ll \varepsilon$ we have

(10) \begin{equation} f(t - \gamma(n+t)) \geq t(n-1) - \binom{t}{2} - \varepsilon n^2\end{equation}

and

(11) \begin{equation} f(u) \geq \binom{\lceil (n+t)/2 \rceil + 1}{2} - \dfrac{\varepsilon n^2}{2}.\end{equation}

Moreover, for $\frac{n - 2\gamma n + 5}{5 + 2\gamma} \leq t \leq \frac{n}{5}$ we have

(12) \begin{equation} f(u) \geq \binom{\lceil (n+t)/2 \rceil + 1}{2} - \dfrac{\varepsilon n^2}{2} \geq t(n-1) - \binom{t}{2} - \varepsilon n^2.\end{equation}

Regardless of the parity of $n+t$ , using (8)–(12) we conclude that (6) holds.

6. Concluding remarks

In this paper, we resolved the deficiency problem for $K_r$ -factors. For a general fixed graph H, it would be interesting to prove deficiency results regarding H-factors. As a starting point for this problem,we pose the following question. Let $\alpha(H)$ denote the size of the largest independent set in H.

Question 6.1 Let $K \,{:\!=}\, K_n$ and $A \subseteq K$ such that $A = K_{\frac{\alpha(H)(n+t)}{|H|} + 1}$ . Define $EX_H(n,t)$ to be the graph obtained by removing E(A) from K. Does there exist a constant $c\,{:\!=}\,c(H)>0$ such that if $t\geq c n$ and G is an n-vertex graph so that $G*K_t$ does not contain an H-factor then $e(G) \leq e(EX_H(n,t))+o(n^2)$ ?

Note that Theorem 1.6 answers this question in the affirmative e.g. for $H=K_{s,s}$ (for fixed $s \in \mathbb N$ ). On the other hand, at least for some H one cannot remove the $o(n^2)$ term in Question 6.1 completely. Indeed, let $H =K_{1,s}$ where $s \geq 2$ and consider the n-vertex graph $EX^\prime_H(n,t)$ obtained from $EX_H(n,t)$ by adding a maximal matching in V(A). It is easy to see that $EX^\prime_H(n,t)*K_t$ does not contain a $K_{1,s}$ -factor. This example suggests it might be rather challenging to resolve the H-factor deficiency problem completely for all graphs H.

It would also be interesting to prove bandwidth deficiency results in the vein of Theorem 1.6 for non-bipartite graphs H.