Bollobás–Leader directed edge-disjoint paths conjecture

Let $Q_n$ be the $n$-dimensional hypercube, identified with the power set $\mathcal{P}[n]$. For disjoint subsets $A,B\subseteq \mathcal{P}[n]$, let $\overrightarrow{p}_e(A,B)$ denote the maximum size of a collection of edge-disjoint directed paths from $A$ to $B$. A down-set is a subset $A$ such that $x\in A$ and $y\subseteq x$ imply $y\in A$, and an up-set is the complement of a down-set. Let $BL_e(|A|,|B|)$ denote the Bollobás–Leader lower bound for the maximum number of edge-disjoint paths between sets of sizes $|A|$ and $|B|$. Bollobás–Leader's directed edge-paths conjecture. If $A$ is a down-set and $B$ is an up-set, and they are disjoint non-empty subsets of $\mathcal{P}[n]$, then

$$\overrightarrow{p}_e(A,B)\geq BL_e(|A|,|B|).$$

In particular, if $|A|=|B|=2^k$, then

$$\overrightarrow{p}_e(A,B)\geq (n-k)2^k.$$

The conjecture asks whether the undirected Bollobás–Leader bounds remain valid when the paths are required to be directed, equivalently when their vertices form chains. The paper presents this as an open problem and proves the conjecture.