We investigate a communication setup where a source output is sent through a free noisy channel first and an additional codeword is sent through a noiseless, but expensive channel later. With the help of the second message the decoder should be able to decide with zero-error whether its decoding of the first message was error-free. This scenario leads to the definition of a digraph parameter that generalizes Witsenhausen's zero-error rate for directed graphs. We investigate this new parameter for some specific directed graphs and explore its relations to other digraph parameters, such as Sperner capacity and dichromatic number. We also look at the natural variant of the above problem, where the decoder should decode the first message with zero-error, not only decide whether its earlier decoding was correct. In this case, the Witsenhausen rate of an appropriately defined undirected graph turns out to be the relevant parameter.

We investigate a communication setup where a source output is sent through a free noisy channel first and an additional codeword is sent through a noiseless but expensive channel later. With the help of the second message the decoder should be able to decide with zero-error whether its decoding of the first message was error-free. This scenario leads to the definition of a digraph parameter that generalizesWitsenhausen's zero-error rate for directed graphs. We investigate this new parameter for some specific directed graphs and explore its relations to other digraph parameters like Sperner capacity and dichromatic number. When the original problem is modified to require zero-error decoding of the complete message then we arrive back to the Witsenhausen rate of an appropriately defined undirected graph.

Körner and Malvenuto asked whether one can find $\binom{n}{\lfloor n/2\rfloor}$ linear orderings (i.e., permutations) of the first n natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Körner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions.

The independence ratio $i(G)$ of a graph G is the ratio of its independence number and the number of vertices. The ultimate categorical independence ratio of a graph G is defined as $\lim_{k\to\infty}i(G^{\times k})$, where $G^{\times k}$ denotes the kth categorical power of G. This parameter was introduced by Brown, Nowakowski, and Rall, who asked about its value for complete multipartite graphs. In this paper we determine the ultimate categorical independence ratio of complete multipartite graphs.