Abstract
Let and be disjoint sets, of size , of vertices of , the -dimensional hypercube. In 1997, Bollobás and Leader proved that there must be edge-disjoint paths between such and . They conjectured that when is a down-set and is an up-set, these paths may be chosen to be directed (that is, the vertices in the path form a chain). We use a novel type of compression argument to prove stronger versions of these conjectures, namely that the largest number of edge-disjoint paths between a down-set and an up-set is the same as the largest number of directed edge-disjoint paths between and . Bollobás and Leader made an analogous conjecture for vertex-disjoint paths and we prove a strengthening of this by similar methods. We also prove similar results for all other sizes of and .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.