TITLE: Prove that the number of pairs in a string starting and ending with $1$ is $\frac{m(m-1)}{2}$
QUESTION [2 upvotes]: In a given binary string, we have to find the number of pairs starting and ending with $1$.
By analysis the solution of this problem is $\frac{m(m-1)}{2}$ where $m$ is the number of $1$'s in the string.
How do we mathematically prove the above statement?

REPLY [2 votes]: I assume you mean substrings of length at least 2. In that case, your formula is simply $m \choose 2$ which makes sense: you want all substrings beginning and ending with 1 of length at least 2. That is, you need to count the number of distinct pairs of 1's. This is exactly that $m \choose 2$ gives you.


text:
\section{Technical proofs}
\label{sec:prmisc}

\subsection{Proof of relation~\eqref{eq:oracle-quad-loss}}

From \eqref{eq:l1f-bias} it follows that
\[\|x - \varphi^o* x\|_{n,2}\leq

\sqrt{2}\kappa_{m,n}\sigma\theta\varrho.
\]

On the other hand,
\[
\|\varphi^o*\zeta\|_{n,2}^2=\langle \zeta,M(\varphi^o)\zeta\rangle_{n},
\]
where $M(\varphi)$ is defined by~\eqref{M(phi)}. Bounding $\|\varphi^o\|_2 \le \|\vphi^o\|_{m,1}^\F$ via~\eqref{eq:l1f}, and using~\eqref{tr22}, we obtain
\[
\|M(\varphi^o)\|_\F^2=(2n+1)\|\varphi^o\|_2^2\leq \kappa_{m,n}^2\varrho^2.
\]
Deviation bound~\eqref{trq1} now implies, for any $0 < \alpha \le 1$, that with probability at least $1-\alpha$,
\be
\|\varphi^o*\zeta\|_{n,2}\leq \sqrt{2}\kappa_{m,n}\varrho\big(1+\sqrt{\log[1/\alpha]}\big),
\ee{eq:varphizeta}
and we arrive at
\eqref{eq:oracle-quad-loss}.
\qed

\subsection{Proof of Proposition \ref{th:l2point}}
We only give the proof for the contrained estimator $\wh\vphi = \wh\vphi_{\con}$; the penalized estimator can be treated analogously.
First, for $t \in \Z$ we decompose
\begin{equation}
\label{eq:l2point-long}
\begin{aligned}
|[x - \widehat\varphi * y]_t|
&=|[(\phi^o+(1-\phi^o))*(x - \widehat\varphi * y)]_t|\\
&\leq |[\phi^o*(x - \widehat\varphi * y)]_t| + |[(1-\widehat \varphi) * (1 - \phi^o) * x]_t|
+ \sigma|[\widehat \varphi * \zeta]_t| + \sigma|[\widehat \varphi * \phi^o * \zeta]_t|\\
&:=\delta^{(1)}+\delta^{(2)}+\delta^{(3)}+\delta^{(4)}.
\end{aligned}
\end{equation}

For the remainder of the proof, let~$t \in \Dom_{n-m_0}$.
Then, we have
\[
\begin{aligned}
\delta^{(1)}
&\leq \|\phi^o\|_2 \big\|\Delta^{-t} [x - \widehat\varphi * y]\big\|_{m_0,2} \nn
&\leq {\rho\over \sqrt{m+1}} \|x - \widehat\varphi * y\|_{n,2}.
\end{aligned}
\]

Using the bound of Corollary  \ref{cor:l2con} with $\bar{\vrho}=2\rho^2$, we conclude that with probability $\ge 1-\alpha/3$,
\[
\delta^{(1)} \leq  {C\sigma\rho\over \sqrt{m+1}}\left[\kappa_{m,n}\rho^2(1+\theta+\sqrt{\log[1/\alpha]}) + \rho\sqrt{(\kappa_{m,n}^2+1)\log[{(m+n)/ \alpha}] + \varkappa\sqrt{\log[{1/ \alpha}]}}+
\sqrt{s}\right].
\]

It remains to make sure that the remaining terms are dominated by~$\delta^{(1)}$.
We get
\[
\begin{aligned}
\delta^{(2)}
&\le \left(1 + \left\|\widehat\varphi\right\|_1\right) \left\|\Delta^{-t}[(1 - \phi^o) * x]\right\|_{m_0,\infty} \\
&\le (1+2\rho^2){\sigma\theta\rho\over \sqrt{m+1}}\\
&\le {C\kappa_{m,n}\rho^3\sigma\theta\over\sqrt{m+1}},
\end{aligned}
\]
where the last transition is due to $n \ge m_0$.

Further, by the Parseval's identity,
\begin{align*}
\delta^{(3)}
&=\sigma|\langle F_{m}[\wh\vphi], F_{m}[\Delta^{-t} \zeta]\rangle| \nn
&\leq \sigma\|\widehat{\varphi}\|^\F_{m,1} \|\Delta^{-t}\zeta\|^\F_{m,\infty} \\
&\le \frac{2\rho^2}{\sqrt{m+1}}\sigma\sqrt{2 \log \left[3(2m+1)(2n-2m_0+1)/\alpha\right]},
\end{align*}
where the last inequality, holding with probability $\ge 1-\alpha/3$, is due to \eqref{eq:complex_gaussian_max}.

Finally, observe that with probability $\geq 1-\alpha/3$ it holds
\[
\|\Delta^{-t}[\phi^o * \zeta]\|_{m,2} \le \|\phi^o * \zeta\|_{n,2} \leq \sqrt{2}\kappa_{m,n}\rho\left(1+\sqrt{\log[3/\alpha]}\right),
\]
cf. \eqref{eq:varphizeta}.
Therefore, we have for $\delta^{(4)}$:
\[
\begin{aligned}
\delta^{(4)}
&\le \sigma\|\widehat \varphi\|_{m,2} \left\| \Delta^{-t} [\phi^o * \zeta] \right\|_{m,2} \nn
&\le \sigma\frac{2\rho^2}{\sqrt{m+1}} \sqrt{2}\kappa_{m,n} \rho\left(1+\sqrt{\log[3/\alpha]}\right)  \nn
&= \frac{2\sqrt{2}\kappa_{m,n} \sigma \rho^3}{\sqrt{m+1}}\left(1+\sqrt{\log[3/\alpha]}\right)
\end{aligned}
\]
with probability $\ge 1-\alpha/3$.
Substituting the bounds for $\delta^{(k)},\,k=1,...,4$, into \eqref{eq:l2point-long}, we arrive at the claim. \qed

config: arxiv


TITLE: Relation between direct sum and tensor product
QUESTION [2 upvotes]: I will risk myself on a general/vague but nonetheless "titillating" question:
-One may have encountered the fact that any representation of a compact group can be written as a direct sum of irreducible representations, in particular the tensor product of two representations i.e. we have an equality of representations of the form
 $$V_a \otimes V_b = \bigoplus_{i\in I} V_i $$
-Similarly to the situation for integers, one has for a vector space $V$ over $\mathbb{K}$
 $$ V\otimes K^{n}= \bigoplus_{i=1}^n V \quad\text{(to compare with)}\; d\times n = d+d+\cdots+ d $$
Is there a category (moinoidal abelian?, for which at least the direct sum and the tensor product exist) where under some appropriate conditions one has equality of a non trivial tensor product  and a non trivial direct sum?
Edit: Indeed I'm not so much interested in the unicity of the decomposition.
However I find it incredible that in the two examples above, one has an object that satisfies two distinct universal properties, namely the one for a tensor product and the one for a coproduct.
In the case one has the direct sum of only itself, the universal doesn't impose anything.
Such situation where two different universal properties are related or actually coincide does occur, e.g. of preadditive category where product and coproduct agree (from biproduct in wikipedia).

REPLY [1 votes]: In a commutative monoid $G\ni g$ one has $n\cdot g = g+ \cdots + g$ n times, for n integer.
i.e. there is a natural action of the non negative intergers on any commutative monoid. Multiplication is the action of the integer, addition is the operation in the monoid.
It seems to transpose to monoidal categories with direct sum.

For the first example, in the so called semi simple category, any object can be written as a finite direct sum. cf. nLab
The second example is of the form
$$ V \otimes (W\oplus Z) = (V\otimes W)\oplus(V\otimes Z)$$
Moreover the field $\mathbb{K}$ is a "tensor unit" or left/right unitor in wiki
cf. also "isotypical representation" (of a compact group I guess), "6 j symbol", "fusion rule"
check this question


TITLE: Conformal structure determined by principal curvatures
QUESTION [5 upvotes]: On a smooth surface of positive Gauss curvature that is embedded in Euclidean 3 space the principal curvatures seem to define a smooth field of ellipses whose major and minor axes are lined up with the directions of curvature and whose ratio of lengths is k1/k2, the ratio of the principal curvatures.
My first question is whether there is true or whether there is a flaw in this observation.
If true, the embedding determines a conformal structure and I assume that the associated Riemannian metric is determined by the usual equations
1 + |u|/ 1 - |u| = k1/k2 or |u| = k1 - k2/ k1 + k2 with arg(u) = 0. So ds^2 = (dz + udz_)^2
My second question is whether this is correct.
Finally, if this construction works what can be said about the possible conformal structures and Riemannian geometries that can be obtained in this way from embeddings of surfaces of positive curvature in 3 space? Can the new metric be realized in 3 space?
Can this be generalized?

REPLY [3 votes]: When defined as a tensor taking values in the normal bundle the second fundamental form of a hypersurface in $\mathbb{R}^{n+1}$ depends only on the affine structure on the ambient space, not on its metric structure. On the locus where it is non-degenerate it determines a conformal structure which has been used in studying the affine geometry of the hypersurface at least since the 1930's (see the second volume of Blaschke's book Vorlesungen über Differentialgeometrie entitled Affine Differentialgeometrie). If one restricts attention to those aspects of the geometry of the hypersurface preserved by unimodular affine transformations, then a particular representative, called the Blaschke or equiaffine metric, is determined. With respect to a Euclidean unit normal, it is the second fundamental form multiplied by the $-1/(n+2)$ power of the Gaussian curvature. That is, if the hypersurface is written locally as the graph of $f$ then the metric is given in coordinates $|\det f_{ij}|^{-1/(n+2)}f_{ij}$, where $f_{ij} = \tfrac{\partial^{2}f}{\partial x^{i} \partial x^{j}}$. When the second fundamental form is locally strictly convex, this metric is Riemannian, and much use of it has been made in the study of such hypersurfaces. To my taste the best introduction to these matters is provided by two papers of Calabi: Complete affine hyperspheres. I (there is no sequel) and Hypersurfaces with maximal affinely invariant area.
When the hypersurface is non-degenerate there can be defined the affine normal, which is a vector field transverse to the hypersurface that transforms equivariantly under the action of unimodular affine transformations on the ambient space. Via the splitting induced by this normal the flat affine connection on the ambient space induces an affine connection on the hypersurface. The difference of this affine connection with the Levi-Civita connection of the equiaffine metric is a tensor, which if its contravariant index is lowered using the metric, is completely symmetric. This completely symmetric covariant tensor three tensor (the Pick form) and the equiaffine metric encode the geometry of the hypersurface. Such a pair can be considered in the abstract, and the local obstructions to realizing it as that induced on a non-degenerate hypersurface are given in terms of the curvature of the affine connection and the Pick form, and, if I remember right, can be found in the textbook Affine differential geometry of Nomizu and Sasaki. Where such obstructions come from can be seen as follows. The map assigning to a point of the hypersurface the annihilator of its tangent space takes values in the projectivization of the vector space dual to the ambient space; this map is an immersion if and only if the hypersurface is non-degenerate. In this case the pullback via this map of the flat projective structure induces a flat projective structure on the hypersurface. A particular connection representative of this projective structure is distinguished by the requirement that its difference with the Levi-Civita connection of the equiaffine metric be the negative of the Pick form. Then for an arbitrary pair comprising a metric and a completely symmetric covariant three tensor to be that induced on an immersed hypersurface, a necessary condition is that the connection formed by adding to the Levi-Civita connection the negative of the three tensor (with an index raised) be projectively flat.
As far as I am aware the question of when such a pair can be realized globally via a proper embedding has not been studied other than in some particular cases, determined by conditions on the affine shape operator of the putative embedding, conditions which can be stated solely in terms of the Ricci curvature of the metric and the Pick form. Much of it boils down to controlling the size of the Pick form. For instance, the heart of Calabi's paper on complete affine hyperspheres is a differential inequality for the Laplacian (in the equiaffine metric) of the norm of the Pick form. In this regard, in addition to the aforementioned papers of Calabi, N. Trudinger and X.-J. Wang's survey The Monge-Ampère equation and its geometric applications and J. Loftin's Survey on affine spheres are good starting points.
In the two-dimensional case the conformal structure determines a complex structure, and it helps to use it. For this two basic references are Changping Wang's Some examples of complete hyperbolic affine $2$-spheres in $\mathbb{R}^{3}$ and Calabi's Convex affine maximal surfaces.


TITLE: Algorithm for deciding satisfiability of a universal statement
QUESTION [2 upvotes]: Question:
Given $\Sigma = \lbrace c , R_1^2, ... , R_k^2 \rbrace $ when c is a constant. Prove / disprove that exists an finite time algorithm for deciding satisfiability of a universal statement A.
My proof:
True: Due to Herbrand's theorem, a universal statement is satisfiable $\iff$ all of it's ground instances are satisfiable. Since there are no function symbols then this just means checking $c$ in every ground instance of the statement A and this is finite as the statement is of finite length.
I want to make sure that this argument is indeed true.

REPLY [3 votes]: Your argument is right, but you don't need to appeal to a strong result like Herbrand's theorem. Universal sentences are preserved under substructures, i.e., if $\phi$ has the form $\forall\overline{x}\psi$ where $\psi$ is quantifier-free and if $\phi$ is valid in a structure $M$, then $\phi$ is valid in any substructure of $N$. For your signature containing only a constant symbol $c$ and some relation symbols, any substructure $M$ has a substructure $N$ whose universe comprises the singleton set $\{c\}$ and $\phi$ must be valid in $N$ if it is to be valid in $M$. This does imply (if you like to put it that way), that $\phi$ is satisfiable iff its ground instances are satisfiable.


