An analysis proof of the Hall marriage theorem

Question

The Hall marriage theorem has several relatively easy combinatorial proofs. Are there short analytical or topological reformulations and proofs of that theorem?

Answer 1

At Gil Kalai's blog, Hall’s theorem for hypergraphs (Ron Aharoni and Penny Haxell, 1999) is given, and then it says, "Ron Aharoni and Penny Haxell described special type of triangulations, and then miraculously deduced their theorem from Sperner’s lemma. This also gives a beautiful, completely new, topological proof of Hall’s marriage theorem itself."

The Aharoni-Haxell paper is available here.

Answer 2

As requested in the comments, there is a standard proof of Hall's Marriage Theorem from the max-flow min-cut theorem. Let $G$ be a bipartite graph satisfying Hall's condition, with bipartition $(A,B)$ such that $|A|=|B|=:n$.

Make a network $D(G)$ from $G$ by first directing all edges from $A$ to $B$. Then add two additional vertices $s$ and $t$ and directed edges $sa$ for each $a \in A$ and $bt$ for each $b \in B$. Set the capacity of each edge to be 1. Let $\delta(S)$ be a minimum $s$-$t$ cut. Write $S=\{s\} \cup A' \cup B'$ where $A' \subseteq A$ and $B' \subseteq B$.

If there is an edge $ab$ where $a \in A'$ and $b \in B'$, then by moving $b$ out of $B'$ we do not decrease the capacity of $\delta(S)$. Thus we may assume that $B'$ is disjoint from $N_G(A')$. Therefore, the capacity of $\delta(S)$ is at least

$|A - A'|+|B'|+|N_G(A')|.$

By Hall's condition, $|N_G(A')| \geq |A'|$, and so the capacity of $\delta(S)$ is at least $n$. Since all capacities are integral, by the (integral) max-flow min-cut theorem, $D(G)$ has an integral flow of value $n$, which corresponds to a perfect matching in $G$.

Comments. The max-flow min-cut theorem has an easy proof via linear programming duality, which in turn has an easy proof via convex duality. So this proof is analytical if you would like it be. Secondly, the integral max-flow min-cut theorem follows easily from the max-flow min-cut theorem, so LP-duality is enough to get the integral version.

Answer 3

Here is an only slightly more direct proof from convex duality and total unimodularity of the constraint matrix.

Let $G = (L \cup R, E)$ be a bipartite graph satisfying Hall's condition, where $|L| = |R| = n$. The matching polytope $P_G$ for this graph is the convex hull of the indicator vectors $x \in \mathbb{R}^E$ of all matchings, and can be written as:

$$ \forall v \in L \cup R: \sum_{e \ni v}{x_{e}} \leq 1\\ \forall e \in E: x_e \geq 0 $$

I.e., if $B$ is the incidence matrix of $G$, then $P_G = \{x: Bx \leq 1, x\geq 0\}$. Let us verify this is the matching polytope. It is clear that all matchings satisfy these constraints, and that all integral points in $P_G$ are matchings. Since the incidence matrix of a bipartite graph is easily seen to be totally unimodular, all vertices of $P_G$ are integral, and we are done.

A maximum cardinality matching in $G$ is naturally formulated as the linear optimization problem $\max\{1^Tx: x\in P_G\}$, whose dual is

$$ \min 1^Ty\\ \text{ subject to}\\ \\ \forall e=(u,v) \in E: y_u + y_v \geq 1\\ \forall u \in L \cup R: y_u\geq 0 $$

(Notice the solution to the above linear optimization problem is just the size of the minimum vertex cover of $G$.) By (strong) duality, which is a consequence of the Hahn-Banach theorem, $G$ has a matching of size $n$ if and only if the optimum of the above program is at least $n$. To prove Hall's theorem we must show that if the above optimization problem has optimal value strictly less than $n$, then Hall's condition is violated. Again by total unimodularity, there exists an integral optimal solution; let $y$ be such a solution and take $S = \{u: y_u = 1\}$ and $S_L = S \cap L$, $S_R = S \cap R$. Since $y$ is feasible, $N_G(L \setminus S_L) = S_R$, and we have $$ |L \setminus S_L| = n - |S_L| = n - |S| + |S_R| > |S_R| = N_G(L \setminus S_L), $$ contradicting Hall's condition.

This approach gives König's theorem immediately, and you get Egerváry's theorem in the weighted case.