[IEEE Trans. on Information Theory, January 2017, pp. 201-229 ]

A Class of Non-Linearly Solvable Networks

Joseph Connelly and Kenneth Zeger

Abstract

For each positive composite integer m a network is constructed which is solvable over an alphabet of size m but is not solvable over any smaller alphabet. These networks have no linear solutions over any module alphabets and are not asymptotically linearly solvable over any finite-field alphabets. The networks' capacities are all shown to equal one, and their linear capacities are all shown to be bounded away from one for all finite-field alphabets. Additionally, if m is a non-power-of-prime composite number, then such a network is not solvable over any prime-power-size alphabet.