La teoría de Ramsey , llamada así en honor al 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 aparición de orden en una subestructura dada una estructura de tamaño conocido. Los problemas en la teoría de Ramsey suelen plantear una pregunta de la forma: "¿Qué tamaño debe tener una estructura para garantizar que se cumpla una propiedad particular?" [1]
Un resultado típico de la teoría de Ramsey comienza con alguna estructura matemática que luego se corta en pedazos. ¿Qué tamaño debe tener la estructura original para garantizar que al menos una de las piezas tenga una determinada propiedad interesante? Esta idea se puede definir como regularidad de partición .
Por ejemplo, considere una gráfica completa de orden n ; es decir, hay n vértices y cada vértice está conectado a todos los demás vértices por una arista. Una gráfica completa de orden 3 se llama triángulo. Ahora colorea cada borde de rojo o azul. ¿Qué tamaño debe tener n para garantizar que haya un triángulo azul o un triángulo rojo? Resulta que la respuesta es 6. Consulte el artículo sobre el teorema de Ramsey para obtener una demostración rigurosa .
Otra forma de expresar este resultado es la siguiente: en cualquier fiesta con al menos seis personas, hay tres personas que son todos conocidos mutuos (cada uno conoce a los otros dos) o desconocidos mutuos (ninguno de ellos conoce a ninguno de los otros dos). ). Ver teorema sobre amigos y extraños .
Este también es un caso especial del teorema de Ramsey, que dice que para cualquier entero c dado , cualquier entero dado n 1 ,..., n c , hay un número, R ( n 1 ,..., n c ), tal que si los bordes de un gráfico completo de orden R ( n 1 ,..., n c ) están coloreados con c colores diferentes, entonces para algún i entre 1 y c , debe contener un subgrafo completo de orden n i cuyo Los bordes son todos de color i . El caso especial anterior tiene c = 2 y n 1 = n 2 = 3.
Dos teoremas clave de la teoría de Ramsey son:
Un teorema similar al teorema de van der Waerden es el teorema de Schur : para cualquier c dado, existe 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 tal que x , y y x + y sean todos del mismo color. Existen muchas generalizaciones de este teorema, incluido 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 de la teoría de Ramsey es Graham, Rothschild, Spencer y Solymosi, actualizado y ampliado en 2015 a su primera edición nueva 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 proporcionan ningún proceso para encontrarla (aparte de la búsqueda por fuerza bruta ). Por ejemplo, el principio del casillero tiene esta forma. En segundo lugar, si bien los resultados de la teoría de Ramsey dicen que los objetos suficientemente grandes deben necesariamente contener una estructura determinada, a menudo la prueba de estos resultados requiere que estos objetos sean enormemente grandes: límites que crecen exponencialmente , o incluso tan rápido como la función de Ackermann, no son infrecuentes. En algunos casos de nichos pequeños, se mejoran los límites superior e inferior, 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 ; vea el teorema de Paris-Harrington como ejemplo. El número de Graham , uno de los números más grandes jamás utilizados en pruebas matemáticas serias, es un límite superior para un problema relacionado con la teoría de Ramsey. Otro gran ejemplo es el problema de los triples pitagóricos booleanos . [3]
Los teoremas de la teoría de Ramsey son generalmente uno de los dos tipos siguientes. Muchos de estos teoremas, que siguen el modelo 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 proporciona información sobre de qué clase se trata. 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 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]