Roots of flow polynomials and Welsh’s conjecture

I recently received an email from Jesus Salas who has finally succeeded in the monster calculation of the flow polynomial of the generalized Petersen graph P(119,7) and discovered that it has real roots at q=5.000019767 and q=5.165342442, thereby throwing wide-open the question of whether there is any upper bound on the real flow roots.

To understand the significance of this, let’s backtrack a little and talk about the Birkhoff-Lewis conjecture on chromatic roots of planar graphs.

The chromatic polynomial of a graph G is the function P_G(q) that counts the number of proper q-colourings of G when q is a positive integer. It is well known that this function is actually a polynomial and so, even though it has no particular combinatorial significance it is entirely possible to compute the value of the chromatic polynomial for any real or complex number. The chromatic roots of a graph are then just the complex roots of the chromatic polynomial.

The 5-colour theorem says that any planar graph G has a proper 5-colouring or, equivalently, that P_G(5) > 0. Birkhoff and Lewis introduced the idea of evaluating the chromatic polynomial at non-integral values and proved that if G is a planar graph then P_G(x) \ge 0 for all x \ge 5, thereby strengthening the 5-colour theorem. They conjectured even more:

Birkhoff-Lewis Conjecture

If G is a planar graph, then P_G(x) \ge 0 for all x \ge 4.

This conjecture really initiated the entire study of real chromatic roots, and it is embarrassing that 60 years later, we still don’t know the answer!

Anyway, the main point here is that the real chromatic roots of planar graphs are bounded above – by 4 if their conjecture is true, but at least by 5. This is no accident as it can be shown that the real chromatic roots of any proper minor-closed family of graphs are bounded above, and planar graphs are just one such family.

Now let’s move to the flow polynomial F_G(q) which counts the nowhere-zero Z_q-flows of G – a nowhere-zero Z_q-flow is an assignment of non-zero values from Z_q to the edges of G (which have been arbitrarily oriented) so that at each vertex, the inward flow is equal to the outward flow. As this is a polynomial we can again evaluate it at any real or complex value, find its roots and so on. Analogously to the chromatic case, we call the roots of the flow polynomial the flow roots of the graph.

The flow polynomial of G is often described as being “dual” to the chromatic polynomial because if G is planar, then up to a factor of q, the flow polynomial of G is the chromatic polynomial of its planar dual. So immediately from Birkhoff and Lewis, we get that the real flow roots of planar graphs are bounded above. But we can talk about flow polynomials for any graph, not just planar graph and so we can ask whether the real flow roots of all graphs are bounded above.

Making this seem likely is that there is a beautiful duality/analogy between colouring theory for planar graphs and flow theory for arbitrary graphs. There is a dual/analgoue of the 5-colour theorem – namely Seymour’s celebrated theorem that every bridgeless graph has a nowhere-zero 6-flow, and while there is no flow version of the 4-colour theorem, the nowhere-zero 5-flow conjecture (due to Tutte) is an outstanding open problem.

So it is  hardly surprising that Dominic Welsh made the obvious dual/analogue of the Birkhoff-Lewis conjecture:

Welsh’s Conjecture

If G is a bridgeless graph, then F_G(x) \ge 0 for all x \ge 4.

Well, one thing is a bit surprising about Welsh’s conjecture – the beautiful duality between the colouring/flow theories always comes with a shift-by-one in the parameters – the 4-colour theorem versus the 5-flow conjecture etc.  So it was a bit surprising to see the value “4” in this conjecture, and a couple of years ago I was delighted to find some counterexamples to his conjecture – actual graphs with real flow roots above 4 – and replaced the conjecture with what I thought should be true.

Modified Welsh’s conjecture

If G is a bridgeless graph, then F_G(x) \ge 0 for all x \ge 5.

I was happy with this conjecture because it seemed to tie up all the loose ends just nicely, not that I had any clue how to prove it.

But I had reckoned without Jesus Salas and Jesper Jacobsen – they work on the boundary of mathematics and statistical physics and are experts on the computation of these type of graphical polynomials (which arise in statistical physics from the partition function of the q-state Potts model). Usually though, they develop techniques for the kinds of graphs of interest to statistical physicists, i.e. graphs, usually lattices, with some sort of repeating structure, where “transfer matrix” techniques can be applied.

One of the counterexamples to the original conjecture of Welsh is the generalized Petersen graph P(16,6) and although it’s not much of a lattice, it does have a sort of repeating structure if you look at it the right way. Anyway, to cut a long story short, Jesus and Jesper worked out the relevant transfer matrices for certain families of generalized Petersen graphs, determined theoretically that a generalized Petersen graph of the form P(7k, 7) should have real flow roots converging to 5 from above, and finally after the above-mentioned mammoth computation, finally produced an actual example.

So, where to from here? What is the next sensible modification of Welsh’s conjecture? There doesn’t seem any particular reason to pick any other number as an upper bound. So perhaps the truth is that the real flow roots are actually unbounded!


Is there any upper bound on the flow roots of graphs?


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

Up ↑

%d bloggers like this: