Sunday, May 14, 2017

William Tutte (1917-2002)

Today we celebrate our mothers of course, but also the 100th anniversary of the birth of Bill Tutte, best known for his role in decrypting the Lorenz cipher used by the Nazi high command. Tutte also made many important advances in graph theory and algorithms.

For this post, let's look at one very powerful concept, the Tutte Polynomial, with a rather technical looking definition. Fix a graph G with vertex set V and edge set E with n = |V|. For a subset A of E, let kA be the number of connected components of A and nA be the number of vertices of the vertices of G induced by A, and k=kE the number of connected components of G.

The Tutte polynomial T(x,y) is the sum over all subsets A of E of the quantity
(x-1)kA-k(y-1)KA+nA-n.

What makes this problem interesting? For some fixed values of x and y we get various properties of the graph.

T(2,1) is the number of forests of G.
T(1,2) number of spanning forests (or spanning trees if G is connected.
T(2,0) is the number of spanning subgraphs.
T(0,2) is the number of strongly connected orientations.
The value (-1)n-kqkT(1-q,0) counts the number of q-colorings of G.

Computing T can be difficult. Counting the number of 3-colorings is #P-complete, equivalent to counting the number of satisfying assignments of a Boolean formula. So even computing T(-2,0) for a given graph G is #P-complete. Leslie Goldberg and Mark Jerrum show that even computing the sign of a Tutte polynomial, just determining whether it is positive, zero or negative, on certain values is still #P-hard.

This is only a sampling of the many applications of the Tutte polynomial. Let's remember Tutte for creating a single function that captures so much information about a graph and helping to defeat the Nazis. Not a bad life. Must have had a good mother.

3 comments:

  1. Not coincidentally, the University of Waterloo, where Tutte spent much of his postwar career, just named a campus street after Tutte.

    https://uwaterloo.ca/math50/events/william-tutte-way-naming-celebration

    ReplyDelete
  2. The Tutte matrix is another nice contribution of Tutte's:
    https://en.wikipedia.org/wiki/Tutte_matrix

    ReplyDelete
  3. I don't whether others are experiencing it as well, but this blog has been taking about 5 minutes to load recently.

    ReplyDelete