De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Para la teoría de Ramsey de conjuntos infinitos, consulte Combinatoria infinita .

La teoría de Ramsey , que lleva el nombre del matemático y filósofo británico Frank P. Ramsey , es una rama de las matemáticas que se centra en la aparición del orden en una subestructura dada una estructura de tamaño conocido. Los problemas de la teoría de Ramsey suelen plantear una pregunta de la forma: "¿qué tamaño debe tener una subestructura 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]

Ejemplos [ editar ]

Un resultado típico en 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 una de las piezas tenga una propiedad interesante determinada? 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é tan grande debe ser n para asegurar 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 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 conocidos en común (cada uno conoce a los otros dos) o extraños en común (cada uno no conoce al otro). dos). Vea el 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.

Resultados [ editar ]

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

  • Van der teorema de Waerden : Para cualquier dado c y n , hay un número de V , de manera que 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 celdas de un cubo H -dimensional n × n × n × ... × n están coloreadas con c colores, debe haber una fila , columna, etc. de longitud n todas cuyas celdas son del mismo color. Es decir: un tic-tac-toe de n en una fila para varios jugadores no puede terminar en tablas, no importa cuán grande sea n , y no importa cuántas personas estén jugando, si juegas en un tablero con suficientes dimensiones. El teorema de Hales-Jewett implicaTeorema 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 sean del mismo color. Muchas generalizaciones de este teorema existen, incluyendo el teorema de Rado , teorema de Rado-Folkman-Sanders , el teorema de Hindman , y el teorema de Taylor-Milliken. 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 constructivas : pueden mostrar que existe alguna estructura, pero no proporcionan ningún proceso para encontrar esta estructura (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 contener necesariamente una estructura dada, 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 pueden mejorarse 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 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 las triples pitagóricas booleanas . [3]

Los teoremas de la teoría de Ramsey son generalmente de los dos tipos siguientes. Muchos de estos teoremas, que se modelan según el teorema de Ramsey mismo, afirman que en cada partición de un objeto estructurado grande, una de las clases contiene necesariamente un subobjeto estructurado grande, pero no dan 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 , según el teorema de Turán . Ejemplos notables incluyen el teorema de Szemerédi, que es un refuerzo del teorema de van der Waerden, y la versión de densidad del teorema de Hales-Jewett. [4]

Ver también [ editar ]

  • Teoría ergódica de Ramsey
  • Teoría de grafos extremos
  • Teorema de goodstein
  • Bartel Leendert van der Waerden
  • Teoría de la discrepancia

Notas [ editar ]

  1. ^ Graham, Ron; Mayordomo, Steve (2015). Rudimentos de la teoría de Ramsey (2ª ed.). Sociedad Matemática Estadounidense. pag. 1. ISBN 978-0-8218-4156-3.
  2. ^ Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H .; Solymosi, József (2015), Ramsey Theory (3.a ed.), Nueva York: John Wiley and Sons, ISBN 978-0470391853.
  3. ↑ Lamb, Evelyn (2 de junio de 2016). "La prueba matemática de doscientos terabytes es la más grande hasta ahora" . Naturaleza . 534 (7605): 17–18. doi : 10.1038 / nature.2016.19990 . PMID 27251254 . 
  4. ^ Furstenberg, Hillel ; Katznelson, Yitzhak (1991), "Una versión de densidad del teorema de Hales-Jewett", Journal d'Analyse Mathématique , 57 (1): 64-119, doi : 10.1007 / BF03041066.

Referencias [ editar ]

  • Landman, BM y Robertson, A. (2004), Teoría de Ramsey sobre los enteros , Biblioteca de matemáticas para estudiantes, 24 , Providence, RI: AMS, ISBN 0-8218-3199-2.
  • Ramsey, FP (1930), "On a Problem of Formal Logic", Proceedings of the London Mathematical Society , s2-30 (1): 264-286, doi : 10.1112 / plms / s2-30.1.264 (detrás de un muro de pago).
  • Erdös, P. & Szekeres, G. (1935), "Un problema combinatorio en geometría" , Compositio Mathematica , 2 : 463–470.
  • Boolos, G .; Burgess, JP; Jeffrey, R. (2007), Computability and Logic (5.a ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-87752-7.
  • Matthew Katz y Jan Reimann Introducción a la teoría de Ramsey: funciones rápidas, infinito y metamatemáticas Biblioteca de matemáticas para estudiantes Volumen: 87; 2018; 207 págs; ISBN 978-1-4704-4290-3