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.
4 comentarios
joseph -
sancho -
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 -
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 -
¿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:)