Skip to content

The Merino-Welsh Conjecture

April 23, 2012

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 2^m orientations for an m-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 n-vertex graph has (n-1) edges. We denote these three quantities \tau(G) for trees, \alpha(G) for acyclic orientations and \alpha^*(G) 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 G is a multigraph with no bridges or loops, then \tau(G) \le \max(\alpha(G),\alpha^*(G)).

There are various stronger versions of this conjecture, such as having \tau(G) 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 \alpha(G) 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 G has at least 4n-4 edges, then \tau(G) < \alpha^*(G).
  • If G is a graph (not multigraph) with at most 16n/15 edges, then \tau(G) < \alpha(G).

Obviously there is a huge gap between these bounds. It is conceivable however that there is a range of low densities where \alpha(G) dominates \tau (i.e. regardless of the structure of G) and a range of higher densities where \alpha^*(G) dominates \tau, and that these two ranges overlap. In fact, Thomassen asked whether m = 2n-2 edges could possibly be the dividing point, so that any multigraph with at most 2n-2 edges has \alpha(G) < \tau(G) and any multigraph with at least 2n-2 edges has \tau(G) < \alpha^*(G). Unfortunately this is not true, as there are graphs with exactly 2n-2 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 T is the Tutte polynomial of G, then:

  • \tau(G) = T(1,1)
  • \alpha(G) = T(2,0)
  • \alpha^*(G) = T(0,2)

So if G 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 T(1,1) \le \max(T(2,0),T(0,2)) 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 f(z) = T(1+z,1-z) and consider the behaviour of this single-variable polynomial for z \in [-1,1]. In particular, it is quite possible that f(z) is convex throughout its domain, except for the case where G is a tree with every edge doubled, in which case f(z) 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 M is a matroid with no loops or co-loops with Tutte polynomial T, then T(1-z,1+z) is convex on the range z \in [-1,1] unless M is a direct sum of pairs of parallel elements.

Advertisements
2 Comments leave one →
  1. Jernej permalink
    April 23, 2012 9:10 pm

    For those of you who are interested in the conjecture and the results of Thomassen, here is a lecture by him about the results

    http://vod.mathnet.or.kr/sub2_2.php?no=1643&key_year=x&key_s_title=KAIST+Discrete+Math+Seminar

    • Gordon Royle permalink*
      April 24, 2012 10:34 pm

      Thanks for that .. nice link!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: