Estoy tratando de encontrar una manera rigurosa de demostrar que dado un gráfico que tiene exactamente 10 3 cliques(triángulos), el número máximo de 4 cliques que se pueden formar es 3. O más generalmente si hay conexión con el número de (k-1) cliques y el número máximo de k cliques.
Respuesta
¿Demasiados anuncios?
No creo que la pregunta sea correcta. Considere $K_5$ (gráfico completo en $5$ vértices). Tiene $\binom{5}{3} = 10$ $3$ -cliques y $\binom{5}{4}=5$ $4$ -cliques.
Se puede obtener un límite aproximado para el caso general como se muestra a continuación. Pero no creo que sea un buen límite, es decir, los límites pueden no ser ajustados para cualquier gráfico.
Cada $k$ La camarilla contiene $k$ número de $k-1$ camarillas en ella. Y cualesquiera dos $k$ Las camarillas pueden tener como máximo un $k-1$ camarilla común. Usando estas dos observaciones podemos obtener algunos límites crudos.
Supongamos que el número de $k$ camarillas es $r$ . A continuación, la primera $k$ camarilla tiene $k$ número de $k-1$ camarillas en ella. La siguiente $k$ camarilla de nuevo tiene $k$ número de $k-1$ camarillas, pero como máximo una de ellas es común con la primera $k$ camarilla. Así que tiene al menos $k-1$ nuevo $k-1$ camarillas. Del mismo modo, la tercera tendrá al menos $k-2$ nuevo $k-1$ camarillas, etc.
Ahora, obtenemos un límite inferior para el número de $k-1$ camarillas (digamos $R$ ) en términos de $r$ como,
si $r \geq k$ ,
$$ R \geq k(k-1)/2 $$
si $r < k$
$$ R \geq k+(k-1)+ \ldots +(k-r+1) = rk - r(r-1)/2 $$
