La teoría de Ramsey , llamada así por el matemático y filósofo británico Frank P. Ramsey , es una rama de las matemáticas que se centra en la aparición de orden en una subestructura dada una estructura de un tamaño conocido. Los problemas en la teoría de Ramsey generalmente plantean una pregunta de la forma: "¿qué tan grande debe ser una estructura para garantizar que se mantenga una propiedad particular?" Más específicamente, Ron Graham describió la teoría de Ramsey como una "rama de la combinatoria ". [1]
Un resultado típico en 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 asegurar que al menos una de las piezas tenga una propiedad interesante dada? Esta idea se puede definir como regularidad de partición .
Por ejemplo, considere un gráfico completo 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é tan grande debe ser n para asegurar que haya un triángulo azul o un triángulo rojo? Resulta que la respuesta es 6. Ver 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 todos conocidos mutuos (cada uno conoce a los otros dos) o extraños mutuos (ninguno de ellos conoce a 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 dado c , cualquier entero dado 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 cuyo los bordes son todos de color i. El caso especial anterior tiene c = 2 y n 1 = n 2 = 3.
Un teorema similar al teorema de van der Waerden es el teorema de Schur : para cualquier c 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 tales que x , y y x + y son 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 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]