The Proofs of Two Directed Paths Conjectures of Bollobás and Leader

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