teorema de ramsey

Declaración en combinatoria matemática.

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 bordes (con colores) de un gráfico completo suficientemente grande . Para demostrar el teorema de dos colores (digamos, azul y rojo), sean r y s dos enteros positivos cualesquiera . ^[1] El teorema de Ramsey establece que existe un entero mínimo positivo R ( r , s ) para el cual cada coloración de borde azul-rojo del gráfico 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 número entero que depende tanto de r como de s .)

El teorema de Ramsey es un resultado fundamental en combinatoria. La primera versión de este resultado fue demostrada por Frank Ramsey . Esto inició la teoría combinatoria ahora 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 conectadas de un solo color.

Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de sólo dos. Más precisamente, el teorema establece que para cualquier número dado de colores, c , y cualquier número entero dado n ₁ ,…, n _c , hay un número, R ( n ₁ ,…, n _c ) , tal que si las aristas de un gráfico completo de orden R ( n ₁ ,…, n _c ) está coloreado con c colores diferentes, entonces, para algún i entre 1 y c , debe contener un subgrafo completo de orden n _i cuyos bordes sean todos de color i . El caso especial anterior tiene c = 2 (y n ₁ = r y n ₂ = s ).

Ejemplos

R (3, 3) = 6

Prueba de caso de 2 colores sin palabras
Debido al principio de casillero, hay al menos 3 aristas del mismo color (púrpura discontinua) de un vértice arbitrario v . Llamando a 3 de los vértices que terminan estos bordes r , s y t , si el borde rs , st o tr (negro sólido) tuviera este color, completaría el triángulo con v . Pero si no, cada uno debe ser de color opuesto, completando primero el triángulo de ese color.

Un etiquetado de 2 bordes de K ₅ sin K _{3 monocromático}

Supongamos que los bordes de un gráfico completo en 6 vértices están coloreados en rojo y azul. Elija un vértice, v . Hay 5 aristas incidentes en v y por lo tanto (según el principio de casillero ) al menos 3 de ellas deben ser del mismo color. Sin pérdida de generalidad, podemos asumir que al menos 3 de estos bordes, que conectan el vértice, v , con los vértices, r , s y t , son azules. (Si no, intercambie rojo y azul en lo que sigue). Si alguno de los bordes, ( rs ) , ( rt ) , ( st ) , también es azul, entonces tenemos un triángulo completamente azul. Si no, entonces esos tres bordes son todos rojos 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 teorema de amigos y extraños .

Una prueba alternativa funciona mediante doble conteo . Dice lo siguiente: Cuente el número de triples ordenados de vértices, x , y , z , de modo que la arista ( xy ) sea roja y la arista ( yz ) sea azul. En primer lugar, cualquier vértice dado será el medio de 0 × 5 = 0 (todos los bordes del vértice son del mismo color), 1 × 4 = 4 (cuatro son del mismo color, uno es del otro color), o 2 × 3 = 6 (tres son del mismo color, dos son del otro color) tales triples. Por lo tanto, hay como máximo 6 × 6 = 36 ternas de este tipo. En segundo lugar, para cualquier triángulo no monocromático ( xyz ) , existen precisamente dos de esos triples. Por tanto, hay como máximo 18 triángulos no monocromáticos. Por tanto, al menos 2 de los 20 triángulos del K ₆ son monocromáticos.

Por el contrario, es posible pintar un K ₅ con 2 colores sin crear ningún K ₃ monocromático , lo que demuestra que R (3, 3) > 5 . El color único ^[a] se muestra a la derecha. Por tanto R (3, 3) = 6 .

La tarea de demostrar que R (3, 3) ≤ 6 fue uno de los problemas del Concurso de Matemáticas William Lowell Putnam en 1953, así como en la Olimpiada de Matemáticas de Hungría en 1947.

Un ejemplo multicolor: R (3, 3, 3) = 17

Los dos únicos 3 colores de K ₁₆ sin K ₃ monocromático , hasta el isomorfismo y la permutación de colores: los colorantes no torcidos (izquierda) y torcidos (derecha).

Un número de Ramsey multicolor es un número de Ramsey que utiliza 3 o más colores. Hay (salvo simetrías) sólo dos números de Ramsey multicolores no triviales cuyo valor exacto se conoce, a saber, R (3, 3, 3) = 17 y R (3, 3, 4) = 30 . ^[2]

