18 312 Algebraic Combinatorics Lionel Levine Lecture 17 Lecture date April 14 2011 Notes by Santiago Cuellar Todays topics 1 Ko nig s Theorem 2 Kasteleyn s Theorem Domino tilings for planar regions matching planar graphs 1 Back to Ko nig s Theorem Theorem 1 Reformulation of Hall s marriage theorem Given sets I1 I2 In n suppose that Ii1 Ii2 Iik k for all 1 i1 i2 ik n 1 Then I1 I2 In has a transversal or a system of distinct representatives That is there exists a permutation Sn such that i Ii for all i 1 n Proof Construct bipartite graph on vertex set V X Y where X I1 I2 In Y n and the edges E Ii j j Ii Then 1 becomes Ii1 Ii2 Iik Ii1 Ii2 Iik k Then by Hall s marriage theorem there is a matching which implies a transversal 2 Slight generalization 1 I1 I2 In m If 1 holds note that this implies n m then there is an injective map n m such that i Ii for all i 1 n Recall the Ko nig s theorem restated as a theorem over bipartite graphs Theorem 2 Ko nig Given a bipartite graph G V E min vertex cover C C max matchings M 17 1 M 2 Proof continued from last lecture It is easy to show C M because each edge of the matching covers at least one vertex from the cover Now we try to prove min C M for some matching M Given a minimal vertex cover C we want to extend into a matching MC Suppose the X and Y are the two components of the graph then let CX C X and CY C Y Example 3 Consider the induced subgraph G0 V 0 E 0 with vertex set V 0 CX Y CY Claim 4 Given a subset A CX Then 0 A A Proof For the sake of contradiction assume 0 A A then C A 0 A would be a smaller vertex cover 2 Likewise G00 V 00 E 00 with vertex set V 00 CY X CX has a matching M 00 using all the vertices of CX Then M M 0 M 00 is the matching we were looking Since M 0 M 00 then M M 0 M 00 CX CY C 2 Example 5 Consider a m n rectangular matrix with entries 1 and 0 We look for a subset of rows and columns that covers all the 1 s 17 2 Let r s is the min number of lines of the matrix containing all the 1 s of M Without loss of generality we can assume all the chosen columns are to the left and the rows are at the top Consider each chosen row it has to have a 1 on the right i e not on the chosen columns Moreover for two rows they have a 1 in different columns otherwise they could be replaced by a column covering both Likewise the columns satisfy a similar property which gives us a set of r S 1 s 2 Kasteleyn s Theorem Domino tilings for planar regions Definition 6 A graph G V E is called planar if there exists a function V R2 and for all i j E there is another continuous injective function i j 0 1 R2 such that i j 0 i i j 1 j and i j 0 1 i0 j 0 0 1 for different edges Intuitively a graph is planar if you can draw it on the plane with no intersection of edges Bipartite planar graphs 1 Square Grid 2 Hexagonal Lattice 3 General Question 7 How many ways can you tile an m n square grid by 2 1 dominoes 17 3 We consider the problem on the dual graph So the question is equivalent to find the number of perfect matchings in the dual graph Let G be a finite induced subgraph of Z2 Definition 8 The Kasteleyn matrix of G is the V V matrix 1 u v is an horizontal edge i 1 u v is a vertical edge Ku v 0 otherwise Theorem 9 Kasteleyn Given the graph defined above and it s Kasteleyn matrix perfect matchings of G Example 10 m 2 n 3 17 4 p det K K 0 0 0 i 1 0 0 0 0 1 i 1 0 0 0 0 1 i i 1 0 0 0 0 1 i 1 0 0 0 0 1 i 0 0 0 Since we only care about the absolute value of the determinant we can swap columns to get i 1 0 A 0 K where A 0 i 1 0 A 0 1 i Then det K det2 A i3 i i 2 9 So there are 3 matchings which can be checked by looking at the match for vertex 2 it has three possibilities and the rest of the matches are uniquely defined afterwards Proof Kasteleyn s theorem G is a bipartite graph with parts X and Y Let 1 if u v is a horizontal edge w u v i if u v is a vertical edge 0 otherwise So K 0 AT A 0 where Au v w u v u v E 0 otherwise By swapping the columns like in the example we get det K det2 A det A 2 From this it is enough to show that det A perfect matchings of G We have n X Y and X u1 u2 un Y v1 v2 vn det A X 1 w 1 1 w n n 3 1 w u1 v 1 w un v n 4 Sn X Sn Notice that in the last part the summands are 0 if and only if one of the w are 0 That is they are not 0 when represents a matching so it s only left to check that some of the matchings don t cancel In other words Claim 11 Any two matchings occur with the same sign in the sum There is no cancelation 17 5 To do this we consider two distinct matchings M and M 0 Which together can be viewed as cycles M M 0 is a disjoint union of even cycles Lemma 12 Let v1 v2 v2k be a cycel in Z2 Let Y Y w vi vi 1 w vi vi 1 i even i odd then 1 k l 1 where l is the number of points in Z2 strictly enclosed in the cycle Proof We prove the lemma by induction over the area enclosed by the cycle The base case is when no area is enclosed Notice that only this case is possible for area no area enclosed because the cycle is the union of two matchings so every vertex has degree exactly 2 In this case w v1 v2 1 1 1 0 1 w v2 v1 Inductive step Without loss of generality we can assume v1 is the topmost vertex in the leftmost column According to this we consider three cases 1 So the new variables …