# Diamond Message Set Groupcasting: From an Inner Bound for the DM Broadcast
Channel to the Capacity Region of the Combination Network

Mohamed Salman and Mahesh K. Varanasi
This work was presented in part at the 2020 IEEE International Symposium on
Information Theory, LA, CA [1]. This research was funded in part by the 2018
and 2019 Qualcomm Faculty Awards. M. Salman and M. K. Varanasi are with the
Electrical, Computer and Energy Engineering Department, University of
Colorado, Boulder, CO, USA (emails: {mohamed.salman, varanasi}@colorado.edu).

###### Abstract

Multiple groupcasting over the broadcast channel (BC) is studied in a special
setting. In particular, an inner bound is obtained for the $K$-receiver
discrete memoryless (DM) BC for the diamond message set which consists of four
groupcast messages: one desired by all receivers, one by all but two
receivers, and two more desired by all but each one of those two receivers.
The inner bound is based on rate-splitting and superposition coding and is
given in explicit form herein as a union over coding distributions of four-
dimensional polytopes. When specialized to the so-called combination network,
which is a class of three-layer (two-hop) broadcast networks parameterized by
$2^{K}-1$ finite-and-arbitrary-capacity noiseless links from the source node
in the first layer to as many nodes of the second layer, our top-down approach
from the DM BC to the combination network yields an explicit inner bound as a
single polytope via the identification of a single coding distribution. This
inner bound consists of inequalities which, in a problem that is akin to
finding a few needles in a haystack, are then identified to be within the
class of a plethora of (indeed, infinitely many) generalized cut-set outer
bounds recently obtained by Salimi et al for broadcast networks. We hence
establish the capacity region of the general $K$-user combination network for
the diamond message set, and do so in explicit form. Such a result implies a
certain strength of our inner bound for the DM BC in that it (a) produces a
hitherto unknown capacity region when specialized to the combination network
and (b) may capture many combinatorial aspects of the capacity region of the
$K$-receiver DM BC itself (for the diamond message set). Moreover, we further
extend that inner bound by adding binning to it and providing that inner bound
also in explicit form as a union over coding distributions of four-dimensional
polytopes in the message rates.

##  I Introduction

A general order-theoretic framework for groupcasting over the $K$-receiver DM
BC was proposed in [2, Theorem 1], that allows for a succinct albeit indirect
description of the rate region achieved by up-set rate-splitting and
superposition coding for simultaneously sending the complete set of
$2^{K}{-}1$ independent messages, each desired by some distinct subset of
receivers. In up-set rate-splitting, a message intended for some subset of
receivers is split into sub-messages, with each sub-message to be delivered to
some distinct subset of receivers for all possible such subsets that include
the originally intended set of receivers. The set of sub-messages that are
intended for the same group of receivers are then collected to form a new
reconstructed message. Among the numerous choices [3], the type of
superposition coding used for generating the codebooks for the reconstructed
messages is the one with the superposition order taken to the subset inclusion
order [2]. Finally, each receiver jointly decodes its desired reconstructed
messages which contain the desired messages as well as the partial
interference contained in the undesired sub-messages assigned to it via rate-
splitting.

The inner bound in [2, Theorem 1] is given in implicit form in that it gives
an indirect description of per-distribution polytopes in terms of the split
rates (in higher dimension) rather than the original messages rates. In
principle, the split rates can be projected away with Fourier Motzkin
elimination (FME) [4], but in practice, this is only possible for small
settings, i.e., small number of receivers and/or small message sets since
projecting away all split rates in this general setting is intractable in
general.

In a different line of work on network coding, certain three-layered broadcast
(single-source) networks named combination networks were introduced in [5] to
demonstrate that network coding for a single multicast session can attain
unbounded gain over routing alone. A combination network is defined more
generally in [6] to be a class of three-layer (two-hop) broadcast networks (as
depicted in Fig. 1 for $K=3$) parameterized by $2^{K}{-}1$ finite-and-
arbitrary-capacity noiseless links from the source node in the first layer to
as many nodes of the second layer, with each node in the second layer
connected to a distinct subset of $K$ destination nodes via infinite capacity
links. For the complete message set linear network coding schemes and matching
converses were provided to obtain the capacity region of the two and three-
receiver combination network in [7] (see also [6]) and the symmetric capacity
region (in which the rates of the messages desired by the same number of users
are equal) of the special class of symmetric combination networks, in which
the capacity of links to nodes in the second layer that are connected to the
same number of receivers are identical, in [8, 6]. The general capacity region
of the general combination network for a complete message set (with
$2^{K}{-}1$ messages) for $K{>}3$ remains an open problem. In this regard, the
work of [9] must be mentioned for having produced partial results: in
particular, for two nested messages, i.e., a multicast message intended for
all receivers and a private message intended for a subset of the receivers,
the capacity of the $K$-user general combination network is established in [9]
when the number of receivers that demand only the multicast message is no more
than three.

The general combination network can be seen as a special class of
deterministic DM BCs as observed in [2]. A top-down approach was initiated
therein to study the combination network. In particular, a portion (i.e., an
inner bound) of the general inner bound of [2, Theorem 1] based on up-set
rate-splitting and superposition coding for the DM BC for a complete message
set is proposed as an achievable rate region for the combination network in
[2, Theorem 2] through the specification of a single random coding
distribution. Its indirect description notwithstanding, it was shown in [2],
via its alternative description in [2, Theorem 2], that that achievable rate
region recovers the capacity (for $K=3$) and symmetric capacity (for general
$K$) for symmetric combination networks, results previously obtained via
linear network coding in [7, 8, 6]. Hence, the work in [2] provides a certain
validation for the strength of the rate-splitting and superposition coding
inner bound of [2, Theorem 1] for the $K$-receiver DM BC itself for the
complete message set.

Bolstered by the success of the top-down approach of [2], we continue that
study but for general (not only symmetric) combination networks for any $K>3$
but by focusing on the diamond message set that consists of four messages, one
desired by all $K$ receivers, one by all but two receivers, and two more
desired by all but each one of those two receivers111The name diamond message
set is derived from the depiction of the associated ordered set of four
message indices, each message index being a subset of the set of all receiver
indices at which that message is desired, with the order taken to be the
subset inclusion order, in the form of a Hasse diagram, which would hence be
diamond-shaped.. In particular, we show that, adopting the general framework
of [2, Theorem 1] as is, even in this incomplete message set case222A more
general framework that builds on that of [2] is given in [10] to account for
incomplete message sets in general, but that extra generality turns out to be
unnecessary for the sake of discovering the capacity of the combination
network for the diamond message set, as demonstrated here. is sufficient to
produce the hitherto unknown capacity region of the combination network for
the diamond message set. The capacity result for the combination network in
the special case of three degraded messages, obtained by setting the rate of
one of the messages desired by all but one receiver to zero, was also
previously unknown. Moreover, special instances of the diamond message set
capacity result for various two message set cases, by setting the rates of the
other two messages to zero, recover two-message capacity results for the
combination network from [9] and [11].

In particular, we present an inner bound for $K$-receiver DM BC in terms of
the actual rates of the four messages instead of the split rates as in [2,
Theorem 1] by projecting away the split rates via Fourier Motzkin elimination
[12] as described in Appendix A, in spite of the indeterminate number of
inequalities that describe the per-distribution achievable rate region in
original- and split-rate space. We then specialize this inner bound to the
combination network by choosing a single distribution for the auxiliary and
input random variables to obtain an explicit polyhedral inner bound for the
general combination network.

We establish the capacity result by identifying the inequalities present in
the aforementioned explicit inner bound to be within the class of infinitely
many possible generalized cut set bounds proposed in [6] as outer bounds for
broadcast networks based on the sub-modularity of entropy. Notably, our order-
theoretic description of the inner bound enables that identification by
permitting a description of the inequalities in the inner bound in a form that
is similar to the form of the generalized cut-set bounds of [6].

Beyond establishing the capacity of the general $K$-user combination network
for the diamond message set, our top-down approach suggests that the inner
bound of [2, Theorem 1] given in a more explicit form here is a good one for
the much more general DM BC (with the diamond message set) in that it
specializes to the capacity region in the combination network without symmetry
assumptions, and possibly captures many combinatorial aspects of the capacity
region of the DM BC itself. Nevertheless, we extend that inner bound by adding
binning to rate-splitting and superposition coding and provide an expression
for the resulting inner bound also in explicit form as a union over coding
distributions of four-dimensional polytopes in the message rates.

The rest of this paper is organized as follows. In Section II, we present the
order theory notation and describe the system model. In Section III, we
present the inner bound for the DM BC and its specialization to the general
$K$-user combination network along with a proof of the converse, establishing
the latter’s capacity region for the diamond message set. In Section IV, we
extend the inner bound for the DM BC of Section III based on rate-splitting
and superposition coding by adding binning to it. While binning is not needed
to achieve the capacity of the combination network it is an interesting open
question as to whether the more general inner bound of Section IV would be
optimal for BCs that are more general than the combination network such as the
deterministic broadcast channel. Finally, the paper is concluded in Section V.
An outline of the Fourier-Motzkin Elimination used to obtain the inner bound
for the DM BC of Section III in terms of explicit per-distribution polytopes
is provided in Appendix A and an outline of the proof of the more general
inner bound resulting from the inclusion of binning is given in Appendix B.

##  II Notation and System Model

###  II-A Order Theory

We find it convenient to introduce ideas from order theory following the
notation in [2] to enable the descriptions of the system model and the
results. We consider the ground set to be an ordered set of subsets of
receiver indices in $\\{1,2,\cdots,K\\}\triangleq[1:K]$. We assume the order
to be that of set inclusion, i.e., $S\leq S^{{}^{\prime}}$ if and only if
$S\subseteq S^{{}^{\prime}}$ while $S$ and $S^{{}^{\prime}}$ are incomparable
if neither $S\subseteq S^{{}^{\prime}}$ nor $S^{{}^{\prime}}\subseteq S$. Let
$\mathsf{P}$ be such an ordered set of sets and $\mathsf{Q}$ be a subset of
$\mathsf{P}$. Note that the sans serif letter is used to represent a set of
sets like $\mathsf{P},\mathsf{Q}$ and $\mathsf{E}$ to distinguish it from
sets. We say that $\mathsf{Q}$ is an up-set if $S\in\mathsf{Q}$,
$S^{{}^{\prime}}\in\mathsf{P}$, and $S^{{}^{\prime}}\geq S$ implies
$S^{{}^{\prime}}\in Q$ and a down-set if $S\in Q$,
$S^{{}^{\prime}}\in\mathsf{P}$, and $S^{{}^{\prime}}\leq S$ implies
$S^{{}^{\prime}}\in\mathsf{Q}$.

