Tutte polynomial

Though originally studied in algebraic graph theory as a generalization of counting problems related to graph coloring and nowhere-zero flow, it contains several famous other specializations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics.

It is essentially a generating function for the number of edge sets of a given size and connected components, with immediate generalizations to matroids.

The random cluster model from statistical mechanics due to Fortuin & Kasteleyn (1972) provides yet another equivalent definition.

Other example, the Tutte polynomial of the octahedron graph is given by 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.”[6] 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 deletion–contraction recursion was W-function, and V-function if multiplicative over components.

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”[7] about the terms dichromate and dichromatic polynomial, introduced by Tutte in different paper, and which differ only slightly.)

[8] Independently of the work in algebraic graph theory, Potts began studying the partition function of certain models in statistical mechanics in 1952.

-plane, the Tutte polynomial evaluates to quantities that have been studied in their own right in diverse fields of mathematics and physics.

Part of the appeal of the Tutte polynomial comes from the unifying framework it provides for analysing these quantities.

denotes the number of connected components of G. For integer λ the value of chromatic polynomial

counts the number of ways to tile a rectangle of width 4m and height 4n with T-tetrominoes.

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.

[dubious – discuss] Various physical quantities analysed in the framework of the Potts model translate to specific parts of the

[dubious – discuss] For a connected and undirected graph G and integer k, a nowhere-zero k-flow is an assignment of “flow” values

, a polynomial in p, that gives the probability that every pair of vertices in G remains connected after the edges fail.

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.[19][21][22] 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.

This is computable in polynomial time as the determinant of a maximal principal submatrix of the Laplacian matrix of G, an early result in algebraic graph theory known as Kirchhoff’s Matrix–Tree theorem.

For planar graphs, the partition function of the Ising model, i.e., the Tutte polynomial at the hyperbola

This idea was developed by Fisher, Kasteleyn, and Temperley to compute the number of dimer covers of a planar lattice model.

Using a Markov chain Monte Carlo method, the Tutte polynomial can be arbitrarily well approximated along the positive branch of

This exploits the close connection between the Ising model and the problem of counting matchings in a graph.

The idea behind this celebrated result of Jerrum and Sinclair[23] is to set up a Markov chain whose states are the matchings of the input graph.

The resulting algorithm is a fully polynomial-time randomized approximation scheme (fpras).

belongs to #P. For general integer pairs, the Tutte polynomial contains negative terms, which places the problem in the complexity class GapP, the closure of #P under subtraction.

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.

Finally, computing the number of four-colorings of a planar graph is #P-complete, even though the decision problem is trivial by the four color theorem.

In contrast, it is easy to see that counting the number of three-colorings for planar graphs is #P-complete because the decision problem is known to be NP-complete via a parsimonious reduction.

[28] 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.

The polynomial is the Tutte polynomial of the bull graph . The red line shows the intersection with the plane , which is essentially equivalent to the chromatic polynomial.
The chromatic polynomial drawn in the Tutte plane
The Jones polynomial drawn in the Tutte plane
The partition functions for the Ising model and the 3- and 4-state Potts models drawn in the Tutte plane.
The flow polynomial drawn in the Tutte plane
The reliability polynomial drawn in the Tutte plane
The deletion–contraction algorithm applied to the diamond graph . Red edges are deleted in the left child and contracted in the right child. The resulting polynomial is the sum of the monomials at the leaves, . Based on Welsh & Merino (2000) .
The Tutte plane. Every point in the real plane corresponds to a computational problem . At any red point, the problem is polynomial-time computable; at any blue point, the problem is #P-hard in general, but polynomial-time computable for planar graphs; and at any point in the white regions, the problem is #P-hard even for bipartite planar graphs.