Uniform multicommodity flow in the hypercube with random edge capacities

Colin McDiarmid, Alex Scott, Paul Withers

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, wi…