Número de $K_{10}$ siempre aumenta

Question

Sea $G=(V,E)$ sea un grafo con $n\geq 10 $ vértices. Supongamos que cuando añadimos cualquier arista a $G$ el número de grafos completos $K_{10}$ en $G$ aumentos. Demuestre que $|E|\geq 8n-36$ .

[Fuente: The probabilistic method, Alon and Spencer 3rd ed., p.12, problem 5].

Para el caso base $n=10$ sabemos $G$ debe tener $44=8\cdot 10-36$ bordes.

Conocemos todos los vértices de $G$ debe tener titulación $\geq 8$ de lo contrario, añadir una arista que conecte ese vértice no puede aumentar el número de $K_{10}$ . Esto da $|E|\geq 4n$ .

Answer 1

La solución a este problema utiliza una aplicación inteligente del Teorema 1.3.3 (en "El método probabilístico, 3ª edición"). Como no todo el mundo tiene acceso al texto, primero expondré aquí el teorema (con las definiciones necesarias).

Definición : Sea $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ sea una familia de pares de subconjuntos de un conjunto base arbitrario. $\mathcal{F}$ es un $(k,\ell)$ -sistema si $|A_{i}|=k$ y $|B_{i}|=\ell$ para $1\leq i\leq h$ , $A_{i}\cap B_{i}=\emptyset$ para todos $1\leq i\leq h$ y $A_{i}\cap B_{j}\neq \emptyset$ para todos $i\neq j$ con $1\leq i, j\leq h$ .

Teorema (1.3.3) Si $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ es un $(k,\ell)$ -sistema, entonces $h\leq \binom{k+\ell}{k}$ .

Ahora, la estrategia para resolver el problema original consiste en crear un $(k,\ell)$ -sistema y aplicar el resultado.

Sea $h$ es el número de aristas que no están en $G$ y enumerar los no-borde de $G$ como $\{e_1, e_2, ..., e_h\}$ . Para cada $e_{i}$ asociar un conjunto de 10 vértices que forman un $K_{10}$ si $e_{i}$ debían añadirse a $G$ . La hipótesis garantiza que existe al menos un conjunto de $10$ vértices; si hay más de uno, elige uno arbitrariamente. Llamaremos a esto "potencial" $K_{10}$ , $K_{10}^{i}$ para indicar que se forma añadiendo la arista $e_{i}$ . Cada borde $e_{i}$ tiene dos extremos, llámalos $v_{i, 1}$ y $v_{i,2}$ . Formar el conjunto $A_{i}=\{v_{i, 1}, v_{i, 2}\}$ . Formar el conjunto $B_{i}=V(G)-V(K_{10}^{i})$ es decir, todos los vértices de $G$ que no están en $K_{10}^{i}$ , el elegido $K_{10}$ formado por la adición de la arista $e_{i}$ . Queremos verificar que $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ es un $(2, n-10)$ -sistema.

Claramente, $|A_{i}|=2$ y $|B_{i}|=n-10$ para $1\leq i\leq h$ . También está claro que $A_{i}\cap B_{i}=\emptyset$ para $1\leq i\leq h$ ya que los vértices de $A_{i}$ están contenidos en $K_{10}^{i}$ . Para cualquier $i\neq j$ Obsérvese que al menos un vértice de $e_{i}$ no está en $K_{10}^{j}$ de lo contrario, ambos $e_{i}$ y $e_{j}$ para que $K_{10}^{j}$ un gráfico completo. Por lo tanto, al menos un vértice en $A_{i}\in B_{j}$ lo que implica que $A_{i}\cap B_{j}\neq \emptyset$ . Por lo tanto, tenemos un $(2, n-10)$ -sistema.

Por el teorema 1.3.3, $h\leq \binom{2+(n-10)}{2}=\binom{n-8}{2}$ . Desde $h$ cuenta el número de no-borde de $G$ podemos concluir que $G$ tiene al menos $\binom{n}{2}-\binom{n-8}{2}$ bordes.

Y, (la parte fácil) \begin{align*} \binom{n}{2}-\binom{n-8}{2} &= \frac{1}{2}\left(n(n-1) - (n-8)(n-9)\right) \\ &= \frac{1}{2}\left(n^2-n -(n^2 - 17n + 72)\right) \\ &= 8n-36. \end{align*}

Answer 2

Ya tiene la mayor parte de la información necesaria para una prueba. Usando la inducción y muy poco trabajo adicional, tendrás tu prueba.

Diremos gráfico $G$ tiene propiedad $\mathcal{P}$ si la adición de cualquier borde adicional aumentará su número de $K_{10}$ s. Digamos que tienes un $G$ con $n > 10$ vértices. Ahora, ¿qué se puede decir (con respecto a la propiedad $\mathcal{P}$ ) sobre el gráfico con $n-1$ vértices obtenidos suprimiendo un vértice arbitrario $v$ de $G$ ? Puede utilizar esta respuesta, información de grado mínimo de $v$ y el principio de inducción para terminar la demostración.