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)

^{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)

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.

^{n-k}q^{k}T(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.

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

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

The Tutte matrix is another nice contribution of Tutte's:

ReplyDeletehttps://en.wikipedia.org/wiki/Tutte_matrix

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

ReplyDelete