Teorema de Ramsey

En combinatoria , el teorema de Ramsey , en una de sus formas de teoría de grafos , establece que se encontrarán camarillas monocromáticas en cualquier etiquetado de aristas (con colores) de un grafo completo suficientemente grande . Para demostrar el teorema para dos colores (por ejemplo, azul y rojo), sean r y s dos enteros positivos cualesquiera . ^[a] El teorema de Ramsey establece que existe un entero positivo mínimo R ( r , s ) para el cual cada coloración azul-roja de las aristas del grafo completo en R ( r , s ) vértices contiene una camarilla azul en r vértices o una camarilla roja en s vértices. (Aquí R ( r , s ) significa un entero que depende tanto de r como de s ).

El teorema de Ramsey es un resultado fundacional de la combinatoria. La primera versión de este resultado fue demostrada por Frank Ramsey . Con ello se inició la teoría combinatoria hoy llamada teoría de Ramsey , que busca la regularidad en medio del desorden: condiciones generales para la existencia de subestructuras con propiedades regulares. En esta aplicación se trata de la existencia de subconjuntos monocromáticos , es decir, subconjuntos de aristas conexas de un solo color.

Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de solo dos. Más precisamente, el teorema establece que para cualquier número dado de colores, c , y cualquier entero dado n ₁ , …, n _c , hay un número, R ( n ₁ , …, n _c ) , tal que si las aristas de un grafo completo de orden R ( n ₁ , …, 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 cuyas aristas sean todas de color i . El caso especial anterior tiene c = 2 (y n ₁ = r y n ₂ = s ).

Supongamos que las aristas de un grafo completo en 6 vértices están coloreadas de rojo y azul. Elija un vértice, v . Hay 5 aristas incidentes a v y entonces (por el principio del palomar ) al menos 3 de ellas deben ser del mismo color. Sin pérdida de generalidad podemos suponer que al menos 3 de estas aristas, que conectan el vértice, v , a los vértices, r , s y t , son azules. (Si no, intercambiemos rojo y azul en lo que sigue.) Si alguna de las aristas, ( rs ) , ( rt ) , ( st ) , también es azul, entonces tenemos un triángulo completamente azul. Si no, entonces esas tres aristas son todas rojas y tenemos un triángulo completamente rojo. Dado que este argumento funciona para cualquier coloración, cualquier K _{6 contiene un} K ₃ monocromático y, por lo tanto, R (3, 3) ≤ 6 . La versión popular de esto se llama el teorema de amigos y extraños .

Una prueba alternativa funciona contando dos veces . Es como sigue: Cuenta el número de triples ordenados de vértices, x , y , z , tales que la arista, ( xy ) , es roja y la arista, ( yz ) , es azul. En primer lugar, cualquier vértice dado será el medio de 0 × 5 = 0 (todas las aristas del vértice son del mismo color), 1 × 4 = 4 (cuatro son del mismo color, una es del otro color), o 2 × 3 = 6 (tres son del mismo color, dos son del otro color) de tales triples. Por lo tanto, hay como máximo 6 × 6 = 36 de tales triples. En segundo lugar, para cualquier triángulo no monocromático ( xyz ) , existen precisamente dos de tales triples. Por lo tanto, hay como máximo 18 triángulos no monocromáticos. Por lo tanto, al menos 2 de los 20 triángulos en el K ₆ son monocromáticos.

Por el contrario, es posible bicolorizar un K ₅ sin crear ningún K ₃ monocromático , lo que demuestra que R (3, 3) > 5 . La coloración única ^[b] se muestra a la derecha. Por lo tanto, R (3, 3) = 6 .

La tarea de demostrar que R (3, 3) ≤ 6 fue uno de los problemas de la Competición Matemática William Lowell Putnam en 1953, así como de la Olimpiada Húngara de Matemáticas en 1947.

Un número de Ramsey multicolor es un número de Ramsey que utiliza 3 o más colores. Existen (salvo simetrías) solo dos números de Ramsey multicolor no triviales para los que se conoce el valor exacto, a saber, R (3, 3, 3) = 17 y R (3, 3, 4) = 30. [ ^1]

Supongamos que tenemos una coloración de aristas de un grafo completo usando 3 colores, rojo, verde y azul. Supongamos además que la coloración de aristas no tiene triángulos monocromáticos. Seleccione un vértice v . Considere el conjunto de vértices que tienen una arista roja en el vértice v . Esto se llama el vecindario rojo de v . El vecindario rojo de v no puede contener ninguna arista roja, ya que de lo contrario habría un triángulo rojo que constaría de los dos puntos finales de esa arista roja y el vértice v . Por lo tanto, la coloración de aristas inducida en el vecindario rojo de v tiene aristas coloreadas con solo dos colores, a saber, verde y azul. Dado que R (3, 3) = 6 , el vecindario rojo de v puede contener como máximo 5 vértices. De manera similar, los vecindarios verde y azul de v pueden contener como máximo 5 vértices cada uno. Como cada vértice, excepto v , se encuentra en uno de los vecindarios rojo, verde o azul de v , el grafo completo puede tener como máximo 1 + 5 + 5 + 5 = 16 vértices. Por lo tanto, tenemos R (3, 3, 3) ≤ 17 .

Para ver que R (3, 3, 3) = 17 , basta con dibujar una coloración de aristas en el grafo completo sobre 16 vértices con 3 colores que evite los triángulos monocromáticos. Resulta que hay exactamente dos coloraciones de este tipo en K ₁₆ , las llamadas coloraciones no torcidas y torcidas. Ambas coloraciones se muestran en las figuras de la derecha, con la coloración no torcida a la izquierda y la coloración torcida a la derecha.

Si seleccionamos cualquier color, ya sea del color sin torcer o torcido, en K ₁₆ y consideramos el gráfico cuyos bordes son precisamente aquellos que tienen el color especificado, obtendremos el gráfico de Clebsch .

Se sabe que hay exactamente dos coloraciones de aristas con 3 colores en K ₁₅ que evitan triángulos monocromáticos, que pueden construirse eliminando cualquier vértice de las coloraciones sin torcer y torcer en K ₁₆ , respectivamente.

También se sabe que hay exactamente 115 coloraciones de aristas con 3 colores en K ₁₄ que evitan los triángulos monocromáticos, siempre que consideremos como iguales las coloraciones de aristas que difieren por una permutación de los colores.

El teorema para el caso de 2 colores se puede demostrar por inducción en r + s . ^[2] De la definición se desprende claramente que para todo n , R ( n , 2) = R (2, n ) = n . Esto inicia la inducción. Demostramos que R ( r , s ) existe hallando un límite explícito para él. Por la hipótesis inductiva, R ( r − 1, s ) y R ( r , s − 1) existen.

Lema 1. ${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1).}$

