Blogia
Tio Petros

El teorema de Ramsey

El teorema de Ramsey A diferencia de la mayoría de los post de este blog, este, y quizás los que sigan exige un poco más de esfuerzo para su comprensión. No obstante, creo que vale la pena. Vamos a intentar entender un teorema difícil. Eso nunca NUNCA es gratis. Además, vamos a intentarlo sin utilizar matemáticas, o casi. Esta vez, el paseo que les propongo es más escarpado. Pero coincidirán conmigo en que el placer de alcanzar la cumbre es proporcional a la pendiente dejada a nuestras espaldas.

Naturalmente, la ilustración que encabeza este post, (que es el enunciado del Teorema de Ramsey ) es una provocación. No es esperable que nadie entienda absolutamente nada al leer una cosa así. Ni siquiera nos hemos puesto de acuerdo con la nomenclatura que vamos a utilizar para entenderlo. Sin embargo, he preferido ponerlo para incentivar al posible lector a avanzar en la comprensión de este enunciado y de sus consecuencias, cosa que haremos poco a poco.

Toda la dificultad de comprender el teorema está motivada precisamente por la gran virtud del mismo: su enorme generalidad. Vayamos viendo poco a poco qué quiere decir. De esta forma seremos capaces de ir saboreando el aroma de los resultados a lo Ramsey .

Pero antes, estableceremos algún convenio de notación:

Hablaré de conjuntos, clases, colecciones y grupos en sentido coloquial: en este contexto querrán decir exactamente lo mismo: agrupaciones de cosas.

Dado un conjunto X, definimos /X/ con el número de elementos de X. Lo habitual es representar esto último con barras verticales, no oblicuas, pero el sistema de este blog no parece permitirme tales barras .

PR(X) es el conjunto de todos los subconjuntos de X que tienen exactamente R elementos.

En el enunciado podemos leer que descomponemos PR(X) en una serie de trozos disjuntos. Esto quiere decir exactamente lo que parece: si tenemos un conjunto original X de , por poner un ejemplo, 20 elementos, P2(X) será la colección de todos los subconjuntos de dos elementos de X, o el conjunto de todas las parejas posibles de elementos de X, que son exactamente (20 x 19)/2=190 posibles. El enunciado nos está diciendo que agrupemos estas 190 parejas en k grupos, no necesariamente iguales. Sin ninguna restricción. Las colecciones de parejas de nuestro ejemplo son los A1,..., Ak del enunciado.

Hacer esto equivale a poner una etiqueta a cada agrupación de parejas. En efecto, lo mismo es decir:

”este conjunto de parejas pertenece a la colección Aj de parejas” que decir

”a este conjunto de parejas le pongo la etiqueta número j”, o aún más gráficamente :

”a este conjunto de parejas le asigno el color j”.

¿Está claro de momento? No está de más recordar que si hablo de “parejas” estoy haciendo R=2 en el enunciado de Ramsey, por simplificar la exposición; lo mismo podíamos hablar en general de tríos o n-tuplas de elementos de X.

Así pues, en el enunciado tenemos un conjunto X, tenemos la colección PR(X) de todos sus subconjuntos de un tamaño prefijado (R) (repetimos: cuando R=2, entonces tenemos parejas), y en este último grupo tenemos coloreados todas las agrupaciones con k colores.

Ahora estamos en condiciones de entender qué es lo que afirma el teorema de Ramsey :

Afirma que si escribimos tantos números enteros (a1,... ak) como colores hemos usado, sean estos cualesquiera, entonces, si X es suficientemente grande , existe en el seno del conjunto X un pedazo o subconjunto que llamaremos Y que cumple alguna de estas propiedades:

1.- Y tiene tantos elementos como el primero de los k números que hemos escrito, y todos sus subconjuntos de tamaño R son del primer color.

2.- Y tiene tantos elementos como el segundo de los k números que hemos escrito, y todos sus subconjuntos de tamaño R son del segundo color.

...

k.- Y tiene tantos elementos como el último de los k números que hemos escrito, y todos sus subconjuntos de tamaño R son del último color.

El tamaño crítico para asegurar el necesario cumplimiento de una de estas k cláusulas es función exclusiva de los k números distintos que hemos escrito, y del tamaño R de los subconjuntos que hemos coloreado, y no depende de nada más. Este tamaño crítico mínimo se denomina número de Ramsey R(a1,... ak; r).

Cuando comenzábamos el post decíamos que no era esperable que nadie entendiera el enunciado del teorema en una primera lectura. Ahora, lo más probable es que la cosa haya mejorado tan sólo un poquito. Seguiremos hincándole el diente al tema en lo sucesivo, viendo conexiones con aspectos inesperados.

Lo más importante es que este teorema nos asegura la existencia de un reducto estructurado (monocromático en la nomenclatura que hemos empleado, pero a nadie se le escapa que el "color" puede ser cualquier cosa)de tamaño arbitrariamente grande en el seno de un conjunto, a condición de que éste sea lo suficientemente grande.

La semana que viene seguiremos comprendiendo este teorema, y sobre todo, sus implicaciones.

Feliz fin de semana para los lectores de este blog.
¿Y esta publicidad? Puedes eliminarla si quieres
¿Y esta publicidad? Puedes eliminarla si quieres

4 comentarios

joseph -

recien lei un libro inspirado en la vida de paul erdös("el hombre que solo amaba los numeros"_año 2000) y en él encontre un ejemplo clásico de la teoria de ramsey explicado en términos de invitados a una fiesta.apuntaban que se habia descubierto hasta el caso de cuantos son necesarios para garantizar que al menos cuatro invitados sean conocidos o desconocidos entre si(fue el propio erdös), quisiera que me ayude a averiguar si desde ese momento a la fecha se ha logrado plantear una solucion para el caso de cinco(esta solo estimado: entre 43 y 49)o mas invitados. gracias

sancho -

La forma en que se explica este teorema es muy buena, sintesis y belleza se entremezclan para explicar uno de los más importantes resultados de la teoria de las combinatoria. Este es de los teorema que conozco uno de los que más nos entusiama para continuar en el camino de seguir desarrollando la teoria y que pone de manifiesto cuales son los limites de las computadoras de hoy, con respecto a la imaginacion de los hombres.
Por ejemplo conocemos que
R(5,5;2) existe pero somos incapaces con las supercomputadoras encontrar este valor lo unico que se conoce es que esta acotado que pensar entonces de R(5,5,5,5,5,4)para poner un ejemplo. Sigamos pues poniendo interes en la teoria para poder llegar más rapido a las conquista del conocimiento

Tute -

Coincido con José. Pero es aún más complicado que un profesor que sepa explicar lo pueda hacer de tal forma que todos en un curso muy numeroso llegen a vislumbrar la posibilidad de entenderlo a tal grado.

Así y todo; sería una injusticia que yo entienda este teorema - en el remoto caso que lo comprenda - y Tío Petros no reciba un premio. Nada muy exagerado, un Nobel en Educación o algo así ;)

jose -

La diferencia entre tú y mis profesores de universidad es que te esfuerzas para que la gente entienda las cosas que explicas. En verdad es un alivio entrar a un sitio de matemáticas y que te interese.
¿Qué es mejor, saberse una demostración de memoria (teorema 1 - demostración - corolario - teorema 2 -demostración - ...) o entender el teorema que se demuestra? No sé, lo que sí sé es cuál de las dos cosas es más fácil para el profesor. gr...

Y perdona que descargue aquí O:)
¿Y esta publicidad? Puedes eliminarla si quieres