The Proofs of Two Directed Paths Conjectures of Bollobas and Leader

摘要

Let A and B be disjoint sets, of size 2(k), of vertices of Q(n), the n-dimensional 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 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. 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.