Moreover, for any subset $\mathsf{Q}\subseteq\mathsf{P}$, we define the
smallest down-set containing $\mathsf{Q}$ as
$\downarrow_{\mathsf{P}}\mathsf{Q}=\\{S^{{}^{\prime}}\in\mathsf{P}:S^{{}^{\prime}}\leq
S,S\in\mathsf{Q}\\}$ and the smallest up-set containing $\mathsf{Q}$ as
$\uparrow_{\mathsf{P}}\mathsf{Q}=\\{S^{{}^{\prime}}\in\mathsf{P}:S\leq
S^{{}^{\prime}},S\in\mathsf{Q}\\}$. For the sake of simplicity, we abbreviate
the set $\\{i_{1},i_{2},..,i_{N}\\}\subseteq\\{1,\cdots,K\\}$ for any positive
number $N\leq K$ as $i_{1}i_{2}\cdots i_{N}$, adopting the convention that
$i_{1}<i_{2}<\cdots<i_{N}$. For instance, let $\mathsf{P}$ be the power set of
$[1:3]$, i.e., $\mathsf{P}=\\{\phi,1,2,3,12,13,23,123\\}$. Then, for instance,
we have $\downarrow_{\mathsf{P}}\\{13\\}=\\{\phi,1,3,13\\}$ and
$\uparrow_{\mathsf{P}}\\{13\\}=\\{13,123\\}$. In some cases, especially when
the set $S=\\{i_{1},i_{2},..,i_{N}\\}$ has many elements, we find it more
convenient to denote it by its complement, i.e., $\overline{S}=[1:K]\backslash
S$. For example, the set $\overline{\\{i_{1}\\}}$, also denoted
$\overline{i}_{1}$, and is the set $[1:K]\backslash\\{i_{1}\\}$.

Finally, for any $\mathsf{F}\subseteq\mathsf{P}$ and $i\in[1:K]$, we define
$\mathsf{W}_{i}^{\mathsf{F}}$ as the set of sets in $\mathsf{F}$ containing
$i$ so that $\mathsf{W}_{i}^{\mathsf{F}}\triangleq\\{S\in\mathsf{F}:i\in
S\\}$.

From the given notation, we can show that the following relationships are
true:

  1. 1.

For any set $S=i_{1}i_{2}\cdots i_{N}\subseteq\\{1,2,\cdots,K\\}$, we have

$\displaystyle\cup_{k\in S}\mathsf{W}_{k}^{\mathsf{P}}$
$\displaystyle=\uparrow_{\mathsf{P}}\\{i_{1},i_{2},\cdots,i_{N}\\}$ (1)
$\displaystyle\cap_{k\in S}\mathsf{W}_{k}^{\mathsf{P}}$
$\displaystyle=\uparrow_{\mathsf{P}}\\{i_{1}i_{2}\cdots i_{N}\\}$ (2)

  2. 2.

For any set $S=i_{1}i_{2}\cdots i_{N}\subset\\{1,2,\cdots,K\\}$ and any
$i\in[1:K]$

$\displaystyle\downarrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{\overline{i_{1}},\overline{i_{2}},\cdots,\overline{i_{N}}\\}\cup\uparrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{S\\}$
$\displaystyle=\mathsf{W}_{i}^{\mathsf{P}}$ (3)
$\displaystyle\downarrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{\overline{i_{1}},\overline{i_{2}},\cdots,\overline{i_{N}}\\}\cap\uparrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{S\\}$
$\displaystyle=\phi$ (4)
$\displaystyle\downarrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{\overline{S}\\}\cup\uparrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{i_{1},i_{2},\cdots,i_{N}\\}$
$\displaystyle=\mathsf{W}_{i}^{\mathsf{P}}$ (5)
$\displaystyle\downarrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{\overline{S}\\}\cap\uparrow_{\mathsf{W}_{i}^{\mathsf{P}}}\\{i_{1},i_{2},\cdots,i_{N}\\}$
$\displaystyle=\phi$ (6)

###  II-B System Model

We consider a DM BC with the transmitter denoted by the transmitted symbol
$X\in\mathcal{X}$, $K$ receivers denoted by their respective channel outputs
$Y_{i}\in\mathcal{Y}_{i}$, and the channel transition probability
$W(y_{1}y_{2}\cdots y_{K}|x)$ where the conditional probability of $n$ channel
outputs $Y_{1}^{n},\cdots,Y_{K}^{n}$ with
$Y_{k}^{n}\triangleq(Y_{k,1},\cdots,Y_{k,n})$, conditioned on $n$ channel
inputs $X^{n}\triangleq(X_{1},\cdots,X_{n})$ is given by

$p(y_{1}^{n}\cdots y_{K}^{n}|x^{n})=\prod_{j=1}^{n}W(y_{1j}\cdots
y_{Kj}|x_{j})$

where $X_{j},Y_{1,j},\cdots Y_{K,j}$ are the channel input and outputs in the
$j^{th}$ channel use.

The message $M_{S}\in[1:2^{nR_{S}}]$ of rate $R_{S}$ is indexed by the subset
$S\subseteq[1:K]$ of receivers it is intended for. Hence, $M_{\overline{S}}$
is the message intended for all receivers except the receivers in
$\overline{S}$. The diamond message set consists of four messages,
$M_{\overline{\phi}}$, a message intended for all receivers,
$M_{\overline{K-1.K}}$ a message intended for the first $K-2$ receivers333The
dot separating $K-1$ and $K$ in $M_{\overline{K-1.K}}$ is a slight abuse of
notation since the subscript in $M_{\overline{K-1K}}$ can be confusing., and
$M_{\overline{K-1}}$ and $M_{\overline{K}}$, two messages intended for all but
receivers $K-1$ or $K$. Define $\mathsf{E}$ as the set of all message indices
so that
$\mathsf{E}=\\{\overline{\phi},\overline{K},\overline{K-1},\overline{K-1.K}\\}$.
Note that receiver $Y_{K}$ demands $M_{\overline{\phi}}$ and
$M_{\overline{K-1}}$, receiver $Y_{K-1}$ demands $M_{\overline{\phi}}$ and
$M_{\overline{K}}$, while the rest of receivers $\\{Y_{i}\\}_{i=1}^{K-2}$
demand all four messages.

The combination network [6, 2] is a special case of the general DM-BC. As
shown in Fig. 1 for the three-receiver case, it consists of three layers of
nodes. The top layer and bottom layer consist of the single source node $X$
and $K$ receivers $\\{Y_{i}\\}_{i=1}^{K}$, respectively. While, the middle
layer consists of $2^{K}-1$ intermediate nodes, denoted $V_{S}$ for all
$S\in\mathsf{P}$ where $\mathsf{P}$ be the power set of $[1:K]$ excluding the
empty set. The source is connected to each of the intermediate nodes $V_{S}$
through a noiseless link of capacity $C_{S}$ (per channel use). On the other
hand, each receiver $Y_{i}$ is connected to $2^{K-1}$ intermediate nodes
$V_{\mathsf{W}_{i}^{\mathsf{P}}}\triangleq\\{V_{S}\\}_{S\in\mathsf{W}_{i}^{\mathsf{P}}}$
via noiseless links of unlimited capacity. An interesting connection between
the combination networks and the DM BC is revealed in [2] wherein the authors
considered the combination network to be a network of noiseless DM BCs with
the channel input $X$ connected in different ways to the channel outputs
$\\{Y_{i}\\}_{i=1}^{K}$ each through a noiseless BC. In particular, the
channel input $X$ contains $2^{K}{-}1$ components $V_{S}$, for all
$S\in\mathsf{P}$. For each $S$, the component $V_{S}\in\mathcal{V}_{S}$, where
$|\mathcal{V}_{S}|=2^{C_{S}}$, is noiselessly received at each receiver
$Y_{i}$ for all $i\in S$ and not received at the receivers $Y_{j}$ with
$j\not\in S$, i.e., $Y_{i}=V_{\mathsf{W}_{i}^{\mathsf{P}}}$.

Denote the set of the four messages $\\{M_{S}:S\in\mathsf{E}\\}$ to be sent
over a $K$-user DM BC as $M_{\mathsf{E}}$. A
$(\\{2^{nR_{S}}\\}_{S\in\mathsf{E}},n)$ code consists of (i) an encoder that
assigns to each message tuple
$m_{\mathsf{E}}\in\prod_{S\in\mathsf{E}}[1:2^{nR_{S}}]$ a codeword
$x^{n}(m_{\mathsf{E}})$ (ii) a decoder at each receiver, with the $k^{th}$
decoder mapping the received sequence $Y_{k}^{n}$ for each $k\in[1:K]$ into
the set of decoded messages
$\\{\tilde{m}_{S}:S\in\mathsf{W}_{k}^{\mathsf{E}}\\}\in\prod_{S\in\mathsf{W}_{k}^{\mathsf{E}}}[1:2^{nR_{S}}]$,
denoted as $\tilde{m}_{\mathsf{W}_{k}^{\mathsf{E}}}$. The probability of error
$P_{e}^{(n)}$ is the probability that not all receivers decode their intended
messages correctly. The rate tuple $(R_{S}:S\in\mathsf{E})$ is said to be
achievable if there exists a sequence of
$(\\{2^{nR_{S}}\\}_{S\in\mathsf{E}},n)$ codes with $P_{e}^{(n)}\rightarrow 0$
as $n\rightarrow\infty$. The closure of the union of achievable rates is the
capacity region.

$X$$V_{1}$$V_{2}$$V_{3}$$V_{12}$$V_{13}$$V_{23}$$V_{123}$$Y_{1}$$Y_{2}$$Y_{3}$
Figure 1: A combination network with $7$ intermediate nodes and three
receivers. The dark/dashed lines represent finite/infinite capacity links,
respectively. The capacity of the dark link connecting the node $X$ to the
node $V_{S}$ is $C_{S}$ for each $S\in\mathsf{P}$. For brevity, the
source/destination nodes are denoted by their transmitted/received symbols and
the intermediate nodes by their output symbols. Encoders/decoders are not
shown.

##  III Results

In the following theorem, we present the inner bound of [2, Theorem 1]
specialized to the diamond message set in the more explicit form of a union of
four-dimensional polytopes.

###### Theorem 1

An inner bound of $K$-user DM BC for the diamond message set with
$\mathsf{E}=\\{\overline{\phi},\overline{K},\overline{K-1},\overline{K-1.K}\\}$
is the set of non-negative rate tuples
($R_{\overline{\phi}},R_{\overline{K}},R_{\overline{K-1}},R_{\overline{K-1.K}}$)
satisfying the following for all $j,j_{1},j_{2}\in\\{1,2,\cdots,K-2\\}$

$\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}\leq
I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (7) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (8) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$ $\displaystyle\hskip
85.35826pt+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (9) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$ $\displaystyle\hskip
85.35826pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (10)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j})$ (11) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$ $\displaystyle\hskip
85.35826pt+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (12)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$ $\displaystyle\hskip
85.35826pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (13)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(14) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(15) $\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(16) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$ $\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(17) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}})$ $\displaystyle\hskip
73.97733pt+I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(18)

