Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

BipartiteGraphs and matchings. Readings: Sections 17.1, 17.4, and 17.5. Click on the date for notes on the error in lecture.

If you attended lecture and are wondering how to make the augmenting path construction actually work (since it didn't), the trick is that Hall's condition gives us that for any sequence x1 y1 x2 y2 ... xk where each yi is matched to xi+1 and x1 is unmatched, there is some yk out there that is not matched to any of the xi but is adjacent to at least one of them (not necessarily xk); if it's unmatched, we can extract an augmenting path by picking any xj adjacent to yk as the first edge, yj-1 as the next edge, and then continuing to work backwards in the same way until we get to x1; if it's matched, then we let xk+1 be its match and keep going. The working-backwards step was where I got confused, since at that point we don't need Hall's condition any more and I kept thinking we did.

A working proof can now be found on the BipartiteGraphs page or in ยง17.4 of BiggsBook.

2014-06-17 11:57