Title: Generalized Index Coding Problem and Discrete Polymatroids,
Abstract: The index coding problem has been generalized recently to accommodate
receivers which demand functions of messages and which possess functions of
messages. The connections between index coding and matroid theory have been
well studied in the recent past. Index coding solutions were first connected to
multi linear representation of matroids. For vector linear index codes discrete
polymatroids which can be viewed as a generalization of the matroids was used.
It was shown that a vector linear solution to an index coding problem exists if
and only if there exists a representable discrete polymatroid satisfying
certain conditions. In this work we explore the connections between generalized
index coding and discrete polymatroids. The conditions that needs to be
satisfied by a representable discrete polymatroid for a generalized index
coding problem to have a vector linear solution is established. From a discrete
polymatroid we construct an index coding problem with coded side information
and shows that if the index coding problem has a certain optimal length
solution then the discrete polymatroid satisfies certain properties. From a
matroid we construct a similar generalized index coding problem and shows that
the index coding problem has a binary scalar linear solution of optimal length
if and only if the matroid is binary representable.