Váli Benedek: The Merino–Welsh Conjecture for Sparse and Dense Graphs

A directed graph is called acyclic if it contains no directed circuit, and totally cyclic if every arc belongs to a directed circuit. For a graph $G$, let $\tau(G)$, $a(G)$, and $c(G)$ denote, respectively, the numbers of spanning trees, acyclic orientations, and totally cyclic orientations of $G$. The Merino–Welsh conjecture states that $\tau(G)\leq \max{a(G),c(G)}$ for every bridgeless and loopless multigraph $G$.

In this talk, we will briefly discuss the history of the conjecture and its connection with the Tutte polynomial. We will then present improved bounds on the edge density that guarantee the conjecture in the sparse and dense regimes.