Demostración. Consideremos un grafo completo de R ( r − 1, s ) + R ( r , s − 1) vértices cuyas aristas están coloreadas con dos colores. Elijamos un vértice v del grafo y partamos los vértices restantes en dos conjuntos M y N , de modo que para cada vértice w , w esté en M si la arista ( vw ) es azul, y w esté en N si ( vw ) es rojo. Como el grafo tiene vértices, se sigue que o bien En el primer caso, si M tiene una K _s roja , entonces también la tiene el grafo original y hemos terminado. De lo contrario, M tiene una K _{r − 1} azul y, por lo tanto, tiene una K _r azul según la definición de M . El último caso es análogo. Por lo tanto, la afirmación es verdadera y hemos completado la demostración para 2 colores.${\displaystyle R(r-1,s)+R(r,s-1)=|M|+|N|+1}$${\displaystyle |M|\geq R(r-1,s)}$${\displaystyle |N|\geq R(r,s-1).}$${\displaystyle M\cup \{v\}}$

En este caso de 2 colores, si R ( r − 1, s ) y R ( r , s − 1) son ambos pares, la desigualdad de inducción se puede fortalecer a: ^[3]

${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)-1.}$

Demostración . Supóngase que p = R ( r − 1, s ) y q = R ( r , s − 1) son ambos pares. Sea t = p + q − 1 y considérese un grafo bicolor de t vértices. Si d _i es el grado del i -ésimo vértice en el subgrafo azul, entonces, por el lema del apretón de manos , es par. Dado que t es impar, debe haber un d _i par . Supóngase sin pérdida de generalidad que d ₁ es par, y que M y N son los vértices incidentes al vértice 1 en los subgrafos azul y rojo, respectivamente. Entonces, tanto y son pares. Por el principio del Pigeonhole , o bien o bien Como es par y p – 1 es impar, la primera desigualdad se puede fortalecer, por lo que o bien o bien Supongamos Entonces, o bien el subgrafo M tiene un K _s rojo y la prueba está completa, o bien tiene un K _{r – 1} azul que junto con el vértice 1 forma un K _r azul . El caso se trata de manera similar.${\displaystyle \textstyle \suma _{i=1}^{t}d_{i}}$${\displaystyle |M|=d_{1}}$${\displaystyle |N|=t-1-d_{1}}$${\displaystyle |M|\geq p-1,}$${\displaystyle |N|\geq q.}$${\estilo de visualización |M|}$${\displaystyle |M|\geq p}$${\displaystyle |N|\geq q.}$${\displaystyle |M|\geq p=R(r-1,s).}$${\displaystyle |N|\geq q=R(r,s-1)}$

Lema 2. Si c > 2 , entonces${\displaystyle R(n_{1},\dots ,n_{c})\leq R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})).}$

Prueba. Consideremos un grafo completo de vértices y coloreemos sus aristas con c colores. Ahora 'volvámonos daltónicos' e imaginemos que c − 1 y c son del mismo color. Por lo tanto, el grafo ahora está ( c − 1) -coloreado. Debido a que la definición de tal grafo contiene o bien un K _{n i} coloreado monocromáticamente con el color i para algún 1 ≤ i ≤ c − 2 o un K _{R ( n c − 1 , n c )} -coloreado en el 'color borroso'. En el primer caso hemos terminado. En el segundo caso, recuperamos la vista de nuevo y vemos que a partir de la definición de R ( n _{c − 1} , n _c ) debemos tener o bien un ( c − 1) -monocromático K _{n c − 1} o un c -monocromo K _{n c} . En cualquier caso, la prueba está completa.${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c}))}$${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})),}$

El lema 1 implica que cualquier R ( r , s ) es finito. El lado derecho de la desigualdad del lema 2 expresa un número de Ramsey para c colores en términos de números de Ramsey para menos colores. Por lo tanto, cualquier R ( n ₁ , …, n _c ) es finito para cualquier número de colores. Esto demuestra el teorema.

