Uniform multicommodity flows in the hypercube with random edge‐capacities - McDiarmid, C; Scott, A; Withers, P (Wiley, 2016)
We give two results for multicommodity flows in thed-dimensional hypercubeQdwithindependent random edge-capacities distributed like a random variableCwhereP[C>0]>1/2.Firstly, with high probability asd→∞, the network can support simultaneous multicommodityflows of volume close toE[C]between all antipodal vertex pairs. Secondly, with high probability,the network can support simultaneous multicommodity flows of volume close to 21−dE[C]betweenall vertex pairs. Both results are best possible.