Teoría de Ramsey

Teoría de Ramsey
Según la teoría de Ramsey, del total de estrellas del cielo nocturno, siempre podemos seleccionar un subconjunto de ellas para dibujar diferentes objetos como: un triángulo, un cuadrilátero, un paraguas o un pulpo.

La teoría de Ramsey, llamada así por Frank P. Ramsey, es un campo de las matemáticas que estudia las condiciones bajo las cuales el orden debe aparecer. Los problemas de la teoría de Ramsey son típicamente de la forma: ¿Cuántos elementos debe contener una estructura para garantizar la existencia de una propiedad particular?

El desorden completo es imposible
Theodore S. Motzkin[1]

Contenido

Ejemplos

Supongamos que n palomas han sido alojados en m nidos. ¿Cuán grande debe ser n, con respecto a m, para que podamos estar seguros de que cuando menos un nido contenga, al menos, dos palomas?. La respuesta esta dada por el Principio del palomar: si n> m, entonces al menos un nido tendrá al menos dos palomas. La teoría de Ramsey generaliza este resultado, como se explica a continuación.

Un resultado típico de la teoría de Ramsey se inicia con alguna estructura matemática que se corta en trozos. ¿Qué tan grande debe ser la estructura original con el fin de garantizar que al menos una de las piezas tenga una propiedad interesante dada?

Por ejemplo, consideremos un grafo completo de orden n, es decir, hay n vértices y cada vértice está conectado a todos los otros vértices por medio de una arista. Un grafo completo de orden 3 se llama triángulo. Ahora bien, cada arista puede tener uno de los siguientes colores: rojo o azul. ¿Qué tan grande debe ser n con el fin de garantizar que exista un triángulo azul o un triángulo rojo?. Resulta que la respuesta es 6. Véase el artículo sobre el teorema de Ramsey para una prueba rigurosa.

Otra manera de expresar este resultado es el siguiente: en cualquier actividad con al menos seis personas, hay tres personas que son mutuamente conocidas o mutuamente desconocidas. Véase el teorema de la amistad.

Este es un caso especial del teorema de Ramsey, que dice que para cualquier entero dado c, y dado los enteros n1,...,nc, existe el número: R(n1,...,nc), llamado número de Ramsey, tal que si las aristas de un grafo completo de orden R(n1,...,nc) se colorean con c colores distintos, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden ni cuyas aristas están todas coloreadas con el color i. El caso especial de arriba tiene c = 2 y n1 = n2 = 3.

Para dos colores y valores de r y s a lo sumo 10 se conocen los siguientes valores exactos y cotas:

r,s 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9 10
3 1 3 6 9 14 18 23 28 36 40–43
4 1 4 9 18 25 35–41 49–61 56–84 73–115 92–149
5 1 5 14 25 43–49 58–87 80–143 101–216 126–316 144–442
6 1 6 18 35–41 58–87 102–165 113–298 132–495 169–780 179–1171
7 1 7 23 49–61 80–143 113–298 205–540 217–1031 241–1713 289–2826
8 1 8 28 56–84 101–216 132–495 217–1031 282–1870 317–3583 331-6090
9 1 9 36 73–115 126–316 169–780 241–1713 317–3583 565–6588 581–12677
10 1 10 40–43 92–149 144–442 179–1171 289–2826 331-6090 581–12677 798–23556

Hay una simetría trivial con respecto la diagonal.

Esta tabla está extraida del survey Small Ramsey Numbers de Stanisław Radziszowski [1].

Para tres colores, el único valor exacto no trivial conocido es R(3,3,3)=17.

De idéntica forma se puede definir el número de Ramsey de grafos que no sean completos, conociéndose para dos colores y grafos con a lo más 5 vértices, todos los valores exactos salvo los dos casos formados por dos grafos completos con 5 vértices y por uno completo de 5 vértices menos una arista y uno completo de 5 vértices.

Resultados

