On the representability of integer polymatroids: Applications in linear code construction
Authors:
Open Access
- 1 September 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 504-508
Abstract
It has been shown that there is a duality between the linear network coding solution and the entropic vectors induced by collection of subspaces in a vector space over a finite field (dubbed linearly constructed entropic vectors). The region of all linearly constructed vectors, coincides with the set of all representable polymatroids. For any integer polymatroid, there is an associated matroid, which uniquely identifies the polymatroid. We conjecture that the representability of the underlying matroid is a sufficient condition for integer polymatroids to be linearly representable. We prove that the conjecture holds for representation over real numbers. Furthermore, we show that any real-valued submodular function (such as Shannon entropy) can be approximated (arbitrarily close) by an integer polymatroid.Keywords
This publication has 6 references indexed in Scilit:
- Linear Network Coding, Linear Index Coding and Representable Discrete PolymatroidsIEEE Transactions on Information Theory, 2016
- Truncation Technique for Characterizing Linear PolymatroidsIEEE Transactions on Information Theory, 2011
- Scalar-linear solvability of matroidal networks associated with representable matroids2010
- Networks, Matroids, and Non-Shannon Information InequalitiesIEEE Transactions on Information Theory, 2007
- Inequalities for Shannon Entropy and Kolmogorov ComplexityJournal of Computer and System Sciences, 2000
- Aspects of the theory of hypermatroids1974