Skip to content

More on the Merino-Welsh conjecture

March 27, 2013

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 m = 2(n-1) — 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!

Advertisements
4 Comments leave one →
  1. March 27, 2013 7:48 pm

    Hi Gordon
    For how large n have you tested the conjecture for all graphs not covered by the theorem of Thomassen?

    • Gordon Royle permalink*
      March 28, 2013 10:40 am

      Hi Klas..

      I think just 10 vertices.

      Mostly I’ve looked at the multigraphs with exactly 2n-2 edges, and I think I stopped after processing the 41 million 10-vertex 18-edge multigraphs.

      But this was before I knew that a minimal counterexample must have every edge in a series or parallel class of size 2 or 3 and if I add that restriction then it would be possible to go further.

      For matroids, already calculating the rank 5, size 10 matroids is a massive task.

  2. March 29, 2013 2:42 am

    Hello !

    I have a few questions related to this problem!

    1. Is the link to the paper correct? Somehow I cannot access it through the link.

    2. As with the number of spanning trees there is an analogous recurrence relation for computing the number of acyclic and totally cyclic orientations of a graph. We have an efficient way to compute the number of spanning trees of a graph – is the same true for he number of acyclic and totally cyclic orientations of a graph? Is there a determinant analog here as well? If not, how did you compute these quantities when testing the conjecture?

    3. Have you perhaps also tested the conjecture that every 3-connected cubic graph has at most 7^{n/2}/n^c acyclic orientations?

    • Gordon Royle permalink*
      March 29, 2013 9:12 am

      The link has been fixed.

      If P is not equal to NP, then there is no efficient algorithm to compute either the totally cyclic or acyclic orientations of a graph. This is due to the seminal results of Jaeger, Vertigan and Welsh showing exactly which evaluations of the Tutte polynomial can be computed efficiently. We used the Tutte polynomial code due to Haggard, Pearce and myself to compute the Tutte polynomials and then just evaluated them at (0,2), (1,1) and (2,0).

      No, I haven’t tested anything about the acyclic orientations. The trouble is that these conjectures about “for some c” don’t really translate to explicit small cases. I guess I could try to identify the 3-connected cubic graphs with “fewest” acyclic orientations and see where that leads.

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: