fbpx
Wikipedia

Teorema de Ramsey

Abril 28, 2022

En combinatoria el teorema de Ramsey establece que en cualquier esquema de color aplicado a un grafo de un grafo completo suficientemente grande, se hallarán subgrafos completos monocromáticos. Para dos colores, el teorema enuncia que para cualquier par de enteros positivos (r,s), existe al menos un entero positivo R(r,s) como aquel para cualquier grafo completo en R(r,s) vértices, cuyas aristas (o ramas) están coloreados de rojo o azul, existe un subgrafo completo de r vértices que es totalmente azul, o un subgrafo completo de s vértices que es totalmente rojo. R(r,s) representa un entero que depende conjuntamente de r y s. Se entiende que representa al entero más pequeño para el que el teorema aplica. A ese número se le llama número de Ramsey.

El teorema de Ramsey es fundacional en combinatoria. La primera versión de estos resultados fueron probados por F. P. Ramsey. Esto inició la teoría combinatoria, ahora llamada teoría de Ramsey, que busca regularidad en medio del desorden: condiciones generales para la existencia de subestructuras con propiedades regulares.

Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de solamente dos. Más precisamente, el teorema enuncia que por cualquier número dado de colores «c», y cualquier entero n1,...,nc, existe un número, R(n1, ..., nc), que si las aristas de un grafo completo de orden R(n1, ...,nc) se colorea con c colores diferentes, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden ni cuyas aristas son de color i. El caso especial de arriba donde c = 2 (y n1 = r y n2 = s).

Otra generalización se obtiene al considerar grafos que no sean completos. Son conocidos todos los valores de R(G1,G2) si G1 y G2 tienen a lo más 5 vértices salvo cuando G1 ó G2 es el grafo completo de 5 vértices y el otro es o bien el grafo completo de 5 vértices o bien el grafo completo de 5 vértices menos una arista.

Ejemplo: R(3,3)=6

 
2 colores en K5 con K3 no monocromático.

En el siguiente ejemplo, la fórmula R(3,3) provee una solución a la pregunta sobre el número mínimo de vértices que debe contener un grafo para asegurar que

  1. al menos tres vértices del grafo están conectados o,
  2. al menos tres vértices están desconectados.

Nótese que debido a la naturaleza simétrica del problema, R(r,s) produce la misma solución que R(s,r). Esto es aún más evidente en el ejemplo R(3,3) porque los valores de r y s son los mismos.

Supongamos que las aristas de un grafo completo de 6 vértices están coloreadas en rojo y verde. Al elegir un vértice v, vemos que hay 5 aristas incidiendo en él, y así, por el principio del palomar, al menos 3 de ellos deben ser del mismo color. Sin pérdida de generalidad podemos asumir que al menos 3 de estas aristas, que conectan con los vértices r, s y t son azules (si no lo son, intercámbiese azul con rojo en lo que sigue). Si alguno de las aristas (r, s), (r, t) o (s, t) es también azul, entonces tenemos un triángulo enteramente azul. Sino, entonces las tres aristas son rojas, y tenemos un triángulo enteramente rojo. Como este argumento funciona para cualquier esquema de color, cualquier K6 contiene un K3 monocromático, y entonces R(3,3) ≤ 6. La versión popular de esta demostración se conoce como teorema de la amistad.

Referencias

Bibliografía

  • Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1980). «A note on Ramsey numbers». J. Combin. Theory Ser. A (en inglés) 29: 354-360. .
  • Bohman, Tom; Keevash, Peter (2010). «The early evolution of the H-free process». Invent. Math. (en inglés) 181: 291-336. doi:10.1007/s00222-010-0247-x. .
  • Conlon, D. (2009). «A new upper bound for diagonal Ramsey numbers». Ann. of Math. (en inglés) 170: 941-960. doi:10.4007/annals.2009.170.941. .
  • Erdős, Paul (1947). «Some remarks on the theory of graphs». Bull. Amer. Math. Soc. (en inglés) 53: 292-294. .
  • Erdős, Paul; Szekeres, George (1935). «A combinatorial problem in geometry». Compositio Math. (en inglés) 2: 463-470. doi:10.1007/978-0-8176-4842-8_3. .
  • Exoo, G. (1989). «A lower bound for R(5,5)». Journal of Graph Theory (en inglés) 13: 97-98. doi:10.1002/jgt.3190130113. .
  • Graham, R.; Rothschild, B.; Spencer, J. H. (1990). Ramsey Theory (en inglés). Nueva York: John Wiley and Sons. .
  • Ramsey, F. P. (1930). «On a problem of formal logic». Proc. London Math. Soc. Series 2 (en inglés) 30: 264-286. doi:10.1112/plms/s2-30.1.264. .
  • Spencer, J. (1975). «Ramsey's theorem - a new lower bound». J. Combin. Theory Ser. A (en inglés) 18: 108-115. doi:10.1016/0097-3165(75)90071-0. .

Enlaces externos

  • .
  • Código lisp para determinar conjuntos de números de Ramsey.
  • Números de Ramsey en grafos directos
  • Weisstein, Eric W. «Número de Ramsey». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  •   Datos: Q918099
  •   Multimedia: Combinatorics

