Tutte polynomial

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 <math>G</math> be a graph, and let <math>P(G;\lambda)</math> denote the number of vertex colourings of <math>G</math> using a set of <math>\lambda</math> colours. It is clear that <math>P(G;\lambda)</math> does not depend on the set of colours. What is less clear is that it is the evaluation at <math>\lambda</math> of a polynomial with integer coefficients. To see this, we observe:

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

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

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

Let <math>M=(E,I)</math> be a matroid, with rank function <math>\rho</math>. The Tutte polynomial <math>T(G;x,y)</math> is the polynomial in <math>x</math> and <math>y</math>(with integer coefficients) given by

<math>T(M;x,y)=\sum_{A \subseteq E} (x-1)^{\rho(E)-\rho(A)}(y-1)^{|A|-\rho(A)}</math>.
[edit]

Application

Tutte polynomial has the following important properties:

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

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

Proposition 1 For any graph <math>G</math>, <math>p(G;\lambda)=(-1)^{\rho(G)}\lambda^{\kappa(G)}T(G;1-\lambda,0)</math>, where <math>\kappa(G)</math> is the number of connected components of <math>G</math> and <math>\rho(G)+\kappa(G)</math> 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) <math>T(M;1,1)</math> is the number of bases of <math>M</math>; and <math>T(M;2,1)</math> is the number of independent sets in <math>M</math>.

[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 0198535635.
  • T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 1990. Section 16.4, Theoretical foundations for greedy methods. ISBN 0262032937.
[edit]

External links

hu:matroid it:Matroide pl:Matroid

Retrieved from "http://www.dictionpedia.com/en/Tutte_polynomial"