Happy Birthday Ron Aharoni!

Posted on November 25, 2012 by Gil Kalai

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.

This theorem answers a conjecture of Erdos which stood open for half a century. The proof is very difficult. It is truly a tour de force.

Infinite Hall

What about Hall’s theorem for infinite graphs? The correct generalization when A and B are sets of the same arbitrary cardinality was achieved in a 1983 paper by Ron Aharoni, Crispin Nash-Williams, and Saharon Shelah. In this case it is quite difficult even to figure out what are the obstructions for perfect mtchings in the case of infinite sets. The proofs rely on rich and deep methods of infinite combinatorics. Infinite combinatorics certainly deserves a separate post.

Mathcing theory and algebraic topology

Hall’s marriage for hypergraphs

Finding analogs for Hall marriage theorem for hypergraphs is a famous difficult problem. Of course, we must keep in mind that even if we talk about 3-uniform hypergraphs the problem is computationally intractable. So, for example, if we have three sets of n women, n men, and n pets and a collection of allowable triples, it is NP-complete to tell if we can find a “perfect matching”, namely a family of n pairwise disjoint triples.

Here is a beautiful generalization of Hall’s theorem to hypergraphs. Suppose we are given n hypergraphs on the same ground set V. A system of disjoint representatives is a collection of n pairwise disjoint edges, one from each hypergraph. Hall’s theorem says that if the hypergraphs are 1-uniform, and then we can regard the k-th hypergraph simply as a subset $H_k$ of V then a necessary and sufficient condition for the existence of a system of disjoint representatives is that, for every r, the union of every r hypergraphs contains r (or more) distinct elements.

Hall’s theorem for hypergraphs (Ron Aharoni and Penny Haxell, 1999): Let $\cal A$ be a family of hypergraphs. For a subfamily ${\cal B}$ of ${\cal A}$ denote by ${\bf U}({\cal B})$ the union of all hypergraphs in $\cal B$ . The following is a sufficient condition for the existence of a system of disjoint representatives for $\cal A$ :

For every subfamily ${\cal B}$ of ${\cal A}$ there exists a matching $M_{\cal B}$ in ${\bf U}({\cal B})$ , which cannot be pinned by fewer than $|{\cal B}|$ disjoint edges from ${\bf U}({\cal B})$

This is a beautiful generalization of Hall’s theorem and the proof is quite amazing. Here is a link, I will add a freely available link if possible.

From Sperner’s lemma to Hall’s marriage theorem and beyond

Sperner’s lemma (Emanuel Sperner, 1928) talks about coloring. Suppose that we are given a triangulation of the d-dimensional simplex. First color the vertices with d+1 different colors and next color every vertex v by one of the colors of the vertices of the minimal face F containing v.

Sperner’s lemma asserts that there must be a rainbow d-dimensional simplex, namely a d-simplex whose d+1 vertices takes all colors.

Sperner’s lemma is used to prove the Brouwer’s fixed point theorem.

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.

Special types of triangulations

Ron and Penny needed some special types of triangulations for the d-dimensional simplex X. To describe these triangulations we need some definitions. The support supp(x) of a point x in X is the unique face of X containing x in its relative interior. A triangulation T of X is called hierarchic if for any two adjacent vertices in the one-dimensional skeleton of T, the support of one is contained in the support of the other. A triangulation is called economically hierarchic (or briefly EH) if, in addition, for each vertex x of T, the neighbors of x in the one-dimensional skeletonof T on the boundary of supp(x) form a (possibly empty) simplex in T.

An EH-triangulation of a triangle (the interior grey triangle can be triangulated arbitrarily)

The miracle

First note that by adding new elements to edges in the hypergraphs we can guarantee that no edge repeats in more than one hypergraph without affecting the condition or the conclusion of the theorem.

Suppose that our family $\cal A$ of hypergraphs has m members and satisfies the conditions in the Aharoni-Haxell theorem. We consider an EH-triangulation T of a (m-1)-dimensional simplex. Now we place on each vertex of T an edge of one of the hypergraphs, so that the following rules are satisfied:

(0) The ith vertex of the simplex corresponds to the ith hypergraph $H_i$ in $\cal A$ .

(1) On two adjacent vertices of T you can place either identical edges or disjoint edges.

(2) On a vertex of T whose support corresponds to a subfamily $\cal B$ of $\cal A$ we place an edge from $M_{\cal B}$ .

Making it work

The EH property of the triangulation and the no pinning condition of the theorem allow you to color its vertices inductively moving from vertices on lower dimenional faces of X upwards.

The punchline

Once we created an EH triangulation and colored its vertices so that requirements (0), (1), and (2) are satisfied, The rainbow simplex is guaranteed by Sperner’s lemma.

The first case of Ryser’s conjecture

