Privileged users in zero-error transmission over a noisy channel
| dc.creator | Alon, Noga | |
| dc.creator | Lubetzky, Eyal | |
| dc.date | 2006-08-03 | |
| dc.date.accessioned | 2026-07-07T07:21:21Z | |
| dc.date.available | 2026-07-07T07:21:21Z | |
| dc.description | 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}α(G^k)^{1/k}$, where $α(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\geq 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. | |
| dc.identifier | https://arxiv.org/abs/math/0608083 | |
| dc.identifier | http://arxiv.org/abs/math/0608083 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/115269 | |
| dc.subject | Combinatorics | |
| dc.title | Privileged users in zero-error transmission over a noisy channel | |
| dc.type | text |