Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let GG be a digraph, finite or infinite, and A,BA,B any two sets of its vertices. Then there are a family P\mathcal P of pairwise vertex-disjoint AA--BB paths and an AA--BB separator SS (a set of vertices meeting every AA--BB path) obtained by choosing exactly one vertex from each path in P\mathcal P. This is Theorem 1.6 of arXiv:math/0509397v4 (2007-12-03), the version read, of Ron Aharoni and Eli Berger, Menger's theorem for infinite graphs, first posted on 2005-09-18 and published as Invent. Math. 176 (2009), no. 1, 1--62; the published version was not compared. It is the statement Erdős conjectured for infinite graphs, often called the Erdős--Menger conjecture; for finite graphs it is equivalent to Menger's theorem.

The theorem answers Problem 599 in the affirmative. The problem asks the same for an undirected graph GG with disjoint independent sets A,BA,B. Replacing each edge of GG by its two orientations turns a finite simple AA--BB path of GG, traversed from AA to BB, into a directed AA--BB path with the same vertex set, and forgetting orientations reverses the correspondence; vertex-disjointness and incidence with a separator are preserved both ways. Since $A\cap B=\varnothing$, no one-vertex AA--BB path occurs, and the independence of AA and BB is not used. The conventions this transfer relies on (Definition 1.3, Notation 1.4, Sections 2.3 and 2.4) are recorded on the source card and on the problem page. The paper's proof, a transfinite structural analysis of digraphs, was not reconstructed here.

Acceptance. The result appeared in a refereed journal, Inventiones Mathematicae, in 2009, the refereed evidence; the inspected text is the arXiv v4 final version, and the version of record was not compared with it. The site's curator, Thomas Bloom, marks the problem PROVED and credits the proof to Aharoni and Berger: that curator credit is the reviewed evidence. The formal-conjectures statement file for the problem, at the commit read and linked from the problem page, holds only statements with sorry bodies, so no formalization is linked and the page lists no formalized evidence.