UNAM
Usted está aquí: Inicio / Actividades académicas / Coloquios / Coloquio de Ciudad Universitaria / Actividades del Coloquio / Entropía y algoritmos de conteo en grafos numerables

Entropía y algoritmos de conteo en grafos numerables

Ponente: Raimundo Briceño
Institución: Universidad de Tel Aviv
Tipo de Evento: Investigación, Divulgación

Cuándo 18/09/2018
de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"
Agregar evento al calendario vCal
iCal

Dado un grafo finito, supongamos que queremos conocer su número de conjuntos independientes, es decir, la cantidad de subconjuntos de vértices que inducen un grafo sin aristas. Este es un problema complejo (#P-completo) y en algunos casos admite aproximaciones que son eficientes en función del tamaño del grafo y la precisión requerida. En esta plática estudiaremos lo siguiente: qué podemos decir cuando nuestro grafo es infinito? Para abordar esta pregunta, nos centraremos en grafos que emergen naturalmente al estudiar grupos numerables con ciertas propiedades especiales (a saber, amenabilidad y ordenabilidad) y definiremos una noción -la entropía- que dé cuenta del número de conjuntos independientes en un grafo infinito de manera razonable. A continuación, veremos que en ciertos casos la entropía admite una representación especial y útil para desarrollar algoritmos de aproximación, en donde elementos de dinámica, física estadística, teoría de grupos y combinatoria confluyen de modo espontáneo. Finalmente, intentaremos explicar cómo parte de estos resultados pueden extenderse a otros sistemas, generalizando resultados de Gamarnik-Katz (2009), Wang-Yin-Zhong (2014) y Marcus-Pavlov (2015).

archivado en: