¿Pregunta de teoría de grafos, probablemente con el teorema de Ramsey?

Question

Tenemos un club con $\frac{s(s+1)}{2}$ personas, y sabemos que no importa cómo elijamos $3$ de ellos, hay al menos $2$ de ellos, que se conocen entre sí.

Demostrar, que si esto es cierto, entonces siempre podemos elegir $s$ personas, donde todos se conocen. En el lenguaje de grafos, tenemos un grafo con $\frac{s(s+1)}{2}$ vértices, y dibujamos aristas si $2$ la gente se conoce. No importa cómo elijamos $3$ vértices, siempre encontramos al menos $1$ borde. Demostrar que este gráfico tiene $K_s$ en él( $s$ vértices con todas las aristas posibles dibujadas).

He intentado demostrar esto de diferentes maneras, pero no puedo concluir por qué es cierto, ¿tal vez se pueda resolver con el teorema de Ramsey?

¿Alguna idea? Gracias.

Answer 1

En efecto, quieres colorear las aristas de tu gráfico con azul, y todas las no aristas con rojo. Esto da una coloración rojo-azul de las aristas de $K_{{s+1\choose 2}}.$

Realmente, el punto principal es mostrar que esa $R(3,s)\leq {s+1\choose 2}$ , donde $R(3,s)$ es el más pequeño $n$ para que cualquier coloración roja-azul de los bordes de $K_n$ tiene un rojo $K_3$ o un azul $K_s$ . Ya que se da que su gráfico no tiene rojo $K_3$ se puede concluir que tiene un azul $K_s$ .

Para mostrar esa cota superior, utilice la inducción y la desigualdad $$R(r, s) \leq R(r − 1, s) + R(r, s − 1)$$ para todos $r,s$ . Además, observe que $R(2,s)=s$ .