Consider now an r-uniform hypergraph. Namely, this is a collection of sets (called “edges”) of cardinality r from a ground set V of vertices. If V is the disjoint union of r sets and every edge has one element from each of these sets then the hypergraph is called r-partite. Simple graphs are simply 2-uniform hypergraphs, and bipartite graphs are 2-partite 2-uniform hypergraphs. A matching in a hypergraph H is a collection of edges which are pairwise-disjoint. The matching number, ν(H), of a hypergraph H is the maximal size of a matching in H. A cover of a hypergraph H is a subset of V meeting all edges of H. The covering number, τ (H), of H is the minimal size of a cover of H.

Ryser’s conjecture: For an r-uniform r-partite hypergraph (r>1) τ(H) ≤ (r−1)ν(H).

(This conjecture was made independently by Ryser and by Laci Lovasz in the mid 70s.)

Dénes Kőnig

For r=2 Ryser’s conjecture asserts that for bipartite graphs τ= ν. This is a theorem by Dénes Kőnig from 1931. (There are easy derivations from Konig theorem to Hall’s marriage theorem and back.)

Ryser’s conjecture is sharp. To see this start with a finite projective plane of order q regarded as a (q+1)-uniform hypergraph. A truncated projective plane is a projective plane from which a vertex is deleted together with all edges incident with it. A truncated projective plane is a q-partite q-uniform hypergraph. The sides in this case are the sets of vertices which, together with the removed vertex, had formed edges in the projective plane. The matching number is 1, while the minimal covers are the sides, which are of size q. Using the Aharoni-Haxell theorem Ron proved the case r=3 of Ryser’s conjecture.

For recent progress on Ryser’s conjecture for the case r=4, 5 see this paper by Haxell and Scott.

Nerves, independence complexes and Garland’s method

The theorem of Aharoni and Haxell was a starting point for a new branch in topological combinatorics. It is closely related to the topological study of simplicial complexes described by independent sets (or cliques) of a given graph. Aharoni, Berger, and Roy Meshulam wrote a beautiful paper containing a far-reaching extension of the Aharoni-Haxell result. They used, for the first time in combinatorics, a method of Garland which allows one to prove vanishing of homology using some spectral properties of links of vertices.

Fractional matching, fractional combinatorics, Scarf lemma, stable marriage, fractional planks, and more

Warming up

Linear programming relaxation and fractional analogs of combinatorial notions is a great topic. Let’s practice fractional thinking on the notions of covers and of matching.

A set S of vertices in a graph (or hypergraph) is a vertex-cover if every edge in the graph contains a vertex from S. In other words a cover is a map f from the set of vertices to {0,1} so that $f(v)+f(u) \ge 1$ for every edge {v,u} in the graph. The covering number, τ (H), of H is the minimal size of a cover of H.

Now a fractional cover is an assignment of a nonnegative weight f(v) for every v so that $f(v)+f(u) \ge 1$ for every edge {v,u} in the graph. The size of a fractional cover is just the sum of f(v) over all the vertices and the fractional covering number, τ*(H), of H is the minimal size of a fractional cover of H.

Here is an exercise: define the fractional matching number, and the maximum size of a fractional matching.

Solution:

A fractional matching is an assignment nonnegative weights f(e) to all edges e of the graph so that the sum of f(e) over all edges containing a given vertex v is at most one. The size of the matching is the sum of f(e) over all edges.

Ron had many beautiful contributions to “fractional combinatorics.” This deserves an entirely new post so let me delay it to another occasion. In one paper with Fleiner a fractional stable marriage theorem was proved for arbitrary hypergraphs. They used in a crucial way a lemma of Herb Scarf which is part of the proof of Scarf’s famous theorem that balanced games have nonempty core. So, if you are familiar with the Gale-Shapley stable marriage theorem, as an advanced exercise try to figure out: what is a stable marriage for an arbitrary hypergraph? What is a fractional stable marriage?

Another new ABC theorem.

Here is a very recent theorem by Ron Aharoni, Eli Berger, and Maria Chudnovsky

Theorem (Aharoni, Berger, and Chudnovski:) Let G and H be graphs on the same vertex set V, such that G has no induced 4-cycles or 5-cycles, and H has no induced 4-cycles. Assume also that the union of the edge sets of G and H is the complete graph on the vertex set. Then there exists a clique C in G and a clique D in H such that $V = C \cup D$ .

This theorem has a very interesting history with one of the roots belonging to Helly-type geometric theorems.

Other things

Ron is a vigorous champion of math education, he also experienced teaching elementary mathematics and we devoted a post to his candid summary of the experience. Recently he wrote books about poetry, jokes, and philosophy. His critical book on philosophy “The cat that is not there” (In Hebrew) led to a private long debate between Ron and me two years ago.