El 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 etiqueta de borde (con colores) de un gráfico completo lo suficientemente grande. Para demostrar el teorema de dos colores (por ejemplo, azul y rojo), sea r y s dos enteros positivos. El teorema de Ramsey establece que existe un número entero mínimo positivo R(r, s) para el cual cada borde azul-rojo colorea el gráfico completo en R(r, s) vértices contiene una camarilla azul en los vértices r o una camarilla roja en el estilo s vértices. (Aquí R(r, s) significa un número entero que depende tanto de r y s).

El teorema de Ramsey es un resultado fundamental en combinatoria. La primera versión de este resultado fue probada por F. P. Ramsey. Esto dio inicio a 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 solo dos. Más precisamente, el teorema establece que para cualquier número dado de colores, c, y cualquier número entero n₁, …, n_c, hay un número, R(n₁, …, n_c), tal que si los bordes de un gráfico completo de orden R(n₁, …, n_c) están coloreados con c diferentes colores, luego para algunos i entre 1 y c, debe contener un subgrafo completo de orden n_i cuyos bordes son todos de color i. El caso especial anterior tiene c = 2 (y n₁ = r y n₂ = s ).

Ejemplos

R(3, 3) = 6

Una etiqueta de 2 niveles K₅ sin monocromático K₃

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 aristas incidentes en v y por lo tanto (según el principio del casillero) al menos 3 de ellas deben ser del mismo color. Sin pérdida de generalidad, podemos suponer al menos 3 de estos bordes, conectando el vértice, v, a 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 son azules, 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, any K₆ contiene una K₃, 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 por doble conteo. Funciona de la siguiente manera: Cuente el número de triples ordenados de vértices, x, y, z, tal que el borde, (xy), es rojo y el borde, (yz), es 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 el otro color) tales triples. Por lo tanto, hay como máximo 6 × 6 = 36 tales triples. 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 en el K₆ son monocromáticos.

Por el contrario, es posible bicolorear un K₅ sin crear ningún K₃, mostrando que R(3, 3) > 5. El color único se muestra a la derecha. Así R(3, 3) = 6.

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

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

Los únicos dos tres colores de K₁₆ sin monocromático K₃, hasta el isomorfismo y la permutación de los colores: los colores intwisted (left) y torcido (derecha).

Un número de Ramsey multicolor es un número de Ramsey que usa 3 o más colores. Hay (hasta simetrías) solo dos números de 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.

Supongamos que tenemos una coloración de borde de un gráfico completo usando 3 colores, rojo, verde y azul. Supongamos además que la coloración 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 el vecindario rojo de v. El vecindario rojo 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 rojo. borde y el vértice v. Por lo tanto, la coloración de 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, 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. Dado que cada vértice, a excepción de v, se encuentra en uno de los vecindarios rojo, verde o azul de v, todo el gráfico 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 un borde coloreando el gráfico completo en 16 vértices con 3 colores que evita los triángulos monocromáticos. Resulta que hay exactamente dos de esos colorantes en K₁₆, los llamados colorantes sin torcer y torcidos. Ambos colores se muestran en las figuras de la derecha, con el color sin torcer a la izquierda y el color torcido a la derecha.

Gráfico Clebsch

Si seleccionamos cualquier color, ya sea sin torcer o torcido, en K₁₆, y consideramos el gráfico cuyo las aristas son precisamente aquellas aristas 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₁₅ que evitan los triángulos monocromáticos, que se puede construir eliminando cualquier vértice de los colores sin torcer y torcidos en K₁₆, respectivamente.

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

Prueba

Estuche de 2 colores

El teorema para el caso de 2 colores se puede probar por inducción sobre r + s. Está claro a partir de la definición que para todos los n, R (n, 2) = R(2, n) = n. Esto inicia la inducción. Probamos que R(r, s) existe encontrando un límite explícito para él. Por la hipótesis inductiva R(r − 1, s) y R(r, s − 1) existen.

Lemma 1. R()r,s)≤ ≤ R()r− − 1,s)+R()r,s− − 1).{displaystyle R(r,s)leq R(r-1,s)+R(r,s-1). }

