[general_dat] Seminario de Grafos - Lunes 26/10 a las 14 hs

[Lucía Busolini]

Buenas tardes!

Escribo para invitarlos al próximo encuentro del seminario de grafos que
será el* lunes 26/10 a las 14 hs. en la sala de reuniones 2119 del Pabellón
0+infinito*.

*Orador:* German Rud

*Título:* De patrones prohibidos a parámetros de ancho en grafos

*Resumen:*

Muchos problemas en teoría de grafos son difíciles de resolver en general,
pero pueden volverse más tratables cuando restringimos la estructura de los
grafos que consideramos. Una forma de estudiar esa estructura consiste en
ordenar los vértices de un grafo y prohibir la aparición de ciertas
configuraciones locales, llamadas patrones. Estas restricciones permiten
caracterizar clases conocidas de grafos, como los grafos bipartitos y los
bosques.


En esta charla presentamos una forma de construir parámetros de ancho a
partir de patrones prohibidos coloreados. La idea es buscar un orden de los
vértices y una partición de los mismos en la menor cantidad posible de
clases, de manera que se evite un determinado patrón. Estos parámetros
pueden interpretarse como una medida de qué tan lejos está un grafo de
pertenecer a la clase asociada al patrón original, el valor uno corresponde
exactamente a los grafos de esa clase.


Nos concentraremos en tres familias de patrones relacionadas con grafos
bipartitos, estrellas y bosques. Mostraremos cómo algunos de los parámetros
obtenidos se relacionan con problemas clásicos, como coloreo de grafos y
vertex cover. También estudiaremos la complejidad computacional de los
problemas asociados y presentaremos algunas de las ideas detrás de las
reducciones que permiten demostrar resultados de NP-completitud.


Son todos bienvenidos y si están interesados en participar frecuentemente
en este seminario, los invitamos a unirse a nuestro grupo de Telegram:
https://t.me/+RkVxwjjIdiE1Yjkx y visitar la página del seminario:
https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos
Para quienes no puedan estar presencialmente, también está la oportunidad
de participar virtualmente, pasaremos el link de Meet por el grupo de
Telegram.

Cualquier duda o consulta pueden escribirnos.

¡Nos vemos!

Saludos,
Lucía