Tutte polynomial

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

[a1]	A. Björner, "The homology and shellability of matroids and geometric lattices" N. White (ed.) , Matroid Applications , Encycl. Math. Appl. , 40 , Cambridge Univ. Press (1992) pp. 226–283
[a2]	T.H. Brylawski, "The Tutte–Grothendieck ring" Algebra Univ. , 2 (1972) pp. 375–388
[a3]	T.H. Brylawski, "The Tutte polynomial. Part 1: General theory" A. Barlotti (ed.) , Matroid Theory and its Applications Proc. Third Mathematics Summer Center C.I.M.E. , Liguori, Naples (1980) pp. 125–275
[a4]	T.H. Brylawski, J.G. Oxley, "The Tutte polynomial and its applications" N. White (ed.) , Matroid Applications , Encycl. Math. Appl. , 40 , Cambridge Univ. Press (1992) pp. 123–225
[a5]	C.J. Colbourn, "The combinatorics of network reliability" , Oxford Univ. Press (1987)
[a6]	H.H. Crapo, "The Tutte polynomial" Aequat. Math. , 3 (1969) pp. 211–229
[a7]	H.H. Crapo, G.-C. Rota, "On the foundations of combinatorial theory: Combinatorial geometries" , MIT (1970) (Edition: Preliminary)
[a8]	G.P. Gordon, E.W. McMahon, "A greedoid polynomial which distinguishes rooted arborescences" Proc. Amer. Math. Soc. , 107 (1989) pp. 287–298
[a9]	C. Greene, T. Zaslavsky, "On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non–Radon partitions, and orientations of graphs" Trans. Amer. Math. Soc. , 280 (1983) pp. 97–126
[a10]	F. Jaeger, D.L. Vertigan, D.J.A. Welsh, "On the computational complexity of the Jones and Tutte polynomials" Math. Proc. Cambridge Philos. Soc. , 108 (1990) pp. 35–53
[a11]	L. Kauffman, "Knots and physics" , World Sci. (1993) (Edition: Second)
[a12]	J.P.S. Kung, "Critical problems" J. Bonin (ed.) et al. (ed.) , Matroid Theory , Contemp. Math. , 197 , Amer. Math. Soc. (1996) pp. 1–128
[a13]	R.P. Stanley, "Acyclic orientations of graphs" Discrete Math. , 5 (1973) pp. 171–178
[a14]	W.T. Tutte, "A contribution to the theory of chromatic polynomials" Canad. J. Math. , 6 (1954) pp. 80–91
[a15]	T. Zaslavsky, "Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes" Memoirs Amer. Math. Soc. , 154 (1975)
[a16]	T. Zaslavsky, "The Möbius functions and the characteristic polynomial" N. White (ed.) , Combinatorial Geometries , Encycl. Math. Appl. , 29 , Cambridge Univ. Press (1987) pp. 114–138