  We introduce a technique for establishing and amplifying gaps between
parameters of network coding and index coding. The technique uses linear
programs to establish separations between combinatorial and coding-theoretic
parameters and applies hypergraph lexicographic products to amplify these
separations. This entails combining the dual solutions of the lexicographic
multiplicands and proving that they are a valid dual of the product. Our result
is general enough to apply to a large family of linear programs. This blend of
linear programs and lexicographic products gives a recipe for constructing hard
instances in which the gap between combinatorial or coding-theoretic parameters
is polynomially large. We find polynomial gaps in cases in which the largest
previously known gaps were only small constant factors or entirely unknown.
Most notably, we show a polynomial separation between linear and non-linear
network coding rates. This involves exploiting a connection between matroids
and index coding to establish a previously unknown separation between linear
and non-linear index coding rates. We also construct index coding problems with
a polynomial gap between the broadcast rate and the trivial lower bound for
which no gap was previously known.
