Tutte polynomial

Let $M$ be a matroid with rank function $r$ on the ground set $E$. The Tutte polynomial $t ( M ; x , y )$ of $M$ is defined by

\begin{equation*} t ( M ; x , y ) = \sum _ { S \subseteq E } ( x - 1 ) ^ { r ( M ) - r ( S ) } ( y - 1 ) ^ { | S | - r ( S )}. \end{equation*}

One also writes $t ( M )$ for $t ( M ; x , y )$ when no confusion can arise about the values of $x$ and $y$. There are several equivalent reformulations of $t ( M )$; the most useful such expression is recursive, using the matroid operations of deletion and contraction:

T0) If $E = \emptyset$, then $t ( M ) = 1$;

T1) If $e$ is an isthmus, then $t ( M ) = x t ( M / e )$;

T2) If $e$ is a loop, then $t ( M ) = y t ( M - e )$;

T3) If $e$ is neither an isthmus nor a loop, then $t ( M ) = t ( M / e ) + t ( M - e )$.

Some standard evaluations of the Tutte polynomial are:

a) $t ( M ; 1,1 )$ is the number of bases of $M$;

b) $t ( M ; 2,1 )$ is the number of independent subsets of $M$;

c) $t ( M ; 1,2 )$ is the number of spanning subsets of $M$;

d) $t ( M ; 2,2 ) = 2 ^ { | E | }$.

When a matroid $M$ is constructed from other matroids $M _ { 1 } , M _ { 2 } , \ldots$, it is frequently possible to compute $t ( M )$ from the $t ( M _ { i } )$. The most fundamental structural result of this kind concerns the direct sum of matroids: $t ( M _ { 1 } \oplus M _ { 2 } ) = t ( M _ { 1 } ) t ( M _ { 2 } )$. Another fundamental structural property of the Tutte polynomial is its transparent relationship with matroid duality: $t ( M ^ { * } ; x , y ) = t ( M ; y , x )$. 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 $t ( M )$ and the chromatic polynomial $\chi ( G ; \lambda )$ of a graph $G$ (cf. also Graph colouring). If $G$ is a graph having $v ( G )$ vertices and $c ( G )$ connected components, then

\begin{equation*} \chi ( G ; \lambda ) = \lambda ^ { c ( G ) } ( - 1 ) ^ { v ( G ) - c ( G ) } t ( M _ { G } , 1 - \lambda , 0 ), \end{equation*}

where $M _ { G }$ is the cycle matroid of $G$ (cf. also Matroid). Thus, when $G$ is planar (cf. Graph, planar), $t ( M _ { G } ; x , y )$ simultaneously carries information concerning proper colourings of $G$ along with proper colourings of its dual graph $G ^ { * }$. 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 $\beta ( M )$, the Möbius function $\mu ( M )$, and the characteristic polynomial $p ( M ; \lambda )$ of a matroid $M$. 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 $a ( G )$ denote the number of acyclic orientations of a graph $G$. Then R. Stanley [a13] proved that $a ( G ) = t ( M _ { G } ; 2,0 )$. A variety of related evaluations appear in [a9].

The critical problem of Crapo and G.-C. Rota [a7]: Let $M$ be a rank-$r$ matroid which is represented over $\operatorname {GF} ( q )$ by $\phi : E \rightarrow \operatorname {GF} ( q ) ^ { n }$ and let $k$ be a positive integer. Then the number of $k$-tuples of linear functionals on $\operatorname{GF} ( q ) ^ { n }$ which distinguish $\phi ( E )$ equals $( - 1 ) ^ { r } q ^ { k ( n - r ) } t ( M ; 1 - q ^ { k } , 0 )$. See [a12] for extensions of the critical problem.

Coding theory: Let $C$ be a linear code over $\operatorname {GF} ( q )$ with code-weight polynomial $A ( C ; q , z ) = \sum _ { \mathbf{v} \in C } z ^ { w (\mathbf{v}) }$, where $w ( \mathbf{v} )$ is the weight of the code word $\mathbf{v}$ (see also Coding and decoding). Then

\begin{equation*} A ( C , q , z ) = ( 1 - z ) ^ { r } z ^ { n - r } t \left( M _ { C } ; \frac { 1 + ( q - 1 ) z } { 1 - z } , \frac { 1 } { z } \right), \end{equation*}

where $M _ { C }$ is the matroid associated with the code $C$. 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 $t ( M _ { H } ; 2,0 )$, where $M _ { H }$ 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 $h _ { M } ( x )$ is the shelling polynomial associated with this complex, then $h _ { M } ( x ) = t ( x , 1 )$ and $h _ { M^* } ( y ) = t ( 1 , y )$. 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 $M$ is a probabilistic matroid, i.e., each $e \in E$ has an independent probability $p ( e )$ of successful operation. The formula

\begin{equation*} t ( M ; x , y ) = \sum _ { S \subseteq E } \left( \prod _ { e \in S } p ( e ) \right) \left( \prod _ { e \notin S } ( 1 - p ( e ) ) \right)\times \end{equation*}

\begin{equation*} \times ( x - 1 ) ^ { r ( M ) - r ( S ) } ( y - 1 ) ^ { | S | - r ( s )} \end{equation*}

then produces a probabilistic Tutte polynomial. In this more general situation, $t ( M ; 1,2 )$ is the reliability of $M$, i.e., the probability that a randomly chosen subset spans $E$. Related Tutte polynomials have applications in statistical mechanics and network reliability [a5] and knot theory [a11].

Greedoids: When $G$ is a greedoid (cf. also Greedy algorithm), the expansion $t ( G ; x , y ) = \sum_{ S \subseteq E} ( x - 1 ) ^ { r ( G ) - r ( S ) } ( y - 1 ) ^ { | S | - r ( S ) }$ remains valid. The recursion of T3) takes a slightly different form, however: If $e$ is feasible, then $t ( G ) = t ( G / e ) + ( x - 1 ) ^ { r ( G ) - r ( G - e ) } t ( G - e )$. 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 $T _ { 1 }$ and $T_2$ are rooted trees (cf. also Tree), then computing the Tutte polynomial in this way gives $t ( T _ { 1 } ) = t ( T _ { 2 } )$ if and only if $T _ { 1 }$ and $T_2$ are isomorphic as rooted trees [a8].

In general, it is $\cal N P$-hard (cf. $\cal N P$) 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 $t ( M ; 1,1 )$, 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