Entropía y algoritmos de conteo en grafos numerables
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).