13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You can certainly pass from finite to infinite graphs by topology (see "The marriage problem" by Halmos and Vaughan for a nice two-page paper), but that sort of compactness argument is a different issue from whether the finite case itself has an analytic or topological proof. $\endgroup$ – Henry Cohn Sep 18 '13 at 3:34
  • $\begingroup$ I need the finite case of the theorem. $\endgroup$ – Mark Sapir Sep 18 '13 at 3:35
  • 1
    $\begingroup$ Would a proof via convex duality work? I'm thinking of max flow/min cut. $\endgroup$ – Anthony Quas Sep 18 '13 at 6:29
  • 2
    $\begingroup$ There's a terrific but long out of print book by Reichmeider on the relations among Hall's Theorem, max-flow-min-cut, Dilworth's Theorem, and a few others. $\endgroup$ – Gerry Myerson Sep 18 '13 at 9:11
  • 1
    $\begingroup$ @GerryMyerson: The book is indeed nice. $\endgroup$ – Mark Sapir Sep 25 '13 at 12:53
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! This may be exactly what I need. It occurred to me that there might be a connection with the Brouwer fixed point theorem. But I would not guess that the connection is that apparent. $\endgroup$ – Mark Sapir Sep 18 '13 at 7:23
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\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.