A Las Vergnas Conjecture

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 {e=vw} has exactly two non-zero entries, both equal to one, in rows {v} and {w}. Viewed as a matrix over {GF(2)}, the row space and null space of this matrix are called the cocycle space {C} and the cycle space {C^\perp} of the graph. The non-zero vectors in {C}, called the cocycles, are the (characteristic vectors of the) cut-sets of the graph, while the non-zero vectors in {C^\perp}, 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 {C \cap C^\perp}. (A coding theorist would call this the hull of the linear code {C}.)

If {T(x,y)} is the Tutte polynomial of the graph, then it is well known that

\displaystyle T(-1,-1) = \pm \ 2^{d(C\cap C^\perp)}

where {d(C\cap C^\perp)} 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 {y=x}, and so he considered the polynomial {D(x) = T(x,x)} and (for reasons unknown to me) its derivates {D'}, {D''}, {D'''}, etc. all evaluated at the point {x=-1}. While he could not find an interpretation for {D'(-1)}, {D''(-1)}, {\ldots} he noticed that the sequence of values generated appeared to be divisible by unexpectedly high powers of {2}, with each differentiation reducing the exponent of {2} by at most one. So he made the following conjecture:

If {G} is a graph with bicycle dimension {d}, and {D(x) = T(x,x)} is its diagonal Tutte polynomial, then  {2^{d-k} \mid D^{(k)}(-1)} for all {k < d}.

For example, for the graph {K_6}, we have

\displaystyle D(x) = x^{10}+5 x^9+15 x^8+41 x^7+88 x^6+172 x^5+300 x^4+390 x^3+236 x^2+48 x

and so {D(-1) = -16}, {D'(-1) = 80}, {D''(-1) = -220}, {D'''(-1) = 270}, which are indeed divisible by {16}, {8}, {4} and {2} respectively.

However a quick computer search revealed that as it stands, the conjecture is false — the graph {K_8} 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 {G} is a planar graph with bicycle dimension {d}, and {D(x) = T(x,x)} is its diagonal Tutte polynomial, then  {2^{d-k} \mid D^{(k)}(-1)} for all {k < d}.

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 \Delta Y graphs.


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 )

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: