Teoría ramsey

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:

Demuestre que en cualquier grupo de 6 personas hay 3 personas que se conocen o 3 personas que no se conocen en parejas.

Resultados clásicos

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] . $norte$ $metro$ $norte$ $n>m$

Teorema de Ramsey

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] ${\displaystyle a_{1},\,a_{2},\,\ldots,\,a_{n))$ $R$ $R$ $norte$ $un_{1}$ $un_{2}$ $norte$ $un$

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. $R$ ${\displaystyle a_{1},\,a_{2},\,\ldots,\,a_{n))$

Teorema de van der Waerden

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] ${\displaystyle a_{1},\,a_{2},\,\ldots,\,a_{n))$ $W$ $W$ $norte$ $un_{1}$ $un_{2}$ $norte$ $un$

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). ${\matemáticas Z}^{n}$

El teorema de Hales-Jewett

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] $norte$ $C$ $H$ $H$ $norte$ $C$ $norte$

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.

La conjetura de Erdős-Székeres Conjetura del polígono convexo

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] $norte$ $norte$

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 $norte$

{\ estilo de visualización f (N) = 1 + 2 ^ {N-2))

para todos También demostraron que un -gon convexo puede no existir en un conjunto con un número menor de puntos. $norte$ $norte$

Teorema de la fracción egipcia monocromática de Kroot

Para cualquier coloración de enteros grandes en colores, existe un subconjunto monocromático finito de enteros tal que $una$ $r>0$ $S$

{\ estilo de visualización \ suma _ {n \ en S} 1/n = 1.}

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. $S$ $r$

Esta conjetura de Erdős-Graham fue probada por Ernest Krut en 2003 .

Características de la teoría

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.

Notas

↑ Revisión de resultados hasta 1990: Graham, R .; Rothschild, B. & Spencer, JH (1990), Teoría de Ramsey (2ª ed.), Nueva York: John Wiley and Sons, ISBN 0-471-50046-1 .
↑ Ramsey, FP Sobre un problema de lógica formal // Proc . Matemáticas de Londres. soc. Serie 2. - 1930. - Vol. 30 . - pág. 264-286 . -doi : 10.1112 / plms/s2-30.1.264 .
↑ van der Waerden, B. L. Beweis einer Baudetschen Vermutung (alemán) // Nieuw. Arco. Wisk.. - 1927. - Bd. 15 _ - S. 212-216 .
↑ Hales A., Jewett R. Regularidad y juegos posicionales (ing.) // Trans. amer Matemáticas. Soc.. - 1963. - Vol. 106 . - pág. 222-229 . -doi : 10.2307/ 1993764 . Archivado desde el original el 19 de enero de 2022.
↑ Erdős, P. & Szekeres, G. (1935), Un problema combinatorio en geometría , Compositio Math Vol. 2: 463-470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > Archivado desde febrero 19, 2019 en la Wayback Machine .

Literatura

Martín Gardner . Capítulo 17. Teoría de Ramsey // De Penrose Tiles a Cifrados Fuertes = Penrose Tiles a Trapdoor Ciphers De inglés. Yu. A. Danilova. - M .: Mir , 1993. - S. 288-308. — 416 pág. — 10.000 copias. — ISBN 5-03-001991-X .

Enlaces

teoría ramsey