The Merino-Welsh conjecture is an intriguing conjecture relating three graphical parameters, namely the numbers of spanning trees, acyclic orientations and totally cyclic orientations of a graph.
First recall the definitions of these terms: an orientation of a graph is an assignment of directions to the edges of the graph (thus there are orientations for an -edge graph), and an orientation is called acyclic if the resulting directed graph contains no directed cycle and, at the opposite extreme, totally cyclic if every directed edge is contained in a directed cycle. A spanning tree is a connected subgraph containing every vertex of the graph, but containing no cycles; it is easy to see that a spanning tree of an -vertex graph has edges. We denote these three quantities for trees, for acyclic orientations and for totally cyclic orientations. Then we have the conjecture, due to serial conjecturer Dominic Welsh, and his former student Criel Merino.
Conjecture (Merino, Welsh) If is a multigraph with no bridges or loops, then .
There are various stronger versions of this conjecture, such as having less than the arithmetic or geometric mean of the other two parameters, but all seem equally difficult and equally unsolved.
Speaking very loosely, if the graph is somewhat sparse, with relatively few edges given the number of vertices, then acyclic orientations are favoured and so tends to dominate the number of spanning trees, while if the graph is dense, then the number of totally cyclic orientations tends to dominate. The best partial results on the conjecture are essentially about graphs at one end of the spectrum or the other, where one or other of the parameters dominates so much that relatively coarse, though ingenious, approximations are sufficient to demonstrate this fact. So, the following results are known, due to Carsten Thomassen:
- If the bridgeless multigraph has at least edges, then .
- If is a graph (not multigraph) with at most edges, then .
Obviously there is a huge gap between these bounds. It is conceivable however that there is a range of low densities where dominates (i.e. regardless of the structure of ) and a range of higher densities where dominates , and that these two ranges overlap. In fact, Thomassen asked whether edges could possibly be the dividing point, so that any multigraph with at most edges has and any multigraph with at least edges has . Unfortunately this is not true, as there are graphs with exactly edges that have more spanning trees than acyclic orientations.
In some sense, although it may work, this approach seems rather unsatisfactory — the conjecture concerns the interplay of two dual parameters whereas the known results essentially focus on just one of the two. This follows because all three parameters are actually evaluations of the Tutte polynomial of the graph at various points. In fact, if is the Tutte polynomial of , then:
So if is planar, then it has the same number of spanning trees as its planar dual, but the numbers of acyclic and totally cyclic orientations swap round. Of course, we don’t need to restrict ourselves to planar graphs – the Tutte polynomial is defined for any matroid, graphic or otherwise, and so the conjecture can be made just as without any reference to the interpretations of these evaluations. So really, rather than crude approximations based on edge or element densities, it would be much more satisfying if there were some structural reason for the truth of the conjecture that exploited this duality – perhaps some way of defining a map from spanning trees to orientations that could be massaged into a suitable injective map.
As well as evaluating the Tutte polynomial at specific points to get numbers, we can get a variety of 1-variable polynomials from it by partially specifying the values, and lots of common graph and matroid polynomials (chromatic, flow, reliability etc) arise in this way. So we could define and consider the behaviour of this single-variable polynomial for . In particular, it is quite possible that is convex throughout its domain, except for the case where is a tree with every edge doubled, in which case is actually constant. Conde and Merino said that this would make a “rather more daring strengthening of the conjecture” which I have paraphrased to incorporate matroids:
Conjecture (Conde-Merino, but for graphs only) If is a matroid with no loops or co-loops with Tutte polynomial , then is convex on the range unless is a direct sum of pairs of parallel elements.