What is the Tutte polynomial encoding?

Question

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about the graph, since there are examples of non-isomorphic graphs with the same Tutte polynomial.

My question is, what information exactly does the Tutte polynomial encapsulate? I'm aware of a few answers to this question, but I don't find any of them particularly satisfying. For instance, T_G(x,y) can be characterized as "the universal Tutte-Grothendieck invariant," but the definition of Tutte-Grothendieck invariants is just as unintuitive as the definition of the Tutte polynomial (because it's essentially the same definition!) One can also define the coefficients as counting certain spanning trees of G, but this doesn't make apparent the fact that the Tutte polynomial specializes to the chromatic polynomial, or the notion that it carries most of the information one can obtain via linear algebra methods.

So is there a nice way of thinking about what data about G the Tutte polynomial encodes?

ETA: Okay, here's a very rough conjecture. Suppose that there's some "computationally simple" (i.e., testing membership is in NP) class of graphs such that there are two connected graphs G, H with the same Tutte polynomial, and G is in the class and H is not. Then there are spanning trees S, T of G, H respectively, such that S is in the class and T is not.

This would mean, in a sense that I can't make entirely rigorous, that the information about a graph G not encoded in the Tutte polynomial is just information about the structure of spanning trees of G. (Update: As Kevin Costello points out in a comment, this idea appears to be severely limited by the existence of certain pairs of co-Tutte graphs. In particular, we would need to count spanning trees with multiplicity for it to have even a chance of being true.)

As stated, the above conjecture is false for trivial reasons. But is there a way of making it true, perhaps by requiring the property to be, in some sense, natural? Is there a broad notion of "graph properties" for which it is true? Can we at least state a conjecture along these lines which does seem to be true?

Answer 1

No-one so far has mentioned matroids. The Tutte polynomial encodes some of the information from the cycle matroid of the graph. Two graphs with the same cycle matroid (and number of vertices) have the same Tutte polynomials. So if a graph property is not determined by the cycle matroid (and the number of vertices) then it can't be obtained from the Tutte polynomial.

Answer 2

I'm going to take the opportunity to advertise one of my results: A number of people have said to me "I always thought there was something $K$-theoretic about the Tutte polynomial". Alex Fink and I have worked out the details.

Let $x$ be a point in the Grassmannian $G(d,n)$. Let $T$ be the torus of diagonal matrices in $GL_n$, and let $Z$ be the closure of $Tx$. Let $\mathcal{O}_Z$ be the structure sheaf of $Z$ and let $\mathcal{O}(1)$ be the Pucker line bundle on $G(d,n)$.

Let $\mathbb{P}$ be the projective space lines in $\mathbb{C}^n$, let $\mathbb{P}^{\vee}$ be the projective space of hyperplanes in $\mathbb{C}^n$, and let $F \subset \mathbb{P} \times G(d,n) \times \mathbb{P}^{\vee}$ be the space of partial flags of dimension $(1,d,n-1)$. Pushing and pulling from $F$ gives a map $\phi: K_0(G(d,n)) \to K_0(\mathbb{P} \times \mathbb{P}^{\vee}) \cong \mathbb{Z}[t,u]/\langle t^n, u^n \rangle$.

Then $\phi([\mathcal{O}_Z \otimes \mathcal{O}(1)])$ is the Tutte polynomial of the matroid $M$ of $x$.

To see a baby case of this, let $\int$ denote the pushforward to $K_0(\mathrm{pt}) \cong \mathbb{Z}$. The projection formula gives us $\int \circ \phi = \int$. Now, $\int \mathcal{O}_Z(1)$ is the dimension of global sections of the Plucker line bundle restricted to $Z$. The Plucker coordiante $p_I$ is zero on $Z$ if and only if $I \not \in M$, and there are no other relations, so $\int \mathcal{O}_Z(1)$ is the number of bases of $M$. On the other hand, $\int : K_0(\mathbb{P} \times \mathbb{P}^{\vee}) \to \mathbb{Z}$ sends $t$ and $u$ to $1$. So this result includes the basic fact that the Tutte polynomial, evaluated at $(1,1)$, is the number of bases of the matroid.

Alex and I suggest that $\phi([\mathcal{O}_Z \otimes \mathcal{O}(k)])$ might be an interesting matroid invariant for other values of $k$.

Answer 3

The real thing to focus on is the rank polynomial R(x,y) = T(x+1,y+1).

This is a generating function that counts the number of subsets of edges according to their size and their rank (where "rank" = "matroid rank" which in the graph case is equivalent to #edges - #components).

(Equivalently, you can view it as counting the numbers of subsets of edges according to their rank and their dual rank i.e. rank in the dual matroid.)

Tutte of course showed that the coefficients of the Tutte polynomial count spanning trees, but then you need to resort to ingenious artifice and introduce things like "numbers of internally active edges" and "numbers of externally active edges" to work out which coefficient each spanning tree is counted under.

In general working out which "graphical" properties are determined by this information - i.e. the numbers of subsets of edges of each size and rank - is non-trivial and so you shouldn't expect to just be able to "see" which properties are determined by the Tutte polynomial or not.

But there are some rules of thumb that the previous answerers have covered:

• firstly, the TP depends on the cycle matroid of the graph and so anything that is non-matroidal will not be determined by the TP, which would include most things that involve "vertices" (such as degree sequence etc). [Just a warning though - there are some things whose natural definition uses vertices but that can through trickery be expressed in terms of edges only.]

• secondly, one of the major results in the area is that the TP captures PRECISELY anything that can be computed by deletion/contraction, such as numbers of spanning trees, chromatic polynomial etc. This is a strong "if and only if" type statement in that a theorem called the "recipe theorem" shows that IF an invariant can be defined by deletion/contraction THEN it is an evaluation of the Tutte polynomial.

I think it is fair to say that MOST of the natural interpretations of the TP have by now been uncovered, but there are still occasional papers appearing that show that a given evaluation of the TP corresponds to a certain graphical invariant

Answer 4

The Tutte polynomial of a graph $G$ is the convolution of the modular flow polynomial and the modular tension polynomial of $G$, c.f. [1,2,3]. This leads to a combinatorial interpretation of the values of the Tutte polynomial at every integer point in the plane [4, Theorem 3.11.7].

1. W. Kook, V. Reiner, and D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B 76 (1999), no. 2, 297–300.
2. V. Reiner, An interpretation for the Tutte polynomial, European J. Combin. 20 (1999), no. 2, 149–161.
3. F. Breuer and R. Sanyal, Ehrhart theory, Modular ow reciprocity, and the Tutte polynomial, Mathematische Zeitschrift, to appear. arXiv:0907.0845
4. F. Breuer, Ham Sandwiches, Staircases and Counting Polynomials, PhD thesis, Freie Universität Berlin, 2009. Available here and here.

Disclaimer: the last two of the cited references are my own.

Answer 5

This probably a more advanced answer than you're looking for, but one answer is the cohomology of a variety called a "hypertoric variety" constructed from the graph in a slightly subtle way. You can read more about this in papers by Hausel and Sturmfels (Toric Hyperkahler Varieties) and Proudfoot and myself (Intersection cohomology of hypertoric varieties). You should be warned that all those papers talk about hyperplane arrangments; you should turn a graph into a hyperplane arrangment by taking a variable for each vertex, and a hyperplane for each edge given by equating the variables at opposite ends.

One problem with this approach is that you can only see one variable at a time; T(x,1) is the Poincare polynomial of one variety (I think the graphical hypertoric variety) and T(1,y) is the Poincare polynomial for another (the cographical hypertoric variety).

Answer 6

I always found the Tutte polynomial to be most intuitively the result of the deletion-contraction tree.

http://en.wikipedia.org/wiki/File:Deletion-contraction.svg

Answer 7

One (small part) of an answer: If I understand the definition of the Tutte polynomial correctly, it is invariant under the addition of isolated vertices. So any property that is destroyed by the addition of an isolated vertex cannot be captured by the Tutte polynomial.

Of course, we could always avoid this by replacing Hamiltonicity by "every connected component has a Hamiltonian cycle", which I suppose is also not captured by the Polynomial, but it sort of suggests why capturing HAmiltonicity is hard.

Answer 8

The Tutte polynomial -- especially by the spanning tree expansion and the associated activity words -- is really concerned with the structure of the graph. Take a look at Tutte's Graph Theory book to see how much attention he pays to this subject in general.

The Bull Graph and the Tadpole Graph have the same Tutte polynomial because they are both two bridges attached to a triangle.

By considering the entire set of spanning trees along with their activity words, you are essentially determining all of the cycle (or dependency, via Matroid Theory) information External activity measures WHERE the cycles lie with regard to a numeration of the edges, and I often find it easier to think of internal activity in terms of co-cycles (which in Matroid Theory are cycles in the "dual" graph). Comparing the activity of two trees whose activity words differ greatly uncovers the underlying structure.

I like to think of the Tutte polynomial (and its other versions) as the strongest thing you can hope to get starting from some sort of deletion-contraction property.

Answer 9

The topological Tutte polynomials of Bollob´as and Riordan: properties and relations to other graph polynomials