UNAM

Pintando vértices de gráficas de Kneser

Encontraremos el número cromático de las gráficas de Knesser a partir de un teorema topológico, el teorema de Borsuk-Ulam.

Cuándo 09/05/2012
de 15:00 a 16:00
Dónde Sala Multimedia
Nombre
Teléfono de contacto 5532617715
Asistentes Alan Arroyo Guevara
Manuel Alejandro Juárez Camacho
Luis Eduardo García Hernández
Leonardo Ignacio Martínez Sandoval
Agregar evento al calendario vCal
iCal

En 1955, Martin Knesser planteó un retador problema de teoría de gráficas. El problema dice así:

Dado el conjunto (1,2,...,n), podemos tomar aquellos subcojuntos que tengan k elementos para alguna k. Consideraremos que cada uno de estos es vértice de una gráfica, y los conectaremos por una arista si no tienen elementos en comú.

Martin Knesser se preguntó cuántos colores se necesitan para pintar los vértices de esta gráfica de modo que no haya dos adyacentes del mismo color.

Sorprendentemente, este problema con un sabor totalmente combinatorio fue resuelto finalmente por Lazslo Lovasz en 1978 utilizando un brillante argumento topológico y el teorema de Borsuk-Ulam. En 2002, Joshua Green, un estudiante universitario simplificó elegantemente la prueba. Es esta versión la que presentaremos.

La historia de este problema muestra cómo las distintas áreas de las matemáticas están interconectadas en las maneras más fantásticas.

Se dice que hay un Libro en el cual Dios tiene escritas las pruebas más hermosas de cada teorema matemático.

Paul Erdos, el matemático brillante del siglo 20, era uno de los que creían en El Libro. Él, Martin Aigner y Gunter Ziegler comenzaron a hacer un esbozo de algunas pruebas que podrían formar parte de este libro. Tras la muerte de Erdos, el trabajo fue continuado por Aigner y Ziegler y desembocó en uno de los libros más astutos y sorprendentes: Proofs from the Book.

Este libro es un paseo sensacional por las distintas pruebas de El Libro en temas como Teoría de Números, Análisis, Combinatoria, Probabilidad y Geometría.

La idea de este seminario es exponer varios de los capítulos del libro Proofs from the Book.