for some joint distribution of the auxiliary and input random variables
$(U_{\overline{\phi}},U_{\overline{K}},U_{\overline{K-1}},X)$ that is of the
form

$\displaystyle p(u_{\overline{\phi}},u_{\overline{K}},u_{\overline{K-1}},x)$
$\displaystyle=p(u_{\overline{\phi}})\times
p(u_{\overline{K}}|u_{\overline{\phi}})\times
p(u_{\overline{K-1}}|u_{\overline{\phi}})$ $\displaystyle\quad\quad\quad\times
p(x|u_{\overline{\phi}},u_{\overline{K}},u_{\overline{K-1}})$ (19)

###### Proof 1

We provide only an outline for the rate-splitting and superposition coding
scheme of [2, Theorem 1]. First, up-set rate splitting is used, i.e., each
message $M_{S}$ is divided into a collection of sub-messages $M_{S\rightarrow
S^{\prime}}$ where $S^{\prime}\in\uparrow_{\mathsf{E}}S$. Then, the sub-
message $M_{S\rightarrow S^{{}^{\prime}}}$ will be treated as if it was
intended for the receivers in the larger set $S^{{}^{\prime}}$ instead of in
$S$. Hence, the messages $M_{\overline{K-1.K}},M_{\overline{K}}$ and
$M_{\overline{K-1}}$ are split into
$(M_{\overline{K-1.K}\rightarrow\overline{\phi}},M_{\overline{K-1.K}\rightarrow\overline{K}},M_{\overline{K-1.K}\rightarrow\overline{K-1}},M_{\overline{K-1.K}\rightarrow\overline{K-1.K}})$,
$(M_{\overline{K}\rightarrow\overline{\phi}},M_{\overline{K}\rightarrow\overline{K}})$,
$(M_{\overline{K-1}\rightarrow\overline{\phi}},M_{\overline{K-1}\rightarrow\overline{K-1}})$,
with rates
$(R_{\overline{K-1.K}\rightarrow\overline{\phi}},R_{\overline{K-1.K}\rightarrow\overline{K}},R_{\overline{K-1.K}\rightarrow\overline{K-1}},R_{\overline{K-1.K}\rightarrow\overline{K-1.K}})$,
$(R_{\overline{K}\rightarrow\overline{\phi}},R_{\overline{K}\rightarrow\overline{K}})$,
and
$(R_{\overline{K-1}\rightarrow\overline{\phi}},R_{\overline{K-1}\rightarrow\overline{K-1}})$,
respectively. The common message and a sub-message of each of the other three
messages of the form $M_{S\rightarrow\bar{\phi}}$, that is, the reconstructed
message
$(M_{\overline{\phi}},M_{\overline{K-1}\rightarrow\overline{\phi}},M_{\overline{K}\rightarrow\overline{\phi}},M_{\overline{K-1.K}\rightarrow\overline{\phi}})$
is represented by the cloud center $U_{\overline{\phi}}$. Conditionally
independently (conditioned on $U_{\overline{\phi}}$), the reconstructed
message pair
$(M_{\overline{K-1}\rightarrow\overline{K-1}},M_{\overline{K-1.K}\rightarrow\overline{K-1}})$
is represented by $U_{\overline{K-1}}$ and
$(M_{\overline{K}\rightarrow\overline{K}},M_{\overline{K-1.K}\rightarrow\overline{K}})$
is represented by $U_{\overline{K}}$. Finally,
$M_{\overline{K-1.K}\rightarrow\overline{K-1.K}}$ is represented by
$U_{\overline{K-1.K}}=X$. Receivers $\\{Y_{i}\\}_{i=1}^{K-2}$ decode the four
intended messages by the joint unique decoding of $X$ (and hence
$U_{\overline{\phi}},U_{\overline{K}},U_{\overline{K-1}},U_{\overline{K-1.K}}$),
and this happens successfully as long as

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j})$ (20) $\displaystyle
R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$ $\displaystyle\quad-
R_{\overline{K-1}\rightarrow\overline{\phi}}-R_{\overline{K}\rightarrow\overline{\phi}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$ (21) $\displaystyle
R_{\overline{K}}+R_{\overline{K-1.K}}-R_{\overline{K}\rightarrow\overline{\phi}}$
$\displaystyle\quad-
R_{\overline{K-1.K}\rightarrow\overline{K-1}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$ (22) $\displaystyle
R_{\overline{K-1}}+R_{\overline{K-1.K}}-R_{\overline{K-1}\rightarrow\overline{\phi}}$
$\displaystyle\quad-
R_{\overline{K-1.K}\rightarrow\overline{K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$ (23) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad-
R_{\overline{K-1.K}\rightarrow\overline{K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$ (24)

for all $j\in\\{1,2,\cdots,K-2\\}$.

On the other hand, receiver $Y_{K-1}$ finds the two intended messages
$M_{\overline{\phi}}$ and $M_{\overline{K}}$ by decoding
$(U_{\overline{\phi}},U_{\overline{K}})$, and receiver $Y_{K}$ find the two
intended messages $M_{\overline{\phi}}$ and $M_{\overline{K-1}}$ by decoding
$(U_{\overline{\phi}},U_{\overline{K-1}})$. Receivers $Y_{K-1}$ and $Y_{K}$
decode their intended pair of messages successfully provided the following
inequalities hold:

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}+R_{\overline{K-1}\rightarrow\overline{\phi}}$
$\displaystyle+R_{\overline{K-1.K}\rightarrow\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (25) $\displaystyle
R_{\overline{K}}-R_{\overline{K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K}}\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$ (26) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}\rightarrow\overline{\phi}}$
$\displaystyle+R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (27) $\displaystyle
R_{\overline{K-1}}-R_{\overline{K-1}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$ (28)

Besides inequalities (20)-(28) there are eight inequalities to account for the
non-negativity of the split rates given in (116)-(123) in Appendix A. Taken
together, these inequalities describe a nine-dimensional polytope (per
admissible distribution of (19)) in original- and split-rates space. By
projecting away the five split rates using a structured form of the FME method
described in Appendix A, we get the achievable region in the positive orthant
defined by the inequalities (7)-(18). A high-level description of the issues
encountered in performing the FME procedure is given in Remark 1. The four
successively reduced-dimensional intermediate polytopes (of dimensions eight
down to five) obtained after projecting out each split rate, in a certain
desirable order, after the elimination of the associated redundant
inequalities in this rather large FME procedure, are given in sequence in
Appendix A. That order permits a relatively efficient completion of the
projection of all five split rates.

###### Remark 1

Note that since $K$ is arbitrary, there are an indeterminate number of
inequalities that describe the polyhedral achievable rate region per random
coding distribution in nine-dimensional original- and split-rate space. In
particular, including the non-negativity of split rates, there are $5K+2$
inequalities given by (20)–(28) and (116)-(123) that describe each such
polytope. This means that the FME procedure must deal with groups of
inequalities (for general $K$) at a time instead of exhaustively listing them
(for this reason, the FME software of [13] cannot be directly used). More
importantly, the elimination of the five split rates presents $5!=120$
possibilities for the orders in which to eliminate them, all of which must
lead, in principle, to the right four-dimensional polytope described by the
inequalities (7)-(18). It turns out however, that at least some of these
orders render the FME procedure too tedious to perform beyond even the second
or third steps of the five-step process, including the identification (and
hence, elimination) of the redundant inequalities that arise at each step.
Appendix A gives a “good” order of elimination and the intermediate results
obtained after projecting out each of the five split rates in that order that
not only makes it possible to complete the five-step task with reasonable
effort but also offers the possibility of verifying if two of the successively
reduced-dimensional polytopes at the end of steps 2 and 4 satisfy certain
symmetry conditions which, intuitively, they must (and which they do).

We next state the inner bound of Theorem 1 when it is applied to the
combination network by setting $X=V_{\mathsf{P}}$ and
$Y_{j}=V_{\mathsf{W}_{j}^{\mathsf{P}}}$. The mutual information terms in the
bounds are written as the difference between the entropy and conditional
entropy so that we may get insights into optimizing the rate region over the
coding distributions.

###### Corollary 1

An inner bound of $K$-user combination networks
$\mathsf{E}=\\{\overline{\phi},\overline{K},\overline{K-1},\overline{K-1.K}\\}$
is the set of non-negative rate tuples
($R_{\overline{\phi}},R_{\overline{K}},R_{\overline{K-1}},R_{\overline{K-1.K}}$)
satisfying the following for all $j,j_{1},j_{2}\in\\{1,2,\cdots,K-2\\}$

$\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}\leq
H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
(29) $\displaystyle R_{\overline{\phi}}+R_{\overline{K}}\leq
H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(30) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
(31) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(32) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}})$ (33) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
(34) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(35) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
(36) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(37) $\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(38) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(39) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}\leq
H(V_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}|U_{\overline{\phi}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{j_{2}}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle\qquad\qquad\qquad\quad+H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})-H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
(40)

for some joint distribution of the auxiliary and input random variables
$(U_{\overline{\phi}},U_{\overline{K}},U_{\overline{K-1}},X=V_{\mathsf{P}})$
that is of the form

$\displaystyle p(u_{\overline{\phi}},u_{\overline{K}},u_{\overline{K-1}},x)$
$\displaystyle=p(u_{\overline{\phi}})\times
p(u_{\overline{K}}|u_{\overline{\phi}})\times
p(u_{\overline{K-1}}|u_{\overline{\phi}})$ $\displaystyle\quad\quad\quad\times
p(x|u_{\overline{\phi}},u_{\overline{K}},u_{\overline{K-1}})$ (41)

In the following theorem, we show that the inner bound in Theorem 1 achieves
the capacity region of the general combination network by identifying the
optimal distribution for the auxiliary random variables
$U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}}$ and the channel
input components $\\{V_{S}\\}_{S\in\mathsf{P}}$. The optimality of that
distribution is proved indirectly by showing that the resulting inequalities
are particular members of the generic family of generalized cut-set (outer)
bounds found in [6].

###### Theorem 2

The capacity region of the $K$-user combination network for the diamond
message set with
$\mathsf{E}=\\{M_{\overline{\phi}},M_{\overline{K}},M_{\overline{K-1}},M_{\overline{K-1.K}}\\}$
is the set of non-negative rate tuples
($R_{\overline{\phi}},R_{\overline{K}},R_{\overline{K-1}},R_{\overline{K-1.K}}$)
satisfying for all $j\in\\{1,2,\cdots,K-2\\}$

