Programa : Matemáticas del azar. Gestionar la complejidad modelando las incertidumbres

Ludena

15 de diciembre 2017
Sede de la Universidad de Cartagena - Centro Histórico     (dirección)

Conferencias en homenaje a Didier Dacunha-Castelle: Matemática Estadística y Compromisos

Conferencista : Carene Ludeña - Universidad Jorge Tadeo Lozano. Bogotá. (co-autores: Miguel Méndez, Nicolas Bolívar)

Algunas aplicaciones de la teoría de descomposición modular de gráfos

Las descomposiciones de estructuras finitas se han estudiado en diferentes ramas de las matemáticas discretas durante
más de 40 años. En 1967, T. Gallai dio un teorema de descomposición principal para gráfos simples que ha dado lugar a una
sólida literatura sobre el tema. Estos trabajos dan relaciones entre la caracterización de ciertas propiedades de gráfos y
algoritmos de optimización sobre gráfos. Sin embargo, aparentemente no ha habido mucha conexión entre las
descomposiciones de gráfos y las aplicaciones en probabilidad y estadística. En esta charla ofreceremos una breve
descripción de la teoría general, brindaremos una perspectiva interesante sobre cómo se ve la descomposición de gráfos para
los modelos de gráfos aleatorios comunes y discutiremos un modelo de gráfo basado en esta noción.

Some applications of modular decomposition theory of graphs

Decompositions of finite structures have been studied in different branches of discrete mathematics for over 40 years. In 1967, T. Gallai gave a prime decomposition theorem for simple graphs which has given rise to a robust literature on the subject, namely related to characterization of certain graph properties and optimization algorithms over graphs. However, there has apparently not been much connection between graph decompositions and applications in probability and statistics. In this talk we will give a brief overview of the general theory, provide some interesting insight on what graph decomposition looks like for common random graph models and discuss a graph model based on this notion.