Tutte polynomial

From Wikipedia, the free encyclopedia

In mathematics, the Tutte polynomial of a matroid can be regarded as a generalisation of the chromatic polynomial of a graph. It is named for W. T. Tutte.

We sketch this connection in order to see the issues involved in its definition.

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

If $G$ has $n$ vertices and no edges, then $P (G;λ) = λ n$ .
If $G$ contains a loop, then $P (G;λ) = 0$ .
If $e$ is an edge which is not a loop, then $p(G;\lambda)=p(G\setminus e;\lambda)-p(G/e;\lambda),$ where $G \setminus e$ and $G / e$ are graphs obtained from $G$ by deleting and contracting $e$ , respectively.

The three conditions above enable us to calculate $P (G;λ)$ , 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;λ)$ counts something, independently of the recurrence.

Similar considerations apply to the Tutte polynomial. In what follows, we adopt the conventions that $u 0 = 1$ for any $u$ , and $0 n = 0$ for any positive integer $n$ .

Let $M = (E, I)$ be a matroid, with rank function $ρ$ . The Tutte polynomial $T (M; x, y)$ is the polynomial in $x$ and $y$ (with integer coefficients) given by

$T(M;x,y)=\sum_{A \subseteq E} (x-1)^{\rho(E)-\rho(A)}(y-1)^{|A|-\rho(A)}$ .

1 Application
2 Evaluation Complexity
3 References
4 External links

[edit] Application

Tutte polynomial has the following important properties:

$T(\emptyset; x,y)=1$ where $\emptyset$ is the empty matroid.
If $e$ is a loop, then $T(M;x,y)=yT(M \setminus e;x,y)$ .
If $e$ is a coloop, then $T (M; x, y) = x T (M / e; x, y)$ .
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 any graph $G$ , $p (G;λ) = ( - 1) ρ(G) λ κ(G) T (G;1 - λ,0)$ , where $κ(G)$ is the number of connected components of $G$ and $ρ(G) + κ(G)$ the number of vertices.

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

[edit] Evaluation Complexity

Considering the evaluation function $G \mapsto T(G,x_0, y_0)$ , one might wonder how hard it is to compute this function. In particular, if $(x 0, y 0) = (0, - 3)$ , then the Tutte polynomial evaluates to the chromatic polynomial $P (G,3)$ , that is, the number of 3-colorings of $G$ . This problem is already known to be #P-complete, because the decision problem, whether a 3-coloring exists or not, is NP-complete.

Jaeger et al. showed, that the evaluation of the Tutte polynomial is #P-hard for almost all points $(x 0, y 0)$ , and Goldberg & Jerrum also showed inapproximability of the evaluation function at most points.

[edit] References

H. Whitney. On the Abstract Properties of Linear Dependence. American Journal of Mathematics, volume 57, p.509–533. 1935.
Jack Edmonds. Matroids and the Greedy Algorithm. Mathematical Programming, volume 1, p.125–136. 1971.
James G. Oxley. Matroid Theory. Oxford University Press, New York, 1992. ISBN 0-19-853563-5.
T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 1990. Section 16.4, Theoretical foundations for greedy methods. ISBN 0-262-03293-7.
F. Jaeger, D.L. Vertigan, and D.J.A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, 108(1):35-53, 1990.
L.A. Goldberg and M. Jerrum. Inapproximability of the tutte polynomial, 2006.

[edit] External links

Weisstein, Eric W., Matroid at 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.

Retrieved from "http://en.wikipedia.org../../../t/u/t/Tutte_polynomial.html"

Categories: Matroid theory | Geometry | Duality theories | Polynomials