A Relaying Graph and Special Strong Product for Zero-Error Problems in Primitive Relay Channels

A primitive relay channel (PRC) has one source (S) communicating a message to one destination (D) with the help of a relay (R). The link between R and D is considered to be noiseless, of finite capacity, and parallel to the link between S and (R,D). Prior work has established, for any fixed number of channel uses, the minimal R-D link rate needed so that the overall S-D message rate equals the zero-error single-input multiple output outer bound (Problem 1). The zero-error relaying scheme was expressed as a coloring of a carefully defined 'relaying compression graph'. It is shown here that this relaying compression graph for n channel uses is not obtained as a strong product from its n = 1 instance. Here we define a new graph, the 'primitive relaying graph' and a new 'special strong product' such that the n-channel use primitive relaying graph corresponds to the n-fold special strong product of the n = 1 graph. We show how the solution to Problem 1 can be obtained from this new primitive relaying graph directly. Further study of this primitive relaying graph has the potential to highlight the structure of optimal codes for zero-error relaying.