Abril 28, 2022
teorema, ramsey, combinatoria, teorema, ramsey, establece, cualquier, esquema, color, aplicado, grafo, grafo, completo, suficientemente, grande, hallarán, subgrafos, completos, monocromáticos, para, colores, teorema, enuncia, para, cualquier, enteros, positivo. En combinatoria el teorema de Ramsey establece que en cualquier esquema de color aplicado a un grafo de un grafo completo suficientemente grande se hallaran subgrafos completos monocromaticos Para dos colores el teorema enuncia que para cualquier par de enteros positivos r s existe al menos un entero positivo R r s como aquel para cualquier grafo completo en R r s vertices cuyas aristas o ramas estan coloreados de rojo o azul existe un subgrafo completo de r vertices que es totalmente azul o un subgrafo completo de s vertices que es totalmente rojo R r s representa un entero que depende conjuntamente de r y s Se entiende que representa al entero mas pequeno para el que el teorema aplica A ese numero se le llama numero de Ramsey El teorema de Ramsey es fundacional en combinatoria La primera version de estos resultados fueron probados por F P Ramsey Esto inicio la teoria combinatoria ahora llamada teoria de Ramsey que busca regularidad en medio del desorden condiciones generales para la existencia de subestructuras con propiedades regulares Una extension de este teorema se aplica a cualquier numero finito de colores en lugar de solamente dos Mas precisamente el teorema enuncia que por cualquier numero dado de colores c y cualquier entero n1 nc existe un numero R n1 nc que si las aristas de un grafo completo de orden R n1 nc se colorea con c colores diferentes entonces para algun i entre 1 y c debe contener un subgrafo completo de orden ni cuyas aristas son de color i El caso especial de arriba donde c 2 y n1 r y n2 s Otra generalizacion se obtiene al considerar grafos que no sean completos Son conocidos todos los valores de R G1 G2 si G1 y G2 tienen a lo mas 5 vertices salvo cuando G1 o G2 es el grafo completo de 5 vertices y el otro es o bien el grafo completo de 5 vertices o bien el grafo completo de 5 vertices menos una arista Indice 1 Ejemplo R 3 3 6 2 Referencias 3 Bibliografia 4 Enlaces externosEjemplo R 3 3 6 Editar 2 colores en K5 con K3 no monocromatico En el siguiente ejemplo la formula R 3 3 provee una solucion a la pregunta sobre el numero minimo de vertices que debe contener un grafo para asegurar que al menos tres vertices del grafo estan conectados o al menos tres vertices estan desconectados Notese que debido a la naturaleza simetrica del problema R r s produce la misma solucion que R s r Esto es aun mas evidente en el ejemplo R 3 3 porque los valores de r y s son los mismos Supongamos que las aristas de un grafo completo de 6 vertices estan coloreadas en rojo y verde Al elegir un vertice v vemos que hay 5 aristas incidiendo en el y asi por el principio del palomar al menos 3 de ellos deben ser del mismo color Sin perdida de generalidad podemos asumir que al menos 3 de estas aristas que conectan con los vertices r s y t son azules si no lo son intercambiese azul con rojo en lo que sigue Si alguno de las aristas r s r t o s t es tambien azul entonces tenemos un triangulo enteramente azul Sino entonces las tres aristas son rojas y tenemos un triangulo enteramente rojo Como este argumento funciona para cualquier esquema de color cualquier K6 contiene un K3 monocromatico y entonces R 3 3 6 La version popular de esta demostracion se conoce como teorema de la amistad Referencias EditarBibliografia EditarAjtai Miklos Komlos Janos Szemeredi Endre 1980 A note on Ramsey numbers J Combin Theory Ser A en ingles 29 354 360 Bohman Tom Keevash Peter 2010 The early evolution of the H free process Invent Math en ingles 181 291 336 doi 10 1007 s00222 010 0247 x Conlon D 2009 A new upper bound for diagonal Ramsey numbers Ann of Math en ingles 170 941 960 doi 10 4007 annals 2009 170 941 Erdos Paul 1947 Some remarks on the theory of graphs Bull Amer Math Soc en ingles 53 292 294 Erdos Paul Szekeres George 1935 A combinatorial problem in geometry Compositio Math en ingles 2 463 470 doi 10 1007 978 0 8176 4842 8 3 Exoo G 1989 A lower bound for R 5 5 Journal of Graph Theory en ingles 13 97 98 doi 10 1002 jgt 3190130113 Graham R Rothschild B Spencer J H 1990 Ramsey Theory en ingles Nueva York John Wiley and Sons Ramsey F P 1930 On a problem of formal logic Proc London Math Soc Series 2 en ingles 30 264 286 doi 10 1112 plms s2 30 1 264 Spencer J 1975 Ramsey s theorem a new lower bound J Combin Theory Ser A en ingles 18 108 115 doi 10 1016 0097 3165 75 90071 0 Enlaces externos EditarRamsey Home Investigacion de Radziszowski sobre pequenos numeros de Ramsey Codigo lisp para determinar conjuntos de numeros de Ramsey Numeros de Ramsey en grafos directos Weisstein Eric W Numero de Ramsey En Weisstein Eric W ed MathWorld en ingles Wolfram Research Numero de Ramsey en Geoffrey Exoo Una prueba de que R 3 6 18 Datos Q918099 Multimedia Combinatorics Obtenido de https es wikipedia org w index php title Teorema de Ramsey amp oldid 142399877, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos