En matemáticas combinatorias , el teorema de Ramsey , en una de sus formas teóricas de grafos , establece que uno encontrará camarillas monocromáticas en cualquier rótulo de borde (con colores) de un grafo completo suficientemente grande . Para demostrar el teorema de dos colores (por ejemplo, azul y rojo), dejar que r y s sea cualquiera de los dos positivos enteros . [1] El teorema de Ramsey establece que existe un número entero positivo mínimo R ( r , s ) para el cual cada color de borde azul-rojo del gráfico completo enLos vértices R ( r , s ) contienen una camarilla azul en losvértices r o una camarilla roja en los vértices s . (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 probada por FP 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 bordes conectados de un solo color.
Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de solo a dos. Más precisamente, el teorema establece que para cualquier número dado de colores, c , y cualquier entero dado n 1 , ..., n c , hay un número, R ( n 1 , ..., n c ), tal que Si las aristas de un gráfico completo de orden R ( n 1 , ..., n c ) están coloreadas con c colores diferentes, entonces para alguna i entre 1 y c , debe contener un subgrafo completo de orden n i cuyas aristas sean todo color i . El caso especial anterior tiene c = 2 (y n 1 = r y n 2 = s ).
Ejemplos de
R (3, 3) = 6
Suponga que los bordes de un gráfico completo en 6 vértices están coloreados de rojo y azul. Elija un vértice, v . Hay 5 bordes incidentes av, por lo que (según el principio del casillero ) al menos 3 de ellos deben ser del mismo color. Sin pérdida de generalidad se puede suponer al menos 3 de estos bordes, que conecta el vértice, v , a los vértices, r , s y t , son de color azul. (Si no es así, intercambie rojo y azul en lo que sigue.) Si alguno de los bordes, ( r , s ), ( r , t ), ( s , t ), 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 color, cualquier K 6 contiene un K 3 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 contando dos veces . Es como sigue: Cuente el número de triples ordenados de vértices, x , y , z , de manera que la arista, ( xy ), sea roja y la arista, ( yz ), sea azul. En primer lugar, cualquier vértice 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 el 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 triples de este tipo. En segundo lugar, para cualquier triángulo no monocromático ( xyz ), existen precisamente dos de esos 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 del K 6 son monocromáticos.
Por el contrario, es posible aplicar dos colores a un K 5 sin crear ningún K 3 monocromático , mostrando que R (3, 3)> 5. El color único [2] 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
Un número Ramsey multicolor es un número Ramsey que utiliza 3 o más colores. Hay (hasta simetrías) sólo dos números Ramsey multicolores no triviales para los que se conoce el valor exacto, a saber, R (3, 3, 3) = 17 y R (3, 3, 4) = 30. [3]
Suponga que tenemos un color de borde de un gráfico completo usando 3 colores, rojo, verde y azul. Supongamos además que el color de los bordes no tiene triángulos monocromáticos. Seleccione un vértice v . Considere el conjunto de vértices que tienen un borde rojo en el vértice v . Esto se llama vecindario rojo 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 que consistiría en los dos extremos de ese borde rojo y el vértice v . Por tanto, la coloración del borde inducida en la vecindad roja de v tiene bordes coloreados con solo 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, los vecindarios verde y azul de v pueden contener como máximo 5 vértices cada uno. Dado que cada vértice, excepto el propio v , está en uno de los vecindarios rojo, verde o azul de v , el gráfico completo 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 arista coloreada en el gráfico completo en 16 vértices con 3 colores que evite los triángulos monocromáticos. Resulta que hay exactamente dos colorantes de este tipo en K 16 , los llamados colorantes no retorcidos y retorcidos. Ambos colores se muestran en las figuras de la derecha, con el color sin torcer en la parte superior y el color retorcido en la parte inferior.
Si seleccionamos cualquier color de color sin torcer o retorcido en K 16 , y consideramos el gráfico cuyos bordes son precisamente aquellos bordes que tienen el color especificado, obtendremos el gráfico de Clebsch .
Se sabe que hay exactamente dos colores de borde con 3 colores en K 15 que evitan los triángulos monocromáticos, que se pueden construir eliminando cualquier vértice de los colores no torcidos y retorcidos en K 16 , respectivamente.
También se sabe que hay exactamente 115 colores de borde con 3 colores en K 14 que evitan los triángulos monocromáticos, siempre que consideremos que los colores de borde que difieren por una permutación de los colores son iguales.
Prueba
Estuche de 2 colores
El teorema para el caso de 2 colores se puede demostrar por inducción en r + s . [4] 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 al encontrar un límite explícito para él. Según la hipótesis inductiva , existen R ( r - 1, s ) y R ( r , s - 1) .
- Lema 1. R ( r , s ) ≤ R ( r - 1, s ) + R ( r , s - 1) :
Prueba. Considere una gráfica completa en los vértices R ( r - 1, s ) + R ( r , s - 1) cuyas aristas están coloreadas 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 ( v , w ) es azul, yw está en N si ( v , w ) es rojo. Porque la gráfica tiene R ( r - 1, s ) + R ( r , s - 1) = | M | + | N | + 1 vértices, se deduce que o | M | ≥ R ( r - 1, s ) o | N | ≥ R ( r , s - 1) . En el primer caso, si M tiene un rojo K s también lo hace el gráfico original y hemos terminado. De lo contrario M tiene un azul K r -1 y así M ∪ { v } tiene un azul K r en la definición de M . El último caso es análogo. Por lo tanto, la afirmación es cierta y hemos completado la prueba para 2 colores.
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 fortalecer a: [5]
- R ( r , s ) ≤ R ( r - 1, s ) + R ( r , s - 1) - 1 .
Prueba . Suponga que p = R ( r - 1, s ) y q = R ( r , s - 1) son pares. Sea t = p + q - 1 y considere una gráfica de dos colores de t vértices. Si es el grado de -th vértice en el gráfico, luego, de acuerdo con el lema de Handshaking ,incluso. Dado que t es impar, debe haber un par. Asumires par, M y N son los vértices incidentes al vértice 1 en los subgrafos azul y rojo, respectivamente. Entonces ambos y son parejos. De acuerdo con el principio Pigeonhole , o bien, o . Desde es par, mientras es extraño, la primera desigualdad se puede fortalecer, por lo que o . Suponer. Entonces el subgrafo M tiene un rojo y la prueba está completa, o tiene un azul que junto con el vértice 1 hace un azul . El caso se trata de manera similar.
Estuche de más colores
Lema 2. Si c> 2, entonces R ( n 1 , ..., n c ) ≤ R ( n 1 , ..., n c −2 , R ( n c −1 , n c )).
Prueba. Considere una gráfica completa de R ( n 1 , ..., n c −2 , R ( n c −1 , n c )) vértices y coloree sus bordes con c colores. Ahora 'hazte ciego al color' y finge que c - 1 y c son del mismo color. Por tanto, la gráfica ahora está coloreada ( c - 1). Debido a la definición de R ( n 1 , ..., n c −2 , R ( n c −1 , n c )), dicho gráfico contiene un K n i coloreado monocromáticamente con el color i para algunos 1 ≤ i ≤ c - 2 o un K R ( n c - 1 , n c ) - coloreado en el 'color difuminado'. En el primer caso, hemos terminado. En el último caso, recuperamos la vista nuevamente y vemos de la definición de R ( n c −1 , n c ) debemos tener un ( c - 1) -monocromo K n c −1 o un c -monocromo K n c . En cualquier caso, la prueba está completa.
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 1 , ..., 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 pide el número mínimo de invitados, R ( m , n ) , que deben ser invitados para que al menos m se conozcan 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 todas las gráficas simples no dirigidas de orden v , contienen una camarilla de orden m , o un conjunto independiente de orden n . El teorema de Ramsey que existe un número tal para todos 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 estrechos y los límites superiores más estrechos. También hay muy pocos números r y s para los que conocen 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 y sin subgrafo K s rojo . Ese contraejemplo se llama gráfico de Ramsey . Brendan McKay mantiene una lista de gráficos de Ramsey conocidos. [6] Los límites superiores son a menudo considerablemente más difíciles de establecer: uno tiene que verificar 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 alienígenas.
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 cn ( n - 1)/2gráficos para buscar (para c colores) si se usa la fuerza bruta. [8] Por lo tanto, la complejidad para buscar todos los gráficos posibles (a través de la fuerza bruta ) es O ( c n 2 ) para c colores y como máximo n nodos.
Es poco probable que la situación mejore con la llegada de las computadoras cuánticas . El algoritmo más conocido [ cita requerida ] exhibe solo una aceleración cuadrática (cf. el algoritmo de Grover ) en relación con las computadoras clásicas, por lo que el tiempo de cálculo sigue siendo exponencial en el número de nodos. [9]
Valores conocidos
Como se describió anteriormente, R (3, 3) = 6 . Es fácil probar que R (4, 2) = 4 y, de manera más general, que R ( s , 2) = s para todos los s : una gráfica en s - 1 nodos con todas las aristas coloreadas de rojo sirve como contraejemplo y prueba que R ( s , 2) ≥ s ; entre las coloraciones de un gráfico en los nodos s , la coloración con todos los bordes de color rojo contiene un subgrafo rojo de nodo s , y todos los demás colorantes contienen un subgráfico 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 lo tanto R (4, 4) ≤ R (4, 3) + R (3, 4) ≤ 18 . Sólo hay dos (4, 4, 16) gráficos (es decir, 2 -colourings de un gráfico completo en 16 nodos sin 4 -node rojo o subgrafos completos azules) entre 6,4 × 10 22 diferentes 2 -colourings de 16 gráficos -node , y solo una gráfica (4, 4, 17) (la gráfica de Paley de orden 17 ) entre 2.46 × 10 26 colorantes. [6] (Esto fue probado 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 los límites débiles. Los límites inferiores para R (6, 6) y R (8, 8) no se han mejorado desde 1965 y 1972, respectivamente. [3]
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 , s <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 numérica de Ramsey es la Dynamic Survey 1 del Electronic Journal of Combinatorics , de Stanisław Radziszowski , que se actualiza periódicamente. [3] Cuando no se indique lo contrario, las entradas de la tabla siguiente se han tomado de la edición de marzo de 2017. (Tenga en cuenta que hay una simetría trivial en la diagonal ya que R ( r , s ) = R ( s , r )) .
s r | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
3 | 6 | 9 | 14 | 18 | 23 | 28 | 36 | 40–42 | ||
4 | 18 | 25 [10] | 36–41 | 49–61 | 59 [14] –84 | 73-115 | 92-149 | |||
5 | 43–48 | 58–87 | 80-143 | 101–216 | 133–316 | 149 [14] –442 | ||||
6 | 102-165 | 115 [14] –298 | 134 [14] –495 | 183–780 | 204-1171 | |||||
7 | 205–540 | 217–1031 | 252-1713 | 292–2826 | ||||||
8 | 282–1870 | 329–3583 | 343–6090 | |||||||
9 | 565–6588 | 581–12677 | ||||||||
10 | 798–23556 |
Asintóticos
La desigualdad R ( r , s ) ≤ R ( r - 1, s ) + R ( r , s - 1) puede aplicarse inductivamente para demostrar que
En particular, este resultado, debido a Erdős y Szekeres , implica que cuando r = s ,
Un límite inferior exponencial,
fue dado por Erdős en 1947 y fue fundamental en su introducción del método probabilístico. Obviamente, existe una gran brecha entre estos dos límites: por ejemplo, para s = 10 , esto da 101 ≤ R (10, 10) ≤ 48620 . Sin embargo, los factores de crecimiento exponencial de cualquiera de los límites no se han mejorado hasta la fecha y siguen siendo 4 y √ 2 respectivamente. 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 se encuentran actualmente en
debido a Spencer y Conlon respectivamente.
Para los números de Ramsey fuera de la diagonal R (3, t ) , se sabe que son de orden; esto puede decirse que es equivalente a decir que el más pequeño posible número de la independencia en un n -vertex gráfico sin triángulos es
El límite superior para R (3, t ) viene dado por Ajtai , Komlós y Szemerédi , el límite inferior fue obtenido originalmente por Kim y fue mejorado por Griffiths, Morris , Fiz Pontiveros y Bohman y Keevash , analizando el triángulo- proceso libre. De manera más general, para números Ramsey fuera de la diagonal, R ( s , t ) , con s fijo y t creciente, los límites más conocidos son
debido a Bohman y Keevash y Ajtai , Komlós y Szemerédi respectivamente.
Extensiones del teorema
Gráficos infinitos
Otro resultado, también llamado comúnmente teorema de Ramsey , se aplica a gráficos infinitos. En un contexto en el que también se discuten los gráficos finitos, a menudo se le denomina "teorema infinito de Ramsey". Como la intuición proporcionada por la representación pictórica de un gráfico disminuye cuando se pasa de gráficos finitos a infinitos, los teoremas en esta área generalmente se expresan en terminología de teoría de conjuntos . [15]
- 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 todos los subconjuntos de tamaño n de M tienen el mismo color.
Prueba : La prueba es por inducción en n , el tamaño de los subconjuntos. Para n = 1, el enunciado equivale a decir que si 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. Dado un color c de los subconjuntos de elementos ( r + 1) de X , sea un 0 un elemento de X y sea Y = X \ { a 0 }. Luego inducimos un color c de los subconjuntos de elementos r de Y , simplemente agregando un 0 a cada subconjunto de elementos r (para obtener un subconjunto de elementos ( r + 1) de X ). Según la hipótesis de la inducción, existe un subconjunto infinito Y 1 de Y tal que cada subconjunto de elementos r de Y 1 está coloreado del mismo color en la coloración inducida. Por tanto, hay un elemento a 0 y un subconjunto infinito Y 1 tal que todos los subconjuntos de elementos ( r + 1) de X que constan de a 0 y r elementos de Y 1 tienen el mismo color. Por el mismo argumento, hay un elemento a 1 en Y 1 y un subconjunto infinito Y 2 de Y 1 con las mismas propiedades. Inductivamente, obtenemos una secuencia { a 0 , a 1 , a 2 , ...} 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 solo del valor de i (1). Además, hay infinitos valores de i ( n ) tales que este color será el mismo. Tome estos a i ( n ) para obtener el conjunto monocromático deseado.
Una forma infinita más fuerte pero desequilibrada del teorema de Ramsey para gráficas, el teorema de Erdős-Dushnik-Miller , establece que cada gráfica infinita contiene un conjunto independiente infinito numerable o una camarilla infinita de la misma cardinalidad que la gráfica original. [dieciséis]
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 . Suponga que el teorema finito de Ramsey es falso. Entonces existen enteros c , n , T tales que para cada entero k , existe un color c desin un conjunto monocromático de tamaño T . Sea C k los colores c desin un conjunto monocromático de tamaño T .
Para cualquier k , la restricción de una coloración en C k +1 a(ignorando el color de todos los conjuntos que contienen k + 1) es una coloración en C k . Definirser los colorantes en C k que son restricciones de los colorantes en C k +1 . Dado que C k +1 no está vacío, tampoco lo está.
Del mismo modo, la restricción de cualquier colorante en es en , lo que permite definir como el conjunto de todas esas restricciones, un conjunto no vacío. Continuando así, definapara todos los enteros m , k .
Ahora, para cualquier entero k ,, y cada conjunto no está vacío. Además, C k es finito como. De ello se deduce que la intersección de todos estos conjuntos no está vacía, y sea. 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 desin cualquier conjunto monocromática de tamaño T . Esto contradice el teorema infinito de Ramsey.
Si se toma 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. [17]
Hipergrafos
El teorema también se puede extender a hipergráficos . Un hipergrafo m es un gráfico cuyos "bordes" son conjuntos de m vértices; en un gráfico normal, un borde es un conjunto de 2 vértices. La declaración completa del teorema de Ramsey para hypergraphs es que para cualquier números enteros m y c , y cualquier número entero n 1 , ..., n c , no es un número entero R ( n 1 , ..., n c ; c , m ) tal que si los hipergrafos de un m -hipergrafo completo de orden R ( n 1 , ..., n c ; c , m ) se colorean con c colores diferentes, entonces para algunos i entre 1 y c , el hipergrafo debe contener un sub- m -hipergrafo completo de orden n i cuyos hiperfondos son todos de color i . Este teorema generalmente se demuestra por inducción en m , el "hiper-ness" del gráfico. El caso base de la demostración es m = 2, que es exactamente el teorema anterior.
Gráficos 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 dirigidos individualmente (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 de 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 2 de los bordes de un gráfico completo no dirigido con ≥ Z nodos, contiene un gráfico monocromático completo 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 "todas las flechas de arco apuntan de la misma manera"; 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 32 ≤ R (7) ≤ 54. [18]
Relación con el axioma de elección
En matemáticas inversas , hay una diferencia significativa en la fuerza de la prueba entre la versión del teorema de Ramsey para gráficas infinitas (el caso n = 2) y para multigrafías infinitas (el caso n ≥ 3). La versión multigráfico del teorema es equivalente en fuerza al axioma de comprensión aritmética , por lo que es parte del subsistema ACA 0 de aritmética de segundo orden , uno de los cinco grandes subsistemas en matemáticas inversas. En contraste, según un teorema de David Seetapun , la versión gráfica del teorema es más débil que ACA 0 , y (combinando el resultado de Seetapun con otros) no cae en uno de los cinco subsistemas grandes. [19] Sin embargo, sobre ZF , la versión gráfica es equivalente al lema clásico de Kőnig . [20]
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
- ^ Algunos autores restringen los valores para que sean mayores que uno, por ejemplo ( Brualdi 2010 ) y ( Harary 1972 ), evitando así una discusión sobre colorear con bordes un gráfico sin bordes, mientras que otros reformulan el enunciado del teorema para requerir, en un gráfico sencillo , ya sea un r -clique o un s - conjunto independiente , ver ( bruto 2008 ) o ( Erdös y Szekeres 1935 ). De esta forma, la consideración de gráficos con un vértice es más natural.
- ^ hasta automorfismos del gráfico
- ↑ a b c Radziszowski, Stanisław (2011). "Pequeños números de Ramsey" . Encuestas dinámicas. Revista electrónica de combinatoria . doi : 10.37236 / 21 .
- ^ Hacer, Norman (2006). "Problemas de partido y teoría de Ramsey" (PDF) . Austr. Matemáticas. Soc. Gaceta . 33 (5): 306–312.
- ^ "Conocidos de la fiesta" .
- ^ a b "Gráficos de Ramsey" .
- ^ Joel H. Spencer (1994), Diez conferencias sobre el método probabilístico , SIAM , p. 4 , ISBN 978-0-89871-325-1
- ^ 2.6 Teoría de Ramsey de las matemáticas iluminada
- ^ Wang, Hefeng (2016). "Determinación de números de Ramsey en una computadora cuántica". Physical Review A . 93 (3): 032301. arXiv : 1510.01884 . Código Bibliográfico : 2016PhRvA..93c2301W . doi : 10.1103 / PhysRevA.93.032301 .
- ^ a b Brendan D. McKay, Stanislaw P. Radziszowski (mayo de 1995). " R (4,5) = 25" (PDF) . Revista de teoría de grafos . 19 (3): 309–322. doi : 10.1002 / jgt.3190190304 .
- ^ 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 .
- ^ Vigleik Angeltveit; Brendan McKay (2017). "". arXiv : 1703.08768v2 [ math.CO ].
- ^ Brendan D. McKay, Stanisław P. Radziszowski (1997). "Subgraph contar identidades y números de Ramsey" (PDF) . Revista de teoría combinatoria . 69 (2): 193-209. doi : 10.1006 / jctb.1996.1741 .
- ^ a b c d 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 bibliográfico : 2015arXiv150402403E . doi : 10.37236 / 5254 .
- ^ Martin Gould. "Teoría de Ramsey" (PDF) .
- ^ 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.
- ^ 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.
- ^ Smith, Warren D .; Exoo, Geoff, respuesta parcial al acertijo n. ° 27: una cantidad similar a la de Ramsey , recuperado el 02-06-2020
- ^ Hirschfeldt, Denis R. (2014). Cortando la verdad . Serie de notas de conferencias del Instituto de Ciencias Matemáticas de la Universidad Nacional de Singapur. 28 . World Scientific.
- ^ Lolli, Gabriele (octubre de 1977). "Sobre el teorema de Ramsey y el axioma de elección" . Diario de Notre Dame de lógica formal . 18 (4): 599–601. doi : 10.1305 / ndjfl / 1093888126 . ISSN 0029-4527 .
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
- Brualdi, Richard A. (2010), Introductory Combinatorics (5.a 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.
- Erdős, Paul (1947), "Algunas observaciones sobre la teoría de los gráficos", Bull. Amer. 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), Ramsey Theory , 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), Graph Theory , Addison-Wesley, págs. 16-17, ISBN 0-201-02787-9
- Ramsey, FP (1930), "Sobre un problema de lógica formal", Proceedings of the 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. Teoría 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.
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.
- La encuesta dinámica de Electronic Journal of Combinatorics de pequeños números de Ramsey (por Stanisław Radziszowski)
- Número de Ramsey: de MathWorld (contiene los límites inferior y superior hasta R (19, 19))
- Número de Ramsey - Geoffrey Exoo (contiene R (5, 5)> 42 contra prueba)