Pintando vértices de gráficas de Kneser
When |
May 09, 2012
from 03:00 PM to 04:00 PM |
---|---|
Where | Sala Multimedia |
Contact Name | Leonardo Ignacio Martínez Sandoval |
Contact Phone | 5532617715 |
Attendees |
Alan Arroyo Guevara Manuel Alejandro Juárez Camacho Luis Eduardo García Hernández Leonardo Ignacio Martínez Sandoval |
Add event to calendar |
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.