1
$\begingroup$

Hall's theorem says that in a bipartite graph with parts $V_0+V_1$, there's a matching of $V_0$ if and only if $U\subset V_0\implies |U|\leq N_G(U)$. Isn't "a matching of $V_0$" the same as saying an injection $V_0\rightarrow V_1$?

Is Hall's theorem just characterizing when there's an injection between finite sets?

$\endgroup$
  • $\begingroup$ I think you might have Hall's theorem slightly wrong. What does "edges $V_0+V_1"$ mean? Hall's theorem holds for any bipartite graph. $\endgroup$ – Mosquite Sep 16 '16 at 20:28
  • $\begingroup$ @Mosquite I mean the bipartite graph has parts $V_0,V_1$. $\endgroup$ – combinarcotics Sep 16 '16 at 20:32
  • 1
    $\begingroup$ A matching is not just an injection because it also require edges to exist in the graph. An injection from $V_0 \to V_1$ is a necessary condition for a matching but not sufficient. Consider a bipartite graph with no edges; it has no matching. I will turn this into an answer. $\endgroup$ – Mosquite Sep 16 '16 at 20:35
1
$\begingroup$

A matching is not just an injection because it also require edges to exist in the graph. An injection from $V_0 \to V_1$ is a necessary condition for a matching but not sufficient. Consider a bipartite graph with $|V_0| = 1$ and $|V_1| = 2$ and no edges; it has no matching, but there is definitely an injection from $V_0$ to $V_1$.

However, a matching induces an injection between $V_0$ and $V_1$. Also, if we take two sets $V_0$ and $V_1$ there exists an injection from $V_0$ to $V_1$ if and only if there is a matching in the complete bipartite graph with parts $V_0$ and $V_1$ that covers $V_0$.

Finally, Hall's theorem more explicitly says "there's a matching that covers $V_0$".

$\endgroup$
0
$\begingroup$

Hall's theorem is not about whether there is an injection between finite sets. This is because that the matched pairs in a "matching of $V_0$" must be adjacent (connected by an edge) in the graph. So Hall's theorem is a much more interesting statement.

If you want to think about it in terms of injectivity, Suppose we are given a relation $\boldsymbol{R}$ (the edge relation), between the finite set $V_0$ and the finite set $V_1$. Hall's theorem gives the necessary and sufficient condition under which this relation has a subset which is an injection $V_0 \to V_1$.

If you apply Hall's theorem in the specific case where the relation is $V_0 \times V_1$ (every pair of $V_0$ and $V_1$ is connected by an edge), then you get that there is an injection $V_0 \to V_1$ iff $|V_0| \le |V_1|$. But Hall's theorem is much more general than this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.