Privileged users in zero-error transmission over a noisy channel

2006/08/03 by Alon, Noga, Lubetzky, Eyal
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.math/0608083

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→∞α(G^k)^1/k, where α(G) denotes the independence number of G. When G is the characteristic graph of a channel C, c(G) measures the effective alphabet size of C in a zero-error protocol. A sum of channels, C=∑_i C_i, describes a setting when there are t≥ 2 senders, each with his own channel 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=∑_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₁,G₂, ...,G_t, so that for every subset I of T, the Shannon capacity of the disjoint union ∑_{i ∈ I} G_i is "large" if I contains a member of F, and is "small" otherwise.

Related

• Improved lower bounds for the Shannon capacity of odd cycles
• Computability of the Zero-Error Capacity of Noisy Channels
• Advances in the Shannon Capacity of Graphs
• Capacity Regions and Bounds for a Class of Z-interference Channels
• On the Capacity Equivalence with Side Information at Transmitter and Receiver