Today I Learned

Some of the things I've learned every day since Oct 10, 2016

68: The Tutte Polynomial

In graph theory, the Tutte polynomial T_G of a graph G is a 2-variable polynomial which is well-defined for any undirected graph and contains information about that graph.

Let G = (V, E) be an undirected graph, and let k(A) denote the number of connected components in G' = (V, A), where A \subseteq E. Then the Tutte polynomial is defined as

T_G (x, y) = \sum _{A \subseteq E} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V|}.

Some properties:

  • Isomorphic graphs have the same Tutte polynomial, but the reverse is not the case
  • Along xy = 1, it specializes to the Jones polynomial of an associated alternating knot
  • T_G (2, 1) is the number of forests of G
  • If G is connected, T_G (1, 1) counts the number of spanning trees.

There are too many to list, but there are many other constraints one can place onto T_G and get various kinds of information about G. It enjoys a wide range of applications, from statistical physics to theoretical computer science.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: