[general_dat] Seminario de Grafos - Lunes 13/4 a las 14 hs

[Lucía Busolini]

¡Buenos días a todos!

Esperamos que hayan tenido unas lindas vacaciones y estén con ganas de
volver al seminario de grafos. Este año (o al menos este cuatrimestre), nos
encontraremos los *lunes a las 14 hs en la sala de reuniones 2119 del
Pabellón 0+infinito*.
La primera charla será este *lunes 13/04*.

*Expositor:* Min Chih Lin (Oscar)

*Título:* Reconocimiento de grafos cuasi-cluster y multipartitos acotados

*Resumen:*

> Estudiamos las clases de grafos [image: latexImage0.png] y [image:
> latexImage1.png], que modelan grafos globalmente cercanos a ser,
> respectivamente, completamente [image: latexImage2.png]-multipartitos o
> agrupables en [image: latexImage2.png] cliques, permitiendo al
> mismo tiempo una cantidad acotada de desviación local por vértice. Estas
> clases refinan los problemas clásicos de coloreo y clustering mediante la
> introducción de un parámetro [image: latexImage4.png] que controla la
> cantidad de inconsistencias locales que puede presentar cada vértice.

Para valores fijos de [image: latexImage2.png] y [image: latexImage4.png],
> se sabe que la clase [image: latexImage0.png]admite caracterizaciones
> mediante una familia finita de subgrafos inducidos prohibidos. Sin embargo,
> salvo para algunos pocos valores pequeños de los parámetros, dichas
> caracterizaciones son puramente existenciales y no conducen a algoritmos
> implementables de reconocimiento. Cerramos esta brecha mostrando que los
> grafos suficientemente grandes de [image: latexImage0.png] exhiben un
> fenómeno estructural nítido: por encima de un umbral natural de tamaño, una
> clase de color completa se vuelve identificable algorítmicamente utilizando
> únicamente información local de grados.

Esta observación da lugar a un algoritmo de reconocimiento simple y
> completamente  constructivo que extrae iterativamente clases de color
> forzadas y reduce el problema a instancias residuales de tamaño acotado. El
> algoritmo resultante corre en tiempo [image: latexImage0.png],  donde [image:
> latexImage9.png] depende únicamente de los parámetros fijos.

Mostramos además que el mismo principio de extracción se aplica, bajo
> complementación, a la clase [image: latexImage0.png] de grafos
> cuasi-cluster, obteniendo así algoritmos de reconocimiento eficientes y
> constructivos también en ese contexto.

Nuestros resultados muestran cómo propiedades estructurales puramente
> existenciales pueden transformarse en algoritmos explícitos y eficientes, y
> destacan el papel de las cotas sobre desviaciones locales como mecanismo
> para recuperar tractabilidad en problemas de descomposición que, en
> general, son difíciles.


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 .

Cualquier duda o consulta pueden escribirnos.

¡Nos vemos pronto!

Saludos,
Lucía