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 $L \leq R$. 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 $L \leq R$ is degree-constrained if $deg(l) \geq deg(r)$ for every $l \in L$ and $r \in R$. "
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 $S \subseteq L$. Let x be a value such that $deg(l) \geq x \geq deg(r)$ for every $l \in L$ and $r \in R$.
Since every edge incident to a node in S is incident to a node in N(S), we know that
$$|N(S)|x \geq |S|x$$
and thus that
$$|N(s)| \geq |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 \geq |S|x$$
in the first place!! Please also provide a brief intuition, if possible, for the same.
No comments:
Post a Comment