El número de camarillas de tamaño $4$ donde todas las aristas son del mismo color es como máximo $\frac{\binom{n}{4}}{3^5}.$

Question

Dejemos que $K_n$ sea el gráfico completo en $n$ vértices. Demostrar que para todos los enteros $n \ge 4$ podemos asignar a cada arista una de $3$ colores tal que el número de camarillas de tamaño $4$ donde todas las aristas son del mismo color es como máximo $$\frac{\binom{n}{4}}{3^5}.$$

---

¿Puede alguien dar alguna pista? No soy capaz de ver el problema.

Hay $\binom{n}{2}$ bordes en $K_n$ .

Answer 1

Fijar un $4$ -y una coloración de bordes elegida uniformemente con un máximo de $3$ colores. La camarilla tiene $\binom{4}{2}=6$ bordes, por lo que la probabilidad de que sea monocromática es $3/3^6$ . Por linealidad de la expectativa, el número esperado de monocromos $4$ -cliques es $\binom{n}{4}3/3^6=\binom{n}{4}/3^5$ . Por lo tanto, existe una coloración con a lo sumo (y también una con a lo sumo) esa cantidad de monocromáticos $4$ -cliques.