Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field F q , with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over F q exists for a network if and only if the network is matroidal with respect to a matroid representable over F q . We define a discrete polymatroidal network and show that a linear fractional solution over a field F q exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over F q . An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over F q for the discrete polymatroid, results in a linear fractional solution over F q for the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages X = {x 1 , x 2 , . . . x k }, and a set of receivers R, which demand messages. A receiver R ∈ R is specified by the tuple (x, H) , where x ∈ X is the message demanded by R and H ⊆ X \ {x} is the side information possessed by R. We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. Rouayheb et al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of Rouayheb et al., by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid. T HE concept of network coding, originally introduced by Ahlswede et al. in [1], helps towards providing more throughput in a communication network than what pure routing solutions provide. For solvable multicast networks, it was shown in [2] that linear solutions exist for sufficiently large field size. An algebraic framework for finding linear solutions in networks was introduced in [3]. The connection between matroids and network coding was studied by Dougherty et al. in [4]. In [4] , the notion of matroidal network was introduced and it was shown that if a scalar linear solution over F q exists for a network, then the network is matroidal with respect to a representable matroid. The converse that a scalar linear solution exists for a network if the network is matroidal with respect to a representable matroid was shown in [5] . A construction procedure was given in [4] to obtain networks from matroids, in which the resulting network admits a scalar linear solution over F q if the matroid is representable over F q . Using the networks constructed with the construction procedure given in [4] , it was shown in [6] that there exists networks which do not admit any scalar and vector linear solution, but admit a non-linear solution. In [7], optimal solutions for cyclic networks were constructed from associated acyclic networks motivated by results from matroid duality theory. Linear network codes over cyclic networks were characterized using matroids in [8] . Extending the notion of matroidal network to networks which admit error correction, it was shown in [9] that a network admits a scalar linear error correcting network code if and only if it is a matroidal error correcting network associated with a representable matroid. Constructions of networks from matroids with error correction capability were provided in [9] and [10] . It was shown in [11] that it is possible for a non-scalar linear solvable network to admit a vector linear solution, in which the edges carry vectors over F q whose dimensions are same as that of the message vectors. Throughout this paper, by a vector network coding solution, we refer to a solution for which all the dimensions of the message vectors are equal to the edge vector dimension. It is possible that a network does not admit any scalar or vector solution, but admits a solution if all the dimensions of the message vectors are not equal to the edge vector dimension. Such network coding solutions, called Fractional Network Coding (FNC) solutions, for which all the dimensions of the message vectors are not necessarily equal to the edge vector dimension, have been considered 0018-9448
It has been shown that a network has an (r, l) fractional linear network code solution over F q if and only if it is a (r, l)-discrete polymatroidal network with respect to a discrete polymatroid representable over F q REF .
Linear Network Coding, Linear Index Coding and Representable Discrete Polymatroids
IEEE Transactions on Information Theory
IEEE Transactions on Information Theory
Mathematics Computer Science