Teorema de Ramsey en combinatoria: enunciado, R(3,3) = 6 y ejemplos
Actualizado el
El teorema de Ramsey dice que en cualquier estructura lo bastante grande aparece necesariamente orden. En su forma más conocida: si se colorean de rojo o azul todas las aristas de un grafo completo con suficientes vértices, siempre habrá un grupo de vértices unidos todos entre sí por aristas del mismo color. El ejemplo clásico es el «problema de la fiesta»: entre 6 personas cualesquiera, siempre hay 3 que se conocen entre sí o 3 que no se conocen entre sí.
La teoría de Ramsey es la rama de la combinatoria que estudia este tipo de resultados.
Enunciado
Un grafo completo Kn tiene n vértices y una arista entre cada par de ellos, en total n(n − 1)/2 aristas.
Teorema de Ramsey (dos colores). Para cualesquiera enteros s, t ≥ 2 existe un número R(s, t) tal que, si n ≥ R(s, t) y se colorea cada arista de Kn de rojo o de azul, hay un Ks con todas sus aristas rojas o un Kt con todas sus aristas azules. R(s, t) es el menor número con esta propiedad y se llama número de Ramsey.
El teorema se generaliza a cualquier número finito de colores y a colorear subconjuntos de k elementos en lugar de aristas (pares). También hay una versión infinita: si se colorean con un número finito de colores las aristas del grafo completo con infinitos vértices, existe un subconjunto infinito de vértices con todas sus aristas del mismo color.
El problema de la fiesta: R(3, 3) = 6
Con 6 personas siempre hay un triángulo de un color
Coloreamos de rojo las parejas que se conocen y de azul las que no. Tomamos una persona A. Tiene 5 aristas, así que, por el principio del palomar, al menos 3 son del mismo color; digamos rojas, hacia B, C y D.
- Si alguna de las aristas BC, BD o CD es roja, junto con A forma un triángulo rojo.
- Si ninguna lo es, BC, BD y CD son las tres azules: triángulo azul.
En cualquier caso hay un triángulo monocromático, así que R(3, 3) ≤ 6.
Con 5 personas puede no haberlo
Se colocan 5 vértices en un pentágono. Se pintan de rojo los 5 lados y de azul las 5 diagonales. Los lados forman un ciclo de 5, sin triángulos; las diagonales forman un pentagrama, que también es un ciclo de 5, sin triángulos. Por tanto R(3, 3) > 5, y queda R(3, 3) = 6.
Comprobación por ordenador: K6 tiene 15 aristas y 215 = 32.768 coloreados posibles con dos colores. Al revisarlos todos, ninguno queda sin triángulo monocromático. La coloración del pentágono, en cambio, no tiene ninguno.
Números de Ramsey conocidos
| R(s, t) | Valor |
|---|---|
| R(3, 3) | 6 |
| R(3, 4) | 9 |
| R(3, 5) | 14 |
| R(4, 4) | 18 |
| R(5, 5) | Desconocido: entre 43 y 46 |
La cota inferior 43 para R(5, 5) es de Geoffrey Exoo (1989); la superior, 46, de Angeltveit y McKay (2024). Calcular números de Ramsey exactos es muy difícil porque el número de coloreados crece como 2 elevado al número de aristas: K43 tiene 903 aristas.
Casos triviales: R(2, t) = t, porque en Kt, o hay una arista roja (un K2 rojo) o todas son azules. Además, R(s, t) = R(t, s), intercambiando los colores.
Demostración del teorema: la cota recursiva
La existencia de R(s, t) se demuestra por inducción con la desigualdad
R(s, t) ≤ R(s − 1, t) + R(s, t − 1)
Idea: sea n = R(s − 1, t) + R(s, t − 1) y elijamos un vértice v de Kn. Sus n − 1 vecinos se reparten en los unidos a v en rojo (conjunto M) y en azul (conjunto N). Como |M| + |N| = n − 1, o |M| ≥ R(s − 1, t) o |N| ≥ R(s, t − 1). En el primer caso, dentro de M hay un Kt azul (y hemos terminado) o un Ks−1 rojo, que con v forma un Ks rojo. El segundo caso es simétrico.
De la desigualdad se deduce R(s, t) ≤ C(s + t − 2, s − 1), un número combinatorio. Para (3, 3) da C(4, 2) = 6, el valor exacto; para (4, 4), C(6, 3) = 20, mientras que el valor real es 18.
Cómo crecen: cotas de Erdős
Para los números diagonales R(k, k), la cota anterior da un crecimiento como mucho del orden de 4k. En 1947 Paul Erdős demostró con el método probabilístico que crecen al menos como (√2)k: eligiendo los colores al azar, si n es menor que unas 2k/2, la probabilidad de que haya un Kk monocromático es menor que 1, así que existe un coloreado sin él. Erdős demostró la existencia de ese coloreado sin construirlo. En 2023 Campos, Griffiths, Morris y Sahasrabudhe presentaron una mejora exponencial de la cota superior, de la forma (4 − ε)k.
Ejemplos y aplicaciones
- Problemas de olimpiada: demostrar que R(3, 3) ≤ 6 apareció en la Olimpiada Matemática de Hungría de 1947 y en el concurso Putnam de 1953.
- Teoría de números: el teorema de Schur (en cualquier coloración de 1, 2, …, N con N suficientemente grande hay x, y, z del mismo color con x + y = z) se deduce del de Ramsey.
- Lógica: una variante, el principio de Paris-Harrington, fue uno de los primeros enunciados «naturales» que no se pueden demostrar en la aritmética de Peano, en la línea de los teoremas de incompletitud de Gödel.
- Informática teórica: se usa en cotas inferiores de complejidad y en el estudio de redes de comunicación.
Errores habituales
- Pensar que R(s, t) se cumple con exactamente R(s, t) − 1 vértices. Con un vértice menos siempre existe algún coloreado que evita los dos subgrafos.
- Confundir «hay un triángulo de un color» con «hay un triángulo de cada color». El teorema solo garantiza uno de los dos.
- Creer que la fórmula combinatoria da el número exacto. Es solo una cota superior.
Historia
Frank Ramsey publicó el resultado en 1930 en el artículo «On a problem of formal logic», en Proceedings of the London Mathematical Society. Lo necesitaba para un problema de lógica; la combinatoria que lleva su nombre se desarrolló después, en gran parte por Erdős y sus colaboradores. Para situar este resultado entre otros de la misma rama, puedes ver la lista de teoremas más importantes de las matemáticas; los grafos coloreados se representan a menudo con conjuntos, y ahí entran los diagramas de Venn y de Euler.
Preguntas frecuentes
¿Qué dice el teorema de Ramsey?
Que si se colorean de dos colores las aristas de un grafo completo con suficientes vértices, siempre aparece un subgrafo completo de un tamaño dado con todas sus aristas del mismo color.
¿Por qué R(3,3) = 6?
Con 6 vértices siempre hay un triángulo de un color (por el principio del palomar). Con 5 no: el pentágono con lados rojos y diagonales azules no tiene ninguno.
¿Se conoce R(5,5)?
No. Se sabe que está entre 43 y 46; la cota superior 46 es de 2024.
¿Qué es la teoría de Ramsey?
La parte de la combinatoria que estudia cuándo una estructura grande contiene obligatoriamente una subestructura ordenada, como un subgrafo monocromático.
RELACIONADOS