Privileged users in zero-error transmission over a noisy channel |
| |
Authors: | Noga Alon Eyal Lubetzky |
| |
Institution: | (1) Schools of Mathematics and Computer Science Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel;(2) School of Mathematics Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel |
| |
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 any of the channels. This corresponds to a disjoint union of the characteristic
graphs, G = Σ
i
G
i
. It is well known that c(G) ≥ Σ
i
c(G
i
), and in 1] it is shown that in fact c(G) can be larger than any fixed power of the above sum.
We extend the ideas of 1] and show that for every F, a family of subsets of t], it is possible to assign a channel C
i
to each sender i ∈ t], such that the capacity of a group of senders X ⊂ t] is high iff X contains some F ∈ F. This corresponds to a case where only privileged subsets of senders are allowed to transmit in a high rate. For instance,
as an analogue to secret sharing, it is possible to ensure that whenever at least k senders combine their channels, they obtain a high capacity, however every group of k − 1 senders has a low capacity (and yet is not totally denied of service). In the process, we obtain an explicit Ramsey construction
of an edge-coloring of the complete graph on n vertices by t colors, where every induced subgraph on exp vertices contains all t colors.
Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
Research partially supported by a Charles Clore Foundation Fellowship. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 05C35 05C55 94A24 |
本文献已被 SpringerLink 等数据库收录! |
|