  While it is known that using network coding can significantly improve the
throughput of directed networks, it is a notorious open problem whether coding
yields any advantage over the multicommodity flow (MCF) rate in undirected
networks. It was conjectured by Li and Li (2004) that the answer is "no". In
this paper we show that even a small advantage over MCF can be amplified to
yield a near-maximum possible gap.
  We prove that any undirected network with $k$ source-sink pairs that exhibits
a $(1+\varepsilon)$ gap between its MCF rate and its network coding rate can be
used to construct a family of graphs $G'$ whose gap is $\log(|G'|)^c$ for some
constant $c < 1$. The resulting gap is close to the best currently known upper
bound, $\log(|G'|)$, which follows from the connection between MCF and sparsest
cuts.
  Our construction relies on a gap-amplifying graph tensor product that, given
two graphs $G_1,G_2$ with small gaps, creates another graph $G$ with a gap that
is equal to the product of the previous two, at the cost of increasing the size
of the graph. We iterate this process to obtain a gap of $\log(|G'|)^c$ from
any initial gap.