TITLE: Splitting the representation of $\mathbb{R}$ on $L^2(\mathbb{R})$ into irreducibles.
QUESTION [6 upvotes]: On p2 of these notes, the author writes that the translation action of $\mathbb{R}$ on $L^2(\mathbb{R})$ is a reducible representation which does not contain any irreducible subrepresentations. Presumably by $L^2(\mathbb{R})$ he means the square integrable functions $f : \mathbb{R}\rightarrow\mathbb{C}$.
"Indeed, for any measurable set $S\subset\mathbb{R}$, the space of functions $f$ for which the Fourier transform $\hat{f}$ has support in $S$ is a proper closed invariant subspace."
This space is certainly invariant - how would one see that it is closed?
"By Schur's lemma, any irreducible subrepresentation $W\subset L^2(\mathbb{R})$ would have dimension 1, ie $W = \langle F\rangle$ where $F: \mathbb{R}\rightarrow\mathbb{C}$ is a function such that $F(x+r)$ is proportional to $F(x)$. Thus, $F(x)$ is proportional to $e^{\lambda x}$ for some $\lambda\in\mathbb{C}$, but no such function lies in $L^2$"
No issues with this.
"However, a representation "decomposes" into a (possibly uncountable) number of irreducibles. This is the theory of "unitary disintegration""
This is my main question - what does he mean by this? Googling "unitary disintegration" did not yield any relevant results. Furthermore, how can a representation decompose into irreducibles, but have no irreducible subrepresentations?
References would be appreciated.

REPLY [2 votes]: Let $G = \mathbb R$, and $V = L^2(\mathbb R)$, which is a unitary representation of $G$ with the translation action.  It is true (more generally of unitary representations of locally compact groups) that if $W \subset V$ is a subrepresentation, then there exists another subrepresentation $W'$ of $V$ such that $V = W \oplus W'$.  Consequently, $V$ is semisimple as an abstract representation of $G$: there exist irreducible subrepresentations $W_i$ of $V$ such that
$$V = \bigoplus\limits_i W_i.$$
This is an algebraic direct sum, which means for every $v \in V$, there exist unique $w_i \in W_i$, all but finitely many of which are $0$, such that $v = \sum\limits w_i$.
This is not what representation theorists who study Hilbert space representations are interested in.  They are interested, in decomposing representations into a direct sum of irreducibles in a different sense: that is, in the best case scenario they are interested in finding closed irreducible representations $W_i$ of $V$ (that is, closed subspaces $W_i$ of $V$ which are subrepresentations of $G$, and which themselves admit no nonzero, proper, closed  subrepresentations $W_i'$ of $W_i$) such that the $W_i$ are mutually orthogonal, and such that
$$V = \hat{\bigoplus\limits_i} W_i \tag{Hilbert space direct sum}$$
This last condition means that for every $v \in V$, there exist $w_i \in W_i$ such that $v = \sum\limits_i w_i$ (as an absolutely convergent sum in the norm topology).
This turns out to be impossible in this case, since $V = L^2(\mathbb R)$ does not have any closed, irreducible subrepresentations: if $W$ were such a subrepresentation, it would have to be one-dimensional and correspond to a unitary character of $\mathbb R$.  Then there would have to exist a function $f: \mathbb R \rightarrow \mathbb C$ and a real number $t$, such that
$$\int\limits_{\mathbb R} |f(x)|^2 dx < \infty$$
$$ f(x+y) = e^{ 2 \pi i ty} f(x) \tag{$x,y \in \mathbb R$}$$
and this is impossible.


text:
\section{Related work}

Our work lies in the intersection of several fields: the theory of Lie groups, Riemannian geometry and deep neural systems. We provide an
overview of the related literature below.

\textbf{Matrix flows.} Differential equations (DEs) on manifolds lie at the heart of modern differential geometry \cite{Ciarlet2005AnIT} which is a key ingredient to understanding structured optimization for stabilizing neural network training \cite{stoch_1}. In our work, we consider in particular matrix gradient flows on $\mathcal{O}(d)$ that are solutions to trainable matrix DEs. In order to efficiently compute these flows, we leverage the theory of compact Lie groups that are compact smooth manifolds equipped with rich algebraic structure \cite{lee, compact_lie, olver}. For efficient inference, we apply local linearizations of $\mathcal{O}(d)$ via its Lie algebra (skew-symmetric matrices vector spaces) and exponential mappings \cite{warner} (see: Sec. \ref{sec:algorithm}).

\textbf{Hypernetworks.} An idea to use one neural network (hypernetwork) to provide weights for another network \cite{ha_1} can be elegantly adopted to the nested Neural ODE setting, where \cite{anode_v2} proposed to construct time-dependent parameters of one Neural ODE as a result of concurrently evolving another Neural ODE. While helpful in practice, this is insufficient to fully resolve the challenge of vanishing and exploding gradients. We expand upon this idea in our gated-$\mathrm{ODEtoODE}$ network, by constraining the hypernetwork to produce skew-symmetric matrices that are then translated to those from the orthogonal group $\mathcal{O}(d)$ via the aforementioned exponential mapping.

\textbf{Stable Neural ODEs.} On the line of work for stabilizing training of Neural ODEs, \cite{how_to_train_neural_ode} proposes regularization based on optimal transport, while \cite{stabilizing_neural_ode} adds Gaussian noise into the ODE equation, turning it into a stochastic dynamical system. \cite{augmented_neural_ode} lifts the ODE to a higher dimensional space to prevent trajectory intersections, while \cite{towards_robust_stochastic_differential_equations, stable_neural_flows} add additional terms into the ODE, inspired by well known physical dynamical systems such as Hamiltonian dynamics.

\textbf{Orthogonal systems.} For classical non-linear networks, a broad class of methods which improve stability and generalization involve orthogonality constraints on the layer weights. Such methods range from merely orthogonal initialization \cite{orthogonal_init, orthogonal_init_proof} and orthogonal regularization \cite{BansalCW18, XieXP17} to methods which completely constrain weight matrices to the orthogonal manifold throughout training using Riemannian optimization \cite{lee}, by projecting the unconstrained gradient to the orthogonal group $\mathcal{O}(d)$ \cite{shalit}. Such methods have been highly useful in preventing exploding/vanishing gradients caused by long term dependencies in recurrent neural networks (RNNs) \cite{ortho_1, ortho_2}. \cite{dynamical_isometry_cnn, dynamical_isometry_rnn} note that \textit{dynamical isometry} can be preserved by orthogonality, which allows training networks of very large depth.


TITLE: How to prove that there is always one non-trivial real solution for the following simultaneous equations?
QUESTION [0 upvotes]: How to prove that there is always one non-trivial  real solution $(x_0,y_0,z_0,r)$ for the following simultaneous equations?
$$
(x_i-x_0)^2 + (y_i-y_0)^2 + (z_i-z_0)^2 = r^2
$$
for $i=1,2,3,4$, and
$$\left|
\begin{array}{ccc}
x_2-x_1 & x_3-x_1 & x_4-x_1 \\
y_2-y_1 & y_3-y_1 & y_4-y_1 \\
z_2-z_1 & z_3-z_1 & z_4-z_1
\end{array}
\right|\not= 0
$$

REPLY [0 votes]: The simultaneous equations can be written as,
$$\begin{cases}
(x_1-x_0)^2+(y_1-y_0)^2+(z_1-z_0)^2=r^2 ~~~~~~~~~(1)\\
(x_2-x_0)^2+(y_2-y_0)^2+(z_2-z_0)^2=r^2 ~~~~~~~~~(2)\\
(x_3-x_0)^2+(y_3-y_0)^2+(z_3-z_0)^2=r^2 ~~~~~~~~~(3)\\
(x_4-x_0)^2+(y_4-y_0)^2+(z_4-z_0)^2=r^2 ~~~~~~~~~(4)
\end{cases}$$
(4) subtract by (1), (3) subtract by (1) and (2) subtract by (1), we get,
$$\begin{cases}
(x_4-x_1)(x_4+x_1-2x_0)+(y_4-y_1)(y_4+y_1-2y_0)+(z_4-z_1)(z_4+z_1-2z_0)=0 ~~~~~~~~~(1)\\
(x_3-x_1)(x_3+x_1-2x_0)+(y_3-y_1)(y_3+y_1-2y_0)+(z_3-z_1)(z_3+z_1-2z_0)=0 ~~~~~~~~~(1)\\
(x_2-x_1)(x_2+x_1-2x_0)+(y_2-y_1)(y_2+y_1-2y_0)+(z_2-z_1)(z_2+z_1-2z_0)=0 ~~~~~~~~~(1)\\
\end{cases}$$
Because the following determinant isn't zeor, there exists an unique solution. The proof is complete.
$$\left|
\begin{array}{ccc}
x_2-x_1 & x_3-x_1 & x_4-x_1 \\
y_2-y_1 & y_3-y_1 & y_4-y_1 \\
z_2-z_1 & z_3-z_1 & z_4-z_1
\end{array}
\right|$$


TITLE: How do I prove that a matrix is equals to 0?
QUESTION [1 upvotes]: So i have an algebra problem that states "Using elementary row operations, show that the matrix is equal to 0".
I'm given this matrix and I don't know what they mean by this? Am I supposed to turn all of the elements into zeros, or only one row?

REPLY [1 votes]: As mentioned in the comments, you are being asked to show that the determinant of this matrix is zero. This can be shown if the rank of the matrix is $<3$.
You can do this by showing the rows are not linearly independent (hence the matrix is not invertible, and thus the determinant is $0$)
HINT: Focus on the first column, and try show that one of the rows equals some combination of the other two. Then check that the same relation holds for the other two columns.


text:
\begin{document}

\maketitle

\begin{abstract}
For positive integers $n$ and $k$ with $n \geq k$, an \emph{$(n,k,1)$-design} is a pair $(V, \B)$ where $V$ is a set of $n$ \emph{points} and $\B$ is a collection of $k$-subsets of $V$ called \emph{blocks} such that each pair of points occur together in exactly one block. If we weaken this condition to demand only that each pair of points occur together in at most one block, then the resulting object is a \emph{partial $(n,k,1)$-design}. A \emph{completion} of a partial $(n,k,1)$-design $(V,\A)$ is a (complete) $(n,k,1)$-design $(V,\B)$ such that $\A \subseteq \B$. Here, for all sufficiently large $n$, we determine exactly the minimum number of blocks in an uncompletable partial $(n,k,1)$-design. This result is reminiscent of Evans' now-proved conjecture on completions of partial latin squares. We also prove some related results concerning edge decompositions of almost complete graphs into copies of $K_k$.
\end{abstract}

{
  \small
\noindent \textbf{\textit{Keywords:}} partial block design, completion, embedding, $K_k$-decomposition, almost complete graph
}

\section{Introduction}

For positive integers $n$, $k$ and $\lambda$ with $n \geq k$, an \emph{$(n,k,\lambda)$-design} is a pair $(V, \B)$ where $V$ is a set of $n$ \emph{points} and $\B$ is a collection of $k$-subsets of $V$ called \emph{blocks} such that each pair of points occur together in exactly $\lambda$ blocks. If we weaken this condition to demand only that each pair of points occur together in at most $\lambda$ blocks, then the resulting object is a \emph{partial $(n,k,\lambda)$-design}. In this paper we are only concerned with $(n,k,1)$-designs and partial $(n,k,1)$-designs. A \emph{completion} of a partial $(n,k,1)$-design $(V,\A)$ is a (complete) $(n,k,1)$-design $(V,\B)$ such that $\A \subseteq \B$. A partial $(n,k,1)$-design is \emph{completable} when it has a completion.  The \textit{leave} of a partial $(n,k,1)$-design $(V,\mathcal{A})$  is the graph $G$ having vertex set $V$ and the edge set $E(G) = \{ xy :  x, y \in V $ such that $ \{x,y\} \nsubseteq A $ for all $ A \in \mathcal{A}  \}$.

Note that an $(n,2,1)$-design exists trivially for each integer $n \geq 2$. It is obvious that if an $(n,k,1)$-design exists then $n(n-1) \equiv 0 \mod{k(k-1)}$ and $n \equiv 1 \mod{(k-1)}$. We call integers $n$ satisfying these restrictions \emph{k-admissible}.  Wilson \cite{Wilson1975} showed that, for each integer $k \geq 3$, there exists an $(n,k,1)$-design for each sufficiently large $k$-admissible value of $n$. Obviously, if a partial $(n,k,1)$-design is completable, then $n$ is $k$-admissible.  Our main result in this paper is to show that, for each sufficiently large $k$-admissible order $n$, all partial $(n,k,1)$-designs with at most $\frac{n-1}{k-1}-k+1$ blocks are completable and that this bound is tight.

\begin{theorem}\label{T:evansBigGenk}
Let $k \geq 3$ be a fixed integer. There is an integer $n_0$ such that for all $k$-admissible integers $n \geq n_0$, any partial $(n,k,1)$-design with at most $\frac{n-1}{k-1}-k+1$ blocks is completable. Furthermore, for all $k$-admissible integers $n \geq (k-1)^2+1$ there is a partial $(n,k,1)$-design with $\frac{n-1}{k-1}-k+2$ blocks that is not completable.
\end{theorem}

The existence of the uncompletable partial designs claimed in Theorem~\ref{T:evansBigGenk} is easily proved (see Lemma~\ref{L:tightnessGenk}(a)). For sufficiently large $n$, Theorem~\ref{T:evansBigGenk} establishes a generalisation of a conjecture of the second author in \cite{Hors2014} that any partial $(n,3,1)$-design having at most $\frac{n-5}{2}$ blocks is completable. Theorem~\ref{T:evansBigGenk} also nicely complements recent results of Nenadov, Sudakov and Wagner \cite{NenadovSudakovWagner2019}. They show that there exist $\epsilon,n_0>0$ such that we can add blocks to any partial $(n,k,1)$-design $(V,\A)$ with $n > n_0$ and $|\A| \leq \epsilon n^2$ to obtain another partial $(n,k,1)$-design whose leave has at most $21k^3\sqrt{|\A|}\,n$ edges. They also show that we can add points and blocks to such a design to obtain a (complete) $(n',k,1)$-design such that $n' \leq n+7k^2\sqrt{|\mathcal{A}|}$.

Theorem~\ref{T:evansBigGenk} is also reminiscent of a well known conjecture of Evans. A partial latin square of order $n$ is an $n \times n$ array in which each cell is either empty or contains an element of $\{1,\ldots,n\}$, and each element of $\{1,\ldots,n\}$ occurs at most once in each row and column. A latin square is a partial latin square with no empty cells. Evans \cite{Evans1960} conjectured that every partial latin square of order $n$ with at most $n-1$ filled cells can be completed to a latin square. This bound is tight because there is a partial latin square of order $n$ with $n$ filled cells that is not completable for each $n \geq 2$. Smetaniuk \cite{Smetaniuk1981} and Anderson and Hilton \cite{AndersonHilton1983} independently proved  Evans' conjecture for all $n$.

There are few completion results available for partial $(n,k,\lambda)$-designs. Colbourn \cite{colbourn paper} has shown that it is $\mathsf{NP}$-complete to decide whether a given partial $(n,3,1)$-design can be completed. In \cite{ColbournCRosa1983} it is observed that partial $(n,3,1)$-designs in which some fixed point is in every block and partial $(n,3,1)$-designs consisting of an odd number of pairwise disjoint blocks are easily seen to be completable. It is then shown that a partial $(n,3,1)$-design is completable if it has two points $x$ and $y$ such that one block contains both $x$ and $y$ and each other block contains either $x$ or $y$.

A \textit{$K_k$-decomposition} of a graph $G$ is a set of copies of $K_k$ in $G$ whose edge sets partition $E(G)$. An $(n,k,1)$-design is equivalent to a $K_k$-decomposition of $K_n$ and a partial $(n,k,1)$-design is equivalent to a $K_k$-decomposition of some subgraph of $K_n$.  Finding a completion of a partial $(n,k,1)$-design is equivalent to finding a $K_k$-decomposition of its leave, and throughout the remainder of the paper we will often view completions in this way. If a graph $G$ has a $K_k$-decomposition, then we must have $|E(G)| \equiv 0 \mod{\binom{k}{2}}$ and $\deg_G(x) \equiv 0 \mod{k-1}$ for each $x \in V(G)$. We call graphs that obey these necessary conditions \emph{$K_k$-divisible}. So Theorem~\ref{T:evansBigGenk} can be rephrased as saying that, for sufficiently large $n$, any graph $G$ on $n$ vertices that is the leave of a partial $(n,k,1)$-design and whose complement has at most $(\frac{n-1}{k-1}-k+1)\binom{k}{2}$ edges, has a $K_k$-decomposition. It is natural to ask whether we can relax the condition that the graph is the leave of a partial design. We prove two subsidiary results which show that this can only be done at the expense of increasing the bound on the number of edges in $G$. Theorem~\ref{T:evansForAdmissibleOrder} considers the case where $G$ need not be a leave but must still have order congruent to $1$ modulo $k-1$, and Theorem~\ref{T:evansForAnyGraph} considers the case where $G$ can be any $K_k$-divisible graph.

\begin{theorem}\label{T:evansForAdmissibleOrder}
Let $k \geq 3$ be a fixed integer. There is an integer $n_0$ such that for all  integers $n \geq n_0$ with $n \equiv 1 \mod{k-1}$, any $K_k$-divisible graph $G$ of order $n$ has a $K_k$-decomposition if

\[|E(G)| > \tbinom{n}{2} - \left(\tfrac{n-1}{k-1}-\ell\right)\tbinom{k}{2} \quad\text{ where }\quad \ell=\tfrac{1}{4}(k^2-k-2).\]
Furthermore, if $k=3$ or $k \equiv 2 \pmod{4}$, then for all $k$-admissible $n \geq \frac{1}{2}k(k-1)^2+1$ there is a $K_k$-divisible graph $G$ of order $n$ such that  $|E(G)| = \tbinom{n}{2} - (\tfrac{n-1}{k-1}-\ell)\tbinom{k}{2}$ and $G$ is not $K_k$-decomposable.
\end{theorem}

\begin{theorem}\label{T:evansForAnyGraph}
Let $k \geq 3$ be a fixed integer. There is an integer $n_0$ such that for all integers $n \geq n_0$, any $K_k$-divisible graph $G$ of order $n$ has a $K_k$-decomposition if
\[|E(G)| >
\begin{cases}
\tbinom{n}{2}-n+\frac{1}{2}(k+1) & \text{if $k \geq 4$}\\
\tbinom{n}{2}-n & \text{if $k=3$.}
\end{cases}
\]
Furthermore, if $k$ divides $s^2-s-1$ for some positive integer $s$, then for $n=s(k-1)+2$ there is a $K_k$-divisible graph $G$ of order $n$ such that  $|E(G)| = \binom{n}{2}-n+\frac{1}{2}(k+1)$ and $G$ is not $K_k$-decomposable. Finally, for each integer $n \geq 12$ with $n \equiv 0 \mod{6}$, there is a $K_3$-divisible graph $G$ of order $n$ such that $|E(G)| = \binom{n}{2}-n$ and $G$ is not $K_3$-decomposable.
\end{theorem}

The case division in Theorem~\ref{T:evansForAnyGraph} is due to the fact that we go to a little extra effort to obtain a tight bound for the special case $k=3$. Note that there are infinitely many values of $k$, all of them odd, such that $k$ divides $s^2-s-1$ for some positive integer $s$. From Theorems~\ref{T:evansForAdmissibleOrder} and~\ref{T:evansForAnyGraph} it is not too difficult to determine the maximum number of edges in a graph of order $n$ that is $K_3$-divisible but not $K_3$-decomposable for all sufficiently large $n$.

\begin{corollary}\label{C:k=3}
There is an integer $n_0$ such that for all integers $n \geq n_0$, any $K_3$-divisible graph $G$ of order $n$ has a $K_3$-decomposition if $|E(G)| > \tbinom{n}{2} - e(n)$, where
\[ e(n)=
\begin{cases}
\frac{1}{2}(3n-9) & \text{if $n \equiv 1, 3 \mod{6}$}\\
\frac{1}{2}(3n-7) & \text{if $n \equiv 5 \mod{6}$}\\
n+2 & \text{if $n \equiv 2,4 \mod{6}$}\\
n & \text{if $n \equiv 0 \mod{6}$.}
\end{cases}\]
Furthermore, for each $n \geq 7$ there is a $K_3$-divisible graph $G$ of order $n$ such that  $|E(G)| = \tbinom{n}{2} - e(n)$ and $G$ is not $K_3$-decomposable.
\end{corollary}

Very recently, Gruslys and Letzter \cite{GruLet} have proved that any graph of order $n \geq 7$ with strictly more than $\binom{n}{2}-(n-3)$ edges has a \emph{fractional} $K_3$-decomposition. This makes an interesting comparison with Theorem~\ref{T:evansForAnyGraph} and Corollary~\ref{C:k=3}. Considering complements, Theorems~\ref{T:evansForAdmissibleOrder} and~\ref{T:evansForAnyGraph} can be thought of as concerning which graphs are or are not the leaves of partial $(n,k,1)$-designs. This question has received some attention: see \cite[Chapter 9]{ColRosBook}, \cite[\S40.4]{StiWeiYin} and the references therein, for example. Perhaps closest to our concerns here, the possible sizes of \emph{triangle-free} graphs whose complements are $K_3$-divisible but not $K_3$-decomposable are considered in \cite{StiWal}. Our results here improve the lower bounds in that paper.

\section{Preliminaries}\label{S:prelim}

For a family $\A$ of subsets of a set $V$ and an element $x \in V$, we let $\A_x=\{A \in \A: x\in A\}$. For a set $A$ of vertices we use $K_A$ to denote the complete graph with vertex set $A$. For a graph $G$ and a subset $S$ of $V(G)$, we denote by $G[S]$ the subgraph of $G$ induced by $S$. We also denote the minimum and maximum degree of $G$ by $\delta(G)$ and $\Delta(G)$ and the complement of $G$ by $\overline{G}$. For graphs $G$ and $H$ we denote by $G \cup H$ the graph with vertex set $V(G) \cup V(H)$ and edge set $E(G) \cup E(H)$ and denote by $G-H$ the graph with vertex set $V(G)$ and edge set $E(G) \setminus E(H)$. For a positive integer $r$, a \emph{$K_r$-factor} of a graph $G$ is a set of copies of $K_r$ in $G$ whose vertex sets partition $V(G)$. For vertices $x$ and $y$ of a graph $G$, we use $N_G(x,y)$ to denote the mutual neighbourhood $N_G(x) \cap N_G(y)$ of $x$ and $y$. In Lemma~\ref{L:tightnessGenk}(a), (b) and (c) below, we  establish the tightness claims in Theorems~\ref{T:evansBigGenk} and \ref{T:evansForAdmissibleOrder} and in the $k\geq4$ case of Theorem~\ref{T:evansForAnyGraph} respectively.

\begin{lemma}\label{L:tightnessGenk} Let $k \geq 3$ be an integer.
\begin{itemize}
    \item[\textup{(a)}]
For all $k$-admissible integers $n \geq (k-1)^2+1$ there is a partial $(n,k,1)$-design with $\frac{n-1}{k-1}-k+2$ blocks that is not completable.
    \item[\textup{(b)}]
If $k=3$ or $k \equiv 2 \pmod{4}$ then, for all $k$-admissible integers $n \geq \frac{1}{2}k(k-1)^2+1$, there is a $K_k$-divisible graph $G$ of order $n$ such that
\[|E(\overline{G})| = \left(\tfrac{n-1}{k-1}-\tfrac{1}{4}(k^2-k-2)\right)\tbinom{k}{2}\]
and $G$ is not $K_k$-decomposable.
    \item[\textup{(c)}]
If $k$ divides $s^2-s-1$ for some positive integer $s$ then, for $n=s(k-1)+2$, there is a $K_k$-divisible graph $G$ of order $n$ with $|E(\overline{G})|=n-\frac{1}{2}(k+1)$ that is not $K_k$-decomposable.
\end{itemize}
\end{lemma}

\begin{proof}
We first prove (a). Let $(V, \A)$ be a partial $(n,k,1)$-design with $|\A|= \frac{n-1}{k-1}-k+2$ such that $\frac{n-1}{k-1}-k+1$ blocks each contain some fixed point $z \in  V$ and the remaining block, say $A_0$, is disjoint from every other block in $\A$. So $|\A_{z}| = \frac{n-1}{k-1}-k+1$. Suppose for a contradiction that $(V,\B)$ is a completion of $(V, \A)$. In $(V,\B)$ each point lies in exactly $\frac{n-1}{k-1}$ blocks. Thus $|\B_z \setminus \A_z|=k-1$. But $|\B_z \setminus \A_z| \geq k$ because each pair in $\{\{x,z\}:x \in A_0\}$ must occur in a different block. This is a contradiction.

We now prove (b). If $k=3$ then the leave of the partial $(n,k,1)$-design defined in (a) has the required properties, so we may assume that $k \equiv 2 \mod{4}$. Let $V$ be a set of $n$ vertices and let $z \in V$. Let $t=\frac{n-1}{k-1}-\frac{k}{2}(k-1)$ and let $A_1,\ldots,A_t$ be $k$-subsets of $V$ such that $A_i \cap A_j=\{z\}$ for all distinct $i,j \in \{1,\ldots,t\}$. Let $A_0$ be a $(\frac{k}{2}(k-1)+1)$-subset of $V$ such that $A_0$ is disjoint from $A_i$ for all $i \in \{1,\ldots,t\}$. Take $G$ to be the graph $K_V-\bigcup_{i=0}^tK_{A_i}$ and note
\[|E(\overline{G})| = t\tbinom{k}{2}+\tbinom{k(k-1)/2+1}{2} = \left(\tfrac{n-1}{k-1}-\tfrac{1}{4}(k^2-k-2)\right)\tbinom{k}{2}.\]
Furthermore, $\deg_{\Gc}(x) \equiv 0 \mod{k-1}$ for each $x \in V$ and hence, using the fact that $K_V$ is $K_k$-divisible since $n$ is $k$-admissible, we have that $G$ is $K_k$-divisible.
Now suppose for a contradiction there is a $K_k$-decomposition $\D$ of $G$. We have $\deg_{G}(z)=n-1-t(k-1)=\frac{k}{2}(k-1)^2$, so $z$ is a vertex of exactly $\frac{k}{2}(k-1)$ copies of $K_k$ in $\D$. But $z$ must be a vertex of at least $|A_0|=\frac{k}{2}(k-1)+1$ copies of $K_k$ in $\D$ because each edge in $\{xz:x \in A_0\}$ must occur in a different copy of $K_k$. This is a contradiction.

Finally, we prove (c). Let $V$ be a set of $n$ vertices, where $n=s(k-1)+2$ for some positive integer $s$ with $s^2 -s-1 \equiv 0 \mod{k}$, and let $z \in V$. Observe that $k$ is odd since $s^2 -s-1$ is odd. Let $G$ be a graph on vertex set $V$ such that $\Gc$ is the vertex-disjoint union of a star with $n-k$ edges centred at $z$ and a perfect matching on the remaining $k-1$ vertices. Note that $|E(G)| = \binom{n}{2}-n+\frac{1}{2}(k+1)$ and hence that $|E(G)| \equiv 0 \mod{\binom{k}{2}}$ because $n = s(k-1)+2$ and $s^2(k-1)^2 +s(k-1)+(k-1) \equiv 0 \mod{k(k-1)}$. Furthermore, $\deg_G(z)=k-1$ and $\deg_G(x)=n-2=s(k-1)$ for all $x \in V \setminus \{z\}$ and hence $G$ is $K_k$-divisible.  Let $U = N_G(z)$ and note that any $K_k$-decomposition of $G$ must include a copy of $K_k$ with vertex set $\{z\} \cup U$. But this is impossible because $\overline{G}[U]$ is a perfect matching on $k-1$ vertices.
\end{proof}

Note that the construction from the proof of Lemma~\ref{L:tightnessGenk}(b) cannot be converted into a counterexample to Theorem~\ref{T:evansBigGenk} because, by Fisher's inequality \cite{Fis}, $K_{k(k-1)/2+1}$ is not $K_k$-decomposable. Also observe that Theorem~\ref{T:evansBigGenk} is tight for almost all feasible values of $k$ and $n$, while Theorems~\ref{T:evansForAdmissibleOrder} and \ref{T:evansForAnyGraph} are tight only for some values of $k$. So there remains the possibility that the bounds in Theorems~\ref{T:evansForAdmissibleOrder} and \ref{T:evansForAnyGraph} can be improved for particular values of $k$.

We also require some examples of graphs that are not $K_3$-divisible to establish the tightness claims in the $k=3$ case of Theorem~\ref{T:evansForAnyGraph} and in Corollary~\ref{C:k=3}. Note that we have already shown that Corollary~\ref{C:k=3} is tight for $n \equiv 1,3 \mod{6}$ in Lemma~\ref{L:tightnessGenk}(b).

\begin{lemma}\label{L:k=3tightness}\phantom{a}\vspace*{-1.5mm}
\begin{itemize}
    \item[\textup{(a)}]
For each integer $n \geq 12$ with $n \equiv 0 \mod{6}$, there is a $K_3$-divisible graph $G$ of order $n$ with $|E(\overline{G})|=n$ that is not $K_3$-decomposable.
    \item[\textup{(b)}]
For each integer $n \geq 11$ such that $n \equiv 5 \mod{6}$ there is a $K_3$-divisible graph $G$ of order $n$ with $|E(\overline{G})|=\frac{1}{2}(3n-7)$  that is not $K_3$-decomposable.
    \item[\textup{(c)}]
For each integer $n \geq 8$ such that $n \equiv 2,4 \mod{6}$ there is a $K_3$-divisible graph $G$ of order $n$ with $|E(\overline{G})|=n+2$ that is not $K_3$-decomposable.
\end{itemize}
\end{lemma}

\begin{proof}
We first prove (a). Let $V$ be a set of $n$ vertices, where $n \geq 12$ and $n \equiv 0 \mod{6}$, and let $z \in V$. Let $G$ be a graph on vertex set $V$ such that $\Gc$ is the vertex-disjoint union of a star with $n-7$ edges centred at $z$, a copy of $K_4$ with some vertex set $A$, and a copy of $K_2$. Clearly $|E(\Gc)|=n$ and $G$ is $K_3$-divisible.
A $K_3$-decomposition of $G$ must contain exactly three copies of $K_3$ that have $z$ as one of their vertices, but each of the four edges between $z$ and a vertex in $A$ must occur in a different copy of $K_3$. So $G$ has no $K_3$-decomposition.

We now prove (b). Let $V$ be a set of $n$ vertices, where $n \geq 11$ and $n \equiv 5 \mod{6}$, and let $z \in V$. Let $G$ be a graph on vertex set $V$ such that $\Gc$ is the union of $\frac{1}{2}(n-9)$ edge-disjoint copies of $K_3$ whose vertex sets pairwise have intersection $\{z\}$, a copy of $K_5$ with some vertex set $A$ that is disjoint from the vertex set of each copy of $K_3$, and three isolated vertices. It is easy to check that $|E(\overline{G})|=\frac{1}{2}(3n-7)$ and $G$ is $K_3$-divisible. A $K_3$-decomposition of $G$ must contain exactly four copies of $K_3$ that have $z$ as one of their vertices, but each of the five edges between $z$ and a vertex in $A$ must occur in a different copy of $K_3$. So $G$ has no $K_3$-decomposition.

Finally we prove (c). Let $V$ be a set of $n$ vertices, where $n \geq 8$ and $n \equiv 2,4 \mod{6}$. Let $G$ be a graph on vertex set $V$ such that $\Gc$ is the union of a star with $n-3$ edges centred at $z$ and the graph with edge set $\{ux,uy,vx,vy,xy\}$, where $u$ and $v$ are distinct leaf vertices of the star and $x$ and $y$ are the two vertices of $V$ not in the star. It is easy to check that $|E(\overline{G})|=n+2$ and $G$ is $K_3$-divisible. A $K_3$-decomposition of $G$ must contain a copy of $K_3$ with vertex set $\{x,y,z\}$ but this is impossible since $xy \in E(\Gc)$.
\end{proof}

The rest of the paper is devoted to proving the first parts of the theorems and Corollary~\ref{C:k=3}. Our approach is based on the fact that $K_k$-divisible graphs with large order and high minimum degree are known to be $K_k$-decomposable. For each integer $k \geq 3$, $\delta_{K_k}$ is defined to be the infimum of all positive real numbers $\delta$ that satisfy the following: there is a positive integer $n_0$ such that every $K_k$-divisible graph of order $n>n_0$ and minimum degree at least $\delta n$ has a $K_k$-decomposition. Delcourt and Postle \cite{DelPos} have shown that $\delta_{K_3} \leq 0.82733$ and Montgomery \cite{Mon} has shown that $\delta_{K_k} \leq 1-\frac{1}{100k}$ for each $k \geq 4$. Both of these results rely on the work of Glock, K\"{u}hn, Lo, Montgomery and Osthus in \cite{GlockKuhnLoMontgomeryOsthus2019}. For our purposes here, it is enough to know that  $\delta_{K_k} < 1$ for each $k \geq 3$. Often, simply applying this fact to an almost complete graph will show it to be $K_k$-decomposable. However, this approach will not work if the graph contains vertices of low degree. In these situations we follow \cite{NenadovSudakovWagner2019} in deleting copies of $K_k$ from the graph until the vertices that began with low degree become isolated. We can then remove the isolated vertices and apply the fact that $\delta_{K_k}<1$ to the resulting graph to show that the original graph is $K_k$-decomposable. We will make use of the following well known theorems of Tur\'an and of Hajnal and Szemer\'{e}di.

\begin{theorem}[\cite{Turan1941}]\label{T:Turan}
Let $r \geq 2$ be an integer. If a graph $H$ has more than $\frac{r-2}{2r-2}|V(H)|^2$ edges, then it contains a copy of $K_{r}$.
\end{theorem}

\begin{theorem}[\cite{HajnalSzemeredi1970}]\label{T:HS}
Let $r$ be a positive integer. If a graph $H$ has $|V(H)| \equiv 0 \mod{r}$ and $\delta(H) \geq \frac{r - 1}{r}|V(H)|$, then it contains a $K_{r}$-factor.
\end{theorem}

The following simple inductive argument encapsulates the basics of our approach. Given a graph $G$ on an indexed vertex set $\{z_1,\ldots,z_s\}$ and two edges $z_iz_j$ and $z_{i'}z_{j'}$ of $G$ where $i<j$ and $i'<j'$, we say that $z_iz_j$ \emph{lexicographically precedes} $z_{i'}z_{j'}$ if either $i < i'$ or $i=i'$ and $j<j'$. Recall that $N_G(x,y)$ is the mutual neighbourhood $N_G(x) \cap N_G(y)$ of $x$ and $y$.

\begin{lemma} \label{L:K_k decomposition1}
Let $k \geq 3$ be a fixed integer and let $\gamma <1-\delta_{K_k}$ be a positive constant. For all sufficiently large integers $n$ the following holds.
Let $G$ be a $K_k$-divisible graph of order $n$, let $S=\{z_1,\ldots,z_s\}$ be an indexed subset of $V(G)$, and suppose that
\begin{itemize}
    \item[\textup{(i)}]
$|N_G(x) \setminus S| \geq (1-\gamma)n+(k-2)|N_G(x) \cap S|$ for each $x \in V(G) \setminus S$;
    \item[\textup{(ii)}]
either $N_G(z)=\emptyset$ or $|N_G(z) \setminus S| > (k-1)\gamma n +(k-2)|N_G(z) \cap S|$ for each $z \in S$;
    \item[\textup{(iii)}]
for any $i,j \in \{1,\ldots,s\}$ such that $i<j$ and $z_iz_j \in E(G)$ we have
\[|N_G(z_i,z_j) \setminus S| > (k-3)\gamma n+(k-2)\ell_G(z_{i}z_{j})\]
where $\ell_G(z_{i}z_{j})=|N_G(z_i) \cap \{z_1,\ldots,z_{j-1}\}|+|N_G(z_j) \cap \{z_1,\ldots,z_{i-1}\}|$ is the number of edges of $G[S]$ that are adjacent to $z_iz_j$ and lexicographically precede it.
\end{itemize}
Then $G$ has a $K_k$-decomposition.
\end{lemma}

\begin{proof}
We prove the result by induction on the quantity $\sigma(G)=\sum_{z \in S}\deg_G(z)$. Let $s=|S|$. If $\sigma(G)=0$, then the vertices in $S$ are isolated and $\deg_G(x) \geq (1-\gamma)n \geq (1-\gamma)(n-s)$ for each $x \in V(G) \setminus S$ by (i). So the graph obtained from $G$ by deleting the vertices in $S$ is $K_k$-decomposable by the definition of $\delta_{K_k}$ since $\gamma <1-\delta_{K_k}$, and thus the result follows. So we may assume that $\sigma(G) > 0$.

We consider two cases according to whether $G[S]$ is empty. In each case we form a new graph $G'$ from $G$ by removing the edges of some number of copies of $K_k$ in $G$ and then complete the proof by showing that $G'$ satisfies the inductive hypotheses. Note that $G'$ will be $K_k$-divisible because $G$ is $K_k$-divisible. In what follows it will be useful to observe that (i) implies that the vertex $x$ is nonadjacent to at most $\gamma n$ vertices in $G$ (including itself) for each $x \in V(G) \setminus S$. \smallskip

\textbf{Case 1:} Suppose that $G[S]$ is not empty. Let $z_iz_j$, where $i <j$, be the lexicographically first edge in $G[S]$. Let $H$ be the subgraph of $G$ induced by $N_G(z_i,z_j) \setminus S$. Then $|V(H)| > (k-3)\gamma n$ by (iii). We claim that there is a subset $X$ of $V(H)$ such that $H[X]$ is a copy of $K_{k-2}$. If $k=3$, this is immediate because $|V(H)| > 0$. If $k \geq 4$, then $\deg_{H}(x) \geq |V(H)|-\gamma n > \frac{k-4}{k-3}|V(H)|$ for each $x \in V(H)$ where the first inequality follows by (i) and the second from $|V(H)| > (k-3)\gamma n$. So it follows from Theorem~\ref{T:Turan} that such an $X$ exists. Let $G'=G-K_B$ where $B=X\cup \{z_i,z_j\}$. Note that $\sigma(G') < \sigma(G)$, so it suffices to show that $G'$ satisfies (i), (ii) and (iii).

Observe that $|N_{G'}(x) \setminus S|=|N_{G}(x) \setminus S|-(k-3)$ and $|N_{G'}(x) \cap S|=|N_G(x) \cap S|-2$ for each $x \in X$, and $N_{G'}(x) =N_G(x)$ for each $x \in V \setminus (S \cup X)$. Thus $G'$ satisfies (i) because $G$ satisfies (i). Also, $|N_{G'}(z) \setminus S|=|N_{G}(z) \setminus S|-(k-2)$ and $|N_{G'}(z) \cap S|=|N_G(z) \cap S|-1$ for each $z \in\{z_i,z_j\}$, and $N_{G'}(z) =N_{G}(z)$ for each $z \in S \setminus \{z_i,z_j\}$. Thus $G'$ satisfies (ii) because $G$ satisfies (ii). If $G'[S]$ is empty, then $G'$ satisfies (iii) trivially. Otherwise, let $z_{i'}z_{j'}$ be an arbitrary edge in $G'[S]$ where $i'<j'$. If $\{i',j'\} \cap \{i,j\}=\emptyset$, then $N_{G'}(z_{i'},z_{j'})  \setminus S = N_{G}(z_{i'},z_{j'}) \setminus S$ and $\ell_{G'}(z_{i'}z_{j'})=\ell_{G}(z_{i'}z_{j'})$. Otherwise either $i'=i$ and $j'>j$ or $i'=j$ by our definition of $z_iz_j$. Then $|N_{G'}(z_{i'},z_{j'}) \setminus S| \geq |N_{G}(z_{i'},z_{j'}) \setminus S| - (k-2)$ and $\ell_{G'}(z_{i'}z_{j'})=\ell_{G}(z_{i'}z_{j'})-1$. Thus $G'$ satisfies (iii) because $G$ satisfies (iii).

\textbf{Case 2:} Suppose that $G[S]$ is empty. Because $\sigma(G)>0$, there is an $i \in \{1,\ldots,s\}$ such that $N_G(z_i) \neq \emptyset$. Let $H$ be the subgraph of $G$ induced by $N_G(z_i)$. By (ii), $|V(H)| > (k-1)\gamma n$ and, because $G$ is $K_k$-divisible, $|V(H)| = t(k-1)$ for some integer $t$. By (i), for each $x \in V(H)$, we have $\deg_{H}(x) \geq |V(H)|-\gamma n > \frac{k-2}{k-1}|V(H)|$. So Theorem~\ref{T:HS} implies that there is a partition $\{X_1,\ldots,X_t\}$ of $V(H)$ such that $H[X_j]$ is a copy of $K_{k-1}$ for each $j \in \{1,\ldots,t\}$. Let $G'=G-\bigcup_{j=1}^tK_{B_j}$ where $B_j=X_j \cup \{z_i\}$ for each $j \in \{1,\ldots,t\}$.

Observe that $|N_{G'}(x) \setminus S|=|N_{G}(x) \setminus S|-(k-2)$ and $|N_{G'}(x) \cap S|=|N_G(x) \cap S|-1$ for each $x \in V(H)$, and $N_{G'}(x)=N_G(x)$ for each $x \in V \setminus (S \cup V(H))$. Thus $G'$ satisfies (i) because $G$ satisfies (i). Also, $N_{G'}(z_i) = \emptyset$ and $N_{G'}(z) = N_{G}(z)$ for each $z \in S \setminus \{z_i\}$. Thus $G'$ satisfies (ii) because $G$ satisfies (ii). Furthermore,  $G'[S]$ is empty and so $G'$ satisfies (iii) trivially.
\end{proof}

Note that $|N_G(x) \cap S|$ in conditions (i) and (ii) of Lemma \ref{L:K_k decomposition1} is at most $s$, and $\ell_G(z_{i}z_{j})$ in condition (iii) is less than $2s$. This will be useful to remember when we apply Lemma~\ref{L:K_k decomposition1} below. We only require Lemma \ref{L:K_k decomposition1} in order to prove our next result,  Lemma~\ref{L:mutualNeighbourhoodDecomp}, which may be of some independent interest. It shows that we can guarantee a $K_k$-divisible graph with a positive proportion of non-edges has a $K_k$-decomposition if we further require that each edge is in sufficiently many triangles.

\begin{lemma}\label{L:mutualNeighbourhoodDecomp}
Let $k \geq 3$ be a fixed integer, and let $\gamma < 1-\delta_{K_k}$ be a positive constant. For any sufficiently large integer $n$, a $K_k$-divisible graph $G$ of order $n$ is $K_k$-decomposable if $|E(G)| \geq (1-\frac{1}{4k}\gamma^2)\binom{n}{2}$ and $|N_G(x,y)|>k \gamma n$ for each $xy \in E(G)$.
\end{lemma}

\begin{proof}
Let $G$ be a $K_k$-divisible graph of order $n$ with $|E(G)| \geq (1-\frac{1}{4k}\gamma^2)\binom{n}{2}$ and $|N_G(x,y)|>k \gamma n$ for each $xy \in E(G)$. Note that $|E(\overline{G})| \leq \frac{1}{4k}\gamma^2\binom{n}{2}$. Let $S=\{x \in V(G): \deg_{\overline{G}} (x) \geq \frac{1}{2}\gamma n\}$ and $|S| = s$. So we have $\frac{1}{2}\gamma n s \leq 2|E(\overline{G})| \leq \frac{1}{2k}\gamma^2\binom{n}{2}$, and hence $s < \frac{1}{2k} \gamma n$. It suffices to show that $G$ and $S$ satisfy conditions (i), (ii) and (iii) of Lemma~\ref{L:K_k decomposition1}.

\textbf{(i)} Consider any vertex $x \in V(G) \setminus S$. We have $\deg_{G}(x) > (1-\frac{1}{2}\gamma)n - 1$ by the definition of $S$. Therefore, $|N_{G}(x) \setminus S| > (1-\frac{1}{2}\gamma)n - 1 -s > (1-\frac{k+1}{2k}\gamma)n - 1$. Thus, condition (i) of Lemma~\ref{L:K_k decomposition1} holds, noting that $(k-2)|N_{G}(x) \cap S| \leq (k-2)s < \frac{k-2}{2k}\gamma n$ in that condition.

\textbf{(ii)} Consider any vertex $x \in S$. If $N_G(x)=\emptyset$, then (ii) is satisfied for $x$. Otherwise, for any vertex $y \in V(G)$  such that $xy \in E(G)$, we have $|N_G(x,y)|> k\gamma n$ by our hypotheses,
and hence
\begin{equation}\label{E:mutualNeighbourhoodDecomp1}
|N_{G}(x) \setminus S| \geq |N_G(x,y) \setminus S|> k\gamma n-s>(k-\tfrac{1}{2k})\gamma n.
\end{equation}
Thus condition (ii) of Lemma~\ref{L:K_k decomposition1} holds, noting that $(k-2)|N_{G}(x) \cap S| \leq (k-2)s < \frac{k-2}{2k}\gamma n$ in that condition.

\textbf{(iii)} Consider any edge $xy \in E(G[S])$. By \eqref{E:mutualNeighbourhoodDecomp1}, we have $|N_G(x,y) \setminus S|>(k-\frac{1}{2k})\gamma n$. Thus, condition (iii) of Lemma~\ref{L:K_k decomposition1} holds, noting that $(k-2)\ell_{G}(xy) < 2(k-2)s < \frac{k-2}{k} \gamma n$ in that condition.
\end{proof}

\section{Proof of Theorem~\ref{T:evansBigGenk}}

Suppose that $(V,\A)$ is a partial $(n,k,1)$-design with $|\A|=\frac{n-1}{k-1}-k+1$ and that $G$ is its leave. One important situation in which we cannot complete $(V,\A)$ by applying Lemma~\ref{L:mutualNeighbourhoodDecomp} to $G$ is when there is a point $z \in V$ which is in nearly every block in $\A$ (since then edges of $G$ incident with $z$ will not be in enough triangles). In this case, completing $(V,\A)$ will necessarily involve finding a $K_{k-1}$-factor in $G[N_G(z)]$. Lemma~\ref{L:colouring} below allows us to accomplish this task. It is simpler and more natural to consider the complement and state the result in terms of a colouring of a union of cliques. A \emph{proper colouring of a graph $H$ with colour set $C$} is an assignment $\varphi:V(H) \rightarrow C$ of colours from $C$ to the vertices of $H$ such that adjacent vertices receive different colours. The \emph{colour class} of a colour $c \in C$ under $\varphi$ is the set $\varphi^{-1}(c)$ of all vertices to which $\varphi$ assigns colour $c$.

The basic strategy in the proof of Lemma~\ref{L:colouring} is the commonly-used one of colouring vertices greedily according to a degeneracy ordering. A \emph{degeneracy ordering} $v_1,\ldots,v_n$ of the vertices of a graph $H$ is one for which $v_i$ is a vertex of minimum degree in $H[\{v_1,\ldots,v_i\}]$ for each $i \in \{1,\ldots,n\}$. Such an ordering is easily obtained by choosing a vertex of minimum degree in a graph, deleting it and placing it last in the ordering, and repeating this procedure recursively. Sometimes our greedy strategy will get stuck, however, and in these cases we will be forced to recolour an already-coloured vertex.

\begin{lemma}\label{L:colouring}
Let $k$ and $a$ be  integers with $k \geq 3$ and $a \geq k-1$, let $V$ be a set of $a(k-1)$ vertices, and let $\A$ be a set of subsets of $V$ such that $|\A| \leq a-k+1$, $|A| \leq k$ for all $A \in \A$ and $|A \cap A'| \leq 1$ for all distinct $A,A' \in \A$. The graph $H$ with vertex set $V$ and edge set $\bigcup_{A \in \A}E(K_{A})$ has a proper colouring with $a$ colours such that each colour class has order $k-1$.
\end{lemma}

\begin{proof}
Let $C$ be a set of $a$ colours. For the duration of this proof we call a proper colouring \emph{legal} if its colour set is (a subset of) $C$ and each of its colour classes has order at most $k-1$. Let $v_1,\ldots,v_{a(k-1)}$ be a degeneracy ordering of the vertices in $V$. Let $V_i=\{v_1,\ldots,v_i\}$ and $H_i=H[V_i]$ for each $i \in \{1,\ldots,a(k-1)\}$. Clearly $H_{a}$ has a legal colouring as we may colour each vertex with a different colour. We assume that there is a legal colouring $\varphi_{j-1}$ of $H_{j-1}$ for some $j \in \{a+1,\ldots,a(k-1)\}$ and proceed to show that we can find a legal colouring of $\varphi_j$ of $H_{j}$. Extending $\varphi_{j-1}$ by assigning $v_j$ a new colour $c$ might fail to result in a legal colouring for two reasons: either $c$ may already be assigned by $\varphi_{j-1}$ to $k-1$ vertices or $c$ may be assigned by $\varphi_{j-1}$ to a vertex adjacent in $H_j$ to $v_j$.  Accordingly, let $\Cf=\{c \in C: |\varphi_{j-1}^{-1}(c)|=k-1\}$, let $\Cn$ be the set of colours in $C$ that are assigned by $\varphi_{j-1}$ to vertices adjacent in $H_j$ to $v_j$, and let $\an=|\Cn|$. We think of colours in $\Cf$ as ``full'' and those in $\Cn$ as ``neighbouring''.

If $C \setminus (\Cf \cup \Cn)$ is nonempty, then we can extend $\varphi_{j-1}$ to a legal colouring $\varphi_j$ of $H_j$ by assigning any colour in $C \setminus (\Cf \cup \Cn)$ to $v_j$. So we may assume that $\Cf \cup \Cn=C$. Since $j-1$, the number of vertices already coloured, is less than $a(k-1)$, it follows from the definition of $\Cf$ that $|\Cf| < a$ and hence that $\Cn \setminus \Cf \neq \emptyset$ and $\an \geq 1$. Let $c'$ be a colour in $\Cn \setminus \Cf$ and let $V'=\varphi^{-1}_{j-1}(c')$. Let $\Vf=\bigcup_{c \in \Cf \setminus \Cn}\varphi^{-1}_{j-1}(c)$ be the set of vertices already assigned a colour in $\Cf \setminus \Cn$. We aim to proceed by colouring $v_j$ with a colour in $\Cf \setminus \Cn$ but also recolouring a vertex of that colour with $c'$. We will be able to do this if the following claim holds.
\begin{claim}
There is a vertex in $\Vf$ that is not adjacent in $H_j$ to any vertex in $V'$.
\end{claim}
\noindent If this claim is true, we can let $u$ be such a vertex in $\Vf$ and let $\varphi_j$ be the colouring of $H_j$ such that $\varphi_j(v_j)=\varphi_{j-1}(u)$, $\varphi_j(u)=c'$, and $\varphi_j(x)=\varphi_{j-1}(x)$ for each $x \in V_{j-1} \setminus \{u\}$. Since $\varphi_{j-1}(u) \notin \Cn$ and $u$ is not adjacent in $H_j$ to any vertex in $V'$, it can be seen that $\varphi_j$ is a proper colouring and since $c' \notin \Cf$ it can be seen that $\varphi_j$ is a legal colouring. So it suffices to prove our claim.

\noindent \textbf{Proof of claim.} Suppose for a contradiction that each vertex in $\Vf$ is adjacent in $H_j$ to some vertex in $V'$. Observe that $V'$ and $\Vf$ are disjoint and that
\begin{equation}\label{E:verticesLowerBounds}
|V'| \geq 1, \qquad |\Vf|=(k-1)(a-\an) \qquad \text{and} \qquad |V_j \setminus (V' \cup \Vf)| \geq \an
\end{equation}
where the second of these follows because each of the $a-\an$ colours in $\Cf \setminus \Cn$ is assigned by $\varphi_{j-1}$ to exactly $k-1$ vertices in $V_{j-1} \setminus V'$ and the third follows because $v_j \in V_{j} \setminus (V' \cup \Vf)$ and each of the $\an-1$ colours in $\Cn \setminus \{c'\}$ is assigned by $\varphi_{j-1}$ to at least one vertex in $V_{j-1} \setminus (V' \cup \Vf)$.

Let $\Phi = \sum_{x \in V_j}|\A_x| -k(a+k-1)$. We will show that $\Phi>0$ and hence obtain a contradiction to the hypothesis of the lemma that $\A$ contains at most $a-k+1$ sets each of size at most $k$. We do this in two cases according to the value of $\an$.

\textbf{Case 1:} Suppose that $\an \leq k-1$. Observe that, for each $x \in V_j$, we have $|\A_x| \geq 1$  because $v_j$ is adjacent in $H_j$ to a vertex of colour $c'$ and thus $\deg_{H_j}(x) \geq \deg_{H_j}(v_j) \geq 1$ by the properties of the degeneracy ordering. So we have $\sum_{x \in V_j \setminus V'}|\A_x| \geq |V_j \setminus V'| \geq (k-1)(a-\an)+\an$ by \eqref{E:verticesLowerBounds}. Furthermore, each of the $|\Vf| +1$ vertices in $\Vf \cup \{v_j\}$ is in a set in $\A$ that also contains a vertex in $V'$ using our assumption that the claim fails and the fact that $c' \in \Cn$. Thus, because $|A|\leq k$ for each $A \in \A$, we have $\sum_{x \in V'}|\A_x| \geq \lceil \frac{1}{k-1}(|\Vf| +1) \rceil = a-\an+1$ where the equality follows by \eqref{E:verticesLowerBounds}. Using these lower bounds on $\sum_{x \in V_j \setminus V'}|\A_x|$ and $\sum_{x \in V'}|\A_x|$,
\[\Phi \geq (k-1)(a-\an)+a+1-k(a-k+1)=(k-1)(k-\an)+1.\]
Thus, since $\an \leq k-1$ by the conditions of this case,  $\Phi > 0$ and we have the required contradiction.

\textbf{Case 2:} Suppose that $\an \geq k$. We show this case cannot arise by obtaining a contradiction without the need for our assumption that the claim is false. Observe that $\deg_{H_j}(v_j) \geq \an$ by the definition of $\Cn$ and hence $\deg_{H_j}(x) \geq \an$ for each $x \in V_j$ by the properties of the degeneracy ordering. Thus we have $\deg_{H_j}(x) \leq |\A_{x}|(k-1)$ for each $x \in V_j$ and hence
\begin{equation}\label{E:hitsLowerBound}
|\A_x| \geq \tfrac{1}{k-1}\deg_{H_j}(x) \geq \tfrac{1}{k-1}\an \quad \text{for each $x \in V_j$.}
\end{equation}
So we have $\sum_{x \in V_j}|\A_x| \geq \frac{1}{k-1}\an|V_j| \geq \frac{1}{k-1}\an((k-1)(a-\an)+\an+1)$ by \eqref{E:verticesLowerBounds} and \eqref{E:hitsLowerBound}. Thus,
\begin{equation}\label{E:PhiLowerBound}
\Phi \geq \mfrac{\an((k-1)(a-\an)+\an+1)}{k-1} - k(a-k+1)=a(\an-k)+k(k-1)-\mfrac{(k-2)\an^2-\an}{k-1}.
\end{equation}
In order to show that $\Phi>0$ using \eqref{E:PhiLowerBound} we require a lower bound on $a$.

We first show that $\Cf \setminus \Cn$ is nonempty and then use this fact to obtain the required lower bound on $a$. Let $m=\max\{|A \cap V_j|:A \in \A\}$ and $A_1$ be a set in $\A$ such that $|A_1 \cap V_j|=m$. Using the definition of $m$ and a similar argument to the one used to establish \eqref{E:hitsLowerBound}, we see that $|\A_x| \geq \frac{1}{m-1}\deg_{H_j}(x) \geq \frac{1}{m-1}\an$ for each $x \in V_j$. So each vertex in $A_1 \cap V_j$ is in at least $\frac{1}{m-1}\an-1$ sets in $\A \setminus \{A_1\}$. Further, no set in $\A \setminus \{A_1\}$ can contain more than one vertex in $A_1 \cap V_j$. Thus $|\A|-1 \geq m(\frac{1}{m-1}\an-1)$ and hence, using $|\A| \leq a-k+1$, we have $a \geq \frac{m}{m-1}\an-m+k$. So we have that $a > \an$ since $m \leq k$ and hence that $\Cf \setminus \Cn$ is indeed nonempty.

Let $c''$ be a colour in $\Cf \setminus \Cn$, let $V''=\varphi^{-1}_{j-1}(c'')$, and note that $|V''|=k-1$ because $c'' \in \Cf$. No set in $\A$ can contain more than one vertex in $V''$ because $\varphi_{j-1}$ is a proper colouring, and each vertex in $V''$ is in at least $\frac{1}{k-1}\an$ sets in $\A$ by \eqref{E:hitsLowerBound}. Thus $a-k+1 \geq |\A| \geq \frac{1}{k-1}\an|V''|=\an$ and hence $a \geq \an+k-1$. Substituting this into \eqref{E:PhiLowerBound} and simplifying, remembering that $\an \geq k$ by the conditions of this case, we obtain
\[\Phi \geq \mfrac{\an(\an-k+2)}{k-1}>0\]
and we have the required contradiction.
\end{proof}

We observed in Lemma~\ref{L:tightnessGenk}(b) that, for each $k \geq 6$ with $k \equiv 2 \mod{4}$, to guarantee a $K_k$-decomposition of a graph $G$ of $k$-admissible order whose complement has at most $(\frac{n-1}{k-1}-k+1)\binom{k}{2}$ edges, we require more than  simply $G$ being $K_k$-divisible (note that $\frac{1}{4}(k^2-k-2) > k-1$ for each $k \geq 6$). It is through Lemma~\ref{L:colouring} that our proof uses the stronger assumption that $G$ is the leave of a partial $(n,k,1)$-design.  The conclusion of Lemma~\ref{L:colouring} does not hold if we merely require that $G$ be a graph of order $a(k-1)$ with at most $(a-k+1)\binom{k}{2}$ edges, even if we further demand that $G$ be $K_k$-divisible. For example, for any integer $k \geq 6$ such that $k \equiv 2 \mod{4}$, if we take $a=\frac{1}{4}(k^2+3k-2)$, then the graph of order $a(k-1)$ consisting of a copy of $K_{k(k-1)/2+1}$ and  isolated vertices has exactly $(a-k+1)\binom{k}{2}$ edges and is $K_k$-divisible, but clearly does not have a proper colouring with $a$ colours.

With Lemma~\ref{L:colouring} in hand we are now in a position to prove Theorem~\ref{T:evansBigGenk}. We find the required $K_k$-decomposition of the leave $G$ of the partial design by first applying Lemma~\ref{L:colouring} to obtain the copies of $K_k$ containing a particular vertex of minimum degree in $G$, and then using Lemma~\ref{L:mutualNeighbourhoodDecomp} to obtain the rest of the decomposition.

\begin{proof}[\textup{\textbf{Proof of Theorem~\ref{T:evansBigGenk}}}]
The second part of the theorem was proved as Lemma~\ref{L:tightnessGenk}(a), so it remains to prove the first part. Let $(V, \A)$ be a partial $(n,k,1)$-design such that $n$ is $k$-admissible and $|\A| \leq \frac{n-1}{k-1}-k+1$. Throughout the proof we assume that $n$ is large relative to $k$ and employ asymptotic notation with respect to this regime. Let $G$ be the leave of $(V, \A)$ and note that $G$ is $K_k$-divisible because $n$ is $k$-admissible. Let $z$ be a point such that $|\A_z| \geq |\A_x|$ for each $x \in V$ and let $\A'=\A \setminus \A_z$. Let $a$ be the  integer such that $|\A_z|=\frac{n-1}{k-1}-a$, and note that $a \geq k-1$ and $|\A'| \leq a-k+1$.

Let $U=N_G(z)$ and observe that $|A| = k$ for each $A \in \A'$, $|A \cap A'| \leq 1$ for all distinct $A,A' \in \A'$ and $\Gc[U] = \bigcup_{A \in \A'}K_{A \cap U}$. Thus, since $|U| = \deg_G(z) = a(k-1)$, we can apply Lemma~\ref{L:colouring} to show there is a proper colouring of $\Gc[U]$ with $a$ colours in which each colour class has order $k-1$. Thus, there is a partition $\mathcal{U}$ of $U$ such that $|\mathcal{U}|=a$ and $G[X]$ is a copy of $K_{k-1}$ for each $X \in \mathcal{U}$. Let $\B=\{X \cup \{z\}:X \in \mathcal{U}\}$.

Let $G'$ be the graph obtained from $G$ by deleting the edges in $\bigcup_{B \in \B}E(K_B)$ and the vertex $z$. It suffices to show that we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp} to find a $K_k$-decomposition $\D'$ of $G'$, because then to complete $(V,\A)$ we can add the blocks in $\B$ along with blocks corresponding to the copies of $K_k$ in $\D'$. So it remains to show that $G'$ satisfies the hypotheses of Lemma \ref{L:mutualNeighbourhoodDecomp}. Since $G$ is $K_k$-divisible, so is $G'$. Observe that
\[G'= K_{V \setminus \{z\}}-\medop\bigcup_{A \in \A_z \cup \B} K_{A \setminus \{z\}} - \medop\bigcup_{A \in \A'} K_A,\]
and that each element of $V \setminus \{z\}$ is in exactly one set in $\{A\setminus\{z\}: A \in \A_z \cup \B\}$. Thus, for each $x \in V \setminus \{z\}$,
\begin{equation}\label{E:degTh1Proof}
\deg_{\overline{G'}}(x) = (k-1)|\A'_x|+k-2.
\end{equation}

Now
\begin{equation}\label{E:edgesTh1Proof}
|E(G')| = \mbinom{n}{2}- (|\A|+|\B|)\mbinom{k}{2} > \mbinom{n}{2}- k(n-1) =\mbinom{n}{2}-O(n)
\end{equation}
where the first inequality follows because $|\A| < \frac{n-1}{k-1}$ by supposition and $|\B| \leq \frac{n-1}{k-1}$ by definition. Now let $uv$ be an arbitrary edge of $G'$ and note that this implies $|\A'_{u} \cap \A'_{v}| =  0$. We have $|\A'_{u}|+|\A'_{v}| \leq \frac{2}{3}|\A|$ because $|\A'_{u}|,|\A'_{v}| \leq |\A_z|$ by the definition of $z$ and $|\A'_{u}|+|\A'_{v}| \leq |\A|-|\A_z|$. Then, using \eqref{E:degTh1Proof},
\begin{equation}\label{E:neighbourhoodTh1Proof}
|N_{G'}(u,v)| \geq n-1-(k-1)(|\A'_{u}|+|\A'_{v}|)-2(k-2) \geq \tfrac{1}{3}n-O(1)
\end{equation}
where the second inequality follows because $|\A'_{u}|+|\A'_{v}| \leq \frac{2}{3}|\A| < \frac{2(n-1)}{3(k-1)}$. In view of \eqref{E:edgesTh1Proof} and \eqref{E:neighbourhoodTh1Proof}, we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp}, choosing $\gamma < \min\{1-\delta_{K_k},\frac{1}{3k}\}$, to find a $K_k$-decomposition $\D'$ of $G'$ and hence complete the proof.
\end{proof}

\section{Proof of Theorems~\ref{T:evansForAdmissibleOrder} and~\ref{T:evansForAnyGraph}}

The proofs of Theorems~\ref{T:evansForAdmissibleOrder} and~\ref{T:evansForAnyGraph} proceed along similar lines to the proof of Theorem~\ref{T:evansBigGenk}, although the details vary significantly. In each case, we first require a lemma analogous to Lemma~\ref{L:colouring}: this is Lemma~\ref{L:colouring2} in the case of Theorem~\ref{T:evansForAdmissibleOrder} and Lemma~\ref{L:colouring3} in the case of Theorem~\ref{T:evansForAnyGraph}. Like Lemma~\ref{L:colouring}, these lemmas are proved by colouring with a greedy algorithm that may recolour already-coloured vertices when required.

\begin{lemma}\label{L:colouring2}
Let $k$ and $a$ be  integers such that $k \geq 3$ and $a > \ell$, where $\ell=\frac{1}{4}(k^2-k-2)$.
Let $H$ be a graph of order $a(k-1)$ such that
$\sum_{x \in V(H)}\lceil\frac{1}{k-1}\deg_H(x)\rceil < k(a-\ell)$. Then $H$ has a proper colouring with $a$ colours such that each colour class contains $k-1$ vertices.
\end{lemma}

\begin{proof}
Note that $\ell$ may not be an integer, but $2\ell=\binom{k}{2}-1$ is an integer. The set-up of the proof proceeds identically to that of the proof of Lemma~\ref{L:colouring} up to and including the paragraph after the claim. So we adopt all the notation defined up to that point and see that it suffices to prove the claim there, which we restate below.
\begin{claim}
There is a vertex in $\Vf$ that is not adjacent in $H_j$ to any vertex in $V'$.
\end{claim}

\noindent \textbf{Proof of claim.} Recall that $v_1,\ldots,v_{a(k-1)}$ is a degeneracy ordering of $V(H)$, $V_i=\{v_1,\ldots,v_i\}$ and $H_i=H[V_i]$ for each $i \in \{1,\ldots a(k-1)\}$ and $\varphi_{j-1}$ is a legal colouring of $H_{j-1}$ with a set $C$ of $a$ colours for some $j \in \{a+1,\ldots,a(k-1)\}$. Further, $V'=\varphi^{-1}_{j-1}(c')$ and $\Vf=\bigcup_{c\in \Cf \setminus \Cn}\varphi^{-1}_{j-1}(c)$ where $c'$ is a colour in $\Cn \setminus \Cf$, $\Cf=\{c \in C: |\varphi_{j-1}^{-1}(c)|=k-1\}$ and $\Cn$ is the set of $\an \geq 1$ colours in $C$ that are assigned by $\varphi_{j-1}$ to vertices adjacent in $H_j$ to $v_j$.

Suppose for a contradiction that each vertex in $\Vf$ is adjacent in $H_j$ to some vertex in $V'$. As in the proof of Lemma~\ref{L:colouring}, observe that $V'$ and $\Vf$ are disjoint and that
\begin{equation}\label{E:verticesLowerBounds2}
|V'| \geq 1, \qquad |\Vf|=(k-1)(a-\an) \qquad \text{and} \qquad |V_j \setminus (V' \cup \Vf)| \geq \an.
\end{equation}

Let $r_x = \lceil\frac{1}{k-1}\deg_{H_j}(x)\rceil$ for each $x \in V$ and let $\Phi=\sum_{x \in V_j}r_x-k(a-\ell)$. We will complete the proof by showing that $\Phi \geq 0$ and hence obtaining a contradiction to the hypothesis of the lemma that $\sum_{x \in V(H)}\lceil\frac{1}{k-1}\deg_H(x)\rceil < k(a-\ell)$. We do this in two cases according to the value of $\an$.

\textbf{Case 1:} Suppose that $\an \leq k-1$. Observe that, for each $x \in V_j$, we have $r_{x} \geq 1$ for all $x \in V_j$  because $v_j$ is adjacent in $H_j$ to a vertex of colour $c'$ and thus $\deg_{H_j}(x) \geq \deg_{H_j}(v_j) \geq 1$ by the properties of the degeneracy ordering. So we have $\sum_{x \in V_j \setminus V'}r_x \geq |V_j \setminus V'| \geq (k-1)(a-\an)+\an$ by \eqref{E:verticesLowerBounds2}. Furthermore, each of the $|\Vf| +1$ vertices in $\Vf \cup \{v_j\}$ is adjacent in $H_j$ to a vertex in $V'$ using our assumption that the claim fails and the fact that $c' \in \Cn$. Thus, $\sum_{x \in V'}\deg_{H_j}(x) \geq |\Vf| +1$ and so $\sum_{x \in V'}r_x \geq \lceil \frac{1}{k-1}(|\Vf| +1) \rceil = a-\an+1$ where the equality follows by \eqref{E:verticesLowerBounds2}. Using these lower bounds on $\sum_{x \in V \setminus V'}r_x$ and $\sum_{x \in V'}r_x$,
\[\Phi \geq (k-1)(a-\an)+a+1-k(a-\ell)=k \ell-\an(k-1)+1 \geq k(\ell-k+2),\]
where the last inequality follows by using the condition of this case that $\an \leq k-1$ and simplifying. Thus $\Phi \geq 0$ and we have the required contradiction because it is easily checked that $\ell \geq k-2$ since $k \geq 3$.

\textbf{Case 2:} Suppose that $\an \geq k$. We show this case cannot arise by obtaining a contradiction without the need for our assumption that the claim is false. Observe that $\deg_{H_j}(v_j) \geq \an$ by the definition of $\Cn$ and hence $\deg_{H_j}(x) \geq \an$ for each $x \in V_j$ by the properties of the degeneracy ordering. Thus,
\begin{equation}\label{E:hitsLowerBound2}
r_x \geq \tfrac{1}{k-1}\an \quad \text{for each $x \in V_j$.}
\end{equation}
So we have $\sum_{x \in V_j}r_x \geq \frac{1}{k-1}\an|V_j| \geq \frac{1}{k-1}\an((k-1)(a-\an)+\an+1)$  by \eqref{E:verticesLowerBounds2} and \eqref{E:hitsLowerBound2}. Thus,
\[\Phi \geq \mfrac{\an((k-1)(a-\an)+\an+1)}{k-1} - k(a-\ell)=a(\an-k)+k\ell-\mfrac{(k-2)\an^2-\an}{k-1} \geq k \ell-\mfrac{\an(k^2-k-1-\an)}{k-1} \]
where for the last inequality we substituted $a \geq \an$ in view of the condition of this case that $\an \geq k$. It is routine to check that $\an(k^2-k-1-\an) \leq k(k-1) \ell$ using the definition of $\ell$ and the fact that either $\an \leq \binom{k}{2}-1$ or $\an \geq \binom{k}{2}$ since $\an$ is an integer. Thus $\Phi \geq 0$ and we have the required contradiction.
\end{proof}

As suggested by the proof of Lemma~\ref{L:tightnessGenk}(b), for any $k \equiv 2 \mod{4}$, the tightness of Lemma~\ref{L:colouring2} can be seen by taking $a=\frac{1}{2}k(k-1)$ and considering the graph of order $a(k-1)$  consisting of a copy of $K_{a+1}$ and isolated vertices.

\begin{proof}[\textbf{\textup{Proof of Theorem~\ref{T:evansForAdmissibleOrder}}}]
The second part of the theorem follows by Lemma~\ref{L:tightnessGenk}(b), so it remains to prove the first part. Let $G$ be a $K_k$-divisible graph of order $n$ such that $n \equiv 1 \mod{(k-1)}$ and $|E(\overline{G})| < (\tfrac{n-1}{k-1}-\ell)\tbinom{k}{2}$. Throughout the proof we assume that $n$ is large relative to $k$.

Observe that $\deg_{\Gc}(x) \equiv 0 \mod{k-1}$ for each $x \in V(G)$ since $G$ is $K_k$-divisible and $n \equiv 1 \mod{(k-1)}$. Let $z$ be a vertex of minimum degree in $G$ and let $U=N_G(z)$. Since $G$ is $K_k$-divisible there is an integer $a$ such that $|U|=\deg_{G}(z)=a(k-1)$.  Now $\deg_{\Gc}(z)=n-1-a(k-1)$, and each of the $n-1-a(k-1)$ vertices in $N_{\Gc}(z)$ has positive degree in $\Gc$ and hence has degree at least $k-1$. Thus $\sum_{x \in V(G) \setminus U}\deg_{\Gc}(x) \geq k(n-1-a(k-1))$, so
\[k(n-1-a(k-1))+\medop\sum_{x \in U}\deg_{\Gc}(x) \leq 2|E(\Gc)|< k(k-1)\left(\tfrac{n-1}{k-1}-\ell\right)\]
and hence $\sum_{x \in U}\deg_{\Gc}(x) < k(k-1)(a-\ell)$.  Thus, again using $\deg_{\Gc}(x) \equiv 0 \mod{k-1}$ for each $x \in V(G)$,
\[\medop\sum_{x \in U}\lceil\tfrac{1}{k-1}\deg_{\Gc[U]}(x)\rceil  \leq \medop\sum_{x \in U}\lceil\tfrac{1}{k-1}\deg_{\Gc}(x)\rceil = \medop\sum_{x \in U}\tfrac{1}{k-1}\deg_{\Gc}(x) < k(a-\ell).\]
So we can apply Lemma~\ref{L:colouring2} to find a proper colouring of  $\Gc[U]$ with $a$ colours in which each colour class has order $k-1$. Thus, there is a partition $\mathcal{U}$ of $U$ such that $|\mathcal{U}|=a$ and $G[X]$ is a copy of $K_{k-1}$ for each $X \in \mathcal{U}$. Let $\D=\{K_{X \cup \{z\}}:X \in \mathcal{U}\}$.

Let $G'$ be the graph obtained from $G$ by removing the edges of each copy of $K_k$ in $\D$ and then deleting the (now isolated) vertex $z$. It suffices to show that we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp} to find a $K_k$-decomposition $\D'$ of $G'$, for then $\D \cup \D'$ will be a $K_k$-decomposition of $G$. Since $G$ is $K_k$-divisible, so is $G'$. Now,
\begin{equation}\label{E:edgesTh2Proof}
|E(G')| = \mbinom{n}{2}-|E(\Gc)|-|\D|\mbinom{k}{2} > \mbinom{n}{2}-k(n-1) =\mbinom{n}{2}-O(n)
\end{equation}
where the first inequality follows because $|E(\Gc)| < \frac{n-1}{k-1}\binom{k}{2}$ and $|\D| \leq \frac{n-1}{k-1}$. Let $uv$ be an arbitrary edge of $G'$, let $T=(N_{\Gc}(u) \cup N_{\Gc}(v)) \setminus \{z\}$, and note that $u,v \notin T$. Each vertex in $T$ has positive degree in $\Gc$ and hence degree at least $k-1$. Also $\deg_{\Gc}(u)+\deg_{\Gc}(v) \geq |T|$ and hence $\deg_{\Gc}(z) \geq \frac{1}{2}|T|$ by the definition of $z$. Thus we have
\[\tfrac{3}{2}|T|+(k-1)|T| \leq \medop\sum_{x \in \{u,v,z\}}\deg_{\Gc}(x)+\medop\sum_{x \in T}\deg_{\Gc}(x) \leq 2|E(\Gc)| < kn\]
and hence $|T| \leq \frac{2k}{2k+1}n$. So we have $|T'| \leq \frac{2k}{2k+1}n+O(1)$, where $T'=N_{\overline{G'}}(u) \cup N_{\overline{G'}}(v)$, because it follows from the definition of $G'$ that $T'$ can be obtained from $T$ by adding at most $2(k-1)$ vertices. Thus $|N_{G'}(u,v)| = n-3-|T'| \geq \frac{1}{2k+1}n-O(1)$. By this fact and \eqref{E:edgesTh2Proof},  we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp}, choosing $\gamma< \min\{1-\delta_{K_k},\frac{1}{k(2k+1)}\}$, to find a $K_k$-decomposition $\D'$ of $G'$ and hence complete the proof.
\end{proof}

In Lemma~\ref{L:colouring3}, we are forced to prove a slightly stronger result for $k=3$ so as to eventually obtain a tight result for $k=3$ in Theorem~\ref{T:evansForAnyGraph}.

\begin{lemma}\label{L:colouring3}
Let $k$ and $a$ be  integers such that $k \geq 3$ and $a \geq 1$. Let $H$ be a graph of order $a(k-1)$ such that either
\begin{itemize}
    \item[\textup{(i)}]
$\sum_{x \in V(H)}\lceil\frac{1}{k-1}(\deg_H(x)-1)\rceil \leq a-2$; or
    \item[\textup{(ii)}]
$k=3$, $\Delta(H) \leq 2a-2$, and $\sum_{x \in V(H)}\lceil\frac{1}{k-1}(\deg_H(x)-1)\rceil \leq a$.
\end{itemize}
Then $H$ has a proper colouring with $a$ colours such that each colour class has order $k-1$.
\end{lemma}

\begin{proof}
The set-up of the proof proceeds identically to that of the proof of Lemma~\ref{L:colouring} up to and including the paragraph after the claim. So we adopt all the notation defined up to that point and see that it suffices to prove the claim there, which we restate below.
\begin{claim}
There is a vertex in $\Vf$ that is not adjacent in $H_j$ to any vertex in $V'$.
\end{claim}

\noindent \textbf{Proof of claim.} Recall that $v_1,\ldots,v_{a(k-1)}$ is a degeneracy ordering of $V(H)$, $V_i=\{v_1,\ldots,v_i\}$ and $H_i=H[V_i]$ for each $i \in \{1,\ldots a(k-1)\}$ and $\varphi_{j-1}$ is a legal colouring of $H_{j-1}$ with a set $C$ of $a$ colours for some $j \in \{a+1,\ldots,a(k-1)\}$. Further, $V'=\varphi^{-1}_{j-1}(c')$ and $\Vf=\bigcup_{c\in \Cf \setminus \Cn}\varphi^{-1}_{j-1}(c)$ where $c'$ is a colour in $\Cn \setminus \Cf$, $\Cf=\{c \in C: |\varphi_{j-1}^{-1}(c)|=k-1\}$ and $\Cn$ is the set of $\an \geq 1$ colours in $C$ that are assigned by $\varphi_{j-1}$ to vertices adjacent in $H_j$ to $v_j$.

Suppose for a contradiction that each vertex in $\Vf$ is adjacent in $H_j$ to some vertex in $V'$. As in the proof of Lemma~\ref{L:colouring}, and further noting that $|V'| \leq k-2$ because $c' \notin \Cf$, observe that $V'$ and $\Vf$ are disjoint and that
\begin{equation}\label{E:verticesLowerBounds3}
k-2 \geq |V'| \geq 1 \qquad \text{and} \qquad |\Vf|=(k-1)(a-\an).
\end{equation}
We consider two cases based on whether $\an=1$.

\textbf{Case 1:} Suppose $\an=1$. Then, since $c' \in \Cn \setminus \Cf$, it must be the case that $\Cn = \Cn \setminus \Cf=\{c'\}$. It follows that $\Cf=C\setminus\{c'\}$ because $\Cf \cup \Cn=C$. Now each vertex in $\Vf$ is adjacent in $H_j$ to a vertex in $V'$ using our assumption that the claim fails. Thus $\sum_{x \in V'}\deg_{H_j}(x) \geq |\Vf|$ and so
\[\medop\sum_{x \in V'}\tfrac{1}{k-1}(\deg_{H_j}(x)-1) \geq \tfrac{1}{k-1}|\Vf| - \tfrac{1}{k-1}|V'| > a-2\]
where the last inequality follows because $|V'| \leq k-2$ and $\Vf=(k-1)(a-1)$ by \eqref{E:verticesLowerBounds3} since $\an=1$.  This contradicts (i) of our hypotheses, so we may assume that (ii) holds and hence $k=3$ and $\Delta(H) \leq 2a-2$. Then $|V'|=\{y\}$ for some $y \in V_{j-1}$ because $1 \leq |V'|\leq k-2=1$ by \eqref{E:verticesLowerBounds3}. Thus $y$ is adjacent in $H_j$ to each of the $(k-1)(a-1)=2a-2$ vertices in $\Vf$ by our assumption that the claim fails. Furthermore, $y$ is adjacent in $H_j$ to $v_j$ since $c' \in \Cn$. Thus $\deg_{H_j}(y) \geq 2a-1$ in contradiction to our assumption that $\Delta(H) \leq 2a-2$.

\textbf{Case 2:} Suppose $\an \geq 2$. We show this case cannot arise by obtaining a contradiction without the need for our assumption that the claim is false. Then $\deg_{H_j}(v_j) \geq \an \geq 2$ by the definition of $\Cn$. So, for each $x \in V_j$, we have $\deg_{H_j}(x) \geq 2$ by the properties of the degeneracy ordering and hence $\lceil\frac{1}{k-1}(\deg_{H_j}(x)-1)\rceil \geq 1$. But then we have $\sum_{x \in V_j}\lceil\frac{1}{k-1}(\deg_{H_j}(x)-1)\rceil \geq j$ which contradicts both (i) and (ii) of our hypotheses since $j \geq a+1$.
\end{proof}

For each odd $k \geq 5$ and each $a \geq 2$, the tightness of the condition $\sum_{x \in V(H)}\lceil\frac{1}{k-1}(\deg_H(x)-1)\rceil \leq a-2$ in Lemma~\ref{L:colouring3} is witnessed by the graph of order $a(k-1)$ that is the vertex disjoint union of a star with $(a-1)(k-1)+1$ edges and a perfect matching with $\frac{1}{2}(k-3)$ edges. In any proper colouring of such a graph, the colour assigned to the centre vertex of the star must be assigned to fewer than $k-1$ vertices. The proof of Theorem~\ref{T:evansForAnyGraph} differs from the proof of Theorems~\ref{T:evansBigGenk} and~\ref{T:evansForAdmissibleOrder} in that it appears that the order, and hence the degrees, of $G$ can belong to any congruence class modulo $k-1$. However we quickly see that the critical case is when the order of $G$ is congruent to 2 modulo $k-1$.

\begin{proof}[\textbf{\textup{Proof of Theorem~\ref{T:evansForAnyGraph}}}]
The second part of the theorem follows by Lemma~\ref{L:tightnessGenk}(c) and Lemma~\ref{L:k=3tightness}(a), so it remains to prove the first part. Let $G$ be a $K_k$-divisible graph of order $n$ such that either $|E(\Gc)| < n-\frac{1}{2}(k+1)$ or $k=3$ and $|E(\Gc)| < n$. Then, because $G$ cannot be $K_3$-divisible if $|E(\Gc)| = n-2$, in fact we have either
\begin{itemize}[nosep]
    \item
$|E(\Gc)| < n-\frac{1}{2}(k+1)$; or
    \item
$k=3$ and $|E(\Gc)| = n-1$.
\end{itemize}
We assume that $n$ is large relative to $k$ and consider three cases according to the congruence class of $n$ modulo $k-1$.

\textbf{Case 1:} Suppose that $k \geq 4$ and $n-1 \equiv j \mod{(k-1)}$ for some $j \in \{2, \ldots, k-2\}$. Then, because $G$ is $K_k$-divisible, $\deg_{\Gc}(x) \equiv j \mod{(k-1)}$ for each $x \in V(G)$.
Therefore, $|E(\Gc)| \geq \frac{1}{2}jn \geq n$, contradicting our assumption. So this case cannot arise.

\textbf{Case 2:} Suppose that $n-1 \equiv 0 \mod{(k-1)}$. Then, because $G$ is $K_k$-divisible, $\deg_{\Gc}(x) \equiv 0 \mod{(k-1)}$ for each $x \in V(G)$. Let $uv$ be an arbitrary edge of $G$. Let $T=N_{\overline{G}}(u) \cup N_{\overline{G}}(v)$ and note that $u,v \notin T$ and $|T| \leq \deg_{\overline{G}}(u)+\deg_{\overline{G}}(v)$. Also, $\deg_{\overline{G}}(x)$ is positive for each $x \in T$ and hence at least $k-1$. We have
\[|T|+(k-1)|T| \leq \medop\sum_{x \in \{u,v\}}\deg_{\Gc}(x)+\medop\sum_{x \in T} \deg_{\Gc}(x) \leq 2|E(\Gc)| < 2n.\]
So $|T| < \frac{2n}{k} \leq \frac{2n}{3}$ since $k \geq 3$. Therefore, $|N_G(u,v)| = n-2-|T| \geq \frac{n}{3} -O(1)$.
We also have $|E(G)| > \binom{n}{2}-n$.  In view of these two facts,  we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp}, choosing $\gamma<\min\{1-\delta_{K_k}, \frac{1}{3k}\}$, to find a $K_k$-decomposition $\D$ of $G$ and hence complete the proof.

\textbf{Case 3:} Suppose that $n-1 \equiv 1 \mod{(k-1)}$. Then, because $G$ is $K_k$-divisible, $\deg_{\Gc}(x) \equiv 1 \mod{(k-1)}$ for each $x \in V(G)$. It will be convenient to define $\rho=0$ if $|E(\Gc)| < n-\frac{1}{2}(k+1)$ and $\rho=2$ if $k=3$ and $|E(\Gc)| = n-1$, so that we always have
$|E(\Gc)| < n-\frac{1}{2}(k+1)+\rho$.

Let $z$ be a vertex of minimum degree in $G$ and let $U=N_G(z)$. We will show that $\Gc[U]$ obeys the hypotheses of Lemma~\ref{L:colouring3}. Since $G$ is $K_k$-divisible there is an integer $a$ such that $|U|=\deg_{G}(z)=a(k-1)$. We may assume that $a \geq 1$ for otherwise $a=0$, $k=3$, $\Gc$ is a star with $n-1$ edges and hence $G$ is $K_3$-decomposable because its edges form a copy of $K_{n-1}$ and $G$ is $K_3$-divisible by assumption. Now $\deg_{\Gc}(z)=n-1-a(k-1)$, and each of the $n-1-a(k-1)$ vertices in $N_{\Gc}(z)$ has degree at least 1 in $\Gc$. Thus $\sum_{x \in V(G) \setminus U}\deg_{\Gc}(x) \geq 2n-2-2a(k-1)$, so
\begin{equation}\label{E:Th3degSuminU}
\medop\sum_{x \in U}\deg_{\Gc}(x) \leq 2|E(\Gc)|-(2n-2-2a(k-1)) < (2a-1)(k-1)+2\rho
\end{equation}
where the last inequality follows because $|E(\Gc)| < n-\frac{1}{2}(k+1)+\rho$. Thus,
\[\medop\sum_{x \in U}\lceil\tfrac{1}{k-1}(\deg_{\Gc[U]}(x)-1)\rceil  \leq \medop\sum_{x \in U}\lceil\tfrac{1}{k-1}(\deg_{\Gc}(x)-1)\rceil = \tfrac{1}{k-1}\medop\sum_{x \in U}\deg_{\Gc}(x)-a < a-1+\rho\]
where the equality holds because $|U|=a(k-1)$ and $\deg_{\Gc}(x) \equiv 1 \mod{k-1}$ for each $x \in U$, and the last inequality follows using \eqref{E:Th3degSuminU} and the fact that $\frac{2}{k-1}\rho=\rho$ in all cases. So we in fact have $\sum_{x \in U}\lceil\tfrac{1}{k-1}(\deg_{\Gc[U]}(x)-1)\rceil \leq a-2+\rho$ because the terms are all integers.
So if $\rho=0$, then $H$ obeys (i) in the hypotheses of Lemma~\ref{L:colouring3}. If $\rho=2$ and hence $k=3$ and $|E(\Gc)|=n-1$, then $\Delta(\Gc[U]) \leq 2a-2$ for otherwise $\Gc$ would have to be a graph obtained by adding exactly one edge to the vertex disjoint union of a star with $n-2a-1$ edges and a star with $2a-1$ edges. This contradicts the fact that each vertex of $\Gc$ has odd degree. So if $\rho=2$, then $H$ obeys (ii) in the hypotheses of Lemma~\ref{L:colouring3}. Thus, by Lemma~\ref{L:colouring3} there exists a proper colouring of $\Gc[U]$ with $a$ colours in which each colour class has order $k-1$. So there is a partition $\mathcal{U}$ of $U$ such that $|\mathcal{U}|=a$ and $G[X]$ is a copy of $K_{k-1}$ for each $X \in \mathcal{U}$. Let $\D=\{K_{X \cup \{z\}}:X \in \mathcal{U}\}$.

Let $G'$ be the graph obtained from $G$ by removing the edges of each copy of $K_k$ in $\D$ and then deleting the (now isolated) vertex $z$. It suffices to show that we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp} to find a $K_k$-decomposition $\D'$ of $G'$, for then $\D \cup \D'$ will be a $K_k$-decomposition of $G$. Since $G$ is $K_k$-divisible, so is $G'$.

Let $uv$ be an arbitrary edge of $G'$, let $T=(N_{\Gc}(u) \cup N_{\Gc}(v)) \setminus \{z\}$, and note that $u,v \notin T$. Furthermore $\deg_{\Gc}(u)+\deg_{\Gc}(v) \geq |T|$. At most two edges of $\Gc$ are incident with two vertices in $\{u,v,z\}$ and hence
\[\deg_{\overline{G}}(u) + \deg_{\overline{G}}(v) + \deg_{\overline{G}}(z) \leq |E(\overline{G})| + 2 \leq n+1.\]
Thus, because $\deg_{\overline{G}}(u),\deg_{\overline{G}}(v)  \leq \deg_{\overline{G}}(z)$ by the definition of $z$, we have that $|T| \leq \deg_{\overline{G}}(u)+\deg_{\overline{G}}(v) \leq \frac{2}{3}n+O(1)$. So, considering the way in which $G'$ is obtained from $G$,  $N_{G'}(u,v) \geq n-3 - |T| - 2(k-1) > \frac{1}{3}n-O(1)$. We also have
\[|E(G')| = \mbinom{n}{2}-|E(\Gc)|-|\D|\mbinom{k}{2} > \mbinom{n}{2}-n-\tfrac{1}{2}k(n-1) =\mbinom{n}{2}-O(n)\]
because $|E(\Gc)| < n$ and $|\D| \leq \frac{n-1}{k-1}$. In view of these two facts,  we can apply Lemma~\ref{L:mutualNeighbourhoodDecomp}, choosing $\gamma< \min\{1-\delta_{K_k}, \frac{1}{3k}\}$, to find a $K_k$-decomposition $\D'$ of $G'$ and so complete the proof.
\end{proof}

The proof of Corollary~\ref{C:k=3} follows easily from Theorems~\ref{T:evansForAdmissibleOrder} and~\ref{T:evansForAnyGraph} and Lemma~\ref{L:k=3tightness}.

\begin{proof}[\textbf{\textup{Proof of Corollary~\ref{C:k=3}}}]
For $n \equiv 1,3 \mod{6}$ the result follows immediately from Theorem~\ref{T:evansForAdmissibleOrder} and for $n \equiv 0 \mod{6}$ the result follows immediately from Theorem~\ref{T:evansForAnyGraph}. For $n \equiv 5 \mod{6}$, Lemma~\ref{L:k=3tightness}(b) gives a $K_3$-divisible graph with $\binom{n}{2}-\frac{1}{2}(3n-7)$ edges that has no $K_3$-decomposition and, furthermore, any $K_3$-divisible graph of order $n$ with more than $\binom{n}{2}-\frac{1}{2}(3n-7)$ edges has at least $\binom{n}{2}-\frac{1}{2}(3n-13)$ edges and hence is $K_3$-decomposable by Theorem~\ref{T:evansForAdmissibleOrder} if $n$ is sufficiently large. For $n \equiv 2,4 \mod{6}$, Lemma~\ref{L:k=3tightness}(c) gives a $K_3$-divisible graph with $\binom{n}{2}-n-2$ edges that has no $K_3$-decomposition and, furthermore, any $K_3$-divisible graph of order $n$ with more than $\binom{n}{2}-n-2$ edges has at least $\binom{n}{2}-n+1$ edges and hence is $K_3$-decomposable by Theorem~\ref{T:evansForAnyGraph} if $n$ is sufficiently large.
\end{proof}

\section{Conclusion}

The work here leaves many avenues for further investigation. It would of course be desirable to establish results similar to ours for all $n$ rather than simply for sufficiently large $n$. However, for general $k$, even the existence problem for $(n,k,1)$-designs is only resolved for large $n$. Even for values of $k$ where the existence problem is completely solved, such an improvement of our results would not be achievable using the techniques we have employed here, due to their reliance on the decomposition results in \cite{GlockKuhnLoMontgomeryOsthus2019}. One could also ask for results similar to Theorem~\ref{T:evansBigGenk} for partial $(n,k,\lambda)$-designs for $\lambda \geq 2$. It may be that the techniques used here could be adapted to prove such results. As mentioned in Section~\ref{S:prelim}, Theorems~\ref{T:evansForAdmissibleOrder} and~\ref{T:evansForAnyGraph} are not necessarily tight for all $k$, and so there is the possibility of improving them for specific values of $k$. Further, one could attempt to prove results analogous to Corollary~\ref{C:k=3} for values of $k$ other than $3$. These last two possible goals may involve significant case analysis, however. Finally, Lemma~\ref{L:mutualNeighbourhoodDecomp} suggests the problem of investigating what conditions on the size and number of triangles per edge of a graph are sufficient to guarantee that it has a $K_k$-decomposition.

\bigskip
\noindent\textbf{Acknowledgments.}
The second author was supported by Australian Research Council grants DP150100506 and FT160100048.


TITLE: How to calculate the phase and group velocity of a superposition of sine waves with different speed and wavelength?
QUESTION [5 upvotes]: This might seem like a trivial question but it is not for me. So, I was reading on group and phase velocities from A.P. French where he calculates the phase and group velocities for a superposition of sine waves of different speed and wavelength. I will write down a brief analysis:
$$y(x,t)=A\sin(k_1x-\omega_1t) + A\sin(k_2x-\omega_2t) $$ which simplifies to
$$y(x,t)=2A\sin\left(\frac{k_1+k_2}{2}x-\frac{\omega_1+\omega_2}{2}t\right)\cos\left(\frac{k_1-k_2}{2}x-\frac{\omega_1-\omega_2}{2}t\right)$$
Now, what I usually find in literature is that for a general wave,the velocity of a wave is defined as $v=\omega/k$ and here we see that by simplifying the superposition, we get a slow moving and a fast moving term and
(1) For the slow moving wave which represents the group envelope, we call the velocity as group velocity $v_g=\Delta \omega/\Delta k=\partial\omega/\partial k$ (for waves with small differences in $\omega$ and $k$).
(2) For the fast moving wave which represents the ripples, we call the velocity as phase velocity $v_g=\bar \omega/\bar k=\omega/ k$ (if $\omega$ is given as a function of $k$).
What I don't understand in this analysis is

Why this definition of velocity? Why did we just divide the factors of x and t and call that as velocity? For a single sine wave, I understand how we can find the displacement of a maxima or minima and see how much it moves in some time t and define that as velocity (just like mentioned here). But is there any similar treatment possible for this?
How did we identify which one was the group and which one was the phase velocity? Also, it is not very intuitive at first site for a person who didn't know this before that there are actually 2 velocities embodied in such a solution?

I would be very grateful if someone could possibly have an answer to these questions.

REPLY [2 votes]: The phase velocity is just velocity of plane wave in the usual sense: $v_p=\omega/k=v$. The group velocity, with definition
$$v_g=\left.\frac{\partial \omega}{\partial k}\right|_{k=k_0}\tag{1}$$
, is originally derived from the presumption of a traveling wave packet (see this Wikipedia for details. In what follows similar annotations and symbols to the article will be used)
with mean momentum value of $k_0$. In that article the wave packet function in space and time is written as
\begin{align}
\alpha(x,t)=\int dkA(k)e^{i(kx-\omega t)}\tag{2}
\end{align}
Note the integral here means superposition of infinite number of complex-valued traveling plane waves $e^{i(kx-\omega t)}$, your question being asked here with superposition of only two wave numbers $k_1$ and $k_2$ is only a special case.
You can rewrite (2) as
\begin{align}
\alpha(x,t)=e^{i(k_0x-\omega_0 t)}\int dkA(k)e^{i(k-k_0)(x-\omega'_0 t)}\tag{3}
\end{align}
where Taylor expansion to first order $\omega\approx \omega_0+(k-k_0)\omega'_0$ is used. The main difference between the two integrands in (2) and (3) is that, all components of exponential term in the integral of (3) has the same "phase velocity" of $\frac{(k-k_0)\omega'_0}{(k-k_0)}=\omega'_0$, independent of the integration variable $k$. It is therefore identified as the group velocity of the wave packet envelope.
Back to your question of: how to identify which term correspond to phase velocity or group velocity? For the simple case of adding two plane waves with constant $k$ and $\omega$, the excellent visualization from the other answer shows that the wave which we call "envelope" must have longer wavelength than the "inner" waves. Since $k=2\pi/\lambda$, we can conclude that the cosine term with smaller wave number ($\frac{k_1-k_2}{2}$ as opposed to $\frac{k_1+k_2}{2}$) corresponds to the group velocity of the wave envelope. If we acknowledge that (1) is correct, then we can also see that the "phase velocity" of the cosine term is consistent with the definition of the group velocity of wave envelope:
\begin{equation}
  \frac{(\omega_1-\omega_2)/2}{(k_1-k_2)/2}=\frac{(\omega_1-\omega_2)}{(k_1-k_2)}=\frac{\partial \omega}{\partial k}
\end{equation}
. The latter follows directly because all $k_1,k_2,\omega_1,\omega_2$ are constant in your example.