Supongamos que tenemos una coloración de bordes de un gráfico completo usando 3 colores, rojo, verde y azul. Supongamos además que el color del borde no tiene triángulos monocromáticos. Seleccione un vértice v . Considere el conjunto de vértices que tienen un borde rojo hasta el vértice v . Esto se llama vecindad roja de v . La vecindad roja de v no puede contener ningún borde rojo, ya que de lo contrario habría un triángulo rojo formado por los dos extremos de ese borde rojo y el vértice v . Por lo tanto, la coloración de bordes inducida en la vecindad roja de v tiene bordes coloreados con sólo dos colores, a saber, verde y azul. Dado que R (3, 3) = 6 , la vecindad roja de v puede contener como máximo 5 vértices. De manera similar, las vecindades verde y azul de v pueden contener como máximo 5 vértices cada una. Dado que cada vértice, excepto el propio v , está en una de las vecindades roja, verde o azul de v , todo el gráfico completo puede tener como máximo 1 + 5 + 5 + 5 = 16 vértices. Por 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 gráfico completo sobre 16 vértices con 3 colores que evite los triángulos monocromáticos. Resulta que en K ₁₆ hay exactamente dos de estos colorantes , los llamados colorantes no retorcidos y retorcidos. Ambos colores se muestran en las figuras de la derecha, con el color no retorcido a la izquierda y el color retorcido a la derecha.

gráfico de clebsch

Si seleccionamos cualquier color de la coloración no torcida o torcida 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 bordes con 3 colores en K ₁₅ que evitan triángulos monocromáticos, que se pueden construir eliminando cualquier vértice de las coloraciones no torcidas y torcidas en K ₁₆ , respectivamente.

También se sabe que hay exactamente 115 colores de bordes con 3 colores en K ₁₄ que evitan los triángulos monocromáticos, siempre que consideremos iguales los colores de bordes que se diferencian por una combinación de colores.

Prueba

estuche de 2 colores

El teorema para el caso de 2 colores se puede demostrar por inducción en r + s . ^[3] De la definición se desprende claramente que para todo n , R ( n , 2) = R (2, n ) = n . Esto inicia la inducción. Probamos que R ( r , s ) existe encontrando una cota explícita para él. Según 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).}$

Prueba. Considere un gráfico completo en R ( r − 1, s ) + R ( r , s − 1 ) vértices cuyos bordes están coloreados con dos colores. Elija un vértice v del gráfico y divida los vértices restantes en dos conjuntos M y N , de modo que para cada vértice w , w esté en M si el borde ( vw ) es azul y w esté en N si ( vw ) es rojo . Debido a que la gráfica tiene vértices, se deduce que o En el primer caso, si M tiene una K _s roja , entonces también la tendrá la gráfica original y hemos terminado. De lo contrario, M tiene un K _{r − 1} azul y también tiene un K _r azul según la definición de M . El último caso es análogo. Por tanto, la afirmación es cierta y hemos completado la prueba 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 pares, la desigualdad de inducción se puede reforzar a: ^[4]

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

Prueba . Supongamos que p = R ( r − 1, s ) y q = R ( r , s − 1) son pares. Sea t = p + q − 1 y considere una gráfica bicolor de t vértices. Si d _i es el grado del i -ésimo vértice en el subgrafo azul, entonces, de acuerdo con el lema del apretón de manos , es par. Dado que t es impar, debe haber un d _i par . Supongamos que d ₁ es par, M y N son los vértices incidentes al vértice 1 en los subgrafos azul y rojo, respectivamente. Entonces ambos y son pares. Según el principio de paloma , ya sea o Desde | METRO | es par, mientras que p – 1 es impar, la primera desigualdad se puede reforzar, por lo que o Supongamos que entonces el subgrafo M tiene una K _s roja y la prueba está completa, o tiene una K _{r – 1} azul que junto con el vértice 1 forma una K _r azul . El caso se trata de manera similar. ${\displaystyle \textstyle \sum _{i=1}^{t}d_{i}}$ ${\displaystyle |M|=d_{1}}$ ${\displaystyle |N|=t-1-d_{1}}$ ${\displaystyle |M|\geq p-1,}$ ${\displaystyle |N|\geq q.}$ ${\displaystyle |M|\geq p}$ ${\displaystyle |N|\geq q.}$ ${\displaystyle |M|\geq p=R(r-1,s).}$ ${\displaystyle |N|\geq q=R(r,s-1)}$

Estuche de más colores

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. Considere un gráfico completo de vértices y coloree sus aristas con c colores. Ahora "vuélvete daltónico" y supone que c − 1 yc son del mismo color. Por lo tanto, la gráfica ahora está coloreada ( c − 1 ) . Debido a la definición de tal gráfico, contiene un K _{n i} monocromáticamente coloreado con el color i para algunos 1 ≤ i ≤ c − 2 o un K _{R ( n c − 1 , n c )} de color en el color borroso. '. En el primer caso hemos terminado. En el último caso, recuperamos la vista nuevamente y vemos a partir de la definición de R ( n _{c − 1} , n _c ) que debemos tener un ( c − 1) -monocromo 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 en el 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 prueba el teorema.

