11
$\begingroup$

In the paper Hall's theorem for hypergraphs (Aharoni and Haxell, 2000), the authors prove a theorem on the existence of perfect matchings in bipartite hypergraphs, using Sperner's lemma. At the last page (6), they say that "we have here a topological proof of Hall's theorem" (for bipartite graphs). I thought it should be easy to write this proof explicitly, since a simple bipartite graph is just a bipartite hypergraph in which each hyperedge is of size 2. But there is a problem: during the proof, the authors assume that the sets of neighbors (i.e., the sets $N(x)$ for each vertex $x\in X$, where $X$ is one part of the hypergraph) are pairwise-disjoint. For a hypergraph, this assumption is without loss of generality, since we can add dummy vertices to edges, and this does not affect the theorem conditions or concludion. But in a graph, we cannot add vertices to edges.

So my question is: is there an explicitly-written proof of Hall's marriage theorem, using Sperner's lemma (or a similar topological theorem)?

$\endgroup$

2 Answers 2

14
$\begingroup$

Penny Haxell's 2011 paper On Forming Committees in the American Mathematical Monthly explicitly uses Sperner's lemma to prove Hall's theorem for bipartite graphs (see theorem 4.1 and 4.2).

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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