$\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}\leq
C_{\mathsf{W}_{K}^{\mathsf{P}}}$ (42) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}\leq C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$
(43) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
C_{\downarrow_{\mathsf{W}_{K-1}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(44) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
C_{\mathsf{W}_{j}^{\mathsf{P}}}$ (45) $\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\qquad
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(46) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\qquad
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K},\overline{K-1}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(47)

where $C_{\mathsf{W}}=\sum_{S\in\mathsf{W}}C_{S}$ for any
$\mathsf{W}\subseteq\mathsf{P}$.

###### Remark 2

This capacity result generalizes three previously known results. First, it
reproduces the capacity region for two nested (i.e., degraded) messages with
at most two receivers demanding only the common messages $M_{\overline{\phi}}$
given in [14, Theorems 4 and 5] and [9, Theorem 3] by setting
$R_{\overline{K-1.K}}=R_{\overline{K-1}}=0$ and
$R_{\overline{K}}=R_{\overline{K-1}}=0$ in (42)-(47). Moreover, Theorem 2 also
recovers the capacity region for two messages each intended for $K-1$
receivers given in [14, Theorem 3] by setting
$R_{\overline{\phi}}=R_{\overline{K-1.K}}=0$ in (42)-(47). It must be noted
here that the converse proofs in [9] and [14] are established from “first
principles”, and while they use the sub-modularity of entropy, they do not
take a top-down approach as we do here in Section III-B of making the
connection to the generalized cut-set bound framework of [6]. Moreover,
achievability for up to two common receivers was proved in [9, Proposition 1]
using linear network coding tailored to the combination network and two nested
messages, whereas we take the top-down approach in Section III-A of [2, 14] of
starting from an inner bound for the DM BC and specializing it to the
combination network.

The special case of Theorem 2 for three degraded messages (which is more
general than [14, Theorem 5] and [9, Theorem 3]) is given next. We simply set
$R_{\overline{K-1}}=0$ in Theorem 2 and note that (44) becomes redundant
because of (49) since
$C_{\downarrow_{\mathsf{W}_{K-1}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}=C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}}}\geq
C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$

###### Corollary 2

The capacity region of the $K$-user combination network for the three degraded
messages, i.e.,
$\mathsf{E}=\\{M_{\overline{\phi}},M_{\overline{K}},M_{\overline{K-1.K}}\\}$
is the set of non-negative rate tuples
($R_{\overline{\phi}},R_{\overline{K}},R_{\overline{K-1.K}}$) satisfying for
all $j\in\\{1,2,\cdots,K-2\\}$

$\displaystyle R_{\overline{\phi}}\leq C_{\mathsf{W}_{K}^{\mathsf{P}}}$ (48)
$\displaystyle R_{\overline{\phi}}+R_{\overline{K}}\leq
C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$ (49) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
C_{\mathsf{W}_{j}^{\mathsf{P}}}$ (50) $\displaystyle
2R_{\overline{\phi}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\qquad
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(51) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\qquad
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K},\overline{K-1}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(52)

###### Remark 3

The capacity region of the $K$-user combination network for the two degraded
messages, i.e., $\mathsf{E}=\\{M_{\overline{\phi}},M_{\overline{K-1.K}}\\}$ is
the set of non-negative rate pairs
($R_{\overline{\phi}},R_{\overline{K-1.K}}$) satisfying for all
$j\in\\{1,2,\cdots,K-2\\}$ the inequalities (48)-(51) (with
$R_{\overline{K}}=0$). The inequality (52) becomes redundant because of (51)
(with $R_{\overline{K}}=0$) since
$C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}\leq
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K},\overline{K-1}\\}}$.
This capacity region coincides with the one found in [14, Theorem 5] and [9,
Theorem 3].

###  III-A Proof of Achievability for Theorem 2

One or both of the two negative conditional entropy terms, namely,
$H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
and
$H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
appear in all the bounds (except in (33)) of the inequalities of Corollary 1.
Hence those bounds can be upper bounded by setting
$V_{\mathsf{W}_{K}^{\mathsf{P}}}=f(U_{\overline{\phi}},U_{\overline{K-1}})$
and
$V_{\mathsf{W}_{K-1}^{\mathsf{P}}}=g(U_{\overline{\phi}},U_{\overline{K}})$
for some deterministic functions $f$ and $g$. Next, one or both of the
positive entropy terms $H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}})$ and
$H(V_{\mathsf{W}_{K}^{\mathsf{P}}})$ appear in each of the bounds (except in
(33)) and all such terms can be maximized by taking the deterministic
functions $f$ and $g$ to be identity maps so that
$V_{\mathsf{W}_{K}^{\mathsf{P}}}=(U_{\overline{\phi}},U_{\overline{K-1}})$ and
$V_{\mathsf{W}_{K-1}^{\mathsf{P}}}=(U_{\overline{\phi}},U_{\overline{K}})$
(thus this choice maximizes the first two bounds (29) and (30) of Corollary
1). Note that this choice also simultaneously maximizes the positive
conditional entropy terms of the form
$H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}})$
and $H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K}})$
in the bounds of (34) and (35) and
$H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
in the bounds of (36)-(39). Next, consider the positive conditional entropy
terms of the form $H(V_{\mathsf{W}_{K-1}^{\mathsf{P}}}|U_{\overline{\phi}})$,
$H(V_{\mathsf{W}_{K}^{\mathsf{P}}}|U_{\overline{\phi}})$ in the bounds of
(31)-(32) and (36)-(37) and
$H(V_{\mathsf{W}_{j}^{\mathsf{P}}}|U_{\overline{\phi}})$ in (39)-(40). All of
these terms are maximized by choosing (given
$V_{\mathsf{W}_{K}^{\mathsf{P}}}=(U_{\overline{\phi}},U_{\overline{K-1}})$ and
$V_{\mathsf{W}_{K-1}^{\mathsf{P}}}=(U_{\overline{\phi}},U_{\overline{K}})$)
$U_{\overline{\phi}}$ to be the just the common part of
$V_{\mathsf{W}_{K-1}^{\mathsf{P}}}$ and $V_{\mathsf{W}_{K}^{\mathsf{P}}}$.
After making these choices, given that there are cardinality constraints on
the alphabet $\mathcal{V}_{S}$ of $V_{S}$ of $2^{C_{S}}$, all the bounds are
maximized by choosing the input components $(V_{S}:S\in\mathsf{F})$ to be
uniform and independent with $\mathcal{V}_{S}$ taken to be $[1:2^{C_{S}}]$.

The above argument suggests (even though it does not prove the optimality of)
the choice of coding distribution resulting by setting

$\displaystyle U_{\overline{\phi}}$
$\displaystyle=V_{\uparrow_{\mathsf{P}}\\{K-1.K\\}}$ (53) $\displaystyle
U_{\overline{K-1}}$ $\displaystyle=V_{\mathsf{W}_{K}^{\mathsf{P}}}$ (54)
$\displaystyle U_{\overline{K}}$
$\displaystyle=V_{\mathsf{W}_{K-1}^{\mathsf{P}}}$ (55) $\displaystyle X$
$\displaystyle=V_{\mathsf{P}}$ (56)

and choosing the channel input components $V_{S}$ for all $S\in\mathsf{P}$ to
be independent and uniformly distributed over $\mathcal{V}_{S}$ where
$|\mathcal{V}_{S}|=2^{C_{S}}$. The achievability proof now follows from
Theorem 1 by choosing the above coding distribution. Note that such a choice
of the auxiliary random variables and the channel input components
$(U_{\overline{\phi}},U_{\overline{K}},U_{\overline{K-1}},X)$ has a joint
distribution that satisfies (19), as it must. For this specific choice, we can
compute the mutual information terms in (7)-(18) using
$Y_{i}=V_{\mathsf{W}_{i}^{\mathsf{P}}}$ and (3)-(6) to obtain

$\displaystyle I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle=C_{\mathsf{W}_{K}^{\mathsf{P}}}$ (57) $\displaystyle
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
$\displaystyle=C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$ (58) $\displaystyle
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$
$\displaystyle=C_{\downarrow_{\mathsf{W}_{K-1}^{\mathsf{P}}}\\{\overline{K}\\}}$
(59) $\displaystyle I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$
$\displaystyle=C_{\downarrow_{\mathsf{W}_{K}^{\mathsf{P}}}\\{\overline{K-1}\\}}$
(60) $\displaystyle I(X;Y_{j})$
$\displaystyle=C_{\mathsf{W}_{j}^{\mathsf{P}}}$ (61) $\displaystyle
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$
$\displaystyle=C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K}\\}}$
(62) $\displaystyle I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$
$\displaystyle=C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1}\\}}$
(63) $\displaystyle
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle=C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}$
(64) $\displaystyle I(X;Y_{j}|U_{\overline{\phi}})$
$\displaystyle=C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K},\overline{K-1}\\}}$
(65)

where $j\in\\{1,2,\cdots,K-2\\}$. Hence, we get (42)-(43) by substituting
(57)-(58) in (7)-(8) and (44) by substituting (59)-(60) in (9)-(10) since
$C_{\downarrow_{\mathsf{W}_{K-1}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}=C_{\downarrow_{\mathsf{W}_{K}^{\mathsf{P}}}\\{\overline{K-1}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$.
Moreover, we get (45) directly by substituting (61) in (11). Then, we obtain
(46) from (16) using (57)-(58) and (64). Finally, we get (47) by substituting
(57)-(58) and (65) in (17).

The rest of the inequalities in the inner bound, i.e., (12)-(15) and (18) are
redundant, as we show next. By computing the mutual information terms in
(12)-(15) and (18) for the specified coding distribution in (53)-(56), it is
left to the reader to verify that we obtain the following five categories of
bounds (with each $j,j_{1},j_{2}$ taking all possible values in the set
$\\{1,2,\cdots,K-2\\}$)

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(66) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$
(67) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\quad
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\downarrow_{\mathsf{W}_{K-1}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(68) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\quad
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\downarrow_{\mathsf{W}_{K}^{\mathsf{P}}}\\{\overline{K-1}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}$
(69) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}\leq$
$\displaystyle\quad
C_{\downarrow_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}\\{\overline{K},\overline{K-1}\\}}+C_{\downarrow_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(70)

We next show that these categories of bounds are all redundant. First, (66)
and (67) are redundant from (45). Using (85), we can rewrite the right hand
side of (66) and lower bound it as follows

$\displaystyle
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle=C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle\geq C_{\mathsf{W}_{j}^{\mathsf{P}}}$ (71)

where (71) follows from the fact that
$C_{\mathsf{W}_{j}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}\leq
C_{\mathsf{W}_{K}^{\mathsf{P}}}$. Similarly, we can show that (67) is
redundant due to (45).

Moreover, (68) and (69) are also redundant from (45) since we can rewrite the
right hand side of (68), using (85), and lower bound it as follows

$\displaystyle
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\downarrow_{\mathsf{W}_{K-1}^{\mathsf{P}}}\\{\overline{K}\\}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle=C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap(\mathsf{W}_{K}^{\mathsf{P}}\cup\mathsf{W}_{K-1}^{\mathsf{P}})}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}-C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle=C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap(\mathsf{W}_{K}^{\mathsf{P}}\cup\mathsf{W}_{K-1}^{\mathsf{P}})}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K-1}^{\mathsf{P}}}$
(72) $\displaystyle\geq C_{\mathsf{W}_{j}^{\mathsf{P}}},$

where (72) follows from the modularity of $C_{\mathsf{W}}$.

