Universidad Nacional de Educación a Distancia

Acceso a la portada del web UNED
asignatura master 2024

asignatura master 2025

COMBINATORIA DE LAS COLORACIONES

Código Asignatura: 21520011

PRESENTACIÓN Y CONTEXTUALIZACIÓN

COMBINATORIA DE LAS COLORACIONES
21520011
2024/2025
TÍTULOS DE MASTER EN QUE SE IMPARTE MÁSTER UNIVERSITARIO EN MATEMÁTICAS AVANZADAS
MICROMÁSTER EN MATEMÁTICAS AVANZADAS
CONTENIDOS
7,5
187,5
SEMESTRE 1
CASTELLANO

Se trata de exponer  algunos resultados importantes en la teoría de  Ramsey sobre coloraciones. Se trata de un campo matemático englobado dentro de la combinatoria.  Parafraseando a varios autores

hay numerosos teoremas en matemáticas que afirman, a grosso modo, que cualquier sistema de un cierto tipo siempre tiene un subsistema grande con más grado de organización que el sistema original.

Ilustremos esto con dos ejemplos:  En una reunión con al menos 2n-1 personas, al menos entre ellas tienen el mismo sexo.   

El segundo es un poco más complejo: Queremos saber si en un grupo de personas P1,...,Pn podemos encontrar al menos tres Pk,Pm,Pn que se conocen entre sí, o que ninguna de ellas se conoce entre sí. El ``sentido común'' nos dice que si el grupo es suficientemente grande, esto será así. La cuestión es, primero saber si esto es siempre cierto, y si eso es así, estimar al menor de esos números n.

El ejemplo que acabamos de explicar es un caso particular de  un principio matemático general, denominado Teorema de Ramsey, demostrado por el filósofo y matemático F. P. Ramsey, y que se puede decir es el origen de la teoría de las coloraciones.  El teorema de Ramsey y variaciones de él ha sido muy utilizado tanto en otras áreas de la matemática como, por ejemplo, en informática teórica (estudio de algoritmos) o en teoría de la información.

También se estudiarán resultados tipo Ramsey donde el orden deseado es geométrico o aritmético, como:

  • El Teorema de Hales-Jewett.  Coloraciones de palabras. Organización geométrica.

  • Teoremas de Van der Waerden y Folkman. Existencia de progresiones aritméticas largas y muchas sumas. Organización aritmética.

Dualizando los resultados, se estudiará el teorema de Ramsey dual.

Hay versiones infinitas de los resultados anteriores, aunque hay que precisar qué se quiere decir por infinita.  De hecho, algunos de los teoremas presentados anteriormente son consecuencia, via un argumento de compacidad, de su versión  infinita: 

  • El teorema de Ramsey infinito.
  • El teorema de Hindman (versión infinita del resultado de Folkman)

Este resultado tiene una demostración muy elegante utilizando los ultrafiltros idempotentes, otro de los objetivos de este curso.

Como principio general, las versiones infinitas de los resultados implican la finita por un argumento llamado de compacidad, que es otro de los objetivos. 

Existe también  otro tipo de versiones infinitas de los resultados anteriores. Para ilustrarlo mencionaremos el Teorema de Galvin-Prikry. En el teorema de Ramsey se colorean los subconjuntos finitos de cardinalidad exactamente d. ¿Se puede tener un resultado similar cuando se colorean los subconjuntos infinitos de números naturales?   El resultado que buscamos es el siguiente: ¿es cierto que para toda coloración finita de todos los subconjuntos infinitos de naturales  en uno de los colores tenemos un conjunto infinito A y todos sus subconjuntos infinitos? Este resultado es falso en general, aunque la coloración mala es "artificial", al estar construida utilizando el axioma de elección. Sin embargo, el resultado de Galvin y Prikry nos dice que para coloraciones definibles (en este caso, borelianas) el resultado es cierto. 

El curso finaliza analizando una demostración teorema de Galvin-Prikry, y que sirve para introducir los denominados espacios de Ramsey.