Graph capacities and zero-error transmission over compound channels

This correspondence investigates the behavior of the compound channel under a zero-error constraint. We derive expressions for the capacity when a) neither the encoder nor decoder has side-information about the channel; b) when only the encoder has such side-information. These expressions are given in terms of capacities of appropriately defined sets of graphs. We clarify that an earlier treatment of the zero-error capacity of a compound channel corresponds to the case where the decoder has side-information about the channel. We also characterize the minimum asymptotic rate for the source coding dual of the compound channel problem, namely, source coding with compound side information. Finally, we contrast the zero-error and asymptotically vanishing error capacities of the compound channel.