Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Claim. Let be a digraph, finite or infinite, and any two sets of its vertices. Then there are a family of pairwise vertex-disjoint -- paths and an -- separator (a set of vertices meeting every -- path) obtained by choosing exactly one vertex from each path in . 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 with disjoint independent sets . Replacing each edge of by its two orientations turns a finite simple -- path of , traversed from to , into a directed -- 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 -- path occurs, and the independence of and 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.