Prueba. Considere un gráfico completo R()r, 1, s) + R()r, s −1) vertices cuyos bordes están coloreados con dos colores. Escoge un vértice v del gráfico, y dividir los vértices restantes en dos conjuntos M y N, tal que por cada vértice w, w está dentro M si el borde ()vw) es azul, y w está dentro N si ()vw) es rojo. Porque el gráfico tiene R()r− − 1,s)+R()r,s− − 1)=SilencioMSilencio+SilencioNSilencio+1{displaystyle R(r-1,s)+R(r,s-1)= habitM durable+Sobrevivir vertices, sigue que SilencioMSilencio≥ ≥ R()r− − 1,s){displaystyle TENSIFICADO ANTERIOR_GEQ R(r-1,s)} o SilencioNSilencio≥ ≥ R()r,s− − 1).{displaystyle tenciónN durablegeq R(r,s-1). } En el caso anterior, si M tiene un rojo K_s entonces también el gráfico original y estamos acabados. De lo contrario M tiene un azul K_{r − 1} y así M∪ ∪ {}v}{displaystyle Mcup {v} tiene un azul K_r por la definición de M. Este último caso es análogo. Así la reclamación es verdadera y hemos completado la prueba de 2 colores.

En este caso de 2 colores, si R(r − 1, s) y R(r, s − 1) son pares, la inducción la desigualdad puede fortalecerse para:

R()r,s)≤ ≤ R()r− − 1,s)+R()r,s− − 1)− − 1.{displaystyle R(r,s)leq R(r-1,s)+R(r,s-1)-1.}

Prueba. Suppose p = R()r, 1, s) y q = R()r, s −1) ambos son incluso. Vamos t = p + q − 1 y considerar un gráfico de dos colores t vertices. Si d_i es grado de i- el vértice en el subgrafo azul, entonces, según el lema de Handshaking, .. i=1tdi{displaystyle textstyle sum ¿Qué? es incluso. Dado que t es extraño, debe haber una d_i. Assume d₁ es incluso, M y N son los vértices incidente a vértice 1 en los subgrafos azul y rojo, respectivamente. Entonces ambos SilencioMSilencio=d1{displaystyle TENSIFICADO } y SilencioNSilencio=t− − 1− − d1{displaystyle Silencio. son incluso. Según el principio Pigeonhole, o SilencioMSilencio≥ ≥ p− − 1,{displaystyle Нали вованый неных p-1,} o SilencioNSilencio≥ ≥ q.{displaystyle SilencioN eternageq q.} Desde SilencioMSilencio es incluso, mientras p – 1 es extraño, la primera desigualdad se puede fortalecer, así que SilencioMSilencio≥ ≥ p{displaystyle ← } o SilencioNSilencio≥ ≥ q.{displaystyle SilencioN eternageq q.} Suppose SilencioMSilencio≥ ≥ p=R()r− − 1,s).{displaystyle tenciónM eternageq p=R(r-1,s). } Entonces... M subgraph tiene un rojo K_s y la prueba está completa, o tiene un azul K_{r – 1} que junto con el vértice 1 hace un azul K_r. El caso SilencioNSilencio≥ ≥ q=R()r,s− − 1){displaystyle TENEDADN SUPERVISIÓNgeq q=R(r,s-1)} se trata de manera similar.

Estuche de más colores

Lemma 2. Si c ■ 2, entonces R()n1,...... ,nc)≤ ≤ R()n1,...... ,nc− − 2,R()nc− − 1,nc)).{displaystyle R(n_{1},dotsn_{c})leq R(n_{1},dotsn_{c-2},R(n_{c-1},n_{c}).}

Prueba. Considere un gráfico completo R()n1,...... ,nc− − 2,R()nc− − 1,nc)){displaystyle R(n_{1},dotsn_{c-2},R(n_{c-1},n_{c})} vertices y color sus bordes con c colores. Ahora ve al color ciego y finge que c − 1 y c son el mismo color. Así el gráfico es ahora ()c −1)- de acuerdo. Debido a la definición de R()n1,...... ,nc− − 2,R()nc− − 1,nc)),{displaystyle R(n_{1},dotsn_{c-2},R(n_{c-1},n_{c}),} tal gráfico contiene o K_ni monocromáticamente de color i para algunos 1 ≤ i ≤ c − 2 o a K_{R()nc − 1, nc)}- color azulado. En el caso anterior estamos acabados. En este último caso, recuperamos nuestra vista de nuevo y vemos desde la definición de R()n_{c − 1}, n_c) debemos tener una ()c −1)-monocromo K_{nc − 1} o a c-monocromo K_nc. 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 colores c 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 Ramsey's teorema (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 a la fiesta problema, 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 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 prueba de el teorema y otros argumentos dan cotas inferiores. (Paul Erdős obtuvo el primer límite inferior exponencial 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 del que conocemos el valor exacto de R(r, s).