Algunos resultados importantes de teoría de Ramsey son:

  • Teorema de Ramsey Infinito (1928). Si tenemos un conjunto infinito y distribuimos sus elementos en un número finito de cajas, entonces hay una caja que contiene infinitos elementos.
  • Teorema de Bolzano. Toda sucesión infinita de números reales contiene una subsucesión infinita creciente o decreciente.
  • Problema del final feliz (Erdős, Szekeres & Klein; 1933). Dados 5 puntos en el plano (de forma que cada 3 de ellos no sean colineales), hay cuatro que forman un cuadrilátero convexo.
  • Teorema de la amistad (Ramsey; 1928). En cualquier reunión de 6 personas, o bien 3 de ellas se conocen entre sí, o bien, 3 de ellas no se conocen entre sí.
  • Teorema de Erdős-Szekeres(1936). Si tenemos n2 + 1 números reales, n + 1 de ellos forman una sucesión monótona.
  • Teorema de van der Waerden (1927). Para todo par de enteros l y c, existe un N tal que, dada una progresión aritmética P de longitud a lo menos N (en un grupo aditivo Z), y si coloreamos la progresión P con c colores, entonces existe una sub-progresión aritmética Po monocromática de longitud l.
  • Teorema de Hales-Jewett (1963): Para enteros n y c, existe el número H de manera que las celdas de un cubo H-dimensional n×n×n×...×n son coloreados con c colores, debe existir una fila, columna, etc. de longitud n en donde sus celdas estan coloreadas con un solo color. Esto es, si se juega el tres en línea en un tablero-hipercubo de dimensiones suficientemente grandes, entonces no se puede terminar el juego en empate, no importando que tan grande sea n (la longitud de X ó 0 necesaria para ganar la partida), ni el número c de jugadores. El teorema de Hales-Jewett implica el teorema de Van der Waerden.
  • Teorema de Schur. Para todo número c, hay un N tal que si los números 1,2, ... , N son coloreados por c colores, existe un par de enteros x , y tal que x, y, x+y tienen el mismo color.

Naturaleza de los resultados

Los resultados en la teoría de Ramsey normalmente tienen dos características básicas. En primer lugar, generalmente no son constructivas, los resultados muestran la existencia de alguna estructura, pero no se da una receta o procedimiento para encontrarla (que no sea la Búsqueda de fuerza bruta). En segundo lugar, mientras los resultados de la teoría de Ramsey nos dicen que un objeto lo suficientemente grande deberá contener necesariamente una estructura dada, a menudo la prueba de estos resultados requiere que estos objetos sean enormemente grandes con límites que crecen de manera exponencial.

Problemas abiertos

  • Problema de Erdős-Szekeres: este problema corresponde a la generalización del problema del final feliz, y es:

N(n)=2^{n-2} -1 \,

  • Problema del Limite de Rk = R(k,k;2). Existe \lim_{k \to \infty} R_k ^{\frac{1}{k}} \;, y de existir ¿Cuál es su valor?

Véase también

Notas

  1. "S. A. Soman" (21 de agosto de 2008). "Computational Methods for Large Sparse Power Systems Analysis". pp. 31. 

Referencias

  • R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1990)
  • Landman and A. Robertson, Ramsey Theory on the Integers, Student Mathematical Library Vol. 24, AMS (2004)
  • F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc., Vol. s2-30, no 1 (1930),
  • P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math., Vol. 2, p. 463-470 (1935)
  • G. Boolos, J. P. Burgess and R. Jeffrey, Computability and Logic, Cambridge: Cambridge University Press. (1974, revised 2004)

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Ramsey Clark — Saltar a navegación, búsqueda Ramsey Clark, 1968 Ramsey Clark, nacido el 18 de diciembre de 1927, es un abogado que trabajó como attorney general bajo el presidente de los EEUU Lyndon B. Johnson en lo …   Wikipedia Español

  • Teoría de la decisión — La teoría de la decisión es una área interdisciplinaria de estudio, relacionada con casi todos los participantes en ramas de la ciencia, ingeniería principalmente la psicología del consumidor (basados en perspectivas cognitivo conductuales).… …   Wikipedia Español

  • JonBenét Ramsey — La sepultura de JonBenét en el Saint James Episcopal Cemetery de Marietta, Georgia …   Wikipedia Español

  • Frank P. Ramsey — Saltar a navegación, búsqueda Frank Plumpton Ramsey (22 de febrero, 1903 19 de enero, 1930) fue un matemático y filósofo inglés cuyos estudios y actividad docente tuvieron lugar en la Universidad de Cambridge. Hizo importantes contribuciones… …   Wikipedia Español

  • Teorema de la amistad — Los 78 grafos posibles de amigos extraños con 6 vértices. En cada grafo, las aristas de color azul/rojo muestran la relación mutua de amigos/extraños. El teorema de amigos y extraños o teorema de la amistad es un teorema en el campo matemático… …   Wikipedia Español

  • Coloración de grafos — Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible. En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del …   Wikipedia Español

  • Número de Graham — Este artículo está huérfano, pues pocos o ningún artículo enlazan aquí. Por favor, introduce enlaces hacia esta página desde otros artículos relacionados …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

  • Problema del final feliz — Saltar a navegación, búsqueda El problema del final feliz: Para todo conjunto de 5 puntos en posición general, contiene los vértices de un cuadrilátero convexo. En matemática, el problema del final feliz (nombrado así por Paul Erdős porque dio a… …   Wikipedia Español

  • Paul Erdős — Saltar a navegación, búsqueda Paul Erdős Paul Erdős en un seminario de estudiantes, Budapest, 1992 …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”