Menger’s theorem for infinite graphs

We prove an old conjecture of Erdos, saying that Menger’s theorem is valid also for infinite graphs, in the following strong form: given sets A and B of vertices in a graph (possibly directed, possibly infinite), there exists a family P of disjoint A-B paths, and an A-B separating set S, such that S consists of a choice of precisely one vertex from each path in P. The talk will describe the history of the problem and the main ideas of our proof. This is joint work with Ron Aharoni.

Speaker Details

Eli Berger received his Ph.D. from Princeton University on 2004, he currently a member of the IAS at the program for Theoretical Computer Science and Discrete Mathematics. His research is combinatorics and complexity theory.

Date:
Speakers:
Eli Berger
Affiliation:
Princeton University
    • Portrait of Jeff Running

      Jeff Running