Uniform multicommodity flow in the hypercube with random edge capacities

Abstract

We give two results for multicommodity flows in the $d$-dimensional hypercube $Q^d$ with independent random edge capacities distributed like $C$ where $\mathrm{Pr}[C>0]>1/2$. Firstly, with high probability as $d\to \infty$, the network can support simultaneous multicommodity flows of volume close to $E[C]$ between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to $2^{1-d}E[C]$ between all vertex pairs. Both results are best possible.

36 pages, 4 figures