Publicación:

Teoremas de Ramsey

Resumen

Se demuestran los teoremas clásicos de Ramsey y dos generalizaciones de estos conocidas como el teorema de Nash-Williams y el teorema de Galvin. Sean S un conjunto y p,r enteros positivos. Una coloración es una función c : [S]? > (1,...,r), donde [S]”representa el conjunto de los subconjuntos de p elementos de S. Decimos que un conjunto A € S es monocromáticoo homogéneo si se tiene que c es constante en [4]”. Cuando S es infinito, el teorema infinito de Ramsey nos diceque para toda coloración de [S]” existe un conjunto infinito A C S tal que A es monocromático. El teorema finitode Ramsey es un resultado similar para conjuntos finitos, y se prueba a partir del teorema infinito de Ramsey. Parala explicación del teorema finito de Ramsey se muestra la relación que existe entre las coloraciones de [5]? y las coloraciones de los segmentos de un grafo completo con n vértices, donde |S| =n. Probaremos que los teoremas de Galvin y Nash-Williams son generalizaciones del teorema infinito de Ramsey, esdecir, que se pueden probar estos teoremas a partir del teorema infinito de Ramsey. Los teoremas de Nash-Williamsy Galvin son resultados acerca de los conjuntos monocromáticos de una familia arbitraria .2 de subconjuntosfinitos de N. Para el teorema de Galvin, la definición de conjunto monocromático se altera de manera abrupta,pues esta no va a depender de ninguna coloración de .4, solo de la familia .7. Por lo tanto en este caso tiene más sentido utilizar el término homogéneo.