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

l i m_{k o i n f t y} a l p h a (G^{k})^{1 / k}

, where

a l p h a (G)

denotes the independence number of

G

. When

G

is the characteristic graph of a channel

m a t h c a l C

,

c (G)

measures the effective alphabet size of

m a t h c a l C

in a zero-error protocol. A sum of channels,

m a t h c a l C = s u m_{i} m a t h c a l C_{i}

, describes a setting when there are

t g e q 2

senders, each with his own channel

m a t h c a l 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 = s u m_{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

s u m_{i i n I} G_{i}

is "large" if

I

contains a member of

F

, and is "small" otherwise.

Cites Work

Cited In (2)

This page was built for publication: Privileged users in zero-error transmission over a noisy channel