Summary: 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} \alpha(G^k)^{\frac 1k}\), where \(\alpha(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 any of the channels. This corresponds to a disjoint union of the characteristic graphs, \(G = \sum_i G_i\). It is well known that \(c(G)\geq \sum_i c(G_i)\), and in N. Alon [Combinatorica 18, 301-310 (1998; Zbl 0921.05039)] it is shown that in fact \(c(G)\) can be larger than any fixed power of the above sum.
We extend the ideas of [N. Alon, ”Shannon capacity of a union,” Combinatorica 18, No.3, 301–310 (1998; Zbl 0921.05039)] and show that for every \(\mathcal F\), a family of subsets of \([t]\), it is possible to assign a channel \(\mathcal C_i\) to each sender \(i \in [t]\), such that the capacity of a group of senders \(X \subset [t]\) is high iff \(X\) contains some \(F \in \mathcal 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.