18 312 Algebraic Combinatorics Lionel Levine Lecture 16 Lecture date April 5 2011 1 Notes by Whan Ghang Matchings and Hall s Marriage Theorem Theorem 1 Hall Let G V E be a finite bipartite graph where V X Y with X Y and X Y Suppose that for all subsets A X we have A A recall that A y Y x y E for some x A Then G has a perfect matching or complete matching Alternatively we can remove the condition that X Y and change the conclusion to say that G has a matching which involves every vertex of X Proof Given a partial matching M with m edges we will produce a partial matching M 0 with m 1 edges It is enough to find a path x0 y1 x1 yk xk yk 1 with x0 6 H yk 1 6 M and yi xi M for i 1 2 k Given such a path the set of edges M 0 M yi xi ki 1 xi yi 1 ki 0 is a matching where M 0 M 1 x0 x1 y1 x2 y2 x4 x3 y3 y4 y5 To construct the path suppose that there exists some x0 X which is unmatched in M The condition x0 1 implies that there exists y1 Y such that x0 y1 E If y1 is unmatched in M then we have a path x0 y1 with the desired properties Otherwise there exists x1 X x0 such that y1 x1 M the condition x0 x1 2 implies that there exists y2 6 y1 such that xr 2 y2 E where r 2 is either 0 or 1 In general given x0 x1 xi 1 we can find some yi 6 y1 yi 1 such that yi xr i E for some r i 0 1 i 1 This process of finding new yi must terminate since Y is finite We have constructed a set x0 y1 x1 yl 1 xl 1 yl such that yi xi M for all M x0 6 M and yl 6 M by construction However xi yi 1 may not be an edge for some i To this end we take the subset yl xr l yr l xr2 l yr2 l which must terminate with the last two terms y1 x0 since r 1 0 and rn k rn 1 k for all n In the above diagram the desired path is y5 x3 y3 x1 y1 x0 2 16 1 Theorem 2 Ko nig Given a rectangular 0 1 matrix M aij where 1 i m and 1 j n define a line of M to be a row or column of M Then the minimum number of lines containing all 1s of M is equal to the maximum number of 1s in M such that no two lie on the same line Proof Define a bipartite graph G V E where V X Y X is the set of rows of M Y is the set of columns of M and ri cj E if and only if aij 1 where ri and cj are arbitrary elements of X and Y respectively This allows us to restate Ko nig s Theorem as follows A vertex cover of G is a set C V such that every edge e E contains some element of C Then min C vertex covers C max M matchings M Given any vertex cover C and any matching M we have M C since C contains at least one vertex from each edge of M Now it suffices to show that given a minimal vertex cover C we want to show that there exists a matching M such that M C Consider the graph G0 V E 0 obtained by removing all the edges within C E 0 E E C C Then G0 is bipartite with parts C and V C no edges between C by construction no edges between V C since C is a vertex cover We check Hall s condition for G0 Suppose there exists A C such that A A The set C A A constitutes a vertex cover of G thus contradicting the minimality of vertex cover C unless there are edges in A that were removed by constructing G0 from G We will consider this case next lecture 2 Definition 3 A permutation matrix P is a matrix whose entries are 1 if j i pij 0 else for some Sn Theorem 4 Birkhoff Let k n N and let M aij ni j 1 be an n n matrix where its entries aij are nonnegative integers satisfying n X i 1 aij n X aij k j 1 Then there exist permutation matrices p1 pk such that M p1 pk Proof We proceed by induction on k Consider the graph G V E with V 1 n 10 n0 where i represents the i j 0 E if and only if aij 1 For all subsets A n 16 2 we have n X X aij j 1 i A n XX aij i A j 1 X k k A i A and also for some fixed j we have sj X n X aij aij k i 1 i A P so at least A of the sj are greater than 0 Since j A if and only if i A aij 0 so A A By Hall s Theorem G has a perfect matching therefore there exists Sn such that i i 0 E for all i 1 2 n So the permutation matrix P corresponding to this permutation satisfies pij aij for all i j Now consider the matrix M P bij n X i 1 bij n X i 1 aij n X pij k 1 i 1 By the induction hypothesis we can write M P as the sum of permutation matrices hence M is the sum of permutation matrices 2 16 3