Tutte Polynomials and Magnitude Functions

Tutte Polynomials and Magnitude Functions:

Last summer in Barcelona, Joachim Kock floated the idea that there might be a connection between two invariants of graphs: the Tutte polynomial and the magnitude function. Here I’ll explain what these two invariants are, I’ll give you some examples, and I’ll ask for your help in understanding what the magnitude function tells us.

The Tutte polynomial of a graph is old and well-understood. It turns a graph G into a polynomial T G in two variables, with natural number coefficients:

T G(x,y)∈ℕ[x,y].

The magnitude function of a graph is new and ill-understood. It turns a graph G into a rational function μ G in one variable, with rational coefficients:

μ G(q)∈ℚ(q).

It can also be expanded as a power series with integer coefficients:

μ G(q)∈ℤ[[q]].

I can’t figure out what the relationship between the two is — if any — or what information is contained in the magnitude function. It’s exasperating! I’ll be very pleased if someone can shed light on the situation.

In this post, “graphs” are always going to be finite and undirected. But some of the time I’ll allow loops and multiple edges, and some of the time I won’t. I’ll say which I’m doing.

(Formally, a graph with loops and multiple edges consists of a finite set V, a finite set E, and a map E→(V×V)/S 2. Here (V×V)/S 2 is the quotient of V×V by the obvious action of the group S 2 of order 2; it can be seen as the set of subsets of V of cardinality 1 or 2. A graph without loops or multiple edges consists of a finite set V and a subset E⊆V×V that, seen as a relation on V, is symmetric and irreflexive.)

The Tutte polynomial

The Tutte polynomial knows a lot about a graph. It knows how many edges the graph has, how many maximal forests it contains, and how many ways there are to colour each of its vertices from a palette of 38 colours without ever giving the same colour to adjacent vertices. It’s related to the Potts model in statistical physics and the Jones polynomial of knot theory.

I’ll give you the definition in a moment, but first we need some terminology.

For this part, graphs will be allowed to have loops and multiple edges. Given an edge e of a graph G, there are two fundamental operations we can perform:

• Deletion. The graph G−e is simply G with the edge e removed (but the vertices left untouched).
• Contraction. The graph G/e is formed from G by first removing e, then identifying the two vertices that it used to join.

An edge e is called a bridge if G−e has more connected-components than G, and a loop if it joins a vertex to itself.

The Tutte polynomial T G(x,y)∈ℕ[x,y] of a graph G is characterized by the following two conditions:

• T G=T G−e+T G/e if e is neither a bridge nor a loop;
• T G(x,y)=x by ℓ if G consists of b bridges, ℓ loops, and no other edges.

It takes some work to prove that there’s any polynomial with these two properties, since in the first condition there are usually many different edges e we could choose. But this form of the definition has the advantage that it provides a nice algorithm for calculating Tutte polynomials. For instance, here’s a picture from Wikipedia of the algorithm at work:



The conclusion is that if G is the five-vertex graph at the top of the tree then

T G(x,y)=x 3+2x 2+y 2+2xy+x+y.

The magnitude function

I’ll say twice what the magnitude function of a graph is: once for people who know what the magnitude of a metric space is, and once for people who don’t. In this part, graphs are not allowed to have loops or multiple edges — or more exactly, they could do, but adjoining or deleting loops or duplicate edges doesn’t make any difference to the magnitude function.

First, here’s the explanation for if you know about magnitude of metric spaces. Every finite metric space A has a magnitude function t↦∣tA∣, where tA is A scaled up by a factor of t and the bars indicate magnitude. (This “function” may have a finite number of singularities.) We can turn a graph G into a metric space by taking the points to be the vertices and the distance between two vertices to be the number of edges in a shortest path joining them. The magnitude function of a graph is the magnitude function of the resulting metric space. It will be convenient to make the substitution q=e −t and write μ G(q)=∣tG∣.

Now here’s a direct explanation.

List the vertices in some order: v 1,…,v n. (The choice of order won’t affect anything.) Let d ij be the number of edges in a shortest path from v i to v j (assuming there is one). Let Z G(q) be the square matrix over ℚ[q] whose (i,j)-entry is q d ij, or 0 if there is no path from v i to v j.

We’re going to want to invert Z G(q), so let’s consider its determinant. It’s a polynomial in q. Also, Z G(0)=I, so detZ G(0)=1; hence detZ G(q) is not the zero polynomial. It follows that the matrix Z G(q) is invertible over ℚ(q), the field of rational functions with rational coefficients. We define

μ G(q)∈ℚ(q)

to be the sum of all n 2 entries of the inverse matrix Z G(q) −1. This is the magnitude function of the graph G.

It’s a fact that the magnitude function of a graph can always be expanded as a power series with integer coefficients. This is a special property of μ G: your average rational function over ℚ is merely a Laurent series with rational coefficients.

(The key to the proof is that the constant term of the polynomial detZ G(q) is 1, which is invertible in ℤ. It follows that 1/detZ G(q) can be expanded as a power series over ℤ. Hence μ G(q) can be too.)

What does the magnitude function tell us about a graph?

I’ll come clean: I have no direct evidence that the magnitude function of a graph tells us anything interesting about it. However, in several other settings, magnitude and related invariants have proven to be very fruitful, producing important quantities associated to topological spaces, metric spaces, sets, groupoids, orbifolds, associative algebras, etc. So it’s a good bet that it’s going to be fruitful for graphs too.

Moreover, in the particularly interesting setting of metric spaces, magnitude has been particularly reluctant to give up its secrets. So, the lack of obvious interpretation for the magnitude function of a graph doesn’t make me think it’s less likely to be interesting: it makes me wonder what it’s hiding!

But what does the magnitude function tell us? It’s hard to see. For instance, take the 4-cycle C 4:



We have

μ C 4(q)=4(1+q) 2=4−8q+12q 2−16q 3+⋯.

How can we interpret this? It’s tempting to try to understand a power series over ℤ as the generating function of something, but what? Even ignoring the negative signs, what’s being counted here?

For another example, take G to be a forest with vertex-set V and edge-set E. Then

μ G(q) =∣π 0(G)∣+∣E∣1−q1+q =∣V∣−2∣E∣q+2∣E∣q 2−2∣E∣q 3+⋯,

where π 0(G) is the set of connected-components of G. What is this function telling us about the graph?

Tutte vs. magnitude

In some ways, the information contained in the magnitude function seems to be complementary to that contained in the Tutte polynomial. For example:

• the magnitude function knows how many vertices a graph has, but the Tutte polynomial doesn’t (at least if we’re allowing disconnected graphs)
• the Tutte polynomial knows how many edges a graph has, but the magnitude function doesn’t (at least if we’re allowing multiple edges).

In other ways, the magnitude function and the Tutte polynomial seem more similar than complementary. Let’s consider some families of graphs known to have the same Tutte polynomial:

• all trees with a given number of edges have the same Tutte polynomial; they also have the same magnitude function.
• The three graphs known as the bull, the (3,2)-tadpole and the cricket (shown below) all have the same Tutte polynomial; they also all have the same magnitude function.

In fact, it’s consistent with the evidence below that for connected graphs, the Tutte polynomial determines the magnitude function.

However, in examples such as those above, I see no way of transforming the Tutte polynomial into the magnitude function. One way of proving that such a transformation exists would be to use the so-called “universal property” of the Tutte polynomial. (I don’t know whether it’s a universal property in the categorical sense.) Roughly, this says that Tutte determines magnitude if μ G is determined by μ G−e and μ G/e whenever e is an edge of G that is neither a bridge nor a loop. But I don’t know whether that’s the case; I suspect not.

All in all, I don’t think the magnitude function is likely to be a specialization of the Tutte polynomial, even for connected graphs. In other words, the magnitude function seems to contain extra information about the graph that Tutte doesn’t. But what?

Properties and examples

I’ll now try to convey an idea of how the magnitude function behaves, by way of some basic properties and examples. For comparison, I’ll show the behaviour of the Tutte polynomial alongside.

1. Disjoint unions Any two graphs G and H have a disjoint union G+H.
   
   Tutte: T G+H=T GT H.
   
   Magnitude: μ G+H=μ G+μ H.
2. Joins Suppose we have a graph G with a distinguished vertex x, and another graph H with a distinguished vertex y. We can form a new graph G*H, the “join”, by first taking G+H then identifying x with y.
   
   Tutte: T G*H=T GT H.
   
   Magnitude: μ G*H=μ G+μ H−1.
3. Knows the number of vertices?
   
   Tutte: no, if we’re allowing graphs to have multiple connected-components: see “discrete graphs” below. Yes, if we stick to connected graphs: then the degree of T G(x,y) as a polynomial in x (with y regarded as constant) is ∣V∣−1.
   
   Magnitude: yes: it’s μ G(0).
4. Knows the number of edges?
   
   Tutte: yes: T G(2,2)=2 ∣E∣. (Here and later, I’ll use E for the set of edges of a graph G, and V for the set of vertices.)
   
   Magnitude: no, if we’re allowing loops or multiple edges, since adding a loop or a duplicate edge doesn’t change the magnitude. Yes, if we stick to graphs without loops or multiple edges: the coefficient of q in the power series expansion of μ G(q) is −2 times the number of edges. In other words, ∣E∣=−μ′ G(0)/2. (See this comment, and the reply to it, below.)
5. Discrete graphs Let G be a discrete graph, that is, one with no
   edges at all.
   
   Tutte: T G(x,y)=1.
   
   Magnitude: μ G(q)=∣V∣.
6. Forests Let G be a forest, that is, a disjoint union of trees.
   
   Tutte: T G(x,y)=x ∣E∣.
   
   Magnitude: μ G(q)=∣π 0(G)∣+∣E∣⋅1−q1+q=∣V∣−2∣E∣q+2∣E∣q 2−2∣E∣q 3+⋯.
