Teoremas de Ramsey
No Thumbnail Available
Date
2021
Authors
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
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.
Description
Keywords
Conjunto monocromático, Coloración, Grafo.