18 312 Algebraic Combinatorics Lionel Levine Lecture 20 Lecture date Apr 26 2011 1 Notes by Josh Alman Plan for the Remainder of the Course Today Applications of the Matrix Tree Theorem Hamming Cube Eulerian Tours Next Class De Bruijn sequences Polya Theory In class final on Thurs May 5th Last week Abelian Sandpile Group 2 Hamming Cube Our first application of the Matrix Tree Thorem will be to find the number of spanning trees in the Hamming Cube Definition 1 The Hamming Cube of dimension n is the undirected graph Hn V E where V 0 1 n is the set of binary strings of length n and x y V are adjacent iff xi yi for all but one index i n Example 2 For n 3 we have that H3 looks like 101 001 111 011 100 000 110 010 Figure 1 The Hamming Cube of dimension 3 20 1 Question 3 How many spanning trees are there in Hn Answer By the Matrix Tree Theorem the number of spanning trees is given by Hn 1 2 N 1 N 1 where N V 2n is the number of vertices and 1 N 1 are the non zero eigenvalues of the Laplacian matrix L nI An where An is the adjacency matrix for Hn Indeed each vertex has degree n since it is adjacent to the vertex which differs from it only in the ith position for all i n Now we are going to find the eigenvalues of An by finding the eigenvalues of A1 and writing the eigenvalues of An as sums of these Notice that Hn H1 H1 H1 n times This gives us exactly that two vertices in Hn are adjacent if they differ in exactly one position as we want Thus we get that An A1 I I I I A1 I I I I I I An 2 One might think that we actually get An A1 A1 A1 n times but this would actually correspond to the graph where two binary strings are adjacent if they differ in every position We can see that 2 is correct Now H1 looks like 0 1 Figure 2 The Hamming Cube of dimension 1 This has adjacency matrix A1 0 1 1 0 1 1 Letting v1 and v2 we can see that 1 1 A1 v1 v1 and A1 v2 v2 so A1 has eigenvectors v1 and v2 with eigenvalues 1 and 1 respectively Thus by 2 we get that the eigenvectors of An are the vectors of the form v v i1 v i2 v in where ir 1 2 r n 20 2 The corresponding eigenvalue for this eigenvector of An is simply the sum of the eigenvalues of the vir s which is X X v 1 1 ir 1 ir 2 n 2 r ir 2 n k Thus since there are ways to pick k of the n ir s to equal 2 we have that An has the eigenvalue n 2k with multiplicity nk for each k 0 1 n this is all the 2n eigenvalues of An Recalling that Ln nI An n we get that Ln has eigenvalue n n 2k 2k with multiplicity m for each k 0 1 n We can finally evaluate 1 keeping in mind that we do not include zero eigenvalues in our product Qn Qn n nk nk Y n k 1 2k k 1 2k Hn 2k k 3 n N 2 1 k 2 Thus the number of spanning trees in Hn is Qn k 2 2k nk Surprisingly despite the form of this answer finding a combinatorial proof of it is an open problem One promising approach involves corresponding spanning trees in Hn to phototropic trees in Hn trees where the sun is placed at the origin and edges grow toward the light More formally Definition 4 A directed spanning tree Tn of Hn rooted at the origin 0n is called phototropic if whenever the arc x y Tn we have that xi yi i n Example 5 Here are directed spanning trees in H2 01 00 11 10 Figure 3 A phototropic tree in H2 20 3 01 00 11 10 Figure 4 A tree in H2 that is not phototropic since there is an arc between 10 and 11 in the wrong direction Counting phototrpphic trees is simple we can construct them by choosing an outward arc for each vertex other than the origin The arc from a vertex x must go to a vertex identical to x except that it has a zero in one position where x has a one and so if there are ax ones in x then there are ax choices for that arc The number of phototropic trees in Hn is thus phototropic trees in Hn Y ax x 0 1 n 0n Y n X x 0 1 n 0n i 1 xn n Y n k k k 1 The similarity of this answer to 3 leads to the idea of corresponding phototropic trees to spanning trees to produce a combinatorial proof of our earlier result 3 3 1 Eulerian Tours Introducing the problem In this section we will use a tricky application spanning trees to find the number of Eulerian tours in a directed graph Definition 6 If G V E is a finite directed graph with n V m E then a directed Eulerian tour of G is a path t0 t1 tm t0 with each ti V such that each directed edge is used exactly once meaning ti ti 1 m 1 i 0 E Example 7 Here are some Eulerian tours on K3 20 4 2 0 1 Figure 5 The complete directed graph on 3 vertices 2 0 1 Figure 6 The Eulerian Tour 021012 2 0 1 Figure 7 The Eulerian Tour 020121 Question 8 Which directed graphs have Eulerian tours One might recall that an undirected graph has an Eulerian tour if every vertex has even degree However here we are dealing with directed graphs so the condition will require that our graph be balanced Definition 9 In a directed graph G V E a vertex v V is said to be balanced if it has equal indegree and outdegree indeg v outdeg v Definition 10 A directed graph G V E is said to be balanced if each of its vertices is balanced 20 5 We can then state our condition on a directed graph having an Eulerian tour Answer 11 A directed graph G V E has an Eulerian tour iff it is balanced It is clear that a directed graph needs to be balanced to have an Eulerian tour The converse ends up being true as well We will see this but we also want to count the number of Eulerian tours in a directed graph that has any Definition 12 If G V E is a directed graph with e E an arc in the graph then we write G e Eulerian tours of G starting with the edge e Since an Eulerian tour goes over all arcs in a graph and we can …