Let be a matroid with rank function on the ground set . The Tutte polynomial of is defined by One also writes for when no confusion can arise about the values of and . There are several equivalent reformulations of ; the most useful such expression is recursive, using the matroid operations of deletion and contraction:

T0) If , then ;

T1) If is an isthmus, then ;

T2) If is a loop, then ;

T3) If is neither an isthmus nor a loop, then .

Some standard evaluations of the Tutte polynomial are:

a) is the number of bases of ;

b) is the number of independent subsets of ;

c) is the number of spanning subsets of ;

d) .

When a matroid is constructed from other matroids , it is frequently possible to compute from the . The most fundamental structural result of this kind concerns the direct sum of matroids: . Another fundamental structural property of the Tutte polynomial is its transparent relationship with matroid duality: . Many related results can be found in [a3].

The Tutte polynomial has many significant connections with invariants in graph theory. Of central importance is the relationship between and the chromatic polynomial of a graph (cf. also Graph colouring). If is a graph having vertices and connected components, then where is the cycle matroid of (cf. also Matroid). Thus, when is planar (cf. Graph, planar), simultaneously carries information concerning proper colourings of along with proper colourings of its dual graph . This is the reason W.T. Tutte referred to it as a dichromatic polynomial in his foundational work in this area [a14]. The polynomial was generalized from graphs to matroids by H.H. Crapo [a5] and T.H. Brylawski [a2].

Other invariants which can be obtained from the Tutte polynomial include the beta invariant , the Möbius function , and the characteristic polynomial of a matroid . See [a16] for more information about these invariants.

Applications.

The Tutte polynomial has applications in various areas, some of which are given below. For an extensive introduction, see [a4].

Acyclic orientations: Let denote the number of acyclic orientations of a graph . Then R. Stanley [a13] proved that . A variety of related evaluations appear in [a9].

The critical problem of Crapo and G.-C. Rota [a7]: Let be a rank- matroid which is represented over by and let be a positive integer. Then the number of -tuples of linear functionals on which distinguish equals . See [a12] for extensions of the critical problem.

Coding theory: Let be a linear code over with code-weight polynomial , where is the weight of the code word (see also Coding and decoding). Then where is the matroid associated with the code . Many standard results in coding theory have interpretations using the Tutte polynomial [a4].

Hyperplane arrangements: The number of regions in a central arrangement of hyperplanes is given by , where is the matroid associated with the arrangement. Many generalizations of this result appear in [a15].

Combinatorial topology: The independent subsets of a matroid form a shellable simplicial complex. If is the shelling polynomial associated with this complex, then and . This result is analogous to the dichromatic interpretation for planar graphs. See [a1] for more information on how the Tutte polynomial is associated to simplicial complexes.

Statistical mechanics, network reliability and knot theory: Suppose is a probabilistic matroid, i.e., each has an independent probability of successful operation. The formula then produces a probabilistic Tutte polynomial. In this more general situation, is the reliability of , i.e., the probability that a randomly chosen subset spans . Related Tutte polynomials have applications in statistical mechanics and network reliability [a5] and knot theory [a11].

Greedoids: When is a greedoid (cf. also Greedy algorithm), the expansion remains valid. The recursion of T3) takes a slightly different form, however: If is feasible, then . There are many combinatorial structures which admit a greedoid rank function in a natural way, but do not possess a meaningful matroid structure. For example, if and are rooted trees (cf. also Tree), then computing the Tutte polynomial in this way gives if and only if and are isomorphic as rooted trees [a8].

In general, it is -hard (cf. ) to compute the Tutte polynomial of a graph or a matroid [a10]. Certain evaluations are computable in polynomial-time for certain classes of matroids, however. For example, the number of spanning trees of a graph can be calculated in polynomial-time by the matrix-tree theorem; since this number equals , this evaluation is tractable.

References