The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a
graph polynomial In mathematics, a graph polynomial is a graph invariant whose values are polynomials. Invariants of this type are studied in algebraic graph theory.
Important graph polynomials include:
*The characteristic polynomial, based on the graph's adjacency ...
. It is a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
in two variables which plays an important role in
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
. It is defined for every
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
and contains information about how the graph is connected. It is denoted by
.
The importance of this polynomial stems from the information it contains about
. Though originally studied in
algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph t ...
as a generalization of counting problems related to
graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
and
nowhere-zero flow In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs.
Definitions
Let ''G'' = (''V'',''E'') be a digraph and let ''M'' be an abelian group. A ...
, it contains several famous other specializations from other sciences such as the
Jones polynomial
In the mathematical field of knot theory, the Jones polynomial is a knot polynomial discovered by Vaughan Jones in 1984. Specifically, it is an invariant of an oriented knot or link which assigns to each oriented knot or link a Laurent polynom ...
from
knot theory
In the mathematical field of topology, knot theory is the study of knot (mathematics), mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are ...
and the
partition functions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of the
Potts model
In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenome ...
from
statistical physics
Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the Mathematics, mathematical tools for dealing with large populations ...
. It is also the source of several central
computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
s in
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
.
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 In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elec ...
under simple transformations. It is essentially a
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
for the number of edge sets of a given size and connected components, with immediate generalizations to
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s. It is also the most general
graph invariant
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
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 one may define the Tutte polynomial as
:
where denotes the number of connected components of the graph . In this definition it is clear that is well-defined and a polynomial in and .
The same definition can be given using slightly different notation by letting
denote the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
of the graph
. 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 of
is equivalent but less easily stated. For connected
we set
:
where
denotes the number of
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s of ''internal activity''
and ''external activity''
.
A third definition uses a
deletion–contraction recurrence. The
edge contraction
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex ide ...
of graph
is the graph obtained by merging the vertices
and
and removing the edge
. We write
for the graph where the edge
is merely removed. Then the Tutte polynomial is defined by the recurrence relation
:
if
is neither a
loop
Loop or LOOP may refer to:
Brands and enterprises
* Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live
* Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets
* Loop Mobile, an ...
nor a
bridge
A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...
, with base case
:
if
contains
bridges and
loops and no other edges. Especially,
if
contains no edges.
The
random cluster model In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elec ...
from statistical mechanics due to provides yet another equivalent definition. The partition sum
:
is equivalent to
under the transformation
:
Properties
The Tutte polynomial factors into connected components. If
is the union of disjoint graphs
and
then
:
If
is planar and
denotes its
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
then
:
Especially, the chromatic polynomial of a planar graph is the flow polynomial of its dual. Tutte refers to such functions as V-functions.
Examples
Isomorphic graphs have the same Tutte polynomial, but the converse is not true. For example, the Tutte polynomial of every tree on
edges is
.
Tutte polynomials are often given in tabular form by listing the coefficients
of
in row
and column
. For example, the Tutte polynomial of the
Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...
,
:
is given by the following table.
Other example, the Tutte polynomial of the octahedron graph is given by
:
History
W. T. Tutte
William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
’s interest in the
deletion–contraction formula
In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
:f(G) = f(G \setminus e) + f(G / e).
Here ''G'' is a graph, ''f'' is a function on graphs, ''e'' is any edge of ''G'', ''G'' \ ' ...
started in his undergraduate days at
Trinity College, Cambridge
Trinity College is a constituent college of the University of Cambridge. Founded in 1546 by Henry VIII, King Henry VIII, Trinity is one of the largest Cambridge colleges, with the largest financial endowment of any college at either Cambridge ...
, originally motivated by
perfect rectangle
Perfect commonly refers to:
* Perfection, completeness, excellence
* Perfect (grammar), a grammatical category in some languages
Perfect may also refer to:
Film
* ''Perfect'' (1985 film), a romantic drama
* ''Perfect'' (2018 film), a science ...
s and
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s. 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
Ronald Martin Foster (3 October 1896 – 2 February 1998), was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines. He published an important paper, ''A Reactance Theorem'', (see Foster ...
had already observed that the
chromatic polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study ...
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. 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
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
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
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph t ...
, Potts began studying the
partition function of certain models in
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
in 1952. The work by Fortuin and Kasteleyn on the
random cluster model In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elec ...
, a generalisation of the
Potts model
In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenome ...
, provided a unifying expression that showed the relation to the Tutte polynomial.
Specialisations
At various points and lines of the
-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.
Chromatic polynomial
At
, the Tutte polynomial specialises to the chromatic polynomial,
:
where
denotes the number of connected components of ''G''.
For integer λ the value of chromatic polynomial
equals the number of
vertex colouring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
s of ''G'' using a set of λ colours. It is clear that
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:
# If ''G'' has ''n'' vertices and no edges, then
.
# If ''G'' contains a loop (a single edge connecting a vertex to itself), then
.
# If ''e'' is an edge which is not a loop, then
::
The three conditions above enable us to calculate
, by applying a sequence of edge deletions and contractions; but they give no guarantee that a different sequence of deletions and contractions will lead to the same value. The guarantee comes from the fact that
counts something, independently of the recurrence. In particular,
:
gives the number of acyclic orientations.
Jones polynomial
Along the hyperbola
, the Tutte polynomial of a planar graph specialises to the
Jones polynomial
In the mathematical field of knot theory, the Jones polynomial is a knot polynomial discovered by Vaughan Jones in 1984. Specifically, it is an invariant of an oriented knot or link which assigns to each oriented knot or link a Laurent polynom ...
of an associated
alternating knot
In knot theory, a knot or link diagram is alternating if the crossings alternate under, over, under, over, as one travels along each component of the link. A link is alternating if it has an alternating diagram.
Many of the knots with crossing ...
.
Individual points
(2,1)
counts the number of
forest
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
s, 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''). If the graph is connected,
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 orientation
In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...
s of ''G''.
[.]
(0,2)
counts the number of
strongly connected orientations of ''G''.
(2,2)
is the number
where
is the number of edges of graph ''G''.
(0,−2)
If ''G'' is a 4-regular graph, then
:
counts the number of
Eulerian orientation
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
s of ''G''. Here
is the number of connected components of ''G''.
(3,3)
If ''G'' is the ''m'' × ''n''
grid graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a latti ...
, then
counts the number of ways to tile a rectangle of width 4''m'' and height 4''n'' with
T-tetrominoes.
If ''G'' is a
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
, then
equals the sum over weighted Eulerian orientations in a
medial graph
In the mathematical discipline of graph theory, the medial graph of plane graph ''G'' is another graph ''M(G)'' that represents the adjacencies between edges in the faces of ''G''. Medial graphs were introduced in 1922 by Ernst Steinitz to study ...
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:
:
the Tutte polynomial specialises to the partition function,
of the
Ising model
The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
studied in
statistical physics
Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the Mathematics, mathematical tools for dealing with large populations ...
. Specifically, along the hyperbola
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 specialises to the partition function of the ''q''-state
Potts model
In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenome ...
. Various physical quantities analysed in the framework of the Potts model translate to specific parts of the
.
Flow polynomial
At
, the Tutte polynomial specialises to the flow polynomial studied in combinatorics. For a connected and undirected graph ''G'' and integer ''k'', a nowhere-zero ''k''-flow is an assignment of “flow” values
to the edges of an arbitrary orientation of ''G'' such that the total flow entering and leaving each vertex is congruent modulo ''k''. The flow polynomial
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
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
, the chromatic polynomial of ''G'' is equivalent to the flow polynomial of its
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
in the sense that
Theorem (Tutte).
:
The connection to the Tutte polynomial is given by:
:
Reliability polynomial
At
, the Tutte polynomial specialises to the all-terminal reliability polynomial studied in network theory. For a connected graph ''G'' remove every edge with probability ''p''; this models a network subject to random edge failures. Then the reliability polynomial is a function
, 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
:
where
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
The Martin polynomial
of an oriented 4-regular graph
was defined by Pierre Martin in 1977. He showed that if ''G'' is a plane graph and
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
Loop or LOOP may refer to:
Brands and enterprises
* Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live
* Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets
* Loop Mobile, an ...
or
bridge
A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...
, 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.
The base case is a monomial
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
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
with solution
:
The analysis can be improved to within a polynomial factor of the number
of
spanning trees of the input graph.
[.] For
sparse graphs with
this running time is
. For
regular graphs
In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed grap ...
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
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H''
: f \colon V(G) \to V(H)
such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...
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
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
efficiently computes the matrix operations
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
and
Pfaffian
In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
. These algorithms are themselves important results from
algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph t ...
and
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
.
equals the number
of
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s of a connected graph. This is
computable in polynomial time as the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of a maximal principal submatrix of the
Laplacian matrix
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplac ...
of ''G'', an early result in algebraic graph theory known as
Kirchhoff’s Matrix–Tree theorem. Likewise, the dimension of the bicycle space at
can be computed in polynomial time by Gaussian elimination.
For planar graphs, the partition function of the Ising model, i.e., the Tutte polynomial at the hyperbola
, can be expressed as a Pfaffian and computed efficiently via the
FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, co ...
. This idea was developed by
Fisher
Fisher is an archaic term for a fisherman, revived as gender-neutral.
Fisher, Fishers or The Fisher may also refer to:
Places
Australia
*Division of Fisher, an electoral district in the Australian House of Representatives, in Queensland
*Elect ...
,
Kasteleyn, and
Temperley
Temperley is a district in Greater Buenos Aires, Argentina, located in the south of Lomas de Zamora Partido.
History
In 1854 the industrial and textile merchant George Temperley (born in 1823 in Newcastle upon Tyne, England) bought from the M ...
to compute the number of
dimer
Dimer may refer to:
* Dimer (chemistry), a chemical structure formed from two similar sub-units
** Protein dimer, a protein quaternary structure
** d-dimer
* Dimer model, an item in statistical mechanics, based on ''domino tiling''
* Julius Dimer ( ...
covers of a planar
lattice model.
Markov chain Monte Carlo
Using a
Markov chain Monte Carlo
In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain ...
method, the Tutte polynomial can be arbitrarily well approximated along the positive branch of
, 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
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
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
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an ins ...
(fpras).
Computational complexity
Several computational problems are associated with the Tutte polynomial. The most straightforward one is
;Input: A graph
;Output: The coefficients of
In particular, the output allows evaluating
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 graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s, so the problem of computing the coefficients of the Tutte polynomial for a given graph is
#P-hard even for planar graphs.
Much more attention has been given to the family of problems called Tutte
defined for every complex pair
:
;
Input: A graph
;
Output: The value of
The hardness of these problems varies with the coordinates
.
Exact computation
If both ''x'' and ''y'' are non-negative integers, the problem
belongs to
#P. For general integer pairs, the Tutte polynomial contains negative terms, which places the problem in the complexity class
GapP
GapP is a counting complexity class, consisting of all of the functions ''f'' such that there exists a polynomial-time non-deterministic Turing machine ''M'' where, for any input ''x'', ''f(x)'' is equal to the number of accepting paths of ''M'' ...
, the closure of
#P under subtraction. To accommodate rational coordinates
, one can define a rational analogue of
#P.
[.]
The computational complexity of exactly computing
falls into one of two classes for any
. The problem is #P-hard unless
lies on the hyperbola
or is one of the points
:
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
become polynomial-time computable as well. All other points remain #P-hard, even for bipartite planar graphs. In his paper on the dichotomy for planar graphs, Vertigan claims (in his conclusion) that the same result holds when further restricted to graphs with vertex degree at most three, save for the point
, which counts nowhere-zero Z
3-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 mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
. 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
In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another (a reduction) that preserves the number of solutions. Informally, it is a bijection between the respective sets of so ...
.
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
is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola
for ''y'' > 0. If the input graphs are restricted to dense instances, with degree
, there is an FPRAS if ''x'' ≥ 1, ''y'' ≥ 1.
[For the case ''x'' ≥ 1 and ''y'' = 1, see . For the case ''x'' ≥ 1 and ''y'' > 1, see .]
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
*
Bollobás–Riordan polynomial The Bollobás–Riordan polynomial can mean a 3-variable invariant polynomial of graphs on orientable surfaces, or a more general 4-variable invariant of ribbon graphs, generalizing the Tutte polynomial
The Tutte polynomial, also called the ...
* A
Tutte–Grothendieck invariant
In mathematics, a Tutte–Grothendieck (TG) invariant is a type of graph invariant that satisfies a generalized deletion–contraction formula. Any evaluation of the Tutte polynomial would be an example of a TG invariant.
Definition
A graph fun ...
is any evaluation of the Tutte polynomial
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
External links
*
* {{MathWorld , urlname=TuttePolynomial, title=Tutte polynomial
*
PlanetMath
PlanetMath is a free, collaborative, mathematics online encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be c ...
br>
Chromatic polynomial* Steven R. Pagano
* Sandra Kingan
Matroid theory Many links.
* Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle
Computational problems
Duality theories
Matroid theory
Polynomials
Graph invariants