Tutte polynomial

In mathematics, the Tutte polynomial of a matroid can be regarded as a normalized generalisation of the chromatic polynomial of a graph. It is named for W. T. Tutte, who discovered it. It was extended to matroids by Crapo.

The Tutte polynomial $T(G;x,y)$ of a graph $G$ can be defined by the following properties:

1. If $G$ has i isthmi (bridges) and j loops and no other edges, then $T(G;x,y)=x^{i}\,y^{j}$
2. If $e$ is an edge which is not a loop or an isthmus, then $T(G;x,y)=T(G-e;x,y)+T(G/e;x,y),$

where $G-e$ and $G/e$ are graphs obtained from $G$ by deleting and contracting $e$, respectively. An ithsmus is defined as an edge that connects two otherwise disconnected components of the graph. The definition was later extended to matroids and the polynomial is often treated in that more general setting.

The two most important properties of the Tutte polynomial are

• that it is a polynomial in the two variables $x$ and $y$, and
• that every function $f$ of graphs that satisfies the two defining properties of the Tutte polynomial is an evaluation of the latter, i.e., there are numerical or algebraic values of $x$ and $y$ such that $f(G)=T(G;x,y)$ (universality).

Specifically, one has $x=f$(isthmus) and $y=f$(loop).

Well definition and the corank-nullity polynomial

It is not obvious from the definition that the Tutte polynomial is well defined, i.e., independent of the order in which edges are deleted and contracted. Tutte originally proved that it is, by a laborious process of comparing different orderings of the edges. A simpler proof follows from a formula for the Tutte polynomial that was found later on, in terms of the corank-nullity polynomial of a graph or matroid G, which is defined as

$R(G;u,v)=\sum _{A\subseteq E}u^{\rho (E)-\rho (A)}v^{|A|-\rho (A)},$

where E is the point set and ρ is the rank function of G. We adopt the conventions that $u^{0}=1$ for any $u$, and $0^{n}=0$ for any positive integer $n$.

Theorem. $T(G;x,y)=R(G;x-1,y-1).$

This is due to Tutte for graphs and to Crapo (1969) for matroids. The proof is by universality: Show that $R$ satisfies the two properties of the Tutte polynomial, and evaluate $x$ and $y$ by evaluating $R$ for an isthmus and a loop.

Connection with the chromatic polynomial

We sketch part of the connection in order to see the issues involved in the definition of the Tutte polynomial.

Let $G$ be a graph, and let $P(G;\lambda )$ denote the number of vertex colourings of $G$ using a set of $\lambda$ colours. It is clear that $P(G;\lambda )$ does not depend on the set of colours. What is less clear is that it is the evaluation at $\lambda$ of a polynomial with integer coefficients. To see this, we observe:

1. If $G$ has $n$ vertices and no edges, then $P(G;\lambda )=\lambda ^{n}$.
2. If $G$ contains a loop, then $P(G;\lambda )=0$.
3. If $e$ is an edge which is not a loop, then $P(G;\lambda )=P(G\setminus e;\lambda )-P(G/e;\lambda )$.

The three conditions above enable us to calculate $P(G;\lambda )$, by applying a sequence of edge deletions and contractions; but they give no guarantee that a different sequence of deletions and contractions will lead to the same value. The guarantee comes from the fact that $P(G;\lambda )$ counts something, independently of the recurrence.

Similar considerations apply to the Tutte polynomial. We know the Tutte polynomial is well defined because it has the formula stated in the theorem.

Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the dichromatic polynomial of a graph. This is

$Q(G;u,v)=\sum _{A\subseteq E}u^{c(A)}v^{|A|-c(A)+|V|)},$

where $c(A)$ is the number of connected components of the spanning subgraph (V,A). This is related to the corank-nullity polynomial by

$Q(G;u,v)=u^{c}\,R(G;u,v),$

where c is the number of components of G. The dichromatic polynomial does not generalize to matroids because c is not a matroid property: different graphs with the same matroid can have different numbers of components.

Applications

The Tutte polynomial has the following important properties:

1. $T(\emptyset ;x,y)=1$ where $\emptyset$ is the empty matroid.
2. If $e$ is a loop, then $T(M;x,y)=yT(M\setminus e;x,y)$.
3. If $e$ is a coloop, then $T(M;x,y)=xT(M/e;x,y)$.
4. If $e$ is neither a loop or a coloop, then $T(M;x,y)=T(M\setminus e;x,y)+T(M/e;x,y)$.

As an application, the chromatic polynomial of a graph is, up to normalisation, a specialisation of the Tutte polynomial.

Proposition 1. For a graph $G$, $p(G;\lambda )=(-1)^{\rho (G)}\lambda ^{\kappa (G)}T(G;1-\lambda ,0)$, where $\kappa (G)$ is the number of connected components of $G$ and $\rho (G)+\kappa (G)$ is the number of vertices.

A similar statement holds for the characteristic polynomial of a matroid, p(M; λ).

Proposition 2. For a matroid M, $p(M;\lambda )=(-1)^{\rho (M)}T(M;1-\lambda ,0)$.

Many other graph invariants related to trees and forests, flows, percolation, reliability, and knot polynomials are evaluations or specialisations of the Tutte polynomial. Two of these are obvious from the definition:

Proposition 3. (a) $T(M;1,1)$ is the number of bases of $M$; and $T(M;2,1)$ is the number of independent sets in $M$.

Evaluation complexity

Considering the evaluation function $G\mapsto T(G;x_{0},y_{0})$ for fixed $(x_{0},y_{0})$, one might wonder how hard it is to compute this function. In particular, if $(x_{0},y_{0})=(-2,0)$, then the Tutte polynomial is closely related to the chromatic polynomial $p(G,3)$ (see Proposition 1), that is, the number of 3-colorings of $G$. The well-known fact that it is NP-complete to even decide whether a graph has at least one 3-coloring shows the hardness of evaluating the Tutte polynomial at this point.

It has been shown that the evaluation of the Tutte polynomial is #P-hard for almost all points $(x_{0},y_{0})$ by Jaeger et al. Goldberg & Jerrum also showed inapproximability of the evaluation function at most points.

References

• Biggs, Norman (1993). Algebraic Graph Theory (2nd ed. ed.). Cambridge: Cambridge University Press. ISBN 0-521-45897-8. {{cite book}}: |edition= has extra text (help)
• Henry H. Crapo (1969), The Tutte polynomial. Aequationes Mathematicae, volume 3, pp. 211–229.
• L.A. Goldberg and M. Jerrum (2006), Inapproximability of the Tutte polynomial. Submitted for publication.
• F. Jaeger, D.L. Vertigan, and D.J.A. Welsh (1990), On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, volume 108, pp. 35–53.
• D.J.A. Welsh (1976), Matroid Theory. London: Academic Press.
• W.T. Tutte (1984), Graph Theory. Reading, Mass.: Addison–Wesley.

External links

• Weisstein, Eric W. "Matroid". MathWorld.
• PlanetMath article on matroids. Contains several other equivalent definitions of matroids.
• Steven R. Pagano: Matroids and Signed Graphs
• Sandra Kingan: Matroid theory. Lots of links.
• C++ Code for efficiently computing Tutte Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]