$R(3,3) \ge 6$

Teoría

La afirmación $R(3,3) \ge 6$ representa la parte de la "cota inferior" de la determinación clásica del número de Ramsey para triángulos. En la Teoría de Ramsey, el número $R(r, s)$ lo definimos como el entero mínimo $n$ tal que cualquier coloración de las aristas de un grafo completo $K_n$ con dos colores (digamos, Rojo y Azul) garantiza que existe un $K_r$ Rojo (un subgrafo completo de tamaño $r$) o un $K_s$ Azul. Para demostrar una cota superior (por ejemplo, $R(3,3) \le 6$), tienes que mostrar que toda coloración funciona. Por el contrario, para demostrar una cota inferior como $R(3,3) > 5$ (que implica $R(3,3) \ge 6$), tienes que dar un contraejemplo específico: una prueba constructiva que muestre una coloración de $K_5$ que no tenga ni un triángulo Rojo ni un triángulo Azul.

Este resultado es fundamental en combinatoria porque introduce el método de las cotas inferiores constructivas. Aunque los métodos probabilísticos (introducidos por Paul Erdős) se usan seguido para números de Ramsey grandes, los números de Ramsey pequeños requieren construcciones de grafos precisas. La construcción que se usa para $R(3,3) \ge 6$ se apoya en la simetría del grupo cíclico $\mathbb{Z}_5$. Demuestra que el desorden local (una coloración arbitraria) no es necesario para evitar estructuras; las estructuras muy simétricas también pueden evitar clanes monocromáticos.

Intuitivamente, esta cota específica corresponde a la geometría de un pentágono regular. Si tomas los 5 vértices del grafo como los vértices de un pentágono, puedes dividir las aristas en dos clases disjuntas: los "lados" del pentágono y las "diagonales" (que forman un pentagrama o estrella). Al colorear los lados de un color y las diagonales de otro, aprovechas el hecho de que un triángulo necesita que tres vértices estén conectados entre sí, pero ni los lados por sí solos ni las diagonales por sí solas conectan tres vértices de esa manera.

Fórmulas Clave

Definición del Número de Ramsey: $$R(r, s) = \min { n \in \mathbb{Z}^+ : \text{cualquier 2-coloración de } K_n \text{ contiene un } K_r \text{ o } K_s \text{ monocromático} }$$

La Desigualdad de la Cota Inferior: Para mostrar que $R(r, s) > n$, tienes que construir una coloración de $K_n$ sin ningún $K_r$ o $K_s$ monocromático. Específicamente: $$R(3,3) > 5 \implies R(3,3) \ge 6$$

Descomposición de Grafos: La demostración se basa en descomponer el grafo completo $K_5$ en dos ciclos de longitud 5 con aristas disjuntas: $$K_5 = C_5 \oplus C_5$$ Donde un $C_5$ representa las aristas rojas y el otro $C_5$ representa las aristas azules.

Demostración

Teorema: $R(3,3) \ge 6$.

Demostración: Para demostrar que $R(3,3) \ge 6$, basta con mostrar que $R(3,3) > 5$. Por definición, esto requiere construir una 2-coloración de las aristas del grafo completo de 5 vértices, $K_5$, de tal manera que no haya ningún triángulo monocromático (ni un $K_3$ Rojo ni un $K_3$ Azul).

Paso 1: Etiquetado de Vértices Toma el conjunto de vértices de $K_5$ como $V = {0, 1, 2, 3, 4}$, que representa los enteros módulo 5.

Paso 2: La Construcción de la Coloración La coloración de la arista que conecta los vértices $i$ y $j$ la definimos basándonos en la diferencia entre ellos módulo 5. Sea $d = (i - j) \pmod 5$. Nota que como el grafo no es dirigido, la distancia es simétrica (la distancia 1 es equivalente a la 4, y la 2 es equivalente a la 3).

• Regla 1 (Aristas Rojas): Colorea la arista $(i, j)$ de Rojo si la diferencia es $\pm 1 \pmod 5$.

  • Aristas Rojas: ${(0,1), (1,2), (2,3), (3,4), (4,0)}$
  • Geométricamente, estos son los lados de un pentágono regular.

• Regla 2 (Aristas Azules): Colorea la arista $(i, j)$ de Azul si la diferencia es $\pm 2 \pmod 5$.

  • Aristas Azules: ${(0,2), (2,4), (4,1), (1,3), (3,0)}$
  • Geométricamente, estas son las diagonales de un pentágono regular (formando una estrella).

Paso 3: Verificación de la Ausencia de Triángulos Hay que verificar que ni el subgrafo Rojo ni el subgrafo Azul contienen un triángulo.

• Revisando el Rojo: Las aristas Rojas forman el ciclo $0-1-2-3-4-0$ (un $C_5$).

  • Para formar un triángulo, necesitas tres vértices $u, v, w$ tales que las aristas $(u,v)$, $(v,w)$ y $(w,u)$ sean todas Rojas.
  • En un $C_5$, cualquier vértice está conectado solo a sus dos vecinos inmediatos. Por ejemplo, el vértice 0 está conectado al 1 y al 4. Sin embargo, los vértices 1 y 4 no están conectados por una arista Roja (su distancia es 3, lo que implica una arista Azul).
  • Por lo tanto, el subgrafo Rojo no contiene triángulos.

• Revisando el Azul: Las aristas Azules forman el ciclo $0-2-4-1-3-0$.

  • Este grafo es isomorfo al grafo Rojo (también es un $C_5$).
  • Como $C_5$ no tiene triángulos, el subgrafo Azul también está libre de triángulos.

Conclusión Ya mostramos una 2-coloración de $K_5$ donde no hay tres vértices que formen un triángulo monocromático. Esto demuestra que un conjunto de 5 personas no necesariamente contiene a 3 conocidos mutuos o a 3 desconocidos mutuos. En consecuencia, el número de Ramsey debe ser estrictamente mayor que 5.

$$R(3,3) \ge 6$$ $\square$