Zero-error coding encompasses a variety of source and channel problems where the probability of error must be exactly zero. This condition is stricter than that of the vanishing error regime, where the error probability goes to zero as the code blocklength goes to infinity. In general, zero-error coding is an open combinatorial question. We investigate two unsolved zero-error problems: the source coding problem with side information and the channel coding problem. We focus our attention on families of independent problems for which the probability distribution decomposes into a product of probability distributions. A crucial step is the additivity property of the optimal rate, which does not always hold in the zero-error regime, unlike in the vanishing error regime. When the additivity holds, the concatenation of optimal codes is optimal. We derive a condition under which the additivity of the complementary graph entropyHfor the AND product of graphs and for the disjoint union of graphs are equivalent. Then we establish the connection with a recent result obtained by Wigderson and Zuiddam and by Schrijver, for the zero-error capacityC0. As a consequence, we provide new single-letter characterizations ofHandC0, for example when the graph is a product of perfect graphs, which is not perfect in general, and for the class of graphs obtained by the product of a perfect graphGwith the pentagon graphC5. By building on Haemers result forC0, we also show that the additivity ofHdoes not hold for the product of the Schläfli graph with its complementary graph.

In the zero-error Slepian-Wolf source coding problem, the optimal rate is given by the complementary graph entropy $\bar H$ of the characteristic graph. It has no single-letter formula, except for perfect graphs, for the pentagon graph with uniform distribution G5, and for their disjoint union. We consider two particular instances, where the characteristic graphs respectively write as an AND product ∧, and as a disjoint union ⊔. We derive a structural result that equates $\bar H( \wedge )$ and $\bar H( \sqcup )$ up to a multiplicative constant, which has two consequences. First, we prove that the cases where $\bar H( \wedge )$ and $\bar H( \sqcup )$ can be linearized coincide. Second, we determine $\bar H$ in cases where it was unknown: products of perfect graphs; and G5∧ G when G is a perfect graph, using Tuncel et al.’s result for $\bar H({G_5} \sqcup G)$. The graphs in these cases are not perfect in general.

We study the zero-error source coding problem in which an encoder with Side Information (SI) g(Y) transmits source symbols X to a decoder. The decoder has SI Y and wants to recover f(X,Y) where f,g are deterministic. We exhibit a condition on the source distribution and g that we call "pairwise shared side information", such that the optimal rate has a single-letter expression. This condition is satisfied if every pair of source symbols "share" at least one SI symbol for all output of g; in the case f(X,Y) = X, the PX,Yand g that satisfy it, induce the worst optimal rate. More generally for all f, it has a practical interpretation, as Y models a request made by the encoder on an image X, and g(Y) corresponds to the type of request. It also has a graph-theoretical interpretation: under "pairwise shared side information" the characteristic graph can be written as a disjoint union of OR products. In the case where the source distribution is full-support, we provide an analytic expression for the optimal rate. We develop an example under "pairwise shared side information", and we show that the optimal coding scheme outperforms several strategies from the literature.

We propose a new approach to construct optimal zero-error codes, based on the concatenation of words of variable length, taken from a generator set. Two zero-error variable-length coding algorithms, referred to as "variable-length coding" and "intermingled coding" are under study. We characterize their asymptotic performances via linear difference equations, in terms of simple properties of the generator set, e.g. the roots of the characteristic polynomial or the spectral radius of an adjacency matrix. For a specific example, we construct an "intermingled" coding scheme that achieves asymptotically the zero-error capacity of a specific channel graph.A full version of this paper is accessible on ArXiv at: https://arxiv.org/abs/2001.03523.