On uniform matroidal networks

Abstract

Matroidal networks play a fundamental role in proving theoretical results on the limits of network coding. This can be explained by the underlying connections between network coding and matroid theory, both of which build upon the fundamental concept of independence. Two existing methods are known in the network coding literature for constructing networks from a matroid. The method due to Dougherty et al. [5] is high in time complexity but can create relatively simple network structures from a given matroid. Another method due to El Rouayheb et al. [3] is low in time complexity, but results in rather complex network structures. This work studies the design of matroidal networks from uniform matroids, targetting both low time complexity and minimum network sizes. Our construction is based on the new technique of dependence deduction, which may serve as a promising direction for constructing general matroidal networks. Some of our constructions lead to new networks for understanding network coding in terms of base field requirement.