18 312 Algebraic Combinatorics Lionel Levine Lecture 18 Lecture date Apr 14 2011 1 Notes by Taoran Chen Kasteleyn s theorem Theorem 1 Kasteleyn Let G be a finite induced subgraph of Z2 Define the Kasteleyn matrix of G to be the V V matrix 1 u v is a horizontal edge Ku v i u v is a vertical edge 0 else then perfect matchings of G p det K Proof continued It suffices to show that any two nonzero terms in the expression X det A 1 w u1 v 1 w u2 v 2 w un v n Sn have the same sign Given two perfect matchings M M 0 of G they correspond to some permutations say and 0 respectively and some nonzero terms in the expression above Their union M M 0 is a disjoint union of even cycles so we can transform M into M 0 by rotating the edges along each cycle in turn It suffices to show that rotation along a single cycle does not affect the sign of the corresponding summand In particular we only need to consider the case when M M 0 is a single cycle Let M M 0 be the cycle u1 v1 u2 v2 un vn where u1 v1 u2 v2 un vn being edges of M and u1 vn u2 v1 un vn 1 being edges of M 0 Then is the identity permutation and 0 n n 1 1 is the cyclic permutation having length n thus 0 1 1 and 1 1 n 1 By a lemma from the last lecture w u1 v 1 w u2 v 2 w un v n w u1 v 0 1 w u2 v 0 2 w un v 0 n w u1 v1 w u2 v2 w un vn w v1 u2 w v2 u3 w vn un 1 1 n l 1 where l is the number of vertices enclosed by M M 0 Since the interior of M M 0 is a disjoint union of even cycles l is even As a consequence ratio of sign for M and sign for M 0 is 1 n l 1 1 n 1 1 which completes the proof 2 18 1 2 Domino tilings of a m n rectangle As an application of the Kasteleyn s theorem we compute the number of tilings by 2 1 domino of a m n rectangle which is equivalent to find the number of perfect matchings of the dual graph G Definition 2 Given graphs G1 V1 E1 and G2 V2 E2 define G1 G2 to be the graph having the following properties The vertex set of G1 G2 is V1 V2 Two vertices u1 u2 and v1 v2 of G1 G2 are connected by an edge if and only if either u1 v1 E1 or u2 v2 E2 Definition 3 Let G V E the adjacency matrix A is the V V matrix such that 1 u v E Au v 0 else We begin our analysis by finding the eigenvalues of the adjacency matrix of the path graph Pn pathgraph png P6 Proposition 4 Let An be the adjacency matrix of the path graph Pn The eigenvalues of j for j 1 2 n An are 2 cos n 1 Proof The adjacency matrix An has the form 0 1 0 0 1 0 1 0 0 1 0 1 An 0 0 1 0 0 0 0 1 0 0 0 1 0 We know that is an eigenvalue of An if and only if there exists a nonzero vector v v1 v2 vn t such that An v v Writting the condition An v v in coordinates we 18 2 obtain the system of equations v2 v1 v3 v2 v4 vn 1 v1 v2 v3 vn If we make the convention that v0 0 vn 1 the system of equation becomes the linear recurrence vi 1 vi 1 vi 1 i n Since the linear recurrence can also be written as E 2 E 1 v 0 its solution has the form vi a i b i unless where are the solutions of the equation x2 x 1 0 In particular 1 From the initial data v0 0 vn 1 we deduce n 1 n 1 This along with the equation 1 gives us 2n 2 1 1 hence is some 2n 2 th root of unity Consequently 2Re 2 cos j n 1 j 0 1 2n 1 j 2 cos 2n 2 j we need only to consider the possibilities j 0 1 2 n Since 2 cos n 1 n 1 1 If j 0 2 the equation x2 x 1 0 has root x 1 of multiplicity 2 In this case the vi has the form ai b Solving the initial data v0 0 vn 1 we find that vi is constantly 0 which is forbidden Similarly we can show that j cannot be n 1 Therefore j the remaining possible values of the eigenvalue are 2 cos n 1 j 1 2 n A n n matrix has exactly n eigenvalues so we conclude that they are indeed the eigenvalues of An 2 The dual graph G of the m n rectangle can be expressed as G Pm Pn where Pm Pn are the path graphs It s not hard to check that the Kasteleyn matrix of G K can be written as K Am In i Im An where the symbol denotes tensor product of matrices and In and Im are the identity matrices We are to find the eigenvalues of K Proposition 5 Let the eigenvalues of Am An be k k 1 2 m and j j 1 2 n respectively Let wk vj be the associated eigenvectors Then k i j k 1 2 m j 1 2 n are the eigenvalues of K with associated eigenvectors wk vj 18 3 Proof We check K wk vj Am In i Im An wk vj Am wk vj iwk An vj k wk vj iwk j vj k wk vj i j wk vj k i j wk vj 2 Finally by the Kasteleyn s theorem and the two propositions we are able to compute the number of domino tilings domino tilings perfect matchings of G p det K m Y n Y k i j 1 2 k 1 j 1 m Y n Y 4 cos2 k 1 j 1 3 j k 4 cos2 1 4 m 1 n 1 Matrix Tree theorem We begin with a few definitions Definition 6 The Complete graph Kn has vertex set V n and E i j i 6 j Definition 7 A spanning subgraph of a graph G V E is a graph of the form H V A for some A E Definition 8 A graph is connected if for every two vertices u v V G contains a path from u to v Definition 9 A graph is acyclic if there does not exist v0 v1 vn v0 such that vi vi 1 E for i 1 2 n A acyclic graph is also …