18 312 Algebraic Combinatorics Lionel Levine Problem Set 7 Due at the beginning of class on Thursday April 21 2011 P30 a Find the number of domino tilings of a 2 n rectangle In class we found a complicated formula for the number of domino tilings of an m n rectangle when mn is even but there is a simpler answer when m 2 b Fix m N and let tn be the number of domino tilings of an m n rectangle Show that the sequence tn n 1 obeys a linear recurrence of order at most 2m Hint For each subset S m consider the number tS n of domino tilings of the region m n s n 1 s S Find a 2m 2m matrix M such that the vector vn tS n S m equals M vn 1 P31 The honeycomb lattice is the infinite graph with vertices V m n m n Z m n is not divisible by 3 where 1 i 3 2 is a primitive cube root of 1 and edges E u v V V u v 1 Let G be a finite induced subgraph pof the honeycomb lattice Prove that the number of perfect matchings of G equals det K where K is the adjacency matrix 1 if u v E Kuv 0 else In other words Kasteleyn s theorem holds without weights 7 1 P32 Let G be a connected graph on n vertices and let T be a spanning subgraph of G Prove that any two of the conditions below imply the third 1 T is connected 2 T is a forest 3 T has exactly n 1 edges 7 2
View Full Document
Unlocking...