5
$\begingroup$

Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets $A$ and $B$, there is a family $F$ of disjoint paths from $A$ to $B$ and a set separating $B$ from $A$ consisting of one vertex of each path in $F$.

But what I need is a criterion (at least, a useful sufficient condition) telling me when there is a family of disjoint paths from $A$ to $B$ covering all of $A$. (I only need it for acyclic digraphs in which every path has at most $3$ vertices.) What is known?

$\endgroup$

1 Answer 1

1
$\begingroup$

In our paper, this is called a "linkage". We define something called a "hindrance" and prove that if there is no hindrance then there is a linkage. This is a sufficient but not a necessary condition. In Aharoni's proof of the theorem for bipartite graphs, he defines something called "obstruction", which is necessary and sufficient.

$\endgroup$
2
  • 4
    $\begingroup$ Hi, welcome to MO! I think that for your answer to be useful, you should at least provide a link to the paper. $\endgroup$ May 1, 2023 at 9:05
  • 2
    $\begingroup$ I think this is the correct link: arxiv.org/abs/math/0509397 $\endgroup$ May 1, 2023 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.