Calcular un límite inferior L para R(r, s) generalmente requiere mostrar una coloración azul/roja del gráfico K<sub L−1 sin azul K_r subgráfico y sin subgráfico K_s. Tal contraejemplo se llama gráfico de Ramsey. Brendan McKay mantiene una lista de gráficos de Ramsey conocidos. Los límites superiores a menudo son 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 reclamando el valor de R(5, 5) o destruirán nuestro planeta. En ese caso, afirma, debemos marshalar todas nuestras computadoras y todos nuestros matemáticos e intentar encontrar el valor. Pero supongan, en cambio, que piden R(6, 6). En ese caso, cree, deberíamos intentar destruir a los alienígenas.

—Joel Spencer

Un sofisticado programa de computadora no necesita mirar todos los colorantes individualmente para eliminarlos a todos; sin embargo, es una tarea computacional muy difícil que el software existente solo puede manejar en tamaños pequeños. Cada gráfico completo K_n tiene 1/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 utiliza la fuerza bruta. Por lo tanto, la complejidad para buscar todos los gráficos posibles (mediante fuerza bruta) es O(cⁿ²) 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 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.

Valores conocidos

Como se describió anteriormente, R(3, 3) = 6. Es fácil demostrar que R(4, 2) = 4 y, de forma más general, que R(s, 2) = s para todos los s: un gráfico en s − 1 nodos con todos los bordes de color rojo sirve como contraejemplo y prueba que R(s, 2) ≥ s; entre los colores de un gráfico en los nodos s, el color con todos los bordes en rojo contiene un estilo s-nodo subgráfico rojo, y todos los demás colores 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. Solo hay dos (4, 4, 16) gráficos (es decir, 2 colores de un gráfico completo en 16 nodos sin subgráficos completos rojos o azules de 4 nodos) entre 6,4 × 10²² 2 colores diferentes de gráficos de 16 nodos, y solo uno (4, 4, 17) gráfico (el gráfico de Paley de orden 17) entre 2,46 × 10²⁶ colorantes. (Evans, Pulham y Sheehan demostraron esto 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.

Se desconoce el valor exacto de R(5, 5), aunque se sabe que se encuentra entre 43 (Geoffrey Exoo (1989)) y 48 (Angeltveit y McKay (2017)) (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).

Para R(r, s) con r, s > 5, solo están disponibles los límites débiles. Límites inferiores para R(6, 6) y R(8, 8) no se han mejorado desde 1965 y 1972, respectivamente.

R(r, s) con <span class="texhtml" 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 vienen 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 del número de Ramsey es la Dynamic Survey 1 del Electronic Journal of Combinatorics, de Stanisław Radziszowski, que se actualiza periódicamente. Cuando no se indique lo contrario, las entradas de la siguiente tabla se tomaron de la edición de enero de 2021. (Tenga en cuenta que hay una simetría trivial en la diagonal ya que R(r, s) = R(s, r).)

Asintóticos

La desigualdad R(r, s) ≤ R(r − 1, s) + R(r, s − 1) se puede aplicar inductivamente para probar que

R()r,s)≤ ≤ ()r+s− − 2r− − 1).{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,

R()s,s)≤ ≤ ()1+o()1))4s− − 1π π s.{displaystyle R(s,s)leq (1+o(1)){frac {4^{s-1}{.

Un límite inferior exponencial,

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

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) ≤ 48.620. Sin embargo, los factores de crecimiento exponencial de cualquiera de los límites no se mejoraron durante mucho tiempo, y el límite inferior todavía se encuentra en √2. No existe una construcción explícita conocida que produzca un límite inferior exponencial. Hasta una preimpresión de 2023, los límites inferior y superior más conocidos para los números de Ramsey diagonales eran

[1+o()1)]2se2s2≤ ≤ R()s,s)≤ ≤ s− − ()clog⁡ ⁡ s)/()log⁡ ⁡ log⁡ ⁡ s)4s,{displaystyle [1+o(1)]{sqrt {2}s}{e}2^{frac {s}{2}leq R(s,s)leq s^{-(clog s)/(log log s)}4^{s} {s} {s} }

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 t²/log t; esto puede expresarse de manera equivalente a decir que el número de independencia más pequeño posible en un gráfico libre de triángulos n-vértice es

.. ()nlog⁡ ⁡ n).{displaystyle Theta left({sqrt {nlog n}right). }

El límite superior para R(3, t) lo dan Ajtai, Komlós y Szemerédi, el El límite inferior fue obtenido originalmente por Kim, y fue mejorado por Griffiths, Morris, Fiz Pontiveros y Bowman y Keevash, mediante el análisis del proceso sin triángulos. Más generalmente, para números de Ramsey fuera de la diagonal, R(s, t), con s fijo y t creciendo, los límites más conocidos son

cs.ts+12()log⁡ ⁡ t)s+12− − 1s− − 2≤ ≤ R()s,t)≤ ≤ csts− − 1()log⁡ ⁡ t)s− − 2,{fnMicrosoft Sans} {fnMicroc {fnMicroc} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f}} {fnMicrosoft Sans Serif} {fnK}}}} {fnMicroc} {fnK}} {f}}} {fnMicroc}} {f}}}} {f}}}}}} {f} {f}}} {f}} {f} {f}} {f} {f}} {f} {f} {f}}}}}}}}}} {f}}}}} {f}}}}}} {f} {f}} {f}} {f}}{f}} {f}}}}{f} {f} {f}} {f}}}}}}}}}}}}}}}}}}}}}}} {ggnMi {S+1}{2}-{frac} {1}{s-2}}}leq ¿Qué?