Finally, (70) is redundant from two times (45) since the right hand side of
(68) can be written, using (85)-(86), and lower bounded as follows

$\displaystyle
C_{\downarrow_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}\\{\overline{K},\overline{K-1}\\}}+C_{\downarrow_{\mathsf{W}_{j_{2}}^{\mathsf{P}}}\\{\overline{K-1.K}\\}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle=C_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}-C_{\mathsf{W}_{j_{1}}^{\mathsf{P}}\cap\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}+C_{\mathsf{W}_{j_{2}}^{\mathsf{P}}}-C_{\mathsf{W}_{j_{2}}^{\mathsf{P}}\cap(\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}})}$
$\displaystyle\quad+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle=C_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}-C_{\mathsf{W}_{j_{1}}^{\mathsf{P}}\cap\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}$
$\displaystyle\quad+C_{\mathsf{W}_{j_{2}}^{\mathsf{P}}}-C_{\mathsf{W}_{j_{2}}^{\mathsf{P}}\cap(\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}})}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}}}$
(73) $\displaystyle\geq
C_{\mathsf{W}_{j_{1}}^{\mathsf{P}}}+C_{\mathsf{W}_{j_{2}}^{\mathsf{P}}},$

where (73) follows from the modularity of $C_{\mathsf{W}}$, and hence,
$C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}=C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}}}$.

This concludes the achievability of the polytope described by the inequalities
(42)-(47) by the single coding distribution given in (53)-(56).

###### Remark 4

In Section III-B, we show that the polytope (in the positive orthant)
described by (42)-(47) is indeed the capacity region of the combination
network. This indirectly shows that when the inner bound of Theorem 1 is
specialized to the combination network as a union of polytopes with the union
taken over all admissible coding distributions of the form (19) then the
distribution given in (53)-(56) is extremal in that the rate region it
produces subsumes the rate regions produced by any other distribution that
satisfies (19).

###  III-B The Converse Proof for Theorem 2

The converse proof of (42)-(43) and (45) follows directly from the cut-set
bounds. In what follows, we show that the inequalities (44) and (46)-(47) are
outer bounds by identifying them as belonging to the infinite class of
generalized cut-set bounds obtained in [6]. Those bounds provide a generic
framework that can be used to obtain upper bounds on the achievable rates sent
over any broadcast network that can be described by a directed acyclic graph
with a non-negative capacity for each link or arc in the graph (and hence,
over the combination network). As shown in [6], these upper bounds take the
generic form

$\sum_{i\in
S^{{}^{\prime}}}\alpha_{i}R_{\Phi_{i}(\mathsf{W}_{1}^{\mathsf{E}},\mathsf{W}_{2}^{\mathsf{E}},\cdots,\mathsf{W}_{K}^{\mathsf{E}})}\leq\sum_{i\in
S^{{}^{\prime}}}\alpha_{i}C_{\Phi_{i}(\mathsf{W}_{1}^{\mathsf{P}},\mathsf{W}_{2}^{\mathsf{P}},\cdots,\mathsf{W}_{K}^{\mathsf{P}})}$
(74)

where $S^{{}^{\prime}}$ is a finite non-empty set, $\alpha_{i}$’s are non-
negative real numbers and $\\{\Phi_{i}\\}_{i\in S^{{}^{\prime}}}$ is a
collection of set operators. The set operator is defined as a finite sequence
of intersections and unions acting on any $K$ subsets of $\mathsf{P}$ to
produce a subset of $\mathsf{P}$. Furthermore, these set operators
$\\{\Phi_{i}\\}_{i\in S^{{}^{\prime}}}$ in (74) must satisfy the following
extremal inequality

$\displaystyle\sum_{i\in
S_{1}}\alpha_{i}f(\Phi_{i}(\mathsf{W}_{1},\cdots,\mathsf{W}_{K}))\leq\sum_{j\in
S_{2}}\beta_{j}f(\Pi_{j}(\mathsf{W}_{1},\cdots,\mathsf{W}_{K}))$
$\displaystyle\;+\sum_{l\in
S_{3}}\gamma_{l}\big{(}f(\Gamma_{l}^{+}(\mathsf{W}_{1},\cdots,\mathsf{W}_{K}))-f(\Gamma_{l}^{-}(\mathsf{W}_{1},\cdots,\mathsf{W}_{K}))\big{)}$
(75)

for any submodular function $f$, with equality holding when $f$ is a modular
function, $\\{\mathsf{W}_{i}\\}_{i=1}^{K}\subseteq\mathsf{P}$, nonempty finite
sets $S_{1},S_{2},S_{3}$, collection of non-negative real numbers
($\alpha_{i},\beta_{j},\gamma_{l}$), and a collection of set operators
$\Pi_{j},\Gamma_{l}^{+},\Gamma_{l}^{-}$ such that $\Pi_{j},\Gamma_{l}^{+}$ are
finite sequences of unions only, and
$\Gamma_{l}^{-}(\mathsf{W}_{1},\mathsf{W}_{2},\cdots,\mathsf{W}_{K})\subseteq\Gamma_{l}^{+}(\mathsf{W}_{1},\mathsf{W}_{2},\cdots,\mathsf{W}_{K})$
for any $l\in S_{3}$.

The main problem in using this generic framework of infinitely many
generalized cut-set bounds of the form (74) is to identify the set operators
$\Phi_{i},\Pi_{j},\Gamma_{l}^{+},\Gamma_{l}^{-}$ for all $i\in S_{1}$, $j\in
S_{2}$ and $l\in S_{3}$ that satisfy the extremal inequality (75) and provide
specific upper bounds (74) that exactly match with (44) and (46)-(47), and
thereby establishing the converse proof. With the aid of the order-theoretic
relations (1)-(6), we show that the following extremal inequalities proposed
before in [6, Proposition 1] provide tight upper bounds that match (44) and
(46)-(47). From [6, Proposition 1], we get the following three extremal
inequalities for $j\in\\{1,2,\cdots,K-2\\}$

$\displaystyle f(\mathsf{W}_{K-1}\cup\mathsf{W}_{K})\leq
f(\mathsf{W}_{K-1})+f(\mathsf{W}_{K})-f(\mathsf{W}_{K-1}\cap\mathsf{W}_{K})$
(76) $\displaystyle
f(\mathsf{W}_{K-1}\cup\mathsf{W}_{K}\cup\mathsf{W}_{j})+f(\mathsf{W}_{K-1}\cap\mathsf{W}_{K})\leq$
$\displaystyle\;f(\mathsf{W}_{j})-f(\mathsf{W}_{j}\cap(\mathsf{W}_{K-1}\cup\mathsf{W}_{K}))+f(\mathsf{W}_{K-1})+f(\mathsf{W}_{K})$
(77) $\displaystyle
f(\mathsf{W}_{K-1}\cup\mathsf{W}_{K}\cup\mathsf{W}_{j})+f((\mathsf{W}_{K-1}\cap\mathsf{W}_{K})\cup$
$\displaystyle\quad(\mathsf{W}_{K-1}\cap\mathsf{W}_{j})\cup(\mathsf{W}_{K}\cap\mathsf{W}_{j}))\leq$
$\displaystyle\;f(\mathsf{W}_{j})-f(\mathsf{W}_{j}\cap\mathsf{W}_{K-1}\cap\mathsf{W}_{K})+f(\mathsf{W}_{K-1})+f(\mathsf{W}_{K})$
(78)

Using them, we get immediately from (74) the following generalized cut-set
bounds

$\displaystyle
R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cup\mathsf{W}_{K}^{\mathsf{E}}}\leq
C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}}}$ (79)
$\displaystyle
R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cup\mathsf{W}_{K}^{\mathsf{E}}\cup\mathsf{W}_{j}^{\mathsf{E}}}+R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cap\mathsf{W}_{K}^{\mathsf{E}}}\leq$
$\displaystyle\quad
C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}}\cup\mathsf{W}_{j}^{\mathsf{P}}}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}$
(80) $\displaystyle
R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cup\mathsf{W}_{K}^{\mathsf{E}}\cup\mathsf{W}_{j}^{\mathsf{E}}}+R_{(\mathsf{W}_{K-1}^{\mathsf{E}}\cap\mathsf{W}_{K}^{\mathsf{E}})\cup(\mathsf{W}_{K-1}^{\mathsf{E}}\cap\mathsf{W}_{j}^{\mathsf{E}})\cup(\mathsf{W}_{K}^{\mathsf{E}}\cap\mathsf{W}_{j}^{\mathsf{E}})}\leq$
$\displaystyle\quad
C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}}\cup\mathsf{W}_{j}^{\mathsf{P}}}+C_{(\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}})\cup(\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{j}^{\mathsf{P}})\cup(\mathsf{W}_{K}^{\mathsf{P}}\cap\mathsf{W}_{j}^{\mathsf{P}})}$
(81)

By computing the left hand side of the above three inequalities, we get for
any $j\in\\{1,2,\cdots,K-2\\}$

$\displaystyle
R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cup\mathsf{W}_{K}^{\mathsf{E}}}=R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}$
(82) $\displaystyle
R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cup\mathsf{W}_{K}^{\mathsf{E}}\cup\mathsf{W}_{j}^{\mathsf{E}}}+R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cap\mathsf{W}_{K}^{\mathsf{E}}}=$
$\displaystyle\quad
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
(83) $\displaystyle
R_{\mathsf{W}_{K-1}^{\mathsf{E}}\cup\mathsf{W}_{K}^{\mathsf{E}}\cup\mathsf{W}_{j}^{\mathsf{E}}}+R_{(\mathsf{W}_{K-1}^{\mathsf{E}}\cap\mathsf{W}_{K}^{\mathsf{E}})\cup(\mathsf{W}_{K-1}^{\mathsf{E}}\cap\mathsf{W}_{j}^{\mathsf{E}})\cup(\mathsf{W}_{K}^{\mathsf{E}}\cap\mathsf{W}_{j}^{\mathsf{E}})}=$
$\displaystyle\quad
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}$
(84)

These match with the left hand side of (44) and (46)-(47).

Showing that the right hand sides of (79)-(81) match with that of (44) and
(46)-(47), respectively, is less straightforward. We first use (1)-(6) to
rewrite the right hand side of (44) and (46)-(47) in a form that is closer to
the generalized cut-set bounds. From (1)-(6), we can show that the following
two equalities hold for any set $S=l_{1}l_{2}\cdots
l_{N}\subset\\{1,2,\cdots,K\\}$ and $j\in[1:K]$

$\displaystyle C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{S}\\}}$
$\displaystyle=C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap(\mathsf{W}_{l_{1}}^{\mathsf{P}}\cup\mathsf{W}_{l_{2}}^{\mathsf{P}}\cup\cdots\cup\mathsf{W}_{l_{N}}^{\mathsf{P}})}$
(85) $\displaystyle
C_{\downarrow_{\mathsf{W}_{j}^{\mathsf{P}}}\\{\overline{l_{1}},\overline{l_{2}},\cdots,\overline{l_{N}}\\}}$
$\displaystyle=C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap(\mathsf{W}_{l_{1}}^{\mathsf{P}}\cap\mathsf{W}_{l_{2}}^{\mathsf{P}}\cap\cdots\cap\mathsf{W}_{l_{N}}^{\mathsf{P}})}$
(86)