números de ramsey

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 conocerán. 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 ) , tal que todos los gráficos 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 demostración 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, existe 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 de 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 gráfico K _{L −1} sin subgrafo K _r azul ni subgrafo K _s rojo . Este contraejemplo se llama gráfico de Ramsey . Brendan McKay mantiene una lista de gráficos de Ramsey conocidos. ^[5] Los límites superiores suelen ser considerablemente más difíciles de establecer: uno tiene que comprobar todos los colores posibles para confirmar la ausencia de un contraejemplo, o presentar un argumento matemático para su ausencia.

Complejidad computacional

Erdős nos pide que imaginemos una fuerza alienígena, mucho más poderosa que nosotros, aterrizando en la Tierra y exigiendo el valor de R (5, 5) o destruirán nuestro planeta. En ese caso, afirma, deberíamos reunir todas nuestras computadoras y 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 extraterrestres. ^[6]

—Joel  Spencer

Un programa informático sofisticado no necesita examinar todos los colorantes individualmente para eliminarlos todos; sin embargo, es una tarea computacional muy difícil que el software existente sólo puede gestionar en tamaños pequeños. Cada gráfico completo K _n tiene1/2n ( n − 1) bordes, por lo que habría un total de c ^{n ( n -1)/2} gráficos para buscar (para c colores) si se usa la fuerza bruta. ^[7] Por lo tanto, la complejidad para buscar todos los gráficos 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 sólo una aceleración cuadrática (véase el algoritmo de Grover ) en comparación con los ordenadores clásicos, de modo que el tiempo de cálculo sigue siendo exponencial en el número de nodos. ^{[8] [9]}

Valores conocidos

Como se describió anteriormente, R (3, 3) = 6 . Es fácil demostrar que R (4, 2) = 4 y, de manera más general, que R ( s , 2) = s para todos los s : un gráfico en s − 1 nodos con todos los bordes coloreados en rojo sirve como contraejemplo y demuestra que R ( s , 2) ≥ s ; entre los colores de un gráfico en s nodos, el color con todos los bordes coloreados en rojo contiene un subgrafo rojo de s nodos, y todos los demás colores contienen un subgrafo azul de 2 nodos (es decir, un par de nodos conectados con un borde azul).

Usando desigualdades de inducción, se puede concluir que R (4, 3) ≤ R (4, 2) + R (3, 3) − 1 = 9 , y por tanto R (4, 4) ≤ R (4, 3) + R (3, 4) ≤ 18 . Solo hay dos (4, 4, 16) gráficos (es decir, 2 colores de un gráfico completo en 16 nodos sin subgrafos completos rojos o azules de 4 nodos) entre 6,4 × 10 ²² 2 colores diferentes de gráficos de 16 nodos , y solo un gráfico (4, 4, 17) (el gráfico de Paley de orden 17) entre 2,46 × 10 ²⁶ coloraciones. ^[5] (Esto fue demostrado por Evans, Pulham y Sheehan en 1979.) 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. ^[10]

Se desconoce el valor exacto de R (5, 5) , aunque se sabe que se encuentra entre 43 (Geoffrey Exoo (1989) ^[11] ) y 48 (Angeltveit y McKay (2017) ^[12] ), inclusive.

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

Para R ( r , s ) con r , s > 5 , solo están disponibles límites débiles. Los límites inferiores de R (6, 6) y R (8, 8) no han mejorado desde 1965 y 1972, respectivamente. ^[2]

R ( r , s ) con r , s ≤ 10 se muestran en la siguiente tabla. Cuando se desconoce el valor exacto, la tabla enumera los límites más conocidos. R ( r , s ) con r < 3 están dados 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 con los números de Ramsey es la Dynamic Survey 1 del Electronic Journal of Combinatorics , de Stanisław Radziszowski , que se actualiza periódicamente. ^{[2] [14]} Salvo que se indique lo contrario, las entradas de la siguiente tabla se han tomado de la edición de enero de 2021. (Tenga en cuenta que hay una simetría trivial a lo largo de la diagonal ya que R ( r , s ) = R ( s , r ) .)

Asintóticas

