Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

1 de Septiembre de 2014
Lógica matemática

Grafos, Ramsey y el teorema de compacidad

Cómo demostrar la existencia de una función que no sabemos calcular.

INVESTIGACIÓN Y CIENCIA

En la columna del mes de junio hablamos sobre la siguiente generalización infinita del teorema de Ramsey:

Si X es un conjunto numerable infinito y a cada miembro de [X]2 le asignamos uno de m colores diferentes, entonces X contiene un subconjunto monocromático infinito.

Recordemos que, dado un conjunto X, [X]2 denota el conjunto de subconjuntos de que contienen exactamente dos elementos. Por otro lado, decimos que un subconjunto Y de X es monocromático si, dada una asignación de colores a los miembros de [X]2, todos los elementos de [Y]2 son de un mismo color.

Allí también mencionamos la existencia de una versión finita del teorema de Ramsey. Si Sn denota el conjunto de los n primeros números naturales, Sn = {1  ,  2  ,  ...  ,  n}, la versión finita nos dice que:

Para cualesquiera m y k, existe un número n tal que, si coloreamos cada elemento de [Sn]2 con uno de m colores distintos, siempre encontraremos un subconjunto monocromático con, al menos, k elementos.

Y, en particular:

Para todo k, existe un número n tal que, si coloreamos los elementos de [Sn]2 con uno de dos colores diferentes, encontraremos un subconjunto monocromático con k elementos.

Artículos relacionados

Puedes obtener el artículo en...

¿Tienes acceso?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.