Return to Answer

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. For each $i$, define a $1$-uniform hypergraph $H_i$ with vertex set $N(x_i)$ and edge set $\{ \{y\} : y \in N(x_i) \}$.

Letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $\mathcal{A}$ has a disjoint set of representatives if and only if $G$ has a matching that saturates $X$. Now the condition of Aharoni and Haxell's Theorem 1.1 applied to the family $\mathcal{A}$ is clearly equivalent to Hall's Condition on $G$.

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. For each $i$, define a $1$-uniform hypergraph $H_i$ with vertex set $N(x_i)$ and edge set $\{ \{y\} : y \in N(x_i) \}$.

Letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $\mathcal{A}$ has a disjoint set of representatives if and only if $G$ has a matching that saturates $X$. Now the condition of Aharoni and Haxell's Theorem 1.1 applied to the family $\mathcal{A}$ is clearly equivalent to Hall's Condition on $G$. Since classical Hall's Theorem falls out of the hypergraph version so quickly, I think it's fair to think of the topological proof of the hypergraph version as also being a topological proof of Hall's theorem.

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. For each $i$, define a $1$-uniform hypergraph $H_i$ with vertex set $N(x_i)$ and edge set $\{ \{y\} : y \in N(x_i) \}$.

Letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $\mathcal{A}$ has a disjoint set of representatives if and only if $G$ has a perfect matching. Now the condition of Aharoni and Haxell's Theorem 1.1 applied to the family $\mathcal{A}$ is clearly equivalent to Hall's Condition on $G$.

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. For each $i$, define a $1$-uniform hypergraph $H_i$ with vertex set $N(x_i)$ and edge set $\{ \{y\} : y \in N(x_i) \}$.

Letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $\mathcal{A}$ has a disjoint set of representatives if and only if $G$ has a matching that saturates $X$. Now the condition of Aharoni and Haxell's Theorem 1.1 applied to the family $\mathcal{A}$ is clearly equivalent to Hall's Condition on $G$.

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. Form a hypergraph $H$ as follows: the vertex set of $H$ consists of those pairs $(x,y)$ such that $x \in X$, $y \in Y$, and $xy \in V(G)$. For each $y_0 \in Y$, we have a hyperedge $\{(x,y_0) : x \in N_G(y_0)\}$.

Letting $H_i$ be the hypergraph consisting of all vertices $(x_i, y)$ for $y \in N_G(x_i)$, and letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $(H_1, \ldots, H_n)$ has a system of disjoint representatives if and only if $G$ has a perfect matching. The condition of Aharoni and Haxell's Theorem 1.1 ("for every subfamily $\mathcal{B}$ of $\mathcal{A}$ there exists a matching $M_{\mathcal{B}}$ in $\bigcup \mathcal{B}$ which cannot be pinned by fewer than $|\mathcal{B}|$ disjoint edges from $\mathcal{B}$") is then seen to be equivalent Hall's Condition for $G$.

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. For each $i$, define a $1$-uniform hypergraph $H_i$ with vertex set $N(x_i)$ and edge set $\{ \{y\} : y \in N(x_i) \}$.

Letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $\mathcal{A}$ has a disjoint set of representatives if and only if $G$ has a perfect matching. Now the condition of Aharoni and Haxell's Theorem 1.1 applied to the family $\mathcal{A}$ is clearly equivalent to Hall's Condition on $G$.