Lecture Eleven: Matching

  • The fundamental theorem about unweighted bipartite matching is Hall' theorem: a bipartite graph (X,Y,E) has a complete match(i.e. a match in which all of X participates) if and only if for every non-empty subset A of X, R(A), its range in Y, satisfies |A| <=|R(A)|.

  • There's a picture proof - in textbook - using flows. Theorem can also be proved by induction on the size of X. Clearly true for base case |X| = 1. Now two parts of induction proof: for all non-empty A, |A| < |R(A)| (strict inequality)! (pf here easy: just strip off any e from x to y); and there exists non-empty proper A for which |A| = |R(A)|. Second case more subtle. By induction, there's a complete match on A to its range. Throw that out. Look at what's left. It smaller, so there's a complete match for the leftovers if for all B subset of leftovers, |B| <= |R(B)|. Punch line: if this fails, that is if for some B |B| > |R(B)|, then B in the original graph must be sending some edges into R(A), and indeed |A+B| > |R(A+B)|, a contradiction.

  • Corollary. If deg(x) for all x in X is >= k, deg(y) for all y in Y is <= k, then there is a complete match.

  • After we worked out this proof, we did some examples, such as "Every Latin Rectangle can be extended to a Latin Square", and "if all girls at a school have k possible boyfriends, and all boys have k possible girlfriends, then a dating arrangement is possible!"
-- RobbieMoll - 17 Oct 2006
Topic revision: r1 - 2006-10-17 - RobbieMoll
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort