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 *y *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*.