[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.