Lunes 5 de mayo, 16:00 hs, Instituto de Computación
Expone: Pablo Romero (Universidad de la República)
Resumen:
Hace poco más de tres décadas, Jason Brown y Charles Colbourn conjeturaron que las raíces de todo polinomio de confiabilidad pertenecen al disco cerrado de radio unidad del plano complejo. En la literatura surgieron contraejemplos a dicha conjetura. a noción esencial para la construcción de contraejemplos es la función de separabilidad de grafos con 2 terminales. En esta charla se presentará el concepto de la función de separabilidad de grafos con 2 terminales, junto con una noción de maximización uniforme de dicha función que fue introducida por Jason Brown e Isaac McMullin en 2023. Luego, introduciremos el concepto de separabilidad local de grafos con 2 terminales. Veremos un teorema de caracterización de grafos localmente más separables seguido de un teorema de inexistencia de grafos uniformemente más separables, dando una respuesta parcial a un problema abierto enunciado por Jason Brown e Isaac McMullin en 2023. Se menciona una generalización del concepto de separabilidad para múltiples terminales. Finalmente, se discutirán problemas abiertos en el área y su posible aplicabilidad en el diseño de sistemas anti-spam.