10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please, use $ for each formula. $\endgroup$ – Smylic Mar 9 '17 at 22:44
  • $\begingroup$ Would you be interested or already know some upper or lower bounds for the minimal amount of times $M$ needs to be applied? $\endgroup$ – benguin Mar 10 '17 at 2:34
  • $\begingroup$ @benguin I would be interested. Working on it. $\endgroup$ – Ola Mar 10 '17 at 8:50
  • 1
    $\begingroup$ The total number of edges in the complete graph $K_t$ is $t(t-1)/2$. The maximum number of edges that can be added in a "move" is $n(n-1)/2$. Thus the minimum number of moves is bounded below by $\lceil {t(t-1) \over n(n-1)} \rceil$. This is not a tight bound, of course. $\endgroup$ – David G. Stork Mar 10 '17 at 17:23
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.