I’m in France at the moment, having spent the last week at a workshop on matroid computation at Henry Crapo’s house in the tiny village of La Vacquerie et Saint Martin de Castries, but now I’ve moved on to Paris for a week.
I had been intending to drop in to see Michel Las Vergnas, but it seems that I somehow missed the sad news that he died in January. Although I only met him once, a few years go in Barcelona, we had frequently communicated about an exasperating conjecture of his.
A quick bit of background: start with the vertex-edge incidence matrix of the graph, such that the column corresponding to the edge has exactly two non-zero entries, both equal to one, in rows and . Viewed as a matrix over , the row space and null space of this matrix are called the cocycle space and the cycle space of the graph. The non-zero vectors in , called the cocycles, are the (characteristic vectors of the) cut-sets of the graph, while the non-zero vectors in , called the cycles, are the subgraphs in which every vertex has even degree. (Notice that this notion of cycle is considerably broader than the usual graph-theoretic notion.) A set of edges that is simultaneously a cycle and a cocycle is called a bicycle, and the bicycle space is the vector space . (A coding theorist would call this the hull of the linear code .)
If is the Tutte polynomial of the graph, then it is well known that
where is the dimension of the bicycle space.
Among many other things, Las Vergnas was interested in a variety of evaluations of the Tutte polynomial along the diagonal where , and so he considered the polynomial and (for reasons unknown to me) its derivates , , , etc. all evaluated at the point . While he could not find an interpretation for , , he noticed that the sequence of values generated appeared to be divisible by unexpectedly high powers of , with each differentiation reducing the exponent of by at most one. So he made the following conjecture:
If is a graph with bicycle dimension , and is its diagonal Tutte polynomial, then for all .
For example, for the graph , we have
and so , , , , which are indeed divisible by , , and respectively.
However a quick computer search revealed that as it stands, the conjecture is false — the graph is a counterexample. But I was slightly intrigued by now, so I searched a bit harder and noticed that no matter how hard I tried, I could not find any planar graphs that did not have the property of the conjecture. So I emailed Michel and we revised the conjecture to
If is a planar graph with bicycle dimension , and is its diagonal Tutte polynomial, then for all .
And that’s basically where it stands. Although it is not a particularly important statement in itself, if it is true, then surely there must be some more combinatorial information to be wrung from the Tutte polynomial if only we knew how to look at it in the right way!
In fact, I think that planar graphs is not the precisely correct class to be working with, but rather some class that includes planar graphs; something perhaps like graphs.