Minimum steps adding edges to form a complete graph

Consider a graph $G$ with $t$ vertices and $0$ edges. Turn it into the complete graph $K_t$ by repeatedly applying the following move $M$:

$M$: Choose $n$ vertices in $G$ and add edges between each of them to make a complete subgraph $K_n$ within $G$. This gives the new $G$.

Question: Given $t$ and $n$, what is the least number $m$ of times $M$ has to be applied before $G$ is $K_t$?

Notes:

If $n=2$ then $m$ is ${t \choose 2}$.

If $n=t-1$ then $m$ is 3.

I'd prefer a comprehensive derivation of some estimation over precise candidates for computation.

Solution 1:

As mentioned in comments there is a trivial lower bound on $m$: $m \ge \left\lceil\frac{t(t - 1)}{n(n - 1)}\right\rceil$. This bounds is not tight even for $t = 4$ and $n = 3$ when $m = 3$ while the bound is $2$.

Let's think deeper: $\deg_{K_t} v = t - 1$ for any $v \in K_t$, and initially $\deg_G v = 0$. Each move $M$ increrases degree of $v$ by at most $n - 1$. Then each of $t$ vertices requires at least $\left\lceil\frac{t - 1}{n - 1}\right\rceil$ moves. And each move affects exactly $n$ vertices. Thus we get $m \ge \left\lceil\left\lceil\frac{t - 1}{n - 1}\right\rceil\cdot\frac{t}{n}\right\rceil$. It is exact up to $(t, n) = (7, 4)$ when $m = 5$ and the bound is $4$. (I mean my bound is exact for $t \le 6$ and for $t = 7$ and $n \le 3$.)

The most trivial upper bound for $n \ge 2$ is $\frac{t(t - 1)}2$ that is the number of edges. Let's try to get something better. To cover all edges incident to a single vertex it would be enought to make $\left\lceil\frac{t - 1}{n - 1}\right\rceil$ moves $M$. After that we can remove this vertex and get $K_{t - 1}$ on all other vertices. And so on until we left only $n$ vertices that need only one move: $$m \le \left\lceil\frac{t - 1}{n - 1}\right\rceil + \left\lceil\frac{t - 2}{n - 1}\right\rceil + \cdots + \left\lceil\frac{n - 1}{n - 1}\right\rceil.$$ To simplify this bound let's use $k = \left\lfloor\frac{t - 2}{n - 1}\right\rfloor$ and $r = (t - 2) - k(n - 1)$. Noting that $\left\lceil\frac xy\right\rceil = \left\lfloor\frac{x + y - 1}{y}\right\rfloor$ for integers $x$ and $y$, we get: $$m \le \left\lfloor\frac{t + n - 3}{n - 1}\right\rfloor + \left\lfloor\frac{t + n - 4}{n - 1}\right\rfloor + \cdots + \left\lfloor\frac{n + n - 3}{n - 1}\right\rfloor\\ = (k + 1) \cdot (r + 1) + k \cdot (n - 1) + (k - 1)\cdot(n - 1) + \cdots + 2 \cdot (n - 1) + 1\\ = (k + 1) \cdot (r + 1) + \left(\frac{k(k + 1)}{2} - 1\right)(n - 1) + 1\\ = \frac{k(k + 1)}{2}(n - 1) + kr + k + r - n + 3.$$

Here I combine these two bounds into one table: $$\begin{array}{c|c|c|c|c|c|c|c} n\backslash t & 2 & 3 & 4 & 5 & 6 & 7 & 8\\\hline 2 & 1 / 1 & 3 / 3 & 6 / 6 & 10 / 10 & 15 / 15 & 21 / 21 & 28 / 28\\\hline 3 & & 1 / 1 & 3 / 3 & \color{red}{5} / 4 & \color{red}{8} / 6 & \color{red}{11} / 7 & \color{red}{15} / 11\\\hline 4 & & & 1 / 1 & 3 / 3 & \color{red}{5} / 3 & \color{red}{7} / \color{red}{4} & \color{red}{10} / 6\\\hline 5 & & & & 1 / 1 & 3 / 3 & \color{red}{5} / 3 & \color{red}{7} / \color{red}{3}\\\hline 6 & & & & & 1 / 1 & 3 / 3 & \color{red}{5} / 3\\\hline 7 & & & & & & 1 / 1 & 3 /3\\\hline 8 & & & & & & & 1 / 1 \end{array}$$

Non-exact bounds are marked with red color. As far as you see both bounds agree on $n = 2$, $n = t$ and $n = t - 1$ and the lower bound is much more close to the answer.

Solution 2:

No doubt you can find something much more up to date, but I happen to have a copy of a survey from 1979, so I will quote a couple of sample results from that.

The survey is: A. E. Brouwer, Packing and covering of $\binom kt$-sets, Mathematical Centre Tracts 106 (1979) 89–97.

Let $V$ be a set of $t$ vertices; the minimum size of a family $\mathcal B$ of $n$-element subsets of $V$ such that every $2$-element subset of $V$ is contained in a member of $\mathcal B$ is called the covering number $C(2,n,t).$

For $n=3,$ the following result is attributed to M. K. Fort, Jr., and G. A. Hedlund, Minimal coverings of pairs by triples, Pacific J. Math. 8 (1958) 709–719: $$C(2,3,t)=\left\lceil\frac t3\left\lceil\frac{t-1}2\right\rceil\right\rceil\text{ for all }t.$$ For $n=4,$ the following results are attributed to W. H. Mills, On the covering of pairs by quadruples, I: J. Combin. Theory Ser. A 13 (1972) 55–78, II: J. Combin. Theory Ser. A 15 (1973) 138–166: $$C(2,4,t)=\left\lceil\frac t4\left\lceil\frac{t-1}3\right\rceil\right\rceil\text{ for }t\ne7,9,10,19,$$ and $$C(2,4,t)=5,8,9,31\text{ for }t=7,9,10,19.$$