Contando árboles generadores

Ponente(s): Criel Merino Lopez

Cada gráfica conexa contiene una subgráfica generadora que es un árbol. Contar los árboles generadores en una gráfica conexa etiquetada es un tema clásico en combinatoria enumerativa y un método general para calcular de manera eficiente este invariante gráfico ya se conocía desde mediados del siglo XIX. El tema principal de la charla es una lista de fórmulas conocidas para el número de árboles de algunas familias de gráficas, comenzando por la famosa fórmula de Cayley (n + 1)^(n − 1) para las gráficas completas. Como acompañamiento, damos algunas generalizaciones de estas fórmulas mediante el uso de diferentes refinamientos del invariante que nos llevan a los grupos abelianos, a los complejos simpliciales y al polinomio de Tutte.