debido a Bowman y Keevash y Ajtai, Komlós y Szemerédi respectivamente.

En un preprint de 2023, Morris, Campos, Griffiths y Sahasrabudhe afirman hacer un progreso exponencial en el límite superior para los números de Ramsey utilizando una construcción algorítmica releyendo sobre una estructura combinatoria apodada libros. Concretamente con 0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε =2− − 7■0{displaystyle varepsilon =2^{-7} {0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf58374ecf308323479c8953f22c45dee41a3eb4" style="vertical-align: -0.338ex; width:11.938ex; height:2.676ex;"/> y 0}" xmlns="http://www.w3.org/1998/Math/MathML">δ δ =150■0{displaystyle delta ={frac {1}{50} {0}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ab8b6cb8531d62530552a5d0ca4c8b1cf950dd33" style="vertical-align: -1.838ex; width:11.569ex; height:5.176ex;"/> reclaman

R()s,s)≤ ≤ ()4− − ε ε )syR()s,t)≤ ≤ e− − δ δ t+o()s)()s+tt).{displaystyle R(s,s)leq (4-varepsilon)}{text{ and }R(s,t)leq e^{-delta t+o(s)}{binom {s+t} {}}}

También anuncian que los parámetros, en particular ε ε =2− − 7{displaystyle varepsilon =2^{-7}, no están optimizados y podrían mejorarse con trabajo técnico adicional.

Ramsey inducida

Hay un análogo menos conocido pero interesante del teorema de Ramsey para los subgrafos inducidos. En términos generales, en lugar de encontrar un subgrafo monocromático, ahora se requiere 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. Erdős, Hajnal y Pósa, Deuber y Rödl demostraron por primera vez de forma independiente el enunciado cualitativo del teorema en la siguiente sección en la década de 1970. Desde entonces, se han realizado muchas investigaciones para obtener buenos límites para los números de Ramsey inducidos.

Declaración

Sea H un gráfico sobre 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 monocromática inducida 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 <span class="texhtml" r_ind(H).

A veces, también consideramos la versión asimétrica del problema. Definimos r_ind(X,Y) para Sea 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 rojo de X o subgrafo azul inducido de Y.

Historial y límites

Al igual que el 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 este es el caso. Sin embargo, las pruebas originales dieron límites terribles (por ejemplo, torres de dos) en los números de Ramsey inducidos. Es interesante preguntarse si se pueden lograr mejores límites. En 1974, Paul Erdős conjeturó que existe una constante c tal que cada gráfico H en k vértices satisface r_ind(H) ≤ 2^ck. 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 partir de ahora.

En 1984, Erdős y Hajnal afirmaron que probaron el límite

rind()H)≤ ≤ 22k1+o()1).{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 mostrar que tiene las propiedades deseadas con probabilidad distinta de cero. La idea de utilizar gráficos aleatorios en planos proyectivos también se ha utilizado anteriormente para estudiar las propiedades de Ramsey con respecto a los colores de los vértices y el problema de Ramsey inducido en gráficos de grados acotados H.

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. De hecho, demostraron que cada gráfico (n,d,λ) G con pequeñas λ y adecuado d 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 algunas constantes c, el gráfico de Paley en n ≥ 2^{ck log2k} vértices es tal que todos sus bordes se colorean en dos Los colores contienen una copia monocromática inducida de cada gráfico de vértice k.

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 los números de Ramsey inducidos generales. De manera similar al trabajo anterior en 2008, demostraron que cada gráfico (n,d,λ) G con λ y densidad de bordes 1⁄2 contiene una copia monocromática inducida de cada gráfico en k vértices en cualquier borde coloreando en dos colores. Actualmente, la conjetura de Erdős de que r_ind(H) ≤ 2^ck permanece abierto y es uno de los problemas importantes en la teoría de grafos extremos.

Para los límites inferiores, no se sabe mucho en general excepto por 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 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 polinomios de números de Ramsey inducidos 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.

Si H es un árbol en k vértices, se sabe que r_ind(H) = O(k² log²k). 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 (dado 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 clase d dependiendo únicamente de Δ. Este resultado fue probado por primera vez por Łuczak y Rödl en 1996, con d(Δ) creciendo como una torre de dos en dos con una altura O(Δ²). 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 el mejor posible hasta factores constantes.

Generalizaciones

De forma similar a los números de Ramsey, podemos generalizar la noción de números de Ramsey inducidos a hipergrafías y configuraciones multicolores.

Más 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) ser 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 subgráfico 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. El límite actual más conocido se debe a Fox y Sudakov, que logra r_ind(H;q) ≤ 2^ck3, donde k es el número de vértices de H y c es una constante que depende únicamente de q.

Hipergrafías

Podemos extender la definición de números de Ramsey inducidos a d-hipergrafías uniformes simplemente cambiando la palabra graph en la instrucción a hypergraph. Además, podemos definir la versión multicolor de los números de Ramsey inducidos de la misma forma que en el subapartado anterior.

Sea H una d -hipergrafo uniforme con k vértices. Defina la función de la torre t_r(x) dejando que t₁(x) = x y para <span class="texhtml" i ≥ 1, t_i+1(x) = 2^t_i(x). Usando el método del contenedor de hipergrafía, 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.

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 grafos finitos, a menudo se le llama el "teorema de Ramsey infinito". 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.

Teorema. Vamos X ser un conjunto infinito y el color de los elementos X ⁽⁾ⁿ⁾ (los subconjuntos de X de tamaño nEn c diferentes colores. Entonces existe un subconjunto infinito M de X tal que el tamaño n subconjuntos de M todos tienen el mismo color.

Prueba: La prueba es por inducción sobre n, el tamaño de los subconjuntos. Para n = 1, la declaración es equivalente 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 cierto para n ≤ r, lo probamos para n = r + 1. Dada una coloración c de (r + 1) subconjuntos de elementos de X, vamos a a ₀ sea un elemento de X y sea Y = X {a₀}. Luego inducimos una c-coloreado de los subconjuntos de elementos r de Y, simplemente agregando a₀ a cada subconjunto de elementos r (para obtener un (r + 1)-subconjunto de elementos de X). Por la hipótesis de inducción, existe un subconjunto infinito Y₁ de Y tal que cada r-elemento subconjunto de Y₁ se colorea 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 consta de 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 (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 una cantidad infinita de valores de i(n) tales que este color será el mismo. Toma estos a_i(n)'s para obtener el conjunto monocromático deseado.

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

La versión infinita implica lo finito

Es posible deducir el teorema de Ramsey finito de la versión infinita mediante una prueba por contradicción. Supongamos que el teorema de Ramsey finito es falso. Entonces existen los enteros c, n, T tal que para cada entero k, existe una coloración c de [ k]⁽ⁿ⁾ sin un conjunto monocromático de tamaño T. Deje que C_k denote el c-colores de [k]⁽ⁿ⁾ 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]⁽⁾ⁿ⁾ (ignorando el color de todos los conjuntos que contienen k + 1) es un colorido en C_k. Define Ck1{displaystyle C_{k} {1} para ser los colores en C_k que son restricciones de coloración en C_{k+ 1}. Desde C_{k+ 1} no está vacío, tampoco está Ck1{displaystyle C_{k} {1}.

Del mismo modo, la restricción de cualquier coloración en Ck+11{displaystyle C_{k+1} {1} está dentro Ck1{displaystyle C_{k} {1}, permitiendo a uno definir Ck2{displaystyle C_{k} {2} como conjunto de todas esas restricciones, un conjunto no vacío. Continuar así, definir Ckm{displaystyle C_{k} {m} para todos los enteros m, k.

Ahora, para cualquier número entero k,

Ck⊇ ⊇ Ck1⊇ ⊇ Ck2⊇ ⊇ ⋯ ⋯ {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

SilencioCkSilencio≤ ≤ ck!n!()k− − n)!{displaystyle SilencioC_{k}}}}}

Se sigue que la intersección de todos estos conjuntos no es vacía, y sea

Dk=Ck∩ ∩ Ck1∩ ∩ Ck2∩ ∩ ⋯ ⋯ {displaystyle D_{k}=C_{k}cap C_{k} {1}cap C_{k} {2}cap cdots }

Entonces cada color en D_k es la restricción de una coloración en D_{k+ 1}. Por lo tanto, sin restricciones una coloración en D_k a una coloración en D_{k+ 1}, y continuando haciéndolo, uno construye una coloración de N()n){displaystyle mathbb {N} {n)} sin ningún conjunto monocromático de tamaño T. Esto contradice el teorema de Ramsey infinito.

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.

Hipergrafías

El teorema también se puede extender a las hipergrafías. Un hipergráfico m es un gráfico cuyos "bordes" son conjuntos de vértices m: en un gráfico normal, una arista es un conjunto de 2 vértices. El enunciado completo del teorema de Ramsey para las hipergrafías es que para cualquier número entero m y c, y cualquier número entero n₁, …, n_c, hay un número entero R(n ₁, …, n_c; m) tal que si los hiperbordes de un m-hipergrafía de orden R(n₁, …, n_c; m) están coloreados con c diferentes colores, luego para algunos i entre 1 y c, la hipergrafía debe contener una subm completa -hipergráfico de orden n_i cuyos hiperbordes son todos de color i. Este teorema generalmente se prueba por inducción en m, la 'hiper-ness' 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. Además, tenemos: R(4, 5; 3) ≥ 35, R(4, 6; 3) ≥ 63 y R(5, 5; 3) ≥ 88.

Gráficos dirigidos

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 gráfico completo con arcos dirigidos individualmente (también llamado "torneo") y con ≥ Q Los nodos contienen un subtorneo n-node 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 2-coloración de los bordes de un nodirigido con ≥ Z nodos, contiene un gráfico monocromático completo en n nodos. (El análogo dirigido de los dos arcos posibles colores son las dos direcciones de los arcos, el análogo de "monocromático" es "todo arco -las 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.

Cardenales de Ramsey

En términos del cálculo de partición el teorema de Ramsey se puede decir como א א 0→ → ()א א 0)kn{displaystyle aleph _{0}rightarrow (aleph _{0} para todos los finitos n y k. Un cardenal Ramsey, κ κ {displaystyle kappa }, es un gran cardenal definido axiomáticamente para satisfacer la fórmula relacionada: <math alttext="{displaystyle kappa rightarrow (kappa)_{2}^{κ κ → → ()κ κ )2.⋅ ⋅ {displaystyle kappa rightarrow (kappa)_{2} {omega }<img alt="{displaystyle kappa rightarrow (kappa)_{2}^{.

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 multigráfica 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 de las matemáticas inversas. 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 grandes cinco subsistemas. Sin embargo, sobre ZF, la versión gráfica es equivalente al lema clásico de Kőnig.