Name
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 $$(\Omega (\sqrt {\log n\log \log n} ))$$ vertices contains all t colors. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00493-007-2263-z | Combinatorica |
Keywords | Field | DocType |
c i,channel c i,privileged user,characteristic graph,sender i,i g i,log n,g i,g k,i c i,zero-error transmission,noisy channel,graph g,shannon capacity | Complete graph,Discrete mathematics,Family of sets,Binary logarithm,Combinatorics,Vertex (geometry),Induced subgraph,Omega,Disjoint union,Channel capacity,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 6 | 0209-9683 |
Citations | PageRank | References |
3 | 0.43 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Eyal Lubetzky | 2 | 355 | 28.87 |