Ponente: Raimundo Briceño
Institución: Universidad de Tel Aviv
18/09/2018 de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"
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)