Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
The bull graph and (3,2) tadpole graph (both shown at mathworld.wolfram.com/BullGraph.html ) share a Tutte polynomial of x^2(x+x^2+y), and seem to have the same spanning trees, though in different quantities. –  Kevin P. Costello Oct 22 '09 at 5:35
1  
It encodes the number of vertices |V|, all the information from the cycle matroid of the graph, and no other information. See page 2 of Sokal's "The multivariate Tutte polynomial" –  Yaroslav Bulatov Oct 24 '10 at 8:31

9 Answers 9

up vote 11 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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$.

share|improve this answer
    
That's breathtakingly beautiful! Has there been any further progress on this? What about the "best" such invariant, with values in the $K$-theory of the Grassmanian itself? The latter must be known I believe. By analogy with the topological case, it must be somehow related to (co)homology operations... –  მამუკა ჯიბლაძე Apr 8 at 7:39
    
@მამუკაჯიბლაძე Thanks! Not much more progress beyond what's in our paper, no. (There are results in the paper which are not in this answer.) For the study of the invariant in $K_0(G(d,n))$, the starting point is Derksen-Fink arxiv.org/abs/0908.2988 , which works out the vector space of matroids modulo "obvious $K$-theory relations". This has dimension $\binom{n}{d}$ and has basis the Schubert matroids. Since $\binom{n}{d} = \dim K_0(G(d,n))$, I had hoped the obvious relations were all of them, but they are not, because the fact that $\dim Z \leq n-1$ also gives relations. (continued) –  David Speyer Apr 8 at 9:40
    
We don't know the dimension of the vector space in $K_0$ spanned by all matroids, although we do know from Derksen-Fink that it is spanned by Schubert matroids. Alex and I did some preliminary work investigating positivity properties of this $K$-class, but nothing we are willing to state publicly yet. –  David Speyer Apr 8 at 9:41

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 and Proudfoot and myself. 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).

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
1  
It's not clear to me from deletion-contraction, though, why the Tutte polynomial should capture the chromatic number of a graph but not whether it has a Hamiltonian path (for instance). –  Harrison Brown Oct 16 '09 at 23:05
    
Regarding not catching the Hamiltonian, for one thing capturing it would break an NP-complete problem. But I'm sure that wasn't quite the answer you were looking for. –  Jason Dyer Oct 20 '09 at 16:15
1  
It would break an NP-complete problem, except that computing the Tutte polynomial is itself NP-hard (think 3-coloring...) –  Harrison Brown Oct 21 '09 at 20:29

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.