The proofs of two directed paths conjectures of Bollobás and Leader

preprint2015arXivOpen access

Abstract

Let AA and BB be disjoint sets, of size 2k2^k, of vertices of QnQ_n, the nn-dimensional hypercube. In 1997, Bollobás and Leader proved that there must be (n−k)2k(n-k)2^k edge-disjoint paths between such AA and BB. They conjectured that when AA is a down-set and BB 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 AA and an up-set BB is the same as the largest number of directed edge-disjoint paths between AA and BB. 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 AA and BB.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.