Tag Archives: Hall Mariage Theorem

Happy Birthday Ron Aharoni!

Ron Aharoni, one of Israel’s and the world’s leading combinatorialists celebrated his birthday last month. This is a wonderful opportunity to tell you about a few of the things that Ron did mainly around matching theory.

Menger’s theorem for infinite graphs

Hall’s marriage theorem

Hall marriage theorem (Philip Hall, 1935) gives a necessary and sufficient condition for a perfect matching in bipartite graphs. Suppose that you have a set A of n men and a set B of n women and a list of pairs of men and women that know each other. A perfect matching  is a bijection from A to B which matches every man to a woman he knows.

Hall’s marriage theorem asserts that a necessary and sufficient condition for a perfect matching is that every set S of men knows together at least |S| women.

This is an extremely important theorem and the starting point for a wonderful matching theory. It is a primary example of combinatorial duality. Other theorems of this kind are Menger’s theorem on connectivity in graphs, Dilworth’s theorem (1950) on covering posets with chains, the max-flow min-cut theorem (1956), and quite a few more.

Menger’s theorem

Menger Theorem (Karl Menger, 1927). Let G be a finite  graph and let x and y be two distinct vertices. Then the minimum number of edges whose removal disconnects x and is equal to the maximum number of pairwise edge-disjoint paths from x to y.

Infinite Menger

Ron Aharoni and Eli Berger proved the following theorem (here is a link to the arxived version):

Aharoni and Berger Theorem (2005): Given two sets of vertices, A and B, in a (possibly infinite) digraph, there exists a family P of disjoint A to B paths, and a separating set consisting of the choice of precisely one vertex from each path in P.

Continue reading