7. Cycles Let C n be the n-cycle:
   
   
   
   Tutte: T C n(x,y)=x n−1+x n−2+⋯+x+y=x n−xx−1+y
   
   Magnitude: μ C n(q)=n(q−1)q ⌊(n+1)/2⌋+q ⌈(n+1)/2⌉−q−1. (Those are the floor and ceiling functions in the denominator.) This naturally splits into two cases. If n is even then
   
   μ C n(q)=n(q−1)(q n/2−1)(q+1).
   
   If n is odd then
   
   μ C n(q)=n(q−1)2q (n+1)/2−q−1.
8. Complete graphs Let K n be the complete graph on n vertices (that
   is, every vertex is joined to every other by a single edge).
   
   Tutte: it seems that there is no neat formula for T K n, and
   that computing it is
   nontrivial.
   A single example:
   
   T K 4(x,y)=(x 3+y 3)+(x 2+y 2)+2(x+y) 2+2(x+y).
   
   Magnitude: μ K n(q)=n1+(n−1)q.
9. Complete bipartite graphs I’ll just do one. Let K 2,3 be this
   graph:
   
   
   
   Tutte: T K 2,3(x,y)=x 4+2x 3+3x 2+3xy+y 2+x+y.
   
   Magnitude: μ K 2,3(q)=5−7q(1+q)(1−2q 2)=5−12q+22q 2−36q 3+56q 4−⋯.
10. Bull, tadpole, cricket These three graphs all have the same
    Tutte polynomial and the same magnitude function:
    
     
     
    
    
    Let G be any one of them.
    
    Tutte: T G(x,y)=x 2(x 2+x+y).
    
    Magnitude: μ G(q)=5+5q−4q 2(1+q)(1+2q)=5−10q+16q 2−28q 3+52q 4−⋯.
    
    There’s no mystery as to why they all have the same Tutte
    polynomial. It’s simply because all three graphs are the join of C 3
    and two copies of the graph consisting of a single edge, and the Tutte
    polynomial of the join of a bunch of graphs is determined by their
    individual Tutte polynomials. The same goes for the magnitude
    functions.
11. Petersen graph Don Knuth observed that the Petersen
    graph “serves as a
    counterexample to many optimistic predictions about what might be true for
    graphs in general”. So even though I don’t have a prediction to be
    counterexampled, I thought I’d better check its magnitude function
    for disturbing behaviour. I’m not disturbed.
    
    
    
    Tutte: according to
    Wikipedia, the
    Petersen graph P has Tutte polynomial
    
    T P(x,y)= 36x+120x 2+180x 3+170x 4+114x 5+56x 6+21x 7+6x 8+x 9 +36y+84y 2+75y 3+35y 4+9y 5+y 6+168xy+240x 2y+170x 3y+70x 4y +12x 5y+171xy 2+105x 2y 2+30x 3y 2+65xy 3+15x 2y 3+10xy 4.
    
    Magnitude: μ P(q)=101+3q+6q 2=10−30q+30q 2+90q 3−450q 4+⋯.
    
    Actually, this does defeat a conjecture! Having read the previous examples,
    you might have wondered whether the coefficients of the
    magnitude function (when expanded as a power series) always alternate
    in sign. The Petersen graph shows that they don’t.
12. Linear codes I’m going to be very sketchy here. (If you want to
    know more, just say so in the comments.) Let F be a finite field. A
    linear code over F is simply a linear subspace of F n, for some n.
    
    Tutte: Every linear code C has a Tutte polynomial T C. (More
    exactly, the definition of Tutte polynomial extends smoothly from
    graphs to matroids, and every linear code gives rise to a matroid.)
    But also, with every linear code is associated an important polynomial
    called its “weight enumerator”. It’s a fact that the weight enumerator
    of a code C is determined by its Tutte polynomial together with the
    cardinalities of C and F n.
    
    Magnitude: On the other hand, every linear code can be regarded as a
    metric space (with the Hamming distance inherited from F n), and so
    has a magnitude function. It’s a fact that the weight enumerator of a
    code is essentially the same thing as its magnitude function; each
    determines the other once you know the cardinality of C.
    
    So in the case of linear codes, the Tutte polynomial (plus the
    cardinalities of C and F n) determines the magnitude function.

Questions

The magnitude function of a graph remains mysterious to me. I have very
little intuition for what it means. I understand the magnitude of a
metric space moderately well for subspaces of ℝ n, but metric
spaces coming from graphs are about as un-Euclidean as can be.

Here are some questions I’d like answering.

1. What information can be read off from the magnitude function of a graph?
2. Is there a useful way to regard the power series expansion of the
   magnitude function as a generating function? In other words, do the
   coefficients count something?
3. It’s consistent with the evidence above that two graphs with
   the same Tutte polynomial and the same number of vertices have the same
   magnitude function. Is it true?
4. It’s consistent with the evidence above that two connected graphs with
   the same Tutte polynomial have the same magnitude function. Is it true?

DIGITAL JUICE