Teoría de Ramsey

Teoría

La Teoría de Ramsey es una rama de la combinatoria que estudia las condiciones bajo las cuales el orden debe aparecer en estructuras grandes y caóticas. La idea central es que "el desorden total es imposible". En el contexto de la teoría de gráficas, dice que para cualquier parámetro entero dado, una gráfica completa lo suficientemente grande inevitablemente tendrá una subgráfica completa monocromática de un tamaño específico, sin importar cómo colorees las aristas. Esta área de estudio generaliza el Principio de la Casilla; mientras que el Principio de la Casilla garantiza que dos elementos compartan un contenedor, la Teoría de Ramsey garantiza que existan patrones estructurales complejos.

En competencias matemáticas como la USAMO o la IMO, la Teoría de Ramsey a menudo aparece como un problema de coloración de aristas. Si coloreas las aristas de una gráfica completa $K_n$ con $c$ colores, la Teoría de Ramsey te ayuda a determinar el $n$ mínimo necesario para garantizar una clique monocromática (una subgráfica completa donde todas las aristas son del mismo color). El ejemplo introductorio más famoso es el "Problema de la Fiesta", que dice que en cualquier grupo de seis personas, o hay tres que se conocen entre sí o hay tres que son completos desconocidos.

El poder de la Teoría de Ramsey está en las pruebas de existencia. Te permite demostrar que cierta estructura existe sin que tengas que construirla explícitamente. Aunque determinar los valores exactos de los números de Ramsey es famosamente difícil (y a menudo imposible computacionalmente para parámetros grandes), entender los límites y la naturaleza recursiva de estos números te da herramientas críticas para resolver problemas combinatorios avanzados que involucran particiones y coloraciones.

Fórmulas Clave

Definición del Número de Ramsey $R(r, s)$ El número de Ramsey $R(r, s)$ es el entero más pequeño $n$ tal que cualquier coloración con 2 colores (digamos, Rojo y Azul) de las aristas de una gráfica completa $K_n$ tiene ya sea una $K_r$ Roja o una $K_s$ Azul.

Valores Fundamentales $$R(3, 3) = 6$$ $$R(3, 4) = R(4, 3) = 9$$ $$R(4, 4) = 18$$

Teorema de Ramsey Para cualquier par de enteros $r, s \ge 2$, el número de Ramsey $R(r, s)$ existe y es finito.

Recurrencia de Erdős-Szekeres (Cota Superior) Para enteros $r, s > 2$: $$R(r, s) \le R(r-1, s) + R(r, s-1)$$ Si tanto $R(r-1, s)$ como $R(r, s-1)$ son pares, la desigualdad es estricta: $$R(r, s) \le R(r-1, s) + R(r, s-1) - 1$$

Cota Superior General Obtenida de la recurrencia de arriba: $$R(r, s) \le \binom{r+s-2}{r-1}$$

Demostración

Teorema: $R(3, 3) = 6$.

Demostración: Para demostrar que $R(3, 3) = 6$, tienes que establecer dos hechos:

1. $R(3, 3) > 5$ (Existe una gráfica de tamaño 5 sin triángulos monocromáticos).
2. $R(3, 3) \le 6$ (Cualquier gráfica de tamaño 6 debe tener un triángulo monocromático).

Parte 1: Cota Inferior ($R(3, 3) > 5$) Considera una gráfica completa con 5 vértices, $K_5$. Acomoda los vértices en un pentágono regular. Colorea las aristas del perímetro de Rojo y las diagonales internas de Azul.

• La subgráfica Roja es un ciclo $C_5$, que no tiene triángulos ($K_3$).
• La subgráfica Azul también es un ciclo $C_5$ (formando un pentagrama), que no tiene triángulos. Como ya construiste una coloración con 2 colores de $K_5$ sin ninguna $K_3$ monocromática, $n=5$ no es suficiente. Por eso, $R(3, 3) > 5$.

Parte 2: Cota Superior ($R(3, 3) \le 6$) Considera una gráfica completa $K_6$ con las aristas coloreadas de Rojo o Azul. Lo que tienes que demostrar es que tiene una $K_3$ monocromática.

1. Elige un vértice arbitrario $v$ de la gráfica.
2. El vértice $v$ tiene 5 aristas incidentes que lo conectan con los otros 5 vértices.
3. Por el Principio de la Casilla, al menos $\lceil 5/2 \rceil = 3$ de estas aristas deben ser del mismo color. Sin perder generalidad, supón que $v$ tiene 3 aristas Rojas que lo conectan con sus vecinos $u_1, u_2$ y $u_3$.
4. Ahora, considera las aristas que forman el triángulo entre estos vecinos: $(u_1, u_2)$, $(u_2, u_3)$ y $(u_3, u_1)$.
5. Caso A: Si cualquiera de estas aristas es Roja (por ejemplo, si $(u_1, u_2)$ es Roja), entonces los vértices ${v, u_1, u_2}$ forman una $K_3$ Roja.
6. Caso B: Si ninguna de estas aristas es Roja, entonces las tres aristas $(u_1, u_2)$, $(u_2, u_3)$ y $(u_3, u_1)$ tienen que ser Azules. En este caso, los vértices ${u_1, u_2, u_3}$ forman una $K_3$ Azul.

En cualquier caso, existe un triángulo monocromático. Por lo tanto, $R(3, 3) \le 6$.

Al combinar la Parte 1 y la Parte 2, puedes concluir que $R(3, 3) = 6$. $\square$