Usted está aquí: Inicio / Actividades / Seminarios / Seminario Preguntón de Matemáticas Discretas / Actividades / El problema de las dos trayectorias

El problema de las dos trayectorias

Ponente: Alan Arroyo
Institución: Universidad de Waterloo
Cuándo 08/01/2015
de 17:00 a 18:00
Dónde CINNMA (Casa Amarilla), Juriquilla, Querétaro
Agregar evento al calendario vCal
iCal

Dada una gráfica G y cuatro vértices especiales x, y, x', y'; el problema de las dos trayectorias consiste en decidir si en G hay dos trayectorias disjuntas que unan los pares (x, y), (x', y'). Inesperadamente, la solución a este problema tiene un sabor topológico: Decidir si una gráfica tiene o no dichos dos caminos es equivalente a decidir si la gráfica tiene un dibujo particular en el plano. Tomaremos esto de pretexto para introducir el problema del número de cruces, que básicamente es, encontrar para cada gráfica un dibujo en el plano con el menor número de cruces entre pares de aristas. El problema del número de cruces ha mostrado ser resistente al paso del tiempo; no obstante, recientemente se han dado resultados estructurales muy importantes. Uno de ellos es la clasificación de casi todas las gráficas 2-cruce-críticas de Bokal, B. Oporowski, R. B. Richter y G. Salazar. En un intento por terminar la clasificación, una caracterización de las gráficas que no tienen dos xy-, x'y'-trayectorias disjuntas sirvió como herramienta para cerrar más esta brecha. Siguiendo la dinámica preguntona, nos centraremos en explicar esta caracterización que es un puente entre un problema combinatórico y uno topológico.