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 k_A be the number of connected components of A and n_A be the number of vertices of the vertices of G induced by A, and k=k_E 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)^k_A-k(y-1)^K_A+n_A-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-kq^kT(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.