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 , the number of spanning trees is equal to any principal minor of the Laplacian.

This cute result gets the number of trees on vertices () 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 , after making the slick observation that , where 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 , the number of arborescences into vertex (that is, trees rooted at where all the edges point towards ) is equal to the -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 , the number of Eulerian circuits is equal to , where is the outdegree of vertex 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 , 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 to start with. Now, from any Eulerian circuit , construct a directed graph as follows: for each vertex (besides ), consider the last step in the circuit away from it towards a vertex . Then add the directed edge to . This is an arborescence into . Note that besides the last exit from (which must be to ), the other exits can be done in any order. This creates a – fold bijection between arborescences into and Eulerian circuits, which is exactly what we need.

Those familiar with knot theory may recall the Alexander polynomial of a link , which one obtains as a minorof a matrix constructed from any diagram of (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 is well-defined (and called the determinant of ). However, it has a combinatorial meaning. Construct the following graph on the strands of : each time the strand is crossed above by and comes out the other side as , draw directed edges and (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 with indegree and outdegree at each vertex. Thus, by considering the construction of , we have:

equals any minor of , which in turn equals both the number of arborescences into any vertex of and the number of Eulerian circuits of .

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.

-Y

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.