Thursday, 22 August 2013

discrete mathematics - Proof of easy matching condition for Hall's theorem

I was studying with the recitations provided in the course 6.042 "Mathematics for Computer Science" of MIT OCW and while studying the proof of Hall's marriage problem, I understood the first proof where the bottleneck condition comes in.



However, since it is not efficient as you would need to check a billion subsets for a set of size 30, he talks of easy matching condition where he provides this theorem.




Theorem - "Let G be a bipartite graph with vertex partition L,R where LR. If G is degree-constrained, then there is a matching that covers L."



and he has provided this def for the term "degree constrained".



Theorem ( for reference ) - "A bipartite graph G with vertex partition L, R where LR is degree-constrained if deg(l)deg(r) for every lL and rR. "



He has proved the matching theorem by contradiction. But I am having problem understanding the theorem!!
Can you provide a better or simple explanation for the same.




EDIT 1:
Following is the proof provided in their "readings" section :



The proof is by contradiction. Suppose that G is degree constrained but that there is no matching that covers L. This means that there must be a bottleneck SL. Let x be a value such that deg(l)xdeg(r) for every lL and rR.



Since every edge incident to a node in S is incident to a node in N(S), we know that
|N(S)|x|S|x


and thus that
|N(s)||S|




This means that S is not a bottleneck, which is a contradiction. Hence G has a matching that covers L.



I am having problem that how did they obtain
|N(S)|x|S|x


in the first place!! Please also provide a brief intuition, if possible, for the same.

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...