Blogia
Tio Petros

Versión infinita del teorema de Ramsey

Comentábamos hace unos días que el Teorema de Ramsey en su versión inicial es finitista: no hace mención alguna de conjuntos infinitos. SIn elbargo existe una versión infinita del mismo, cuyo enunciado podría ser el siguiente:

Dado un conjunto infinito numerable A, si coloreamos todos sus subconjuntos de k elementos con r colores, entonces existe un subjonjunto B infinito tal que todos sus subconjuntos de k elementos llevan el mismo color.

En el lenguaje de los grafos ( lo cual, recordemos, sólo es posible cuando los subconjuntos son de tamaño k=2), tendríamos:

Si en un grafo completo infinito numerable coloreamos sus aristas con r colores, necesariamente tendremos un subgrafo monocromático de tamaño infinito.

Lo realmente extraordinario es que este teorema nos facilita una demostración inmediata del famoso Teorema de Bolzano .

Este teorema dice que Toda sucesión infinita de números reales contiene una subsucesión infinita que es monótona (creciente o decreciente)

La demostración es interesantísima por su simplicidad:

Sea A tal sucesión infinita de reales. Coloreemos todos sus subconjuntos de tres elementos {a,b,c}con cuatro colores, dependiendo de la disposición de los tres números que forman el subconjunto:

Color 1: si los tres elementos forman una secuencia creciente

Color 2: si el central es el mayor de los tres

Color 3: si el central es el menor de los tres

Color 4: si los tres elementos forman una secuencia decreciente.

No hay más posibilidades, de forma que nos bastan cuatro colores para asignar un color a cada uno de los subconjuntos de tamaño tres de la sucesión.

Pues bien: la versión infinita de Ramsey nos garantiza la existencia de un subconjunto infinito de A tal que todos sus subconjuntos de tres elementos son del mismo color. Es evidente que ese color sólo puede ser el 1 ó el 4, que corresponderían a la subsucesión creciente o decreciente del teorema de Bolzano.

Creo sinceramente que quien no se sorprenda con esta demostración, es que no ha entendido nada; o tiene la sensibilidad matemática de un celentéreo.
¿Y esta publicidad? Puedes eliminarla si quieres
¿Y esta publicidad? Puedes eliminarla si quieres

10 comentarios

Yazu -

Tío Petros, tengo dudas propias de mi ignorancia en el tema, pero, ¿cual sería el orden subyacente en la disposición de los decimales de un número irracional?, por ejemplo Pi.
Porque la explicación hipersimplificada de la teoría de Ramsey dice "El desorden completo es imposible" entonces la disposición de los decimales de un número irracional debería tener un orden.

EDWIN -

d q supuesto parto para demostrar de manera explicita el teorema de los 4 colores

Giselle -

Intente acceder a mipagina.cantv.net/jhnieto1/tc.pdf pero el resultado fue que no existe. Por favor como pudiera encontrar informacion concreta y clara respecto al teorema de Ramsey? y seria de gran ayuda si me ayudaran a plantear alguna aplicacion practica
Saludos
Giselle

xor and -

Hola:
Caigo por aqui de casualidad, googleando informacion sobre el teorema de Ramsey (accesible para mortales no matemáticos como yo). Mi inquietud o confusión es: es aplicable en algo el teorema de Ramsey a los numeros primos ? - Me explico: si en un conjunto suficienteme grande de numeros primos (cercano al infinito) se puede hallar una sucesion racional ( con racional quiero decir que cumplan alguna condicion común )

Ricardo -

Donde puedo encontrar alguna referencia que mencione algo parecido a lo siguiente: En comparación con el infinito cualquier cantidad finita tiende a ser cero o nada"

yandhery -

¿CUAL ES LA DEMOSTRACION DEL TEOREMA DE RAMSEY QUE DICE: QUE TODO GRAFO CON SEIS O MAS VERTICES CUMPLE: CONTIENE UN TRIANGULO?

Tio Petros -

Hola Anónimo:
Una demostración del teorema de Ramsey la tienes en el excelente documento PDF siguiente:
mipagina.cantv.net/jhnieto1/tc.pdf

En las páginas 86-88 se desarrolla la demostración que pides.

Dicha demostración se apoya en el llamado principio de Dirichlet (conocido vulgarmente como "el principio del palomar"), y se desarrolla en varias fases: se demuestra para r=1, como un corolario del principio arriba citado, luego para casos más complicados, por inducción. Creo que es una demostración difícil (para mi lo es). Un saludo.

Anónimo -

Hola Tio Petros, me alegro de haberlo entendido, ahora sólo falta una cosa, y es la demostración (del Teorema de Ramsey), lo he intentado, pero no lo he conseguido, de modo que espero que no tardes mucho en explicárnosla, o al menos en dar alguna indicación de cómo puede demostrarse.

Un saludo

Tio Petros -

Hola Pepe. Lo has entendido perfectamente, por eso lo has explicado tan bien. Se trata de TODOS los subconjuntos de k elementos de B que todos los subconjuntos de k elementos de B, que tienen los elementos colocados en el orden de la numeración de A.
En caso contrario, no tendría sentido las cuatro diferenciaciones que hemos hecho para asignar los cuatro colores.
La omisión es mía, el mérito de explicarlo, tuyo.
Un saludo.

pepe -

Pues yo no se si soy un celentéreo o no he entendido nada, pero no es lo mismo un conjunto numeraBLE que un conjunto numeraDO, ni es lo mismo TODOS los subconjuntos de k elementos de B que todos los subconjuntos de k elementos de B, que tienen los elementos colocados en el orden de la numeración de A.

Un saludo
¿Y esta publicidad? Puedes eliminarla si quieres