↑ arvau

Wikipedia / Tutte polynomial

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph.

. 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 also the source of several central computational problems in theoretical computer science.

The Tutte polynomial has several equivalent definitions. It is essentially 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 number of connected components, with immediate generalizations 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. one may define the Tutte polynomial as

denotes the number of connected components..

denote the rank. Then the Whitney rank generating function is defined as

The two functions are equivalent under a simple change of variables:

Tutte’s dichromatic polynomial is the result of another simple transformation:

Tutte’s original definition we set

denotes the number of spanning treess of internal activity and external activity is said to be internally active if it is the smallest edge of its fundamental cutset is said to be externally active to be the number of spanning forests.

A third definition uses a deletion–contraction recurrence. The edge contraction is merely removed. Then the Tutte polynomial is defined by the recurrence relation

is neither a loop nor a bridge, with base case

contains no edges.

The random cluster model from statistical mechanics due to provides yet another equivalent definition. The partition sum

under the transformation

Properties

then

.

denotes its dual graph then

In particular, the chromatic polynomial of a planar graph is the flow polynomial of its dual. Tutte refers to such functions as V-functions.

Examples

of a small graph with four nodes and four edges, either via the deletion–contraction formula or by enumeration of spanning trees.

. For example, the Tutte polynomial of the Petersen graph,

is given by the following table.Other example, the Tutte polynomial of the octahedron graph is given by

History

The polynomial was introduced by W. T. Tutte in his 1954 paper, "A contribution to the theory of chromatic polynomials" . Tutte’s interest in the deletion–contraction formula started already in his undergraduate days at Trinity College, Cambridge, originally motivated by perfect rectangles and spanning treess. As he wrote in a later account, 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, which he wrote about in a paper published in 1947, "A ring in graph theory". His original terminology for graph invariants that satisfy the deletion–contraction recursion was W-function, and V-function if multiplicative over components. Tutte writes in the later account, “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 the earlier 1947 paper, the two differing only slightly by a change of variables.) 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

-plane recovers quantities that have been studied in their own right in diverse fields of mathematics and physics, and part of the appeal of the Tutte polynomial thus comes from the unifying framework it provides for analysing these quantities. Here we list various polynomials that can be recovered as specializations of the Tutte polynomial, up to a factor that depends only on the number of components, rank, and/or nullity of a graph.

Chromatic polynomial

,

denotes the number of connected components of G.

equals the number of vertex colourings of G does not depend on the set of colours. What is less clear is that it is the evaluation at λ of a polynomial with integer coefficients. To see this, we observe:

  1. If G has n.

  2. If G.

  3. If e is an edge which is not a loop, then

counts something, independently of the recurrence. In particular,

gives the number of acyclic orientations.

Jones polynomial

, the Tutte polynomial of a planar graph specialises to the Jones polynomial of an associated alternating knot obtained via the medial graph construction. Louis Kauffman has proposed a generalization of the Tutte polynomial for signed graphs, which yields by the medial construction a knot polynomial that specializes to the Jones polynomial as well as to the Kauffman bracket polynomial.

Individual points

(2, 1)

counts the number of forestss, i.e., the number of acyclic edge subsets.

(1, 1)

counts the number of spanning forests (edge subsets without cycles and the same number of connected components as G counts the number of spanning trees.

(1, 2)

counts the number of spanning subgraphs (edge subsets with the same number of connected components as G).

(2, 0)

counts the number of acyclic orientations of G.

(0, 2)

counts the number of strongly connected orientations of G.

(2, 2)

is the number of edges of graph G.

(0, −2)

If G is a 4-regular graph, then

counts the number of Eulerian orientations of G is the number of connected components of G.

(3, 3)

If G is the m×n grid graph counts the number of ways to tile a rectangle of width 4m and height 4n with T-tetrominoes.

If G is a planar graph equals the sum over weighted Eulerian orientations in a medial graph of G, where the weight of an orientation is 2 to the number of saddle vertices of the orientation (that is, the number of vertices with incident edges cyclicly ordered "in, out, in out").

Potts and Ising models

Define the hyperbola in the xy−plane:

of the Ising model studied in statistical physics the two are related by the equation:

In particular,

for all complex α.

More generally, if for any positive integer q, we define the hyperbola:

then the Tutte polynomial determines the partition function of the q-state Potts model.

Flow polynomial

. For a connected and undirected graph G and integer k, a nowhere-zero k to the edges of an arbitrary orientation of G such that the total flow entering and leaving each vertex is congruent modulo k denotes the number of nowhere-zero k-flows. This value is intimately connected with the chromatic polynomial, in fact, if G is a planar graph, the chromatic polynomial of G is equivalent to the flow polynomial of its dual graph in the sense that

Theorem (Tutte).

The connection to the Tutte polynomial is given by:

Reliability polynomial

. For a connected graph G remove every edge with probability p, a polynomial in p, that gives the probability that every pair of vertices in G remains connected after the edges fail. The connection to the Tutte polynomial is given by

Dichromatic polynomial

Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the dichromatic polynomial of a graph. This is

is the number of connected components of the spanning subgraph (V,A). This is related to the corank-nullity polynomial by

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.

Related polynomials

Martin polynomial

was defined by Pierre Martin in 1977. He showed that if G is its directed medial graph, then

Algorithms

Deletion–contraction

The deletion–contraction recurrence for the Tutte polynomial,

immediately yields a recursive algorithm for computing it for a given graph: as long as you can find an edge e that is not a loop or bridge, recursively compute the Tutte polynomial for when that edge is deleted, and when that edge is contracted. Then add the two sub-results together to get the overall Tutte polynomial for the graph.

where m is the number of bridges, and n is the number of loops.

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

of spanning trees of the input graph. For sparse graphs. For regular graphs of degree k, the number of spanning trees can be bounded by

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.

of spanning treess of a connected graph. 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 can be computed in polynomial time by Gaussian elimination.

, can be expressed as a Pfaffian and computed efficiently via the FKT algorithm. This idea was developed by Fisher, Kasteleyn, and Temperley to compute the number of dimer covers of a planar lattice model.

Markov chain Monte Carlo

Using a Markov chain Monte Carlo, equivalently, the partition function of the ferromagnetic Ising model. 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 is to set up a Markov chain whose states are the matchings of the input graph. The transitions are defined by choosing edges at random and modifying the matching accordingly. The resulting Markov chain is rapidly mixing and leads to “sufficiently random” matchings, which can be used to recover the partition function using random sampling. The resulting algorithm is a fully polynomial-time randomized approximation scheme (fpras).

Computational complexity

Several computational problems are associated with the Tutte polynomial. The most straightforward one is

which is equivalent to counting the number of 3-colourings of G. This latter question is #P-complete, even when restricted to the family of planar graphs, so the problem of computing the coefficients of the Tutte polynomial for a given graph is #P-hard even for planar graphs.

:

.

Exact computation

If both x and y 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, one can define a rational analogue of #P.

or is one of the points

in which cases it is computable in polynomial time. become polynomial-time computable as well. All other points remain #P-hard, even for bipartite planar graphs., which counts nowhere-zero Z3-flows and is computable in polynomial time.

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

Approximation

The question of which points admit a good approximation algorithm for y, there is an FPRAS if x ≥ 1, y ≥ 1.

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.

See also

Notes

References

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .