Teoría ramsey

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 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 en particular?" Más específicamente, Ron Graham describió la teoría de Ramsey como una "rama de la combinatoria".

Ejemplos

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. Consulte el artículo sobre el teorema de Ramsey para obtener 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 conocidos mutuos (cada uno conoce a los otros dos) o extraños mutuos (ninguno de ellos conoce a ninguno de los dos). 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 número entero c, cualquier número entero n₁,...,n_c, hay un número, R(n₁,...,n_c), tal que si los bordes de un gráfico completo de orden R(n₁,...,n_c) están coloreadas con c colores diferentes, entonces para alguna i entre 1 y c, debe contener un subgrafo completo de orden n_i cuyas aristas son todas de color i. El caso especial anterior tiene c = 2 y n₁ = n₂ = 3.

Resultados

Dos teoremas clave de la teoría de Ramsey son:

• Teorema de Van der Waerden: Para cualquier c y n, hay un número V, tal si V números consecutivos se colorean con c diferentes colores, entonces debe contener una progresión aritmética de longitud n cuyos elementos son todos del mismo color.
• Teorema de Hales-Jewett: Para cualquier n y c, hay un número H tal que si las células de una H-dimensional n×n×n×n cubo son de color c colores, debe haber una fila, columna, etc. de longitud n todas sus células son del mismo color. Eso es: un multijugador n-en-a-row tic-tac-toe no puede terminar en un empate, no importa lo grande n es, y no importa cuánta gente esté jugando, si juegas en un tablero con bastantes dimensiones. El teorema Hales-Jewett implica Teorema de Van der Waerden.

Un teorema similar al teorema 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 enteros x , y tal 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.

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 casillero tiene esta forma. En segundo lugar, si bien los resultados de la teoría de Ramsey 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: los límites que crecen exponencialmente, o incluso tan rápido como la función de Ackermann, no son infrecuentes. En algunos casos de nicho pequeño, 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; consulte el teorema de París-Harrington para ver un 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.

Los teoremas en 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 gran objeto estructurado, 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 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, por el teorema de Turán. Los 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.