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 Qn, the ndimensional hypercube. In 1997, Bollobas 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 edgedisjoint 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. Bollobas 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.