More on the Merino-Welsh conjecture
I’ve just posted a paper entitled “The Merino-Welsh Conjecture holds for Series-Parallel Graphs” to the arxiv which proves precisely the assertion given in the paper’s title. This paper resulted from Steve Noble’s visit here last year, where we worked quite hard on this conjecture, and in fact I blogged about the problem then. The conjecture is that the number of spanning trees of a graph is dominated either by the number of acyclic orientations or by the number of totally cyclic orientations.
Previous results on the Merino-Welsh conjecture had proved the result for either very sparse graphs (where the number of spanning trees is dominated by the number of acyclic orientations) or very dense graphs (where the number of spanning trees is dominated by the number of totally cyclic orientations) regardless of the graph’s structure. However for intermediate-sized graphs — in particular those with — the graph structure counts, and there is a subtle interplay between the numbers of the two types of orientations.
Series-parallel graphs are always a great test case, because there is a natural decomposition of a series-parallel graph into smaller series-parallel graphs that provides an ideal inductive framework for a vast range of applications. For us, it provides enough structure to be able to keep track of the numbers of spanning trees and both types of orientation. Not entirely precisely, but enough to identify certain series-parallel graphs that cannot form part of a minimal counterexample to the conjecture. Working systematically, it was possible to ultimately exhaust all the possibilities for graphs that might be part of a minimal counterexample, thereby showing that this hypothetical counterexample cannot actually exist.
On one hand, I rather like this paper because the approach to coping with the interaction between the parameters seems novel and interesting, but on the other hand it relies heavily on the very constrained construction steps allowed in building series-parallel graphs and so will be almost impossible to generalise to larger classes!