where $C_{\mathsf{W}}=\sum_{S\in\mathsf{W}}C_{S}$ for any
$\mathsf{W}\subseteq\mathsf{P}$. Using (85)-(86), we can rewrite the
achievable bounds in (44) and (46)-(47) as follows

$\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}-C_{\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}}}$
(87) $\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\qquad
C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap(\mathsf{W}_{K-1}^{\mathsf{P}}\cup\mathsf{W}_{K}^{\mathsf{P}})}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(88) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq$
$\displaystyle\qquad
C_{\mathsf{W}_{j}^{\mathsf{P}}}-C_{\mathsf{W}_{j}^{\mathsf{P}}\cap(\mathsf{W}_{K-1}^{\mathsf{P}}\cap\mathsf{W}_{K}^{\mathsf{P}})}+C_{\mathsf{W}_{K-1}^{\mathsf{P}}}+C_{\mathsf{W}_{K}^{\mathsf{P}}}$
(89)

By comparing (79)-(80) with (87)-(89), the new representation of the
achievable bound, we can see that the right hand side of both group of
inequalities are identical using the extremal inequalities (76)-(78) for
modular function since $C_{\mathsf{W}}$ is modular function for any
$\mathsf{W}\subseteq\mathsf{P}$. Hence, the generalized cut-set bounds in
(79)-(80) are tight. This concludes the converse proof.

###### Example 1

The capacity region for the complete message set for the four-receiver
combination network is not known. We specify the achievable rate region of
Theorem 2 for $K=4$ for the diamond message set, but without the structure in
the order-theoretic specification of the bounds, as being the explicit
polytope in the positive orthant described by the set of rate pairs
($R_{12},R_{123},R_{124},R_{1234}$) that satisfy the following nine linear
inequalities

$\displaystyle R_{1234}+R_{124}\leq C_{4}+C_{14}+C_{24}+C_{34}$
$\displaystyle\hskip 42.67912pt+C_{124}+C_{134}+C_{234}+C_{1234}$ (90)
$\displaystyle R_{1234}+R_{123}\leq C_{3}+C_{13}+C_{23}+C_{34}$
$\displaystyle\hskip 42.67912pt+C_{123}+C_{134}+C_{234}+C_{1234}$ (91)
$\displaystyle R_{1234}+R_{124}+R_{123}\leq C_{3}+C_{4}+C_{13}$
$\displaystyle\hskip 42.67912pt+C_{14}+C_{23}+C_{24}+C_{34}+C_{123}$
$\displaystyle\hskip 42.67912pt+C_{124}+C_{134}+C_{234}+C_{1234}$ (92)
$\displaystyle R_{1234}+R_{124}+R_{123}+R_{12}\leq C_{1}+C_{12}+C_{13}+C_{14}$
$\displaystyle\hskip 42.67912pt+C_{123}+C_{124}+C_{134}+C_{1234}$ (93)
$\displaystyle R_{1234}+R_{124}+R_{123}+R_{12}\leq C_{2}+C_{12}+C_{23}+C_{24}$
$\displaystyle\hskip 42.67912pt+C_{123}+C_{124}+C_{234}+C_{1234}$ (94)
$\displaystyle 2R_{1234}+R_{124}+R_{123}+R_{12}\leq C_{1}+C_{3}+C_{4}+C_{12}$
$\displaystyle\hskip 42.67912pt+C_{13}+C_{14}+C_{23}+C_{24}+2C_{34}+C_{123}$
$\displaystyle\hskip 42.67912pt+C_{124}+2C_{134}+2C_{234}+2C_{1234}$ (95)
$\displaystyle 2R_{1234}+R_{124}+R_{123}+R_{12}\leq C_{2}+C_{3}+C_{4}+C_{12}$
$\displaystyle\hskip 42.67912pt+C_{13}+C_{14}+C_{23}+C_{24}+2C_{34}+C_{123}$
$\displaystyle\hskip 42.67912pt+C_{124}+2C_{134}+2C_{234}+2C_{1234}$ (96)
$\displaystyle 2R_{1234}+2R_{124}+2R_{123}+R_{12}\leq
C_{1}+C_{3}+C_{4}+C_{12}$ $\displaystyle\hskip
42.67912pt+2C_{13}+2C_{14}+C_{23}+C_{24}+2C_{34}+2C_{123}$
$\displaystyle\hskip 42.67912pt+2C_{124}+2C_{134}+2C_{234}+2C_{1234}$ (97)
$\displaystyle 2R_{1234}+2R_{124}+2R_{123}+R_{12}\leq
C_{2}+C_{3}+C_{4}+C_{12}$ $\displaystyle\hskip
42.67912pt+C_{13}+C_{14}+2C_{23}+2C_{24}+2C_{34}+2C_{123}$
$\displaystyle\hskip 42.67912pt+2C_{124}+2C_{134}+2C_{234}+2C_{1234}$ (98)

##  IV Inner Bound For the DM BC With Binning

For the sake of completeness and further investigation, we generalize Theorem
1 by enhancing the achievable scheme therein by adding to it the technique of
binning.

###### Theorem 3

An inner bound of $K$-user DM BC for the diamond message set with
$\mathsf{E}=\\{\overline{\phi},\overline{K},\overline{K-1},\overline{K-1.K}\\}$
is the set of non-negative rate tuples
($R_{\overline{\phi}},R_{\overline{K}},R_{\overline{K-1}},R_{\overline{K-1.K}}$)
satisfying the following for all $j,j_{1},j_{2}\in\\{1,2,\cdots,K-2\\}$

$\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}\leq
I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (99) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (100) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle\hskip
85.35826pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (101)
$\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
$\displaystyle\hskip
85.35826pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (102)
$\displaystyle 2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ $\displaystyle\hskip
42.67912pt+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$
(103) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j})$ (104) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$ $\displaystyle\hskip
128.0374pt+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (105)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$ $\displaystyle\hskip
128.0374pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (106)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (107)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
71.13188pt+I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (108)
$\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (109)
$\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$ $\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (110)
$\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}})$ $\displaystyle\hskip
73.97733pt+I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (111)
$\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$ $\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (112)
$\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$ $\displaystyle\hskip
73.97733pt+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
$\displaystyle\hskip
128.0374pt-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$ (113)
$\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}},U_{\overline{K}})$ $\displaystyle\hskip
42.67912pt+I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K-1}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
$\displaystyle\hskip
42.67912pt+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$
(114)

for some joint distribution of the auxiliary and input random variables
$(U_{\overline{\phi}},U_{\overline{K}},U_{\overline{K-1}},X)$ that is of the
form

$\displaystyle
p(u_{\overline{\phi}},u_{\overline{K}},u_{\overline{K-1}},x)=p(u_{\overline{\phi}})$
$\displaystyle\times
p(u_{\overline{K}},u_{\overline{K-1}}|u_{\overline{\phi}})$
$\displaystyle\times
p(x|u_{\overline{\phi}},u_{\overline{K}},u_{\overline{K-1}})$ (115)

###### Proof 2

An outline of the proof is given in Appendix B.

###### Remark 5

By setting $I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})=0$
(i.e., no binning), we get that (103) is redundant from (99) and (100), (112)
is redundant from (105) and (100), (113) is redundant from (106) and (99), and
(114) is redundant from (105) and (106), thereby recovering Theorem 1. While
the greater generality offered by binning is not necessary in establishing the
capacity region of the combination network for the diamond message set it is
an interesting open question as to whether the above achievable rate region is
tight for say the more general deterministic DM BC where each output $Y_{i}$
is some deterministic function of $g_{i}(X)$.

###### Remark 6

In the achievable rate region for the $K=2$ case of Theorem 3 obtained for the
complete message set $\mathsf{E}=\\{1,2,12\\}$ by setting
$R_{\overline{K-1.K}}=0$ (in this case $X$ is a function of $U_{1},U_{2}$ and
$U_{12}$) and $Y_{j}={\rm const.}$ for $j\in[3:K]$ it is easily seen that all
but the first five inequalities (99)-(103) are redundant. In particular, this
special case of Theorem 3 recovers [15, Theorem 5], where it was first
obtained, as it must, and is also given in [16, Theorem 8.4].

###### Remark 7

The special case of $K=3$ and three degraded messages with
$\mathsf{E}=\\{1,12,123\\}$ which is a subset of the diamond message set
$\mathsf{E}=\\{1,12,13,123\\}$ can be deduced by setting $K=3$ and $R_{13}=0$
in Theorem 3. This special case was also addressed in [17, Theorem 2]. There
are some notable differences between the two regions however444There is a
typographical error in the last inequality in the rate region given in [17,
Theorem 2]: the term $I(U_{12};Y_{2}|U_{123})$ in the bound should instead be
$I(U_{12},U_{123};Y_{2})$.. First, the distributions for the input and
auxiliary random variables is taken to belong to a more restrictive class in
[17, Theorem 2] that can be obtained by setting $U_{123}=U$,
$(U_{123},U_{12})=V_{2}$ and $(U_{123},U_{13})=V_{3}$ and restricting to joint
distributions wherein we have the Markov chains
$U\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}V_{2}\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}(V_{3},X)$
and
$U\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}V_{3}\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}(V_{2},X)$
which is a stronger restriction than the one herein which is that
$U_{123}\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}(U_{12},U_{13})\mathrel{\multimap}\joinrel\mathrel{-}\mspace{-9.0mu}\joinrel\mathrel{-}X$.
However, the restriction in the class of coding distributions in [17, Theorem
2] is without loss of generality as argued in [17]. More importantly however,
the achievable region of [17, Theorem 2] corresponds to one wherein Receiver 3
decodes the common message $M_{123}$ non-uniquely via $V_{3}$ whereas in the
specialization of Theorem 3 Receiver 3 decodes the common message uniquely via
$U_{123}$. This results in more inequalities in the region of Theorem 3 (when
specialized to $K=3$ and $\mathsf{E}=\\{1,12,123\\}$) than the ones in [17,
Theorem 2]. However, it is left to the reader to verify along the lines of
[17, Proposition 8] that unique and non-unique decoding at Receiver 3 result
in the same region per coding distribution. In effect, the additional
inequalities due to unique-decoding are redundant. In particular, [17,
Proposition 8] shows that the achievable region of [17, Theorem 2] for the
three degraded message set in which Receiver 2 decodes the common message
uniquely and Receiver 3 decodes the common message non-uniquely, when
specialized to the two degraded message set $\mathsf{E}=\\{1,123\\}$ (by
setting $R_{12}=0$), is equivalent to the achievable rate region of [17,
Proposition 5] obtained by having both Receivers 2 and 3 decode the common
message non-uniqely.