Los números R ( r , s ) en el teorema de Ramsey (y sus extensiones a más de dos colores) se conocen como números de Ramsey. El número de Ramsey R ( m , n ) da la solución al problema de la fiesta, que pregunta el número mínimo de invitados, R ( m , n ) , que deben ser invitados para que al menos m se conozcan entre sí o al menos n no se conozcan entre sí. En el lenguaje de la teoría de grafos, el número de Ramsey es el número mínimo de vértices, v = R ( m , n ) , tales que todos los grafos simples no dirigidos de orden v , contienen una camarilla de orden m , o un conjunto independiente de orden n . El teorema de Ramsey establece que tal número existe para todos los m y n .

Por simetría, es cierto que R ( m , n ) = R ( n , m ) . Se puede extraer un límite superior para R ( r , s ) de la prueba del teorema, y ​​otros argumentos dan límites inferiores. (El primer límite inferior exponencial fue obtenido por Paul Erdős utilizando el método probabilístico .) Sin embargo, hay una gran brecha entre los límites inferiores más estrictos y los límites superiores más estrictos. También hay muy pocos números r y s para los que conocemos el valor exacto de R ( r , s ) .

Calcular un límite inferior L para R ( r , s ) generalmente requiere exhibir una coloración azul/roja del grafo K _{L −1} sin ningún subgrafo azul K _r y ningún subgrafo rojo K _s . Un contraejemplo de este tipo se llama grafo de Ramsey . Brendan McKay mantiene una lista de grafos de Ramsey conocidos. ^[4] Los límites superiores suelen ser considerablemente más difíciles de establecer: uno tiene que verificar todas las coloraciones posibles para confirmar la ausencia de un contraejemplo, o presentar un argumento matemático para su ausencia.

Erdős nos pide que imaginemos una fuerza alienígena, mucho más poderosa que nosotros, que aterriza en la Tierra y exige el valor de R (5, 5) o destruirá nuestro planeta. En ese caso, afirma, deberíamos reunir a todos nuestros ordenadores y a todos nuestros matemáticos e intentar encontrar el valor. Pero supongamos, en cambio, que piden R (6, 6) . En ese caso, cree, deberíamos intentar destruir a los alienígenas. ^[5]

—Joel  Spencer

Un programa informático sofisticado no necesita examinar todos los colores individualmente para eliminarlos todos; sin embargo, es una tarea computacional muy difícil que el software existente solo puede manejar en tamaños pequeños. Cada grafo completo K _n tiene1/2n ( n − 1) aristas, por lo que habría un total de c ^{n ( n -1)/2 grafos} para buscar (para c colores) si se utiliza la fuerza bruta. ^[6] Por lo tanto, la complejidad para buscar todos los grafos posibles (mediante fuerza bruta ) es O ( c ^{n 2} ) para c coloraciones y como máximo n nodos.

Es poco probable que la situación mejore con la llegada de las computadoras cuánticas . Uno de los algoritmos de búsqueda más conocidos para conjuntos de datos no estructurados muestra solo una aceleración cuadrática (cf. el algoritmo de Grover ) en relación con las computadoras clásicas, de modo que el tiempo de cálculo sigue siendo exponencial en el número de nodos. ^{[7] [8]}

Como se describió anteriormente, R (3, 3) = 6 . Es fácil demostrar que R (4, 2) = 4 , y, más generalmente, que R ( s , 2) = s para todo s : un grafo en s − 1 nodos con todas las aristas coloreadas de rojo sirve como contraejemplo y demuestra que R ( s , 2) ≥ s ; entre las coloraciones de un grafo en s nodos, la coloración con todas las aristas coloreadas de rojo contiene un subgrafo rojo de s nodos, y todas las demás coloraciones contienen un subgrafo azul de 2 nodos (es decir, un par de nodos conectados con una arista azul).

Usando desigualdades de inducción y el lema del apretón de manos , se puede concluir que R (4, 3) ≤ R (4, 2) + R (3, 3) − 1 = 9 , y por lo tanto R (4, 4) ≤ R (4, 3) + R (3, 4) ≤ 18 . Solo hay dos grafos (4, 4, 16) (es decir, 2-coloraciones de un grafo completo en 16 nodos sin subgrafos completos rojos o azules de 4 nodos) entre 6,4 × 10 ²² 2-coloraciones diferentes de grafos de 16 nodos, y solo un grafo (4, 4, 17) (el grafo de Paley de orden 17) entre 2,46 × 10 ²⁶ coloraciones. ^[4] (De ello se deduce que R (4, 4) = 18 .

El hecho de que R (4, 5) = 25 fue establecido por primera vez por Brendan McKay y Stanisław Radziszowski en 1995. ^[9]

Se desconoce el valor exacto de R (5, 5) , aunque se sabe que está entre 43 (Geoffrey Exoo (1989) ^[10] ) y 46 (Angeltveit y McKay (2024) ^[11] ), inclusive.

En 1997, McKay, Radziszowski y Exoo emplearon métodos de generación de grafos asistidos por computadora para conjeturar que R (5, 5) = 43. Pudieron construir exactamente 656 grafos (5, 5, 42) , llegando al mismo conjunto de grafos a través de diferentes rutas. Ninguno de los 656 grafos puede extenderse a un grafo (5, 5, 43) . ^[12]

Para R ( r , s ) con r , s > 5 , solo hay límites débiles disponibles. Los límites inferiores para R (6, 6) y R (8, 8) no se han mejorado desde 1965 y 1972, respectivamente. ^[1]

R ( r , s ) con r , s ≤ 10 se muestran en la tabla siguiente. Cuando se desconoce el valor exacto, la tabla enumera los límites más conocidos. R ( r , s ) con r < 3 se dan por R (1, s ) = 1 y R (2, s ) = s para todos los valores de s .

La encuesta estándar sobre el desarrollo de la investigación del número de Ramsey es la Encuesta dinámica 1 del Electronic Journal of Combinatorics , de Stanisław Radziszowski , que se actualiza periódicamente. ^{[1] [13]} A menos que se cite lo contrario, las entradas en la tabla siguiente se toman de la edición de junio de 2024. (Tenga en cuenta que hay una simetría trivial en la diagonal ya que R ( r , s ) = R ( s , r ) .)

La desigualdad R ( r , s ) ≤ R ( r − 1, s ) + R ( r , s − 1) puede aplicarse inductivamente para demostrar que

${\displaystyle R(r,s)\leq {\binom {r+s-2}{r-1}}.}$

En particular, este resultado, debido a Erdős y Szekeres , implica que cuando r = s ,

${\displaystyle R(s,s)\leq (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.}$

Un límite inferior exponencial,

${\displaystyle R(s,s)\geq (1+o(1)){\frac {s}{{\sqrt {2}}e}}2^{s/2},}$

fue dada por Erdős en 1947 y fue instrumental en su introducción del método probabilístico. Hay una enorme brecha entre estos dos límites: por ejemplo, para s = 10 , esto da 101 ≤ R (10, 10) ≤ 48,620 . Sin embargo, los factores de crecimiento exponencial de cualquiera de los límites no se mejoraron durante mucho tiempo, y para el límite inferior todavía se mantiene en √ 2 . No se conoce ninguna construcción explícita que produzca un límite inferior exponencial. Los límites inferior y superior más conocidos para los números diagonales de Ramsey son

${\displaystyle [1+o(1)]{\frac {{\sqrt {2}}s}{e}}2^{\frac {s}{2}}\leq R(s,s)\leq s^{-(c\log s)/(\log \log s)}4^{s},}$

debido a Spencer y Conlon , respectivamente; una preimpresión de 2023 de Campos, Griffiths, Morris y Sahasrabudhe afirma haber logrado un progreso exponencial utilizando una construcción algorítmica basada en una estructura gráfica llamada " libro ", ^{[17] [18]} mejorando el límite superior a

${\displaystyle R(s,s)\leq (4-\varepsilon )^{s}{\text{ and }}R(s,t)\leq e^{-\delta t+o(s)}{\binom {s+t}{t}}.}$

con y donde se cree que estos parámetros podrían optimizarse, en particular .${\displaystyle \varepsilon =2^{-7}}$${\displaystyle \delta =50^{-1}}$${\displaystyle \varepsilon }$

Para los números de Ramsey fuera de la diagonal R (3, t ) , se sabe que son de orden ⁠dos^​/registro t⁠ ; esto se puede expresar de manera equivalente a decir que el número de independencia más pequeño posible en un gráfico sin triángulos con n vérticeses

${\displaystyle \Theta \left({\sqrt {n\log n}}\right).}$

El límite superior para R (3, t ) está dado por Ajtai , Komlós y Szemerédi , ^[19] el límite inferior fue obtenido originalmente por Kim , ^[20] y la constante implícita fue mejorada independientemente por Fiz Pontiveros, Griffiths y Morris , ^[21] y Bohman y Keevash , ^{[22] mediante el análisis del proceso libre de triángulos. Además, el estudio del "proceso libre de} H " más general ha establecido los límites inferiores asintóticos más conocidos para los números de Ramsey generales fuera de la diagonal, ^[23] R ( s , t )

${\displaystyle c'_{s}{\frac {t^{\frac {s+1}{2}}}{(\log t)^{{\frac {s+1}{2}}-{\frac {1}{s-2}}}}}\leq R(s,t)\leq c_{s}{\frac {t^{s-1}}{(\log t)^{s-2}}}.}$

Para los límites se convierte en , pero una preimpresión de 2023 ^{[24] [25]} ha mejorado el límite inferior a lo que resuelve una cuestión de Erdős que ofreció 250 dólares por una prueba de que el límite inferior tiene la forma . ^{[26] [27]}${\displaystyle s=4}$${\displaystyle c'_{s}t^{\frac {5}{2}}(\log t)^{-2}\leq R(4,t)\leq c_{s}t^{3}(\log t)^{-2}}$${\displaystyle c'_{s}t^{3}(\log t)^{-4}}$${\displaystyle c'_{s}t^{3}(\log t)^{-d}}$

Hay un análogo menos conocido pero interesante del teorema de Ramsey para subgrafos inducidos . En términos generales, en lugar de encontrar un subgrafo monocromático, ahora se requiere que encontremos un subgrafo inducido monocromático. En esta variante, ya no es suficiente restringir nuestro enfoque a grafos completos , ya que la existencia de un subgrafo completo no implica la existencia de un subgrafo inducido. El enunciado cualitativo del teorema en la siguiente sección fue demostrado por primera vez de forma independiente por Erdős , Hajnal y Pósa , Deuber y Rödl en la década de 1970. ^{[28] [29] [30]} Desde entonces, ha habido mucha investigación para obtener buenos límites para los números de Ramsey inducidos.

Sea H un grafo de n vértices. Entonces, existe un grafo G tal que cualquier coloración de las aristas de G con dos colores contiene una copia inducida monocromática de H (es decir, un subgrafo inducido de G tal que es isomorfo a H y sus aristas son monocromáticas). El menor número posible de vértices de G es el número de Ramsey inducido r _ind ( H ) .

A veces, también consideramos la versión asimétrica del problema. Definimos r _ind ( X , Y ) como el menor número posible de vértices de un grafo G tal que cada coloración de los bordes de G utilizando solo rojo o azul contiene un subgrafo inducido rojo de X o un subgrafo inducido azul de Y .

De manera similar al teorema de Ramsey, no está claro a priori si existen números de Ramsey inducidos para cada grafo H . A principios de la década de 1970, Erdős , Hajnal y Pósa , Deuber y Rödl demostraron independientemente que este es el caso. ^{[28] [29] [30]} Sin embargo, las pruebas originales dieron límites terribles (por ejemplo, torres de dos ) en los números de Ramsey inducidos. Es interesante preguntar si se pueden lograr mejores límites. En 1974, Paul Erdős conjeturó que existe una constante c tal que cada grafo H en k vértices satisface r _ind ( H ) ≤ 2 ^ck . ^[31] Si esta conjetura es verdadera, sería óptima hasta la constante c porque el grafo completo logra un límite inferior de esta forma (de hecho, es lo mismo que los números de Ramsey). Sin embargo, esta conjetura todavía está abierta a partir de ahora.

En 1984, Erdős y Hajnal afirmaron que habían demostrado el límite ^[32]

${\displaystyle r_{\text{ind}}(H)\leq 2^{2^{k^{1+o(1)}}}.}$

Sin embargo, esto todavía estaba lejos del límite exponencial conjeturado por Erdős. No fue hasta 1998 cuando Kohayakawa , Prömel y Rödl lograron un gran avance , quienes demostraron el primer límite casi exponencial de r _ind ( H ) ≤ 2 ^{ck (log k ) 2} para alguna constante c . Su enfoque fue considerar un grafo aleatorio adecuado construido en planos proyectivos y demostrar que tiene las propiedades deseadas con probabilidad distinta de cero. La idea de usar grafos aleatorios en planos proyectivos también se ha utilizado anteriormente en el estudio de las propiedades de Ramsey con respecto a las coloraciones de vértices y el problema de Ramsey inducido en grafos de grado acotado H . ^[33]

El límite de Kohayakawa, Prömel y Rödl siguió siendo el mejor límite general durante una década. En 2008, Fox y Sudakov proporcionaron una construcción explícita para números de Ramsey inducidos con el mismo límite. ^[34] De hecho, demostraron que cada ( n , d ,λ) -grafo G con λ pequeño y d adecuado contiene una copia monocromática inducida de cualquier grafo en k vértices en cualquier coloración de aristas de G en dos colores. En particular, para alguna constante c , el grafo de Paley en n ≥ 2 ^{ck log 2 k} vértices es tal que todas sus coloraciones de aristas en dos colores contienen una copia monocromática inducida de cada grafo de k vértices.

En 2010, Conlon , Fox y Sudakov pudieron mejorar el límite a r _ind ( H ) ≤ 2 ^{ck log k} , que sigue siendo el mejor límite superior actual para números de Ramsey inducidos generales. ^[35] De manera similar al trabajo anterior en 2008, demostraron que cada ( n , d , λ) -grafo G con λ pequeño y densidad de aristas 1 ⁄ 2 contiene una copia monocromática inducida de cada grafo en k vértices en cualquier coloración de aristas en dos colores. Actualmente, la conjetura de Erdős de que r _ind ( H ) ≤ 2 ^ck permanece abierta y es uno de los problemas importantes en la teoría de grafos extremales .

En cuanto a los límites inferiores, no se sabe mucho en general, excepto el hecho de que los números de Ramsey inducidos deben ser al menos los números de Ramsey correspondientes. Se han obtenido algunos límites inferiores para algunos casos especiales (consulte Casos especiales).

Si bien los límites generales para los números de Ramsey inducidos son exponenciales en el tamaño del gráfico, el comportamiento es muy diferente en clases especiales de gráficos (en particular, los dispersos). Muchas de estas clases tienen números de Ramsey inducidos polinómicos en el número de vértices.

Si H es un ciclo , camino o estrella en k vértices, se sabe que r _ind ( H ) es lineal en k . ^[34]

Si H es un árbol de k vértices, se sabe que r _ind ( H ) = O ( k ² log ² k ) . ^[36] También se sabe que r _ind ( H ) es superlineal (es decir, r _ind ( H ) = ω( k ) ). Nótese que esto contrasta con los números de Ramsey habituales, donde la conjetura de Burr–Erdős (ahora probada) nos dice que r ( H ) es lineal (ya que los árboles son 1- degenerados ).

Para grafos H con número de vértices k y grado acotado Δ , se conjeturó que r _ind ( H ) ≤ cn ^{d (Δ)} , para alguna constante d que dependa solo de Δ . Este resultado fue demostrado por primera vez por Łuczak y Rödl en 1996, con d (Δ) creciendo como una torre de dos con altura O (Δ ² ) . ^[37] Desde entonces se obtuvieron límites más razonables para d (Δ) . En 2013, Conlon, Fox y Zhao demostraron usando un lema de conteo para grafos pseudoaleatorios dispersos que r _ind ( H ) ≤ cn ^2Δ+8 , donde el exponente es el mejor posible hasta factores constantes. ^[38]

De manera similar a los números de Ramsey, podemos generalizar la noción de números de Ramsey inducidos a hipergrafos y configuraciones multicolores.

También podemos generalizar el teorema de Ramsey inducido a un entorno multicolor. Para los grafos H ₁ , H ₂ , …, H _r , definamos r _ind ( H ₁ , H ₂ , …, H _r ) como el número mínimo de vértices en un grafo G tal que cualquier coloración de las aristas de G en r colores contenga un subgrafo inducido isomorfo a H _i donde todas las aristas están coloreadas en el i -ésimo color para algún 1 ≤ i ≤ r . Sea r _ind ( H ; q ) := r _ind ( H , H , …, H ) ( q copias de H ).

Es posible derivar un límite en r _ind ( H ; q ) que es aproximadamente una torre de dos de altura ~ log q aplicando iterativamente el límite en el caso de dos colores. El límite mejor conocido actualmente se debe a Fox y Sudakov, que logra r _ind ( H ; q ) ≤ 2 ^{ck 3} , donde k es el número de vértices de H y c es una constante que depende solo de q . ^[39]

Podemos extender la definición de números de Ramsey inducidos a hipergrafos d -uniformes simplemente cambiando la palabra grafo en el enunciado por hipergrafo . Además, podemos definir la versión multicolor de los números de Ramsey inducidos de la misma manera que en la subsección anterior.

Sea H un hipergrafo d -uniforme con k vértices. Defina la función de torre t _r ( x ) haciendo t ₁ ( x ) = x y para i ≥ 1 , t _{i +1} ( x ) = 2 ^{t _i ( x )} . Utilizando el método del contenedor de hipergrafos, Conlon, Dellamonica, La Fleur, Rödl y Schacht pudieron demostrar que para d ≥ 3, q ​​≥ 2 , r _ind ( H ; q ) ≤ t _d ( ck ) para alguna constante c que depende solo de d y q . En particular, este resultado refleja el límite mejor conocido para el número de Ramsey habitual cuando d = 3 . ^[40]

Otro resultado, también llamado comúnmente teorema de Ramsey , se aplica a los grafos infinitos. En un contexto en el que también se discuten grafos finitos, a menudo se lo llama "teorema de Ramsey infinito". Como la intuición proporcionada por la representación gráfica de un grafo disminuye cuando se pasa de grafos finitos a grafos infinitos, los teoremas en esta área suelen expresarse en terminología de teoría de conjuntos . ^[41]

Teorema. Sea un conjunto infinito y coloreemos los elementos de (los subconjuntos de de tamaño ) con distintos colores. Entonces existe un subconjunto infinito de tal que los subconjuntos de tamaño de todos tienen el mismo color.${\displaystyle X}$${\displaystyle [X]^{n}}$${\displaystyle X}$${\displaystyle n}$${\displaystyle c}$${\displaystyle M}$${\displaystyle X}$${\displaystyle n}$${\displaystyle M}$

Prueba : La prueba es por inducción sobre n , el tamaño de los subconjuntos. Para n = 1 , la afirmación es equivalente a decir que si divides un conjunto infinito en un número finito de conjuntos, entonces uno de ellos es infinito. Esto es evidente. Suponiendo que el teorema es verdadero para n ≤ r , lo demostramos para n = r + 1 . Dado un c -coloreado de los subconjuntos de ( r + 1) -elementos de X , sea a ₀ un elemento de X y sea Y = X \ { a ₀ }. Luego inducimos un c -coloreado de los subconjuntos de r -elementos de Y , simplemente añadiendo un ₀ a cada subconjunto de r -elementos (para obtener un subconjunto de ( r + 1) -elementos de X ). Por la hipótesis de inducción, existe un subconjunto infinito Y ₁ de Y tal que cada subconjunto de r -elementos de Y ₁ está coloreado del mismo color en el coloreado inducido. Por lo tanto, existe un elemento a ₀ y un subconjunto infinito Y ₁ tales que todos los subconjuntos de ( r + 1) elementos de X que consisten en a ₀ y r elementos de Y ₁ tienen el mismo color. Por el mismo argumento, existe un elemento a ₁ en Y ₁ y un subconjunto infinito Y ₂ de Y ₁ con las mismas propiedades. Inductivamente, obtenemos una secuencia { a ₀ , a ₁ , a ₂ , …} tal que el color de cada subconjunto de ( r + 1) elementos ( a _{i (1)} , a _{i (2)} , …, a _{i ( r + 1)} ) con i (1) < i (2) < … < i ( r + 1) depende solo del valor de i (1)Además, hay una cantidad infinita de valores de _{i(n) que hacen que este color sea el mismo. Tome estos i} ( n ) para obtener el _{conjunto monocromático deseado} .

Una forma infinita más fuerte pero desequilibrada del teorema de Ramsey para grafos, el teorema de Erdős–Dushnik–Miller , establece que cada grafo infinito contiene un conjunto independiente numerablemente infinito o una camarilla infinita de la misma cardinalidad que el grafo original. ^[42]

Es posible deducir el teorema finito de Ramsey a partir de la versión infinita mediante una prueba por contradicción . Supóngase que el teorema finito de Ramsey es falso. Entonces existen números enteros c , n , T tales que para cada número entero k , existe una c -coloración de [ k ] ^{( n )} sin un conjunto monocromático de tamaño T . Sea C _k la c -coloración de [ k ] ^{( n )} sin un conjunto monocromático de tamaño T .

Para cualquier k , la restricción de una coloración en C _{k +1} a [ k ] ^{( n )} (ignorando el color de todos los conjuntos que contienen k + 1 ) es una coloración en C _k . Defina ⁠ ⁠${\displaystyle C_{k}^{1}}$ como las coloraciones en C _k que son restricciones de coloraciones en C _{k +1} . Dado que C _{k +1} no está vacío, tampoco lo está ⁠ ⁠${\displaystyle C_{k}^{1}}$ .

De manera similar, la restricción de cualquier coloración en ⁠ ⁠${\displaystyle C_{k+1}^{1}}$ está en ⁠ ⁠${\displaystyle C_{k}^{1}}$ , lo que permite definir ⁠ ⁠${\displaystyle C_{k}^{2}}$ como el conjunto de todas esas restricciones, un conjunto no vacío. Continuando así, defina ⁠ ⁠${\displaystyle C_{k}^{m}}$ para todos los enteros m , k .

Ahora, para cualquier entero k ,

${\displaystyle C_{k}\supseteq C_{k}^{1}\supseteq C_{k}^{2}\supseteq \cdots }$

y cada conjunto no es vacío. Además, C _k es finito como

${\displaystyle |C_{k}|\leq c^{\frac {k!}{n!(k-n)!}}}$

De ello se deduce que la intersección de todos estos conjuntos no es vacía, y sea

${\displaystyle D_{k}=C_{k}\cap C_{k}^{1}\cap C_{k}^{2}\cap \cdots }$

Entonces, cada coloración en D _k es la restricción de una coloración en D _{k +1} . Por lo tanto, al no restringir una coloración en D _k a una coloración en D _{k +1} , y continuar haciéndolo, se construye una coloración de sin ningún conjunto monocromático de tamaño T . Esto contradice el teorema de Ramsey infinito.${\displaystyle \mathbb {N} ^{(n)}}$

Si se adopta un punto de vista topológico adecuado, este argumento se convierte en un argumento de compacidad estándar que muestra que la versión infinita del teorema implica la versión finita. ^[43]

El teorema también se puede extender a los hipergrafos . Un m -hipergrafo es un grafo cuyas "aristas" son conjuntos de m vértices – en un grafo normal una arista es un conjunto de 2 vértices. El enunciado completo del teorema de Ramsey para hipergrafos es que para cualesquiera enteros m y c , y cualesquiera enteros n ₁ , …, n _c , hay un entero R ( n ₁ , …, n _c ; m) tal que si las hiperaristas de un m -hipergrafo completo de orden R ( n ₁ , …, n _c ; m ) están coloreadas con c colores diferentes, entonces para algún i entre 1 y c , el hipergrafo debe contener un sub- m -hipergrafo completo de orden n _i cuyas hiperaristas sean todas de color i . Este teorema se demuestra usualmente por inducción sobre m , la 'hiper-idad' del grafo. El caso base para la prueba es m = 2 , que es exactamente el teorema anterior.

Para m = 3 conocemos el valor exacto de un número de Ramsey no trivial, a saber, R (4, 4; 3) = 13. Este hecho fue establecido por Brendan McKay y Stanisław Radziszowski en 1991. ^[44] Además, tenemos: R (4, 5; 3) ≥ 35 , ^[45] R (4, 6; 3) ≥ 63 y R (5, 5; 3) ≥ 88. [ ^45]

También es posible definir números de Ramsey para grafos dirigidos ; estos fueron introducidos por P. Erdős y L. Moser (1964). Sea R ( n ) el número más pequeño Q tal que cualquier grafo completo con arcos dirigidos simples (también llamado "torneo") y con ≥ Q nodos contenga un subtorneo acíclico (también llamado "transitivo") de n nodos.

Este es el análogo en grafo dirigido de lo que (arriba) se ha llamado R ( n , n ; 2) , el número más pequeño Z tal que cualquier coloración bidimensional de las aristas de un grafo completo no dirigido con ≥ Z nodos, contiene un grafo completo monocromático en n nodos. (El análogo dirigido de los dos colores de arco posibles son las dos direcciones de los arcos, el análogo de "monocromático" es "todas las flechas de arco apuntan en la misma dirección"; es decir, "acíclico").

Tenemos R (0) = 0 , R (1) = 1 , R (2) = 2 , R (3) = 4 , R (4) = 8 , R (5) = 14 , R (6) = 28 y 34 ≤ R (7) ≤ 47. [ ^{46] [47]}

En términos del cálculo de particiones, el teorema de Ramsey puede enunciarse como para todos los n y k finitos . Wacław Sierpiński demostró que el teorema de Ramsey no se extiende a gráficos de tamaño al mostrar que . En particular, la hipótesis del continuo implica que . Stevo Todorčević demostró que, de hecho, en ZFC , , una afirmación mucho más sólida que . Justin T. Moore ha reforzado aún más este resultado. En el lado positivo, un cardinal de Ramsey , , es un cardinal grande definido axiomáticamente para satisfacer la fórmula relacionada: . La existencia de cardinales de Ramsey no se puede demostrar en ZFC.${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$${\displaystyle \aleph _{1}}$${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle \aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}$${\displaystyle \aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle \kappa }$${\displaystyle \kappa \rightarrow (\kappa )_{2}^{<\omega }}$

En matemáticas inversas , hay una diferencia significativa en la fuerza de la prueba entre la versión del teorema de Ramsey para grafos infinitos (el caso n = 2) y para multigrafos infinitos (el caso n ≥ 3). La versión multigrafo del teorema es equivalente en fuerza al axioma de comprensión aritmética , por lo que forma parte del subsistema ACA ₀ de la aritmética de segundo orden , uno de los cinco grandes subsistemas en matemáticas inversas. Por el contrario, por un teorema de David Seetapun , la versión gráfica del teorema es más débil que ACA ₀ y (combinando el resultado de Seetapun con otros) no cae en uno de los cinco grandes subsistemas. ^[48] ​​Sin embargo, sobre ZF , la versión gráfica implica el lema clásico de Kőnig , mientras que la implicación inversa no se cumple, ^[49] ya que el lema de Kőnig es equivalente a la elección contable de conjuntos finitos en este contexto. ^[50]

• Cardenal de Ramsey
• Teorema de París-Harrington
• Sim (juego de lápiz)
• Teoría de Ramsey infinita
• Número de Van der Waerden
• Juego de Ramsey
• Teorema de Erdös-Rado

• Ajtai, Miklós ; Komlós, János ; Szemerédi, Endre (1980), "Una nota sobre los números de Ramsey", J. Combin. Teoría Ser. A , 29 (3): 354–360, doi : 10.1016/0097-3165(80)90030-8.
• Bohman, Tom; Keevash, Peter (2010), "La evolución temprana del proceso libre de hidrógeno", Invent. Math. , 181 (2): 291–336, arXiv : 0908.0429 , Bibcode :2010InMat.181..291B, doi :10.1007/s00222-010-0247-x, S2CID  2429894
• Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Prentice-Hall, págs. 77–82, ISBN 978-0-13-602040-0
• Conlon, David (2009), "Un nuevo límite superior para los números diagonales de Ramsey", Annals of Mathematics , 170 (2): 941–960, arXiv : math/0607788v1 , doi :10.4007/annals.2009.170.941, MR  2552114, S2CID  9238219.
• Erdős, Paul (1947), "Algunas observaciones sobre la teoría de grafos", Bull. Amer. Math. Soc. , 53 (4): 292–294, doi : 10.1090/S0002-9904-1947-08785-1.
• Erdős, P .; Moser, L. (1964), "Sobre la representación de grafos dirigidos como uniones de ordenamientos" (PDF) , A Magyar Tudományos Akadémia, Matematikai Kutató Intézetének Közleményei , 9 : 125–132, MR  0168494
• Erdős, Paul ; Szekeres, George (1935), "Un problema combinatorio en geometría" (PDF) , Compositio Mathematica , 2 : 463–470, doi :10.1007/978-0-8176-4842-8_3, ISBN 978-0-8176-4841-1.
• Exoo, G. (1989), "Un límite inferior para R(5,5)", Journal of Graph Theory , 13 : 97–98, doi :10.1002/jgt.3190130113.
• Graham, R .; Rothschild, B.; Spencer, JH (1990), Teoría de Ramsey , Nueva York: John Wiley and Sons.
• Gross, Jonathan L. (2008), Métodos combinatorios con aplicaciones informáticas , CRC Press, pág. 458, ISBN 978-1-58488-743-0
• Harary, Frank (1972), Teoría de grafos , Addison-Wesley, págs. 16-17, ISBN 0-201-02787-9
• Ramsey, FP (1930), "Sobre un problema de lógica formal", Actas de la London Mathematical Society , 30 : 264–286, doi :10.1112/plms/s2-30.1.264.
• Spencer, J. (1975), "Teorema de Ramsey: un nuevo límite inferior", J. Combin. Theory Ser. A , 18 : 108–115, doi : 10.1016/0097-3165(75)90071-0.
• Bian, Zhengbing; Chudak, Fabian; Macready, William G.; Clark, Lane; Gaitan, Frank (2013), "Determinación experimental de los números de Ramsey", Physical Review Letters , 111 (13): 130505, arXiv : 1201.1842 , Bibcode :2013PhRvL.111m0505B, doi :10.1103/PhysRevLett.111.130505, PMID  24116761, S2CID  1303361.

El Wikilibro Combinatoria tiene una página sobre el tema: Números de Ramsey

• "Teorema de Ramsey", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Ramsey@Home es un proyecto de computación distribuida diseñado para encontrar nuevos límites inferiores para varios números de Ramsey utilizando una serie de técnicas diferentes.
• Revista Electrónica de Combinatoria: estudio dinámico de números de Ramsey pequeños (por Stanisław Radziszowski)
• Número de Ramsey – de MathWorld (contiene límites inferior y superior hasta R(19, 19))
• Número de Ramsey – Geoffrey Exoo (Contiene R(5, 5) > 42 contraprueba)