La teoría de Ramsey es una rama de las matemáticas que estudia las condiciones bajo las cuales debe aparecer algún orden en objetos matemáticos arbitrariamente formados. El nombre de Frank Ramsey .
Los problemas en la teoría de Ramsey generalmente toman la forma de la pregunta "¿cuántos elementos debe haber en algún objeto para garantizar que se satisfaga una condición dada o que exista una estructura dada". El ejemplo más simple:
Supongamos, por ejemplo, que sabemos que los conejos están colocados en jaulas. ¿Qué tamaño tiene que tener para garantizar que haya al menos 2 conejos en una de las jaulas? De acuerdo con el principio de Dirichlet , si , entonces hay una celda que contiene al menos 2 conejos. La teoría de Ramsey generaliza este principio [1] .
El propio Ramsey demostró el siguiente teorema:
Que se den números . Entonces hay un número tal que, no importa cómo coloreemos los bordes del gráfico completo en los vértices en colores, hay un subgráfico completo del primer color en los vértices, o un subgráfico completo del segundo color en los vértices . , ... o un subgrafo completo del th color en los vértices . [2] |
También fue generalizado por él para el caso de una hipergrafía .
El número mínimo para el cual, para un conjunto dado de argumentos , existe la coloración especificada en el teorema se llama número de Ramsey. Los valores de los números de Ramsey son conocidos por un número muy pequeño de conjuntos de argumentos.
El teorema de van der Waerden es similar en formulación pero difiere en demostración.
Para cualquier conjunto de números, hay un número tal que, sin importar cómo coloreemos los primeros números naturales en colores, hay una progresión aritmética del primer color de longitud , o una progresión aritmética del segundo color de longitud , . .., o una progresión aritmética del th color de longitud . [3] |
El número más pequeño de este tipo se llama número de van der Waerden .
En lugar de un conjunto de números naturales, podemos considerar una red y progresiones aritméticas: figuras en él, homotéticas a la dada, y la declaración del teorema sigue siendo verdadera (teorema generalizado de van der Waerden).
Para cualquier número y es posible encontrar un número tal que si las celdas de un cubo bidimensional con un lado de longitud están coloreadas en colores, entonces hay al menos una línea (filas, columnas, algunas diagonales se consideran líneas) desde celdas de un solo color. [cuatro] |
De este teorema se deduce que al jugar tres en raya multidimensional para cualquier longitud de la línea y cualquier número de jugadores, puede encontrar tal número de dimensiones que un empate será imposible.
Para cualquier natural , cualquier conjunto suficientemente grande de puntos en una posición general en el plano tiene un subconjunto de puntos que son vértices de un polígono convexo. [5] |
De acuerdo con la conjetura de Erdős y Székeres sobre polígonos convexos, el número de puntos en posición general en los que necesariamente existe un -gon convexo está dado por
para todos También demostraron que un -gon convexo puede no existir en un conjunto con un número menor de puntos.
Para cualquier coloración de enteros grandes en colores, existe un subconjunto monocromático finito de enteros tal que En este caso, el elemento máximo, y por tanto el tamaño del conjunto , está limitado por una función exponencial de base constante. |
Esta conjetura de Erdős-Graham fue probada por Ernest Krut en 2003 .
Los resultados dentro del marco de la teoría de Ramsey se caracterizan por dos propiedades. En primer lugar, no son constructivos. Se prueba que existe alguna estructura, pero no se propone otra forma de construirla que no sea la enumeración directa. En segundo lugar, para que existan las estructuras deseadas, se requiere que los objetos que las contienen estén compuestos por una gran cantidad de elementos. La dependencia del número de elementos de un objeto del tamaño de la estructura suele ser al menos exponencial.