Posted by: yanzhang | August 20, 2009

Trees, The BEST Theorem, and Alexander Polynomials

Most of my “free math time” has been used to study for quals, but today I’ve made myself post to stop Steven from taking over this blog.

One of my favorite elementary algebric combinatorial results is the Matrix Tree Theorem, which states:

In a nondirected graph with vertices labelled 1, 2, \ldots n, the number of spanning trees is equal to any principal minor of the Laplacian.

This cute result gets the number of trees on n vertices (n^{n-2}) fairly quickly with some matrix manipulation, which I will leave as an exercise to the reader. I know two proofs of this theorem: the first one involves using the Cauchy-Binet formula on the Laplacian L, after making the slick observation that L = MM^t, where M is the incidence matrix. Another quick solution can be obtained by invoking the lesser-known version of the Matrix Tree Theorem for directed graphs, which is actually a bit simpler to prove:

In a directed graph with vertices labelled 1, 2, \ldots n, the number of arborescences into vertex i (that is, trees rooted at i where all the edges point towards i) is equal to the i-th minor of the Laplacian.

But this is not all!

I actually recently learned of a third proof (involving Gessel-Viennot, of all things), but I will not mention it here (see the second reference of this post). The reason I mention the directed version and arborescences is to introduce a lesser-known but closely related result to the Matrix Tree Theorem, the forcibly-named BEST Theorem (‘B’ for de Bruijn, ‘S’ for Smith, ‘T’ for Tutte, and ‘E’ for… van Ardenne-Ehrenfest):

In a balanced directed graph (that is, for each vertex the out- and in-degrees equal) with vertices labelled 1, 2, \ldots n, the number of Eulerian circuits is equal to T \prod_v (d_v - 1)!, where d_v is the outdegree of vertex v and $T$ is the number of directed arborescences into any vertex.

This result is neat, for a couple of reasons. One, it shows immediately that the number of directed arborescences into any vertex in a balanced graph is equal, which is totally not obvious. Second, it implies a connection between Eulerian circuits and spanning trees, which is counterintuitive; in fact, when each vertex has in- and out- degree 2, which is a kind of graph we get quite often (especially when we consider nondirected graphs as directed graphs), we get that the number of Eulerian circuits is exactly the number of arborescences.

Sketch of Proof: pick any edge (i, j) to start with. Now, from any Eulerian circuit C, construct a directed graph T' as follows: for each vertex v (besides i), consider the last step in the circuit away from it towards a vertex j. Then add the directed edge (v, j) to T'. This is an arborescence into i. Note that besides the last exit from v (which must be to j), the other d_v - 1 exits can be done in any order. This creates a \prod_v (d_v - 1)! – fold bijection between arborescences into i and Eulerian circuits, which is exactly what we need.

Those familiar with knot theory may recall the Alexander polynomial \Delta_L(t) of a link L, which one obtains as a minorof a matrix M_D constructed from any diagram D of L (though it does not depend on the diagram). I’ll not review the construction since it is best done by example, it is a little tedious to type, and I’m too lazy to draw pictures (though there’s a functional Wikipedia page here). Now, it is well known that |\Delta_L(-1)| is well-defined (and called the determinant of L). However, it has a combinatorial meaning. Construct the following graph on the strands 1, 2, \ldots, n of L: each time the strand i is crossed above by j and comes out the other side as k, draw directed edges (i, j) and (i, k) (I think this even works if $i = j$, though I believe (I don’t know much knot theory and this is pure intuition, so correct me if I’m wrong!!!) you can always draw diagrams to avoid this). It takes a bit of thinking, but convince yourself that this creates a graph G with indegree and outdegree 2 at each vertex. Thus, by considering the construction of M_D, we have:

|\Delta_L(-1)| equals any minor of M_D(-1), which in turn equals both the number of arborescences into any vertex of G and the number of Eulerian circuits of G.

This is basically all I know about knot theory, so I’ll stop here.

References: Enumerative Combinatorics Vol. 2 (Stanley) for the Matrix Tree Theorem and the BEST Theorem, and A Course in Enumeration (Aigner) for the BEST Theorem and Alexander polynomials.


P.S. The latter reference deserves some mention, because it has a neat presentation. At the end of each chapter, Aigner gives a “highlight” section with a particularly pretty result (the BEST Theorem being one of them), which serves as fun enrichment material. I wish more math books did this (though this is not the first book I know which does this – Alon’s The Probabilistic Method also has similar sections, which were equally delightful). The exposition is quite good, coming from one of the writers of the beautiful Proofs from the BOOK.



  1. Hah, did you read my post? This is a hilarious coincidence. And also fruitful, maybe! Other than an intro post on the Alexander polynomial, I guess I should also write up (what I know) about this graph theory – knot theory connection, because at the heart of it is (IMHO) a very interesting open research problem (to do with a topological definition of the Jones polynomial).

    So I should soon have more graph theory questions for you!

    But for now, let me just ask if your theorem on the determinant should maybe be true only for alternating knots? I haven’t looked over it carefully yet, but that’s usually how these things go.

  2. TBH I didn’t read your post too carefully. I’m studying for quals, so instead of actually reading most math articles I would otherwise read, I star them in Google Reader. I was going to go back through them after quals. Hilarious coincidence it is.

    I feel the theorem just works for all crossing diagrams, if I understand everything correctly (they’re relatively new to me).

  3. Oh I see where it may break – because I’ve implicitly assumes that each strand crosses just one other pair of strands when I made the degree comment. Well, I think the only thing it really affects is that the resulting thing will no longer have in- and out-degrees both 2. However, the determinant should still give you the number of arborescences – you just might get a factor on the Eulerian circuits.

  4. Nice post! (lewallen’s previous post too).

    I guess your assumption that “each strand crosses just one other pair of strands” is the same as saying the diagram is alternating. I was trying to think what happens if you allow i=j. The case i=j=k shows up for the diagram of a figure-eight curve (not the figure-eight knot).

    I’m not really familiar with computing Alexander polynomial from matrices (compared to skein relation definition). So I really look forward to future posts on this topics.

  5. Right, that’s what I meant by my comment. So I do assume alternating. However, I think the determinant still works.

  6. Two years later… do you think there might be the possibility to invert the construction and assign to a balanced digraph with any possible out- and in-degrees?

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: