Conjetura de Merino—Welsch.

Resumen: En 1999 Criel Merino y Dominic Welsh conjeturan que para cada grafo conexo sin loops ni puentes, se cumple que el número de spanning trees es menor que el máximo entre el número de orientaciones cíclicas y el número de orientaciones totalmente acíclicas.

Como estas tres cantidades son evaluaciones del polinomio de Tutte, esta pregunta puede ser formulada en el contexto más amplio de matroides no necesariamente gráficas

Luego de varios resultados parciales, la versión matroide fue des-probada la semana pasada, pero el contraejemplo no es simple ni viene de un grafo.

Vamos a repasar cual es el status actual de esta conjetura.

Posted on Nov 16, 2023 in Seminario de Grafos, Seminars