La teoría de Ramsey , llamada así por el matemático y filósofo británico Frank P. Ramsey , es una rama del campo matemático de la combinatoria que se centra en la apariencia de orden en una subestructura dada una estructura de un tamaño conocido. Los problemas de la teoría de Ramsey suelen plantear una pregunta de la forma: "¿qué tan grande debe ser una estructura para garantizar que se mantenga una propiedad particular?" [1]
Un resultado típico de la teoría de Ramsey comienza con una estructura matemática que luego se corta en pedazos. ¿Qué tamaño debe tener la estructura original para garantizar que al menos uno de los pedazos tenga una propiedad interesante determinada? Esta idea se puede definir como regularidad de partición .
Por ejemplo, considere un grafo completo de orden n ; es decir, hay n vértices y cada vértice está conectado a cada uno de los otros vértices por una arista. Un grafo completo de orden 3 se llama triángulo. Ahora coloree cada arista de rojo o azul. ¿Qué tan grande debe ser n para garantizar que haya un triángulo azul o un triángulo rojo? Resulta que la respuesta es 6. Vea el artículo sobre el teorema de Ramsey para una prueba rigurosa .
Otra forma de expresar este resultado es la siguiente: en cualquier fiesta con al menos seis personas, hay tres personas que son o bien conocidos mutuos (cada uno conoce a los otros dos) o bien desconocidos mutuos (ninguno de ellos conoce a ninguno de los otros dos). Véase el teorema sobre amigos y desconocidos .
Este también es un caso especial del teorema de Ramsey, que dice que para cualquier entero dado c , cualesquiera enteros dados n 1 ,..., n c , hay un número, R ( n 1 ,..., n c ), tal que si las aristas de un grafo completo de orden R ( n 1 ,..., n c ) están coloreadas con c colores diferentes, entonces para algún i entre 1 y c , debe contener un subgrafo completo de orden n i cuyas aristas sean todas de color i . El caso especial anterior tiene c = 2 y n 1 = n 2 = 3.
Dos teoremas claves de la teoría de Ramsey son:
Un teorema similar al de van der Waerden es el teorema de Schur : para cualquier c dado hay un número N tal que si los números 1, 2, ..., N están coloreados con c colores diferentes, entonces debe haber un par de números enteros x , y tales que x , y y x + y sean todos del mismo color. Existen muchas generalizaciones de este teorema, incluyendo el teorema de Rado , el teorema de Rado–Folkman–Sanders , el teorema de Hindman y el teorema de Milliken–Taylor . Una referencia clásica para estos y muchos otros resultados en la teoría de Ramsey es Graham, Rothschild, Spencer y Solymosi, actualizado y ampliado en 2015 a su primera nueva edición en 25 años. [2]
Los resultados de la teoría de Ramsey suelen tener dos características principales. En primer lugar, no son constructivos : pueden mostrar que existe alguna estructura, pero no dan ningún proceso para encontrar esta estructura (aparte de la búsqueda de fuerza bruta ). Por ejemplo, el principio del palomar es de esta forma. En segundo lugar, si bien los resultados de la teoría de Ramsey sí dicen que los objetos suficientemente grandes deben contener necesariamente una estructura dada, a menudo la prueba de estos resultados requiere que estos objetos sean enormemente grandes: no son infrecuentes los límites que crecen exponencialmente , o incluso tan rápido como la función de Ackermann . En algunos casos de nichos pequeños, los límites superior e inferior se mejoran, pero no en general. En muchos casos, estos límites son artefactos de la prueba, y no se sabe si se pueden mejorar sustancialmente. En otros casos, se sabe que cualquier límite debe ser extraordinariamente grande, a veces incluso mayor que cualquier función recursiva primitiva ; véase el teorema de París-Harrington como ejemplo. El número de Graham , uno de los números más grandes jamás utilizados en una prueba matemática seria, es un límite superior para un problema relacionado con la teoría de Ramsey. Otro gran ejemplo es el problema de las ternas pitagóricas de Boole . [3]
Los teoremas de la teoría de Ramsey son generalmente de uno de los dos tipos siguientes. Muchos de estos teoremas, que se modelan a partir del propio teorema de Ramsey, afirman que en cada partición de un objeto estructurado grande, una de las clases contiene necesariamente su propio objeto estructurado, pero no da información sobre qué clase es. En otros casos, la razón detrás de un resultado de tipo Ramsey es que la clase de partición más grande siempre contiene la subestructura deseada. Los resultados de este último tipo se denominan resultados de densidad o resultado de tipo Turán , en honor al teorema de Turán . Ejemplos notables incluyen el teorema de Szemerédi , que es un fortalecimiento del teorema de van der Waerden, y la versión de densidad del teorema de Hales-Jewett. [4]