Pasos mínimos añadiendo aristas para formar un gráfico completo

Question

Considere un gráfico $G$ con $t$ vértices y $0$ bordes. Convertirlo en el gráfico completo $K_t$ aplicando repetidamente el siguiente movimiento $M$ :

$M$ : Elija $n$ vértices en $G$ y añadir aristas entre cada una de ellas para formar un subgrafo completo $K_n$ en $G$ . De este modo, el nuevo $G$ .

Pregunta: Dado $t$ y $n$ , cuál es el menor número $m$ de veces $M$ debe aplicarse antes de $G$ es $K_t$ ?

---

Notas:

Si $n=2$ entonces $m$ es ${t \choose 2}$ .

Si $n=t-1$ entonces $m$ es 3.

Preferiría una derivación exhaustiva de alguna estimación antes que candidatos precisos para el cálculo.

Answer 1

Como se ha mencionado en los comentarios, existe un límite inferior trivial para $m$ : $m \ge \left\lceil\frac{t(t - 1)}{n(n - 1)}\right\rceil$ . Este límite no es ajustado ni siquiera para $t = 4$ y $n = 3$ cuando $m = 3$ mientras que el límite es $2$ .

Pensemos más profundamente: $\deg_{K_t} v = t - 1$ para cualquier $v \in K_t$ y en un principio $\deg_G v = 0$ . Cada movimiento $M$ aumenta el grado de $v$ por un máximo de $n - 1$ . Entonces cada uno de $t$ vértices requiere al menos $\left\lceil\frac{t - 1}{n - 1}\right\rceil$ se mueve. Y cada movimiento afecta exactamente $n$ vértices. Así, obtenemos $m \ge \left\lceil\left\lceil\frac{t - 1}{n - 1}\right\rceil\cdot\frac{t}{n}\right\rceil$ . Es exacto hasta $(t, n) = (7, 4)$ cuando $m = 5$ y el límite es $4$ . (Quiero decir que mi límite es exacto para $t \le 6$ y para $t = 7$ y $n \le 3$ .)

El límite superior más trivial para $n \ge 2$ es $\frac{t(t - 1)}2$ que es el número de aristas. Intentemos conseguir algo mejor. Para cubrir todas las aristas que inciden en un solo vértice bastaría con hacer $\left\lceil\frac{t - 1}{n - 1}\right\rceil$ se mueve $M$ . Después podemos eliminar este vértice y obtener $K_{t - 1}$ en todos los demás vértices. Y así sucesivamente hasta que dejemos sólo $n$ vértices que sólo necesitan un movimiento: $$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.$$ Para simplificar este límite vamos a utilizar $k = \left\lfloor\frac{t - 2}{n - 1}\right\rfloor$ y $r = (t - 2) - k(n - 1)$ . Observando que $\left\lceil\frac xy\right\rceil = \left\lfloor\frac{x + y - 1}{y}\right\rfloor$ para los enteros $x$ y $y$ obtenemos: $$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.$$

Aquí combino estos dos límites en una sola tabla: $$\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}$$

Los límites no exactos están marcados en rojo. Por lo que se ve ambos límites coinciden en $n = 2$ , $n = t$ y $n = t - 1$ y el límite inferior está mucho más cerca de la respuesta.

Answer 2

Sin duda se puede encontrar algo mucho más actualizado, pero resulta que tengo una copia de una encuesta de 1979, así que citaré un par de resultados de muestra de la misma.

La encuesta es: A. E. Brouwer, Packing and covering of $\binom kt$ -sets, Mathematical Centre Tracts 106 (1979) 89-97.

Dejemos que $V$ sea un conjunto de $t$ vértices; el tamaño mínimo de una familia $\mathcal B$ de $n$ -subconjuntos de elementos de $V$ de manera que cada $2$ -subconjunto de elementos de $V$ está contenido en un miembro de $\mathcal B$ se llama número de cobertura $C(2,n,t).$

Para $n=3,$ el siguiente resultado se atribuye a M. K. Fort, Jr. y 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.$$ Para $n=4,$ los siguientes resultados se atribuyen a W. H. Mills, On the covering of pairs by quadruples, I: J. Combin. A 13 (1972) 55-78, II: J. Combin. 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,$$ y $$C(2,4,t)=5,8,9,31\text{ for }t=7,9,10,19.$$