Privileged users in zero-error transmission over a noisy channel

Abstract

The $k$-th power of a graph $G$ is the graph whose vertex set is $V(G{)}^k$, where two distinct $k$-tuples are adjacent iff they are equal or adjacent in $G$ in each coordinate. The Shannon capacity of $G$, $c(G)$, is ${\lim }_{k\to \infty }\alpha (G^k{)}^{1/k}$, where $\alpha (G)$ denotes the independence number of $G$. When $G$ is the characteristic graph of a channel $\mathcal{C}$, $c(G)$ measures the effective alphabet size of $\mathcal{C}$ in a zero-error protocol. A sum of channels, $\mathcal{C}={\sum }_i{\mathcal{C}}_i$, describes a setting when there are $t\ge 2$ senders, each with his own channel ${\mathcal{C}}_i$, and each letter in a word can be selected from either of the channels. This corresponds to a disjoint union of the characteristic graphs, $G={\sum }_i{G}_i$. We show that for any fixed $t$ and any family $F$ of subsets of $T=1,2,...,t$, there are $t$ graphs $G_1,G_2,...,G_t$, so that for every subset $I$ of $T$, the Shannon capacity of the disjoint union ${\sum }_{i\in I}{G}_i$ is "large" if $I$ contains a member of $F$, and is "small" otherwise.