La desigualdad R ( r , s ) ≤ R ( r − 1, s ) + R ( r , s − 1) se puede aplicar 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 dado por Erdős en 1947 y contribuyó decisivamente a la 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 mejoraron durante mucho tiempo, y para el límite inferior todavía se encuentra en √ 2 . No se conoce ninguna construcción explícita que produzca un límite inferior exponencial. Los límites superior e inferior 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 Morris, Campos, Griffiths y Sahasrabudhe afirma haber logrado un progreso exponencial utilizando una construcción algorítmica basada en una estructura gráfica llamada " libro ", ^{[18] [19]} 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 ordent ²/registro t; esto se puede expresar de manera equivalente como decir que el número de independencia más pequeño posible en un gráfico sin triángulos de n vértices es

${\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 , ^[20] el límite inferior fue obtenido originalmente por Kim , ^[21] y fue mejorado por Griffiths, Morris , Fiz Pontiveros, ^[22] y Bohman y Keevash , ^[23] analizando el proceso sin triángulos y, de manera más amplia, estos trabajos establecen los límites asintóticos más conocidos para los números de Ramsey generales fuera de la diagonal, R ( s , t ) ${\displaystyle 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}}},}$

Porque los límites se vuelven , pero una preimpresión de 2023 ^{[24] [25]} ha mejorado el límite inferior, lo que resuelve una cuestión de Erdos que ofreció 250 dólares por una prueba de que el límite inferior tiene 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}}$

Ramsey inducido

Existe 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 debemos encontrar un subgrafo monocromático inducido. 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 de 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, se han realizado muchas investigaciones para obtener buenos límites para los números de Ramsey inducidos.

Declaración

Sea H una gráfica de n vértices. Entonces, existe un gráfico G tal que cualquier coloración de los bordes de G usando 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 bordes son monocromáticos). 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 gráfico G tal que cada coloración de los bordes de G usando solo rojo o azul contiene un subgrafo inducido por rojo de X o un subgrafo inducido por azul de Y.

Historia y límites

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

En 1984, Erdős y Hajnal afirmaron que habían demostrado la obligación ^[32]

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

Sin embargo, eso 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 gráfico aleatorio adecuado construido en planos proyectivos y demostrar que tiene las propiedades deseadas con una probabilidad distinta de cero. La idea de utilizar gráficos aleatorios en planos proyectivos también se ha utilizado anteriormente en el estudio de las propiedades de Ramsey con respecto a la coloración de los vértices y el problema de Ramsey inducido en gráficos de grados acotados H. ^[33]

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

En 2010, Conlon , Fox y Sudakov pudieron mejorar el límite superior para r _ind ( H ) ≤ 2 ^{ck log k} , que sigue siendo el mejor límite superior actual para los números de Ramsey inducidos generales. ^[35] De manera similar al trabajo anterior en 2008, demostraron que cada ( n , d , λ) -gráfico G con λ pequeño y densidad de borde 1 ⁄ 2 contiene una copia monocromática inducida de cada gráfico en k vértices en cualquier coloración de borde 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 extremos .

Para los límites inferiores, en general no se sabe mucho, 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 (ver Casos especiales).

Casos especiales

Si bien los límites generales de 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 han inducido números polinomiales de Ramsey en el número de vértices.

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

Si H es un árbol en 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 ) ). Tenga en cuenta 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 gráficos H con número de vértices k y grado acotado Δ , se conjeturó que r _ind ( H ) ≤ cn ^{d (Δ)} , para alguna constante d que depende solo de Δ . Este resultado fue probado 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 el uso de un lema de conteo para gráficos pseudoaleatorios dispersos que r _ind ( H ) ≤ cn ^2Δ+8 , donde el exponente es mejor posible hasta factores constantes. ^[38]

Generalizaciones

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

Mas colores

También podemos generalizar el teorema de Ramsey inducido a un entorno multicolor. Para gráficos H ₁ , H ₂ , …, H _r , defina r _ind ( H ₁ , H ₂ , …, H _r ) como el número mínimo de vértices en un gráfico G tal que cualquier coloración de los bordes de G en r Los colores contienen un subgrafo inducido isomorfo a H _i donde todos los bordes están coloreados en el i -ésimo color para algunos 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. La cota más conocida actual 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 sólo de q . ^[39]

Hipergrafos

Podemos extender la definición de números de Ramsey inducidos a hipergrafos d -uniformes simplemente cambiando la palabra gráfico en la declaración a hipergrafo . Además, podemos definir la versión multicolor de los números de Ramsey inducidos de la misma forma que en la subsección anterior.

Sea H un hipergrafo d -uniforme con k vértices. Defina la función de la torre t _r ( x ) dejando t ₁ ( x ) = x y para i ≥ 1 , t _{i +1} ( x ) = 2 ^{t _i ( x )} . Utilizando el método del contenedor de hipergrafo, 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 dependiendo solo de d y q . En particular, este resultado refleja el límite más conocido para el número de Ramsey habitual cuando d = 3 . ^[40]

Extensiones del teorema

graficos infinitos

Otro resultado, también comúnmente llamado teorema de Ramsey , se aplica a gráficos infinitos. En un contexto donde también se discuten los gráficos finitos, a menudo se le llama "teorema de Ramsey infinito". Como la intuición proporcionada por la representación pictórica de un gráfico disminuye al pasar de gráficos finitos a infinitos, los teoremas en esta área generalmente se expresan en terminología de teoría de conjuntos . ^[41]

Teorema. Sea X un conjunto infinito y coloree los elementos de X ^{( n )} (los subconjuntos de X de tamaño n ) en c colores diferentes. Entonces existe un subconjunto infinito M de X tal que los n subconjuntos de tamaño M tienen todos el mismo color.

Prueba : La prueba es por inducción sobre n , el tamaño de los subconjuntos. Para n = 1 , la afirmación equivale a decir que si se divide 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 . Dada una coloración c de los subconjuntos de elementos ( r + 1 ) de X , sea a ₀ un elemento de X y sea Y = X \ { a ₀ }. Luego inducimos una coloración c de los subconjuntos de elementos r de Y , simplemente agregando un ₀ a cada subconjunto de elementos r (para obtener un subconjunto de elementos ( r + 1) de X ). Según 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 la coloración inducida. Por lo tanto, hay un elemento a ₀ y un subconjunto infinito Y ₁ tal que todos los subconjuntos de elementos ( r + 1) de X que consisten en a ₀ y r elementos de Y ₁ tienen el mismo color. Por el mismo argumento, hay 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 elementos ( r + 1 ) ( a _{i (1)} , a _{i (2)} , …, a _{i ( r + 1)} ) con i (1) < i (2) < … < i ( r + 1) depende sólo del valor de i (1). Además, hay infinitos valores de i ( n ) tales que este color será el mismo. Tome estas a _{i ( n )} para obtener el conjunto monocromático deseado.

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

La versión infinita implica lo finito.

Es posible deducir el teorema finito de Ramsey a partir de la versión infinita mediante una prueba por contradicción . Supongamos 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 coloración c de [ k ] ^{( n )} sin un conjunto monocromático de tamaño T. Sea C _k las c -coloraciones 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 )} (al ignorar el color de todos los conjuntos que contienen k + 1 ) es una coloración en C _k . Defina 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}}$ ${\displaystyle C_{k}^{1}}$

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

Ahora, para cualquier número entero k ,

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

y cada conjunto no está 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 está 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 sin ningún conjunto monocromático de tamaño T. Esto contradice el teorema infinito de Ramsey. ${\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]

Hipergrafos

El teorema también se puede extender a los hipergrafos . Un m -hipergrafo es un gráfico cuyos "aristas" son conjuntos de m vértices; en un gráfico normal, un borde es un conjunto de 2 vértices. El enunciado completo del teorema de Ramsey para hipergrafos es que para cualesquiera números enteros m y c , y cualesquiera números enteros n ₁ ,…, n _c , existe un número entero R ( n ₁ ,…, n _c ; m) tal que si los hipergrafos de un hipergrafo m completo de orden R ( n ₁ , …, n _c ; m ) están coloreados con c colores diferentes, entonces, para alguna i entre 1 y c , el hipergrafo debe contener un subhipergrafo m completo de orden n _i cuyos hiperbordes son todos de color i . Este teorema generalmente se demuestra por inducción sobre m , la "hiperactividad" del gráfico. 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]

Grafos dirigidos

También es posible definir números de Ramsey para gráficos 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 gráfico completo con arcos individualmente dirigidos (también llamado "torneo") y con ≥ Q nodos contenga un subtorneo de n nodos acíclico (también llamado "transitivo").

Este es el análogo en gráfico 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 bicolor de los bordes de un gráfico completo no dirigido con ≥ Z nodos, contiene un Gráfico completo monocromático en n nodos. (El análogo dirigido de los dos posibles colores de arco son las dos direcciones de los arcos, el análogo de "monocromático" es "todos los arcos-flechas 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]}

Cardenales incontables

En términos del cálculo de partición, el teorema de Ramsey se puede expresar como para todos los n y k finitos . Wacław Sierpiński demostró que el teorema de Ramsey no se extiende a las gráficas de tamaño al demostrar que . En particular, la hipótesis del continuo implica que . Stevo Todorčević demostró que en el ZFC , la declaración es mucho más contundente que la de . Justin T. Moore ha reforzado aún más este resultado. En el lado positivo, un cardenal de Ramsey , es un cardenal grande definido axiomáticamente para satisfacer la fórmula relacionada :. La existencia de los cardenales Ramsey no se puede probar 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 }}$

