Zero-Error Capacity Regions of Noisy Networks

This paper presents the first systematic study of the zero-error capacity regions of noisy networks. First, we consider two simple such networks, each consisting of a stationary memoryless multiple access channel with two binary inputs and one discrete output. There are two users in each network. Each of the two users transmits a message through the network, and the sink(s) of the network can decode both messages with zero error. A graph is used to represent the distinguishability of the inputs of the channel, and a graph set is used to represent the distinguishability of the inputs of the network. We show that for two networks represented by the same graph set, their zero-error capacity regions are the same. We list all the possible graph sets for the two networks and determine the zero-error capacity regions for some of these graph sets. Based on this result, we explore a relation between graph theory and set theory, and then redefine the cancellative pair of families of subsets. We further extend the problem formulation to a general network called the parallel network, which may consist of more than one channel with multiple inputs and multiple outputs.