The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph
Contents
- Definitions
- Properties
- Examples
- History
- Specialisations
- Chromatic polynomial
- Jones polynomial
- 21
- 11
- 12
- 20
- 02
- 33
- Potts and Ising models
- Flow polynomial
- Reliability polynomial
- Dichromatic polynomial
- Martin polynomial
- Deletioncontraction
- Gaussian elimination
- Markov chain Monte Carlo
- Computational complexity
- Exact computation
- Approximation
- References
The importance of this polynomial stems from the information it contains about
The Tutte polynomial has several equivalent definitions. It is equivalent to Whitney’s rank polynomial, Tutte’s own dichromatic polynomial and Fortuin–Kasteleyn’s random cluster model under simple transformations. It is essentially a generating function for the number of edge sets of a given size and connected components, with immediate generalisations to matroids. It is also the most general graph invariant that can be defined by a deletion–contraction recurrence. Several textbooks about graph theory and matroid theory devote entire chapters to it.
Definitions
Definition. For an undirected graph
The same definition can be given using slightly different notation by letting
The two functions are equivalent under a simple change of variables:
Tutte’s dichromatic polynomial
Tutte’s original definition of
where
A third definition uses a deletion–contraction recurrence. The edge contraction
if
if
The random cluster model from statistical mechanics due to Fortuin & Kasteleyn (1972) provides yet another equivalent definition. The polynomial
is equivalent to
Properties
The Tutte polynomial factors into connected components: If
If
Especially, the chromatic polynomial of a planar graph is the flow polynomial of its dual.
Examples
Isomorphic graphs have the same Tutte polynomial, but the converse is not true. For example, the Tutte polynomial of every tree on
Tutte polynomials are often given in tabular form by listing the coefficients
is given by the following table.
Other example, the Tutte polynomial of the octahedron graph is given by
History
W. T. Tutte’s interest in the deletion–contraction formula started in his undergraduate days at Trinity College, Cambridge, originally motivated by perfect rectangles and spanning trees. He often applied the formula in his research and “wondered if there were other interesting functions of graphs, invariant under isomorphism, with similar recursion formulae.” R. M. Foster had already observed that the chromatic polynomial is one such function, and Tutte began to discover more. His original terminology for graph invariants that satisfy the delection–contraction recursion was W-function, and V-function if multiplicative over components. Tutte writes, “Playing with my W-functions I obtained a two-variable polynomial from which either the chromatic polynomial or the flow-polynomial could be obtained by setting one of the variables equal to zero, and adjusting signs.” Tutte called this function the dichromate, as he saw it as a generalization of the chromatic polynomial to two variables, but it is usually referred to as the Tutte polynomial. In Tutte’s words, “This may be unfair to Hassler Whitney who knew and used analogous coefficients without bothering to affix them to two variables.” (There is “notable confusion” about the terms dichromate and dichromatic polynomial, introduced by Tutte in different paper, and which differ only slightly.) The generalisation of the Tutte polynomial to matroids was first published by Crapo, though it appears already in Tutte’s thesis.
Independently of the work in algebraic graph theory, Potts began studying the partition function of certain models in statistical mechanics in 1952. The work by Fortuin and Kasteleyn on the random cluster model, a generalisation of the Potts model, provided a unifying expression that showed the relation to the Tutte polynomial.
Specialisations
At various points and lines of the
Chromatic polynomial
At
where
For integer λ the value of chromatic polynomial
- If G has n vertices and no edges, then
χ G ( λ ) = λ n - If G contains a loop (a single edge connecting a vertex to itself), then
χ G ( λ ) = 0 . - If e is an edge which is not a loop, then
The three conditions above enable us to calculate
gives the number of acyclic orientations.
Jones polynomial
Along the hyperbola
(2,1)
(1,1)
(1,2)
(2,0)
(0,2)
(0,−2)
If G is a 4-regular graph, then
counts the number of Eulerian orientations of G. Here
(3,3)
If G is the m × n grid graph, then
If G is a planar graph, then
Potts and Ising models
Define the hyperbola in the xy−plane:
the Tutte polynomial specialises to the partition function,
In particular,
for all complex α.
More generally, if for any positive integer q, we define the hyperbola:
then the Tutte polynomial specialises to the partition function of the q-state Potts model. Various physical quantities analysed in the framework of the Potts model translate to specific parts of the
Flow polynomial
At
Theorem (Tutte).
The connection to the Tutte polynomial is given by:
Reliability polynomial
At
Dichromatic polynomial
Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the dichromatic polynomial of a graph. This is
where
The dichromatic polynomial does not generalize to matroids because k(A) is not a matroid property: different graphs with the same matroid can have different numbers of connected components.
Martin polynomial
The Martin polynomial
Deletion–contraction
The deletion–contraction recurrence for the Tutte polynomial,
immediately yields a recursive algorithm for computing it: choose any such edge e and repeatedly apply the formula until all edges are either loops or bridges; the resulting base cases at the bottom of the evaluation are easy to compute.
Within a polynomial factor, the running time t of this algorithm can be expressed in terms of the number of vertices n and the number of edges m of the graph,
a recurrence relation that scales as the Fibonacci numbers with solution
The analysis can be improved to within a polynomial factor of the number
where
so the deletion–contraction algorithm runs within a polynomial factor of this bound. For example:
In practice, graph isomorphism testing is used to avoid some recursive calls. This approach works well for graphs that are quite sparse and exhibit many symmetries; the performance of the algorithm depends on the heuristic used to pick the edge e.
Gaussian elimination
In some restricted instances, the Tutte polynomial can be computed in polynomial time, ultimately because Gaussian elimination efficiently computes the matrix operations determinant and Pfaffian. These algorithms are themselves important results from algebraic graph theory and statistical mechanics.
For planar graphs, the partition function of the Ising model, i.e., the Tutte polynomial at the hyperbola
Markov chain Monte Carlo
Using a Markov chain Monte Carlo method, the Tutte polynomial can be arbitrarily well approximated along the positive branch of
Computational complexity
Several computational problems are associated with the Tutte polynomial. The most straightforward one is
In particular, the output allows evaluating
Much more attention has been given to the family of problems called Tutte
The hardness of these problems varies with the coordinates
Exact computation
If both x and y are non-negative integers, the problem
The computational complexity of exactly computing
in which cases it is computable in polynomial time. If the problem is restricted to the class of planar graphs, the points on the hyperbola
These results contain several notable special cases. For example, the problem of computing the partition function of the Ising model is #P-hard in general, even though celebrated algorithms of Onsager and Fisher solve it for planar lattices. Also, the Jones polynomial is #P-hard to compute. Finally, computing the number of four-colourings of a planar graph is #P-complete, even though the decision problem is trivial by the four colour theorem. In contrast, it is easy to see that counting the number of three-colourings for planar graphs is #P-complete because the decision problem is known to be NP-complete via a parsimonious reduction.
Approximation
The question which points admit a good approximation algorithm has been very well studied. Apart from the points that can be computed exactly in polynomial time, the only approximation algorithm known for
Even though the situation is not as well understood as for exact computation, large areas of the plane are known to be hard to approximate.