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:
“... in a history of spiritual rupture, a social compact built on fantasy and collective secrets, poetry becomes more necessary than ever: it keeps the underground aquifers flowing; it is the liquid voice that can wear through stone.”
—Adrienne Rich (b. 1929)
“[Men say:] “Don’t you know that we are your natural protectors?” But what is a woman afraid of on a lonely road after dark? The bears and wolves are all gone; there is nothing to be afraid of now but our natural protectors.”
—Frances A. Griffin, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 19, by Susan B. Anthony and Ida Husted Harper (1902)
“I assure you that in our next class we will concern ourselves solely with the history of Egypt, and not with the more lurid and non-curricular subject of living mummies.”
—Griffin Jay, and Reginald LeBorg. Prof. Norman (Frank Reicher)