Relación con el axioma de elección

En matemáticas inversas , existe una diferencia significativa en la fuerza de la prueba entre la versión del teorema de Ramsey para gráficos infinitos (el caso n = 2) y para multigrafos infinitos (el caso n ≥ 3). La versión multigrafista del teorema es equivalente en fuerza al axioma de comprensión aritmética , lo que lo convierte en parte del subsistema ACA ₀ de aritmética de segundo orden , uno de los cinco grandes subsistemas de la matemática inversa. Por el contrario, según 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 de Kőnig clásico , 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 entorno. ^[50]

Ver también

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

Notas

1. hasta automorfismos del gráfico

1. Algunos autores restringen los valores para que sean mayores que uno, por ejemplo (Brualdi 2010) y (Harary 1972), evitando así una discusión sobre cómo colorear los bordes de un gráfico sin bordes, mientras que otros reformulan el enunciado del teorema para requerir, en un gráfico simple , ya sea un r -clique o un s - conjunto independiente , ver (Gross 2008) o (Erdős & Szekeres 1935). De esta forma, la consideración de gráficos con un vértice es más natural.
2. Radziszowski, Stanisław (2011). "Pequeños números de Ramsey". Encuestas dinámicas. Revista Electrónica de Combinatoria . 1000 . doi : 10.37236/21 .
3. Hazlo, normando (2006). "Problemas de partido y teoría de Ramsey" (PDF) . austriaco. Matemáticas. Soc. Gaceta . 33 (5): 306–312.
4. "Conocidos del partido".
5. "Gráficos de Ramsey".
6. Joel H. Spencer (1994), Diez conferencias sobre el método probabilístico, SIAM , p. 4, ISBN 978-0-89871-325-1
7. 2.6 Teoría de Ramsey de Mathematics Illuminated
8. Montanaro, Ashley (2016). "Algoritmos cuánticos: una descripción general". npj Información cuántica . 2 : 15023. arXiv : 1511.04206 . Código Bib : 2016npjQI...215023M. doi :10.1038/npjqi.2015.23. S2CID  2992738 – vía Naturaleza.
9. Wang, Hefeng (2016). "Determinación de los números de Ramsey en una computadora cuántica". Revisión física A. 93 (3): 032301. arXiv : 1510.01884 . Código Bib : 2016PhRvA..93c2301W. doi :10.1103/PhysRevA.93.032301. S2CID  118724989.
10. McKay, Brendan D.; Radziszowski, Stanislaw P. (mayo de 1995). "R(4,5) = 25" (PDF) . Revista de teoría de grafos . 19 (3): 309–322. doi :10.1002/jgt.3190190304.
11. Exoo, Geoffrey (marzo de 1989). "Un límite inferior para R (5, 5) ". Revista de teoría de grafos . 13 (1): 97–98. doi :10.1002/jgt.3190130113.
12. Vigleik Angeltveit; Brendan McKay (septiembre de 2018). " ". Revista de teoría de grafos . 89 (1): 5-13. arXiv : 1703.08768v2 . doi :10.1002/jgt.22235. ${\displaystyle R(5,5)\leq 48}$
13. Brendan D. McKay, Stanisław P. Radziszowski (1997). "Subgrafo contando identidades y números de Ramsey" (PDF) . Revista de teoría combinatoria . Serie B. 69 (2): 193–209. doi : 10.1006/jctb.1996.1741 .
14. Stanisław Radziszowski. "DS1" . Consultado el 17 de agosto de 2023 .
15. Angeltveit, Vigleik (31 de diciembre de 2023). "R(3,10) <= 41". arXiv : 2401.00392 [matemáticas.CO].
16. Exoo, Geoffrey; Tatarevic, Milos (2015). "Nuevos límites inferiores para 28 números clásicos de Ramsey". Revista Electrónica de Combinatoria . 22 (3): 3. arXiv : 1504.02403 . Código Bib : 2015arXiv150402403E. doi : 10.37236/5254 .
17. Exoo, Geoffrey (26 de octubre de 2023). "Un límite inferior para R (5,6)". arXiv : 2310.17099 [matemáticas.CO].
18. Campos, Marcelo; Griffiths, Simón; Morris, Robert; Sahasrabudhe, Julián (2023). "Una mejora exponencial para la diagonal Ramsey". arXiv : 2303.09521 [math.CO].
19. Sloman, Leila (2 de mayo de 2023). "Un pequeño gran salto adelante en la teoría de grafos". Revista Quanta .
20. Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1 de noviembre de 1980). "Una nota sobre los números de Ramsey". Revista de teoría combinatoria, serie A. 29 (3): 354–360. doi : 10.1016/0097-3165(80)90030-8 . ISSN  0097-3165.
21. Kim, Jeong Han (1995), "El número de Ramsey R (3, t ) tiene un orden de magnitud t ² /log t ", Algoritmos y estructuras aleatorias , 7 (3): 173–207, CiteSeerX 10.1.1.46.5058 , doi :10.1002/rsa.3240070302 
22. "El proceso sin triángulos y el número de Ramsey $ R (3, k) $". librería.ams.org . Consultado el 27 de junio de 2023 .
23. Bohman, Tom; Keevash, Peter (1 de agosto de 2010). "La evolución temprana del proceso libre de H". Invenciones matemáticas . 181 (2): 291–336. arXiv : 0908.0429 . doi :10.1007/s00222-010-0247-x. ISSN  1432-1297.
24. Mateo, Sam; Verstraete, Jacques (6 de junio de 2023). "Las asintóticas de r (4, t)". arXiv : 2306.04007 – vía ArXiv . {{cite journal}}: Citar diario requiere |journal=( ayuda )
25. Cepelewicz, Jordana (22 de junio de 2023). "Los matemáticos descubren una nueva forma de predecir la estructura en gráficos". Revista Quanta .
26. Erdös, Paul (1990), Nešetřil, Jaroslav; Rödl, Vojtěch (eds.), "Problemas y resultados en gráficos e hipergráficos: similitudes y diferencias", Matemáticas de la teoría de Ramsey , Algoritmos y combinatoria, Berlín, Heidelberg: Springer, págs. 12–28, doi :10.1007/978-3 -642-72905-8_2, ISBN 978-3-642-72905-8, recuperado el 27 de junio de 2023
27. "Problemas de Erdős". www.erdosproblems.com . Consultado el 12 de julio de 2023 .
28. Erdős, P .; Hajnal, A.; Posa, L. (1975). "Fuertes incrustaciones de gráficos en gráficos coloreados". Conjuntos infinitos y finitos, vol. 1 . Coloquios Mathematica Societatis János Bolyai. vol. 10. Holanda Septentrional, Ámsterdam/Londres. págs. 585–595.
29. Deuber, W. (1975). "Una generalización del teorema de Ramsey". Conjuntos infinitos y finitos, vol. 1 . Coloquios Mathematica Societatis János Bolyai. vol. 10. Holanda Septentrional, Ámsterdam/Londres. págs. 323–332.
30. Rödl, V. (1973). La dimensión de un gráfico y teoremas de Ramsey generalizados (tesis de maestría). Universidad Carolina.
31. Erdős, P. (1975). "Problemas y resultados sobre gráficas finitas e infinitas". Avances recientes en teoría de grafos (Actas del Segundo Simposio Checoslovaco, Praga, 1974) . Academia, Praga. págs. 183-192.
32. Erdős, Paul (1984). «Sobre algunos problemas de teoría de grafos, análisis combinatorio y teoría combinatoria de números» (PDF) . Teoría de grafos y combinatoria : 1–17.
33. Kohayakawa, Y.; Prömel, HJ; Rodl, V. (1998). "Números de Ramsey inducidos" (PDF) . Combinatoria . 18 (3): 373–404. doi : 10.1007/PL00009828 .
34. Zorro, Jacob ; Sudakov, Benny (2008). "Teoremas de tipo Ramsey inducido". Avances en Matemáticas . 219 (6): 1771–1800. arXiv : 0706.4112 . doi : 10.1016/j.aim.2008.07.009 .
35. Conlón, David ; Zorro, Jacob ; Sudakov, Benny (2012). "Sobre dos problemas de la teoría gráfica de Ramsey". Combinatoria . 32 (5): 513–535. arXiv : 1002.0045 . doi : 10.1007/s00493-012-2710-3 .
36. Beck, József (1990). "Sobre el tamaño de Ramsey, número de caminos, árboles y circuitos. II". En Nešetřil, J.; Rödl, V. (eds.). Matemáticas de la teoría de Ramsey . Algoritmos y Combinatoria. vol. 5. Springer, Berlín, Heidelberg. págs. 34–45. doi : 10.1007/978-3-642-72905-8_4 . ISBN 978-3-642-72907-2.
37. Łuczak, Tomasz; Rödl, Vojtěch (marzo de 1996). "Sobre números de Ramsey inducidos para gráficos con grado máximo acotado". Revista de teoría combinatoria . Serie B. 66 (2): 324–333. doi : 10.1006/jctb.1996.0025 .
38. Conlón, David ; Zorro, Jacob ; Zhao, Yufei (mayo de 2014). "Resultados extremos en gráficos pseudoaleatorios dispersos". Avances en Matemáticas . 256 : 206–29. arXiv : 1204.6645 . doi : 10.1016/j.aim.2013.12.004 .
39. Zorro, Jacob ; Sudakov, Benny (2009). "Teoremas de densidad para gráficos bipartitos y resultados relacionados de tipo Ramsey". Combinatoria . 29 (2): 153–196. arXiv : 0707.4159v2 . doi : 10.1007/s00493-009-2475-5 .
40. Conlón, David ; Dellamonica Jr., Domingos; La Flor, Steven; Rödl, Vojtěch ; Schacht, Mathías (2017). "Una nota sobre los números de Ramsey inducidos". En Loebl, Martín; Nešetřil, Jaroslav ; Thomas, Robin (eds.). Un viaje por las matemáticas discretas . Springer, Cham. págs. 357–366. arXiv : 1601.01493 . doi : 10.1007/978-3-319-44479-6_13 . ISBN 978-3-319-44478-9.
41. Martín Gould. "Teoría de Ramsey" (PDF) .
42. Dushnik, Ben; Miller, EW (1941). "Conjuntos parcialmente ordenados". Revista Estadounidense de Matemáticas . 63 (3): 600–610. doi :10.2307/2371374. hdl : 10338.dmlcz/100377 . JSTOR  2371374. SEÑOR  0004862.. Véanse en particular los teoremas 5.22 y 5.23.
43. Diestel, Reinhard (2010). "Capítulo 8, Gráficos infinitos". Teoría de grafos (4 ed.). Heidelberg: Springer-Verlag. págs. 209-2010. ISBN 978-3-662-53621-6.
44. McKay, Brendan D.; Radziszowski, Stanislaw P. (1991). "Se calcula el primer número de Ramsey clásico para hipergráficos". Actas del segundo simposio anual ACM-SIAM sobre algoritmos discretos, SODA'91 : 304–308.
45. Dybizbański, Janusz (31 de diciembre de 2018). "Un límite inferior en el hipergráfico número de Ramsey R (4,5; 3)". Contribuciones a la Matemática Discreta . 13 (2). doi : 10.11575/cdm.v13i2.62416 . ISSN  1715-0868.
46. Smith, Warren D.; Exoo, Geoff, respuesta parcial al acertijo n.° 27: una cantidad similar a Ramsey , consultado el 2 de junio de 2020.
47. Neiman, David; Mackey, Juan; Heule, Marijn (1 de noviembre de 2020). "Límites más estrictos en Ramsey número R (7) dirigido". arXiv : 2011.00683 [math.CO].
48. Hirschfeldt, Denis R. (2014). Cortando la verdad . Serie de notas de conferencias del Instituto de Ciencias Matemáticas de la Universidad Nacional de Singapur. vol. 28. Científico mundial.
49. Blass, Andreas (septiembre de 1977). "El teorema de Ramsey en la jerarquía de principios de elección". La revista de lógica simbólica . 42 (3): 387–390. doi :10.2307/2272866. ISSN  1943-5886.
50. Forster, TE; Truss, JK (enero de 2007). "Teorema de Ramsey y lema de König". Archivo de Lógica Matemática . 46 (1): 37–42. doi :10.1007/s00153-006-0025-z. ISSN  1432-0665.

Referencias

• 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 H", Invent. Matemáticas. , 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. América. Matemáticas. 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. 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 Sociedad Matemática de Londres , 30 : 264–286, doi :10.1112/plms/s2-30.1.264.
• Spencer, J. (1975), "Teorema de Ramsey: un nuevo límite inferior", J. Combin. Teoría Ser. A , 18 : 108–115, doi : 10.1016/0097-3165(75)90071-0.
• Bian, Zhengbing; Chudak, Fabián; Macready, William G.; Clark, carril; Gaitan, Frank (2013), "Determinación experimental de 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.

enlaces externos

• "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.
• Estudio dinámico del Electronic Journal of Combinatorics de pequeños números de Ramsey (por Stanisław Radziszowski)
• Número de Ramsey: de MathWorld (contiene límites superior e inferior hasta R(19, 19))
• Número de Ramsey – Geoffrey Exoo (Contiene R(5, 5) > 42 contraprueba)