##  V Conclusion

In this paper, we propose an inner bound based on rate-splitting and
superposition coding in explicit form for the $K$-user DM BC as a union of
four-dimensional polytopes described in terms of the rates of the four
messages. By specializing it to the so-called combination network through the
choice of a single yet optimal coding distribution we obtain a single polytope
which is then shown to be the capacity region of that network for the diamond
message set. Our converse proof uses the generalized cut-set bound framework
of [6] to recognize, by developing key connections between our order-theoretic
description of the inner bound and the set-theoretic description of the
generalized cut-set bounds, the inequalities in the inner bound as indeed
being generalized cut-set outer bounds. Most significantly, our interpretation
of this capacity result is that it suggests a certain strength of the coding
scheme for the general DM BC itself, from whence it was obtained. Put
differently, our top-down approach allows us to conclude that rate-splitting
and superposition coding (with subset inclusion order) results in a strong
inner bound for the DM BC with the diamond message set as opposed to
presenting the more conventional view that rate-splitting and superposition
coding may not be strong enough to attain the capacity of the entire DM BC for
the diamond message set. Nevertheless, we extend the rate-splitting and
superposition coding inner bound by adding binning to it and obtain a rate
region that is again given as a union of explicit four-dimensional polytopes
in terms of the four message rates.

Moreover, we expect that the proposed top-town approach, initiated in [2] and
continued in [14] and the present work, can be used to obtain inner bounds for
the DM BC for message sets other than the diamond message set, and validate
them as being strong, provided that, when specialized to the combination
network, they establish its capacity region.

##  Appendix A The FME for Theorem 1

Besides the inequalities in (20)-(28), we have the following inequalities to
ensure the non-negativity of the split rates

$\displaystyle-R_{\overline{K-1.K}}+$ $\displaystyle\qquad
R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
0$ (116) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq 0$
(117) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{K}}\leq 0$ (118)
$\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq 0$ (119)
$\displaystyle-R_{\overline{K}}+R_{\overline{K}\rightarrow\overline{\phi}}\leq
0$ (120) $\displaystyle-R_{\overline{K}\rightarrow\overline{\phi}}\leq 0$
(121) $\displaystyle-
R_{\overline{K-1}}+R_{\overline{K-1}\rightarrow\overline{\phi}}\leq 0$ (122)
$\displaystyle-R_{\overline{K-1}\rightarrow\overline{\phi}}\leq 0$ (123)

The problem is to project the above nine-dimensional polytope in original- and
split-rates space (described by the inequalities (20)-(28) and (116)-(123))
onto the space of the four original rates using the FME procedure. The size of
the problem is large in that there are a large number of (groups of)
inequalities and as many as five split rates to be eliminated. Performing the
FME procedure correctly for a problem of this size in an error-free manner can
be an arduous task. In particular, the order in which the split rates are
eliminated appears to have a strong bearing on whether the task can be
completed at all, with reasonable effort. We propose an order that we were not
only able to use to perform the projection to its completion but that also
provides opportunities for identifying errors in the process early enough and
hence correcting them before proceeding further. In particular, we propose to
do the projection in five steps in the following order:

  1. 1.

$R_{\overline{K-1}\rightarrow\overline{\phi}}$

  2. 2.

$R_{\overline{K}\rightarrow\overline{\phi}}$

  3. 3.

$R_{\overline{K-1.K}\rightarrow\overline{K}}$

  4. 4.

$R_{\overline{K-1.K}\rightarrow\overline{K-1}}$

  5. 5.

$R_{\overline{K-1.K}\rightarrow\overline{\phi}}$

Note that this order maintains a certain symmetric structure in the problem,
in that after projecting away the first two split rates in the above list we
expect a symmetry in the description of the resulting seven-dimensional
polytope around $K$ and $K-1$ (i.e., exchanging $K$ and $K-1$ should not
change it). Similarly, such a symmetry should result again after projecting
away the first four split rates in the above list, and eventually after
projecting away the fifth split rate that yields the four-dimensional
polytopes specified in Theorem 1, which is indeed symmetric in the sense
described above.

Note also that the number of inequalities in (20)-(24) is indeterminate since
it is function of $K$. Hence, we deal with these groups of inequalities at
once, instead of exhaustively listing them. Moreover, at the end of each
projection to eliminate a split rate, it is important to remove all redundant
inequalities so that the FME procedure remains tractable in future steps. We
do not address the issue of why inequalities that are not retained at the end
of each step are redundant, leaving this task at each step (beyond step 2,
when they arise) to the interested reader. Judicious applications of the data
processing inequality and the Markov chain relationships between the involved
random variables are all that are needed. The task of identifying which
inequalities are redundant is, however, solved for the reader at each step in
that these are precisely the inequalities that we omit from including in the
projected reduced-dimensional region given at the end of each step.

In the first two steps, we project away the split rates
$R_{\overline{K-1}\rightarrow\overline{\phi}}$ and
$R_{\overline{K}\rightarrow\overline{\phi}}$ and obtain, after rearranging the
inequalities, the following inequalities with $j\in\\{1,2,\cdots,K-2\\}$

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(124) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(125) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j})$ (126) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$ (127) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}-R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$
(128) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}-R_{\overline{K-1.K}\rightarrow\overline{K}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$ (129) $\displaystyle
R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$ (130) $\displaystyle
R_{\overline{K-1.K}\rightarrow\overline{K}}\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$ (131) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (132)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle\quad\leq I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (133)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(134) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(135) $\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+$
$\displaystyle\quad
R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle\quad\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(136) $\displaystyle R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+$
$\displaystyle\quad
R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle\quad\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(137) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}-R_{\overline{K-1.K}\rightarrow\overline{K-1}}-R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle 2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+$
$\displaystyle\quad
R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(139) $\displaystyle-R_{\overline{K-1.K}}+$ $\displaystyle\qquad
R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
0$ (140) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq 0$
(141) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{K}}\leq 0$ (142)
$\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq 0$ (143)

Observe that the above seven-dimensional polytope remains unchanged if $K-1$
and $K$ are exchanged, as one might expect. Indeed, observe this symmetry in
every group of inequalities separated by a new line. There were no redundant
inequalities in the first two steps.

In the third step, we project away the split rate
$R_{\overline{K-1.K}\rightarrow\overline{K}}$. Notice now that we have a group
of inequalities in (LABEL:AchRegion_FME_2_15) which give lower bounds for
$R_{\overline{K-1.K}\rightarrow\overline{K}}$ and a group of inequalities in
(135) and (139) that give upper bounds for
$R_{\overline{K-1.K}\rightarrow\overline{K}}$. Hence, to project the split
rate $R_{\overline{K-1.K}\rightarrow\overline{K}}$ from these, we have to
introduce new variables $j_{1},j_{2}\in\\{1,2,\cdots,K-2\\}$ since we get a
multiplicative increase in the number of inequalities. By projecting away the
split rate $R_{\overline{K-1.K}\rightarrow\overline{K}}$, we obtain, by
rearranging the inequalities and getting rid of the redundant ones 555Note
that we get redundant inequalities by eliminating the split rate
$R_{\overline{K-1.K}\rightarrow\overline{K}}$ from (129) and (133), (135),
(137), and (139), and also from (142) and (135). , the following for
$j,j_{1},j_{2}\in\\{1,2,\cdots,K-2\\}$

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(144) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(145) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j})$ (146) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(147) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(148) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}})+I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(149) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$ (150) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$
(151) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}-R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$
(152) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}-R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$
(153) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}+R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(154) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+2R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}-$
$\displaystyle\quad R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}})+$ $\displaystyle\quad
I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(155) $\displaystyle R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})$ (156) $\displaystyle
R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$ (157) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (158) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(159) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(160) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (161)
$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(162) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
$\displaystyle\quad\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(163) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad+R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$
$\displaystyle\quad+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(164) $\displaystyle-
R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
0$ (165) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{K-1}}\leq 0$
(166) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq 0$
(167)

In the fourth step, we project away the split rate
$R_{\overline{K-1.K}\rightarrow\overline{K-1}}$ from the polytope described by
the inequalities (144)-(167). Note that the inequalities (152)-(155) and (166)
give lower bounds and the inequalities (156)-(157), and (159)-(165) give upper
bounds on $R_{\overline{K-1.K}\rightarrow\overline{K-1}}$. Hence, we have
$K^{2}{-}K{-}1$ lower bounds and $4K{-}3$ upper bounds with the rest of the
inequalities remaining unchanged.

Projecting away the split rate $R_{\overline{K-1.K}\rightarrow\overline{K-1}}$
from the aforementioned inequalities, in which there are five lower bounds and
nine upper bounds, counting a group of inequalities as one inequality, we
obtain 45 groups of inequalities (including groups of size one). However, and
we leave it to the reader to show this, the nine inequalities, besides the
unchanged inequalities, shown next, are the only ones that are not redundant.
Hence, we get the five-dimensional polytope described by the following
inequalities for all $j,j_{1},j_{2}\in\\{1,2,\cdots,K-2\\}$

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(168) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(169) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}\leq
I(X;Y_{j})$ (170) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(171) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(172) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+2R_{\overline{K-1.K}}$
$\displaystyle\quad\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}})+I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(173) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (174) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (175) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(176) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$
(177) $\displaystyle
2R_{\overline{\phi}}+R_{\overline{K-1}}+R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(178) $\displaystyle
2R_{\overline{\phi}}+2R_{\overline{K-1}}+2R_{\overline{K}}+R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}})+I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})+I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$
(179) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq
I(X;Y_{j}|U_{\overline{\phi}})$ (180) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j_{1}}|U_{\overline{\phi}},U_{\overline{K-1}})+I(X;Y_{j_{2}}|U_{\overline{\phi}},U_{\overline{K}})$
(181) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}})+I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$
(182) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K}})+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$
(183) $\displaystyle
R_{\overline{K-1.K}}-R_{\overline{K-1.K}\rightarrow\overline{\phi}}$
$\displaystyle\quad\leq
I(X;Y_{j}|U_{\overline{\phi}},U_{\overline{K-1}},U_{\overline{K}})$
$\displaystyle\quad+I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})+I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$
(184) $\displaystyle-
R_{\overline{K-1.K}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq 0$
(185) $\displaystyle-R_{\overline{K-1.K}\rightarrow\overline{\phi}}\leq 0$
(186)

Observe again the symmetry in the above five-dimensional polytope, which is
that it remains unchanged when $K-1$ and $K$ are exchanged (even within every
group of inequalities separated by new line), as expected.

Finally, in the fifth step, we project away the split rate
$R_{\overline{K-1.K}\rightarrow\overline{\phi}}$ from the five-dimensional
polytope described by the inequalities (168)-(186). After doing this
projection, and eliminating redundant inequalities, it is left to the reader
to verify that we obtain the four-dimensional polytope in the original rates
given in Theorem 1. Note again the presence of symmetry of that polytope when
$K-1$ and $K$ are exchanged in that four-dimensional polytope. This concludes
the outline of the FME procedure.

##  Appendix B Proof of Theorem 3

The achievable scheme of Theorem 1 that is based on rate-splitting and
superposition coding is enhanced by adding to it the technique of binning that
involves generating the $U_{\overline{K}}$ and $U_{\overline{K-1}}$ codebooks
at excess rate and creating bins of codewords in place of codewords for the
associated messages and selecting a pair of codewords from the product bins
selected by the messages that are jointly typical per the allowed joint
distribution of $U_{\overline{K}}$ and $U_{\overline{K-1}}$ (conditioned on
$U_{\overline{\phi}}$). In particular, the messages $M_{\overline{K}}$,
$M_{\overline{K-1}}$, and $M_{\overline{K-1.K}}$ are split as in the proof of
Theorem 1. The reconstructed message
$(M_{\overline{\phi}},M_{\overline{K-1}\rightarrow\overline{\phi}},M_{\overline{K}\rightarrow\overline{\phi}},M_{\overline{K-1.K}\rightarrow\overline{\phi}})$
is represented by the cloud center $U_{\overline{\phi}}$ again as in Theorem
1. For each
$u_{\overline{\phi}}^{n}(m_{\overline{\phi}},m_{\overline{K-1}\rightarrow\overline{\phi}},m_{\overline{K}\rightarrow\overline{\phi}},m_{\overline{K-1.K}\rightarrow\overline{\phi}})$
randomly and independently generate (a) $2^{n\tilde{R}_{\overline{K}}}$
independent sequences
$u_{\overline{K}}^{n}(m_{\overline{\phi}},m_{\overline{K-1}\rightarrow\overline{\phi}},m_{\overline{K}\rightarrow\overline{\phi}},m_{\overline{K-1.K}\rightarrow\overline{\phi}},\tilde{m}_{\overline{K}})$,
for each $\tilde{m}_{\overline{K}}\in[1:2^{n\tilde{R}_{\overline{K}}}]$ with

$\displaystyle\tilde{R}_{\overline{K}}\geq
R_{\overline{K-1.K}\rightarrow\overline{K}}+R_{\overline{K}\rightarrow\overline{K}}$
(187)

and (b) $2^{n\tilde{R}_{\overline{K-1}}}$ independent sequences
$u_{\overline{K-1}}^{n}(m_{\overline{\phi}},m_{\overline{K-1}\rightarrow\overline{\phi}},m_{\overline{K}\rightarrow\overline{\phi}},m_{\overline{K-1.K}\rightarrow\overline{\phi}},\tilde{m}_{\overline{K-1}})$
for each $\tilde{m}_{\overline{K-1}}\in[1:2^{n\tilde{R}_{\overline{K-1}}}]$
and

$\displaystyle\tilde{R}_{\overline{K-1}}\geq
R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1}\rightarrow\overline{K-1}}$
(188)

Partition the $2^{n\tilde{R}_{\overline{K}}}$ sequences $u_{\overline{K}}^{n}$
into
$2^{n(R_{\overline{K-1.K}\rightarrow\overline{K}}+R_{\overline{K}\rightarrow\overline{K}})}$
equi-sized subcodebooks (or bins) and the $2^{n\tilde{R}_{\overline{K-1}}}$
sequences $u_{\overline{K-1}}^{n}$ into
$2^{n(R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1}\rightarrow\overline{K-1}})}$
equi-sized subcodebooks, with the subcodebooks indexed by the sub-message
pairs
$(m_{\overline{K-1.K}\rightarrow\overline{K}},m_{\overline{K}\rightarrow\overline{K}})$
and
$(m_{\overline{K-1.K}\rightarrow\overline{K-1}},m_{\overline{K-1}\rightarrow\overline{K-1}})$,
respectively. The tuple $(m_{\overline{\phi}}$
$,m_{\overline{K-1}\rightarrow\overline{\phi}},$
$m_{\overline{K}\rightarrow\overline{\phi}},$
$m_{\overline{K-1.K}\rightarrow\overline{\phi}},$
$m_{\overline{K-1.K}\rightarrow\overline{K}},$
$m_{\overline{K}\rightarrow\overline{K}},$
$m_{\overline{K-1.K}\rightarrow\overline{K-1}},$
$m_{\overline{K-1}\rightarrow\overline{K-1}})$ identifies two subcodebooks of
$u_{\overline{K}}^{n}$ and $u_{\overline{K-1}}^{n}$ sequences respectively
from which a jointly typical ($u_{\overline{K}}^{n}$, $u_{\overline{K-1}}^{n}$
) pair is selected. For each such pair, generate
$2^{nR_{\overline{K-1.K}\rightarrow\overline{K-1.K}}}$ independent $x^{n}$
sequences indexed by the sub-message
$m_{\overline{K-1.K}\rightarrow\overline{K-1.K}}$. To ensure that each product
bin contains a jointly typical pair with arbitrarily high probability, we
require by the mutual covering lemma [16] that

$\displaystyle R_{\overline{K-1.K}\rightarrow\overline{K}}$
$\displaystyle+R_{\overline{K}\rightarrow\overline{K}}+R_{\overline{K-1.K}\rightarrow\overline{K-1}}+R_{\overline{K-1}\rightarrow\overline{K-1}}$
(189)
$\displaystyle\leq\tilde{R}_{\overline{K}}+\tilde{R}_{\overline{K-1}}-I(U_{\overline{K}};U_{\overline{K-1}}|U_{\overline{\phi}})$

Receivers $\\{Y_{j}\\}_{j=1}^{K-2}$ decode all four intended messages by the
joint unique decoding of $X$ (and hence of
$U_{\overline{\phi}},U_{\overline{K}},U_{\overline{K-1}},U_{\overline{K-1.K}}$),
and this happens successfully as long as (20)-(24) hold. On the other hand,
receiver $Y_{K-1}$ finds its two intended messages $M_{\overline{\phi}}$ and
$M_{\overline{K}}$ by jointly uniquely decoding
$(U_{\overline{\phi}},U_{\overline{K}})$, and similarly, receiver $Y_{K}$ find
its two intended messages $M_{\overline{\phi}}$ and $M_{\overline{K-1}}$ by
jointly uniquely decoding $(U_{\overline{\phi}},U_{\overline{K-1}})$.
Receivers $Y_{K-1}$ and $Y_{K}$ decode their intended pair of messages
successfully provided the following inequalities hold:

$\displaystyle
R_{\overline{\phi}}+R_{\overline{K}\rightarrow\overline{\phi}}+R_{\overline{K-1}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+\tilde{R}_{\overline{K}}$
$\displaystyle\hskip 28.45274pt\leq
I(U_{\overline{\phi}},U_{\overline{K}};Y_{K-1})$ (190)
$\displaystyle\tilde{R}_{\overline{K}}\leq
I(U_{\overline{K}};Y_{K-1}|U_{\overline{\phi}})$ (191) $\displaystyle
R_{\overline{\phi}}+R_{\overline{K}\rightarrow\overline{\phi}}+R_{\overline{K-1}\rightarrow\overline{\phi}}+R_{\overline{K-1.K}\rightarrow\overline{\phi}}+\tilde{R}_{\overline{K-1}}$
$\displaystyle\leq I(U_{\overline{\phi}},U_{\overline{K-1}};Y_{K})$ (192)
$\displaystyle\tilde{R}_{\overline{K-1}}\leq
I(U_{\overline{K-1}};Y_{K}|U_{\overline{\phi}})$ (193)

At this point, inequalities (20)-(24), (187)- (193) and the non-negativity of
message rate constraints define a 11-dimensional polytope. Extending the FME
method as outlined in Appendix A for the projection required in Theorem 1 —the
details of which are left to the reader —we obtain the rate region given in
the statement of Theorem 3.

## References

  * [1] M. Salman and M. K. Varanasi, “Diamond message set groupcasting: From an achievable rate region for the dm broadcast channel to the capacity of the combination network,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 1498–1503.
  * [2] H. P. Romero and M. K. Varanasi, “Superposition coding in the combination network,” in _International Symposium on Information Theory (ISIT)_. IEEE, 2016, pp. 2149–2153.
  * [3] ——, “A unifying order-theoretic framework for superposition coding: Polymatroidal structure and optimality in the multiple-access channel with general message sets,” _IEEE Trans. Inform. Th._ , vol. 63, no. 1, pp. 21–37, 2017.
  * [4] A. Schrijver, _Theory of linear and integer programming_. John Wiley & Sons, 1998.
  * [5] C. K. Ngai and R. W. Yeung, “Network coding gain of combination networks,” in _IEEE Information Theory Workshop, 2004_. IEEE, 2004, pp. 283–287.
  * [6] A. Salimi, T. Liu, and S. Cui, “Generalized cut-set bounds for broadcast networks,” _IEEE Trans. Inform. Th._ , vol. 61, no. 6, pp. 2983–2996, 2015\.
  * [7] L. Grokop and D. N. Tse, “Fundamental constraints on multicast capacity regions,” _arXiv preprint arXiv:0809.2835_ , 2008.
  * [8] C. Tian, “Latent capacity region: A case study on symmetric broadcast with common messages,” _IEEE Transactions on Information Theory_ , vol. 57, no. 6, pp. 3273–3285, 2011.
  * [9] S. S. Bidokhti, V. M. Prabhakaran, and S. N. Diggavi, “Capacity results for multicasting nested message sets over combination networks,” _IEEE Trans. Inform. Th._ , vol. 62, no. 9, pp. 4968–4992, 2016.
  * [10] H. P. Romero and M. K. Varanasi, “Rate splitting and superposition coding for concurrent groupcasting over the broadcast channel: A general framework,” in _International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 1888–1892.
  * [11] M. Salman and M. K. Varanasi, “An achievable rate region for the K-receiver two nested groupcast DM broadcast channel and a capacity result for the combination network,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1415–1419.
  * [12] A. Schrijver, “Theory of integer and linear programming,” 1986.
  * [13] I. B. Gattegno, Z. Goldfeld, and H. H. Permuter, “Fourier-motzkin elimination software for information theoretic inequalities,” _arXiv preprint arXiv:1610.03990_ , 2016.
  * [14] M. Salman and M. K. Varanasi, “An achievable rate region for two groupcast messages over the K-user broadcast channel and capacity results for the combination network,” _arXiv preprint arXiv:1812.10525_ , 2018.
  * [15] Y. Liang and G. Kramer, “Rate regions for relay broadcast channels,” _IEEE Transactions on Information Theory_ , vol. 53, no. 10, pp. 3517–3535, 2007.
  * [16] A. El Gamal and Y.-H. Kim, _Network information theory_. Cambridge university press, 2011.
  * [17] C. Nair and A. El Gamal, “The capacity region of a class of three-receiver broadcast channels with degraded message sets,” _IEEE Trans. Inform. Th._ , vol. 55, no. 10, pp. 4479–4493, 2009.