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 component). 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 papers and differ 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 of Fortuin & Kasteleyn (1972) on the random cluster model, a generalisation of Potts model, provided a unifying expression that showed the relation to the Tutte polynomial.
Read more about this topic: Tutte Polynomial
Famous quotes containing the word history:
“No one can understand Paris and its history who does not understand that its fierceness is the balance and justification of its frivolity. It is called a city of pleasure; but it may also very specially be called a city of pain. The crown of roses is also a crown of thorns. Its people are too prone to hurt others, but quite ready also to hurt themselves. They are martyrs for religion, they are martyrs for irreligion; they are even martyrs for immorality.”
—Gilbert Keith Chesterton (1874–1936)
“The history of his present majesty, is a history of unremitting injuries and usurpations ... all of which have in direct object the establishment of an absolute tyranny over these states. To prove this, let facts be submitted to a candid world, for the truth of which we pledge a faith yet unsullied by falsehood.”
—Thomas Jefferson (1743–1826)
“America is the only nation in history which, miraculously, has gone directly from barbarism to degeneration without the usual interval of civilization.”
—Attributed to Georges Clemenceau (1841–1929)