Tutte Polynomial - History

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:

    “If man is reduced to being nothing but a character in history, he has no other choice but to subside into the sound and fury of a completely irrational history or to endow history with the form of human reason.”
    —Albert Camus (1913–1960)

    “The one duty we owe to history is to rewrite it.”
    —Oscar Wilde (1854–1900)

    “In history an additional result is commonly produced by human actions beyond that which they aim at and obtain—that which they immediately recognize and desire. They gratify their own interest; but something further is thereby accomplished, latent in the actions in question, though not present to their consciousness, and not included in their design.”
    —Georg Wilhelm Friedrich Hegel (1770–1831)