We consider the problem of
error control
in a coded, multicast network,
focusing on the scenario where the errors can
occur only on a proper subset of the network edges.
We model this problem via an adversarial noise, presenting
a formal framework and a series of techniques to obtain upper and lower bounds on the network's (1-shot) capacity, improving on the best
currently known
In particular,
we show that
traditional cut-set bounds are not tight in general in the presence of a restricted adversary,
and that the non-tightness of these is caused precisely
by the restrictions imposed on the noise (and not, as one may expect, by the alphabet size).
We also show that, in sharp contrast
with the typical situation within network coding,
cannot be achieved in general by combining linear network coding with end-to-end channel coding, not even when the underlying network has a single source and a single terminal.
We finally illustrate how network
decoding techniques
are necessary to achieve capacity in the scenarios we examine, exhibiting capacity-achieving schemes
and lower bounds for various classes of networks.0pt

§ INTRODUCTION

Global propagation of interconnected devices and the ubiquity of communication demands in unsecured settings signify the importance of a unified understanding of the limits of communications in networks.
The correction of errors modeled by an adversarial noise
has been studied in a number of previous works, with results ranging from those concerning network capacity to specific code design (see [30, 3, 28, 11, 17, 26, 29, 5, 20, 12, 31, 19] among many others). In this paper, we focus on the effects of a small, and yet crucial,
modification of previous models, where a malicious actor can access and alter transmissions across a proper subset of edges within a network. We show that not only does this modification disrupt the sharpness of known results on network capacity, but that more specialized network coding (in fact, network decoding) becomes necessary to achieve the capacity.

We adopt the setting of a communication network whose inputs are drawn from a finite alphabet and whose internal (hereafter referred to as intermediate) nodes may process incoming information before forwarding (this is known as network coding; see e.g. [1, 15, 14]).
We phrase our work in terms of adversarial noise, but we note that our treatment truly addresses worst-case errors, also providing guarantees in networks where there may be random noise, or a combination of random and adversarial noise. We assume that the adversary is omniscient in the sense that they may design their attacks given full knowledge of the network topology, of the symbols sent along all its edges,
and of the operations performed at the intermediate nodes.

Again, in contrast to most previous work in the area, we concentrate on networks with noise occurring only on a proper subset of the network edges: for example, an adversary who may see all transmitted symbols, but has limited access to edges in the network when actively corrupting symbols. We examine the 1-shot capacity of adversarial networks with these restricted adversaries, which roughly measures the number of alphabet symbols that can be sent with zero error during a single transmission round. The case of multi-shot capacity, where more than one transmission round is considered, is also interesting, but will involve a separate treatment and different techniques from our work here.  Compellingly, the simple act of restricting possible error locations fundamentally alters the problem of computing the 1-shot capacity, as well as the manner in which this capacity may be achieved. This is discussed in further detail below.

This paper expands upon (and disrupts) the groundwork laid in [20], where a combinatorial framework for adversarial networks and a generalized method for porting point-to-point coding-theoretic results to the network setting are established. The work in [20] makes a start on addressing the case of restricted adversaries, also unifying the best-known upper bounds on 1-shot capacity for such networks. These upper bounds fall under the category of cut-set bounds, where an edge-cut is taken between network source(s) and terminal(s) and a bound on capacity is derived from an induced channel that takes only the cut-set edges into account. We note that Cai and Yeung previously gave generalizations of the Hamming, Singleton, and Gibert-Varshamov bounds to the network setting using edge-cuts in [30, 3]. The work in [20] allows for any point-to-point bound to be ported via an edge-cut.

In the case of random noise in a single-source, single-terminal network, it is well-known that the cut-set upper bound on capacity given by the Max-Flow Min-Cut Theorem may be achieved simply by forwarding information at the intermediate network nodes; see e.g. [6]. It has also been shown that in the scenarios of multiple terminals or where a malicious adversary may choose among all network edges, cut-set bounds may be achieved via  linear operations (over the relevant finite field) at intermediate nodes (combined with rank-metric codes in the presence of a malicious adversary); see [22, 5, 18]. In prior, preliminary work in this area [2], we demonstrated a minimal example of a network,
which we called the Diamond Network,
with a restricted adversary, where both (1) the Singleton cut-set bound (the best cut-set bound for this network) cannot be achieved, and (2) the actual 1-shot capacity cannot be achieved using linear operations at intermediate nodes. In fact, this example of network requires network decoding in order to achieve capacity. Via an extension of the Diamond Network, termed the Mirrored Diamond Network, we found that it is possible with restricted adversaries for the 1-shot capacity to meet the Singleton cut-set bound, but still be forced to use non-linear network codes to achieve this rate.

Generally speaking, the act of limiting the location of adversarial action is enough to put an end to the tightness of the best currently known cut-set bounds, and also to destroy the ability to achieve capacity with linear network codes in combination with end-to-end coding/decoding. This paper is the first stepping stone aimed at understanding the effects of restricting an adversary to a proper subset of the networks' edges, and how to compute (1-shot) capacities of such adversarial networks.

The paper is organized as follows. Sections <ref> and <ref> introduce our problem set-up and notation. Section <ref> is devoted to the Diamond Network mentioned above, which gives the smallest example illustrating our results. In Subsection <ref> we present an information-theoretic view of our problem for the case of random rather than adversarial noise, in order to generate further intuition.
To address the more general problem at hand, we will later in the paper (in Section <ref>) present a technique showing that the capacity of any network is upper bounded by the capacity of an induced, much less complicated network. The induced network utilized borrows from the original idea of cut-sets, but instead of studying the information flow through a single edge-cut, it considers the information flow between two edge-cuts. We call the result we obtain as an application of this idea the Double-Cut-Set Bound.
The less-complicated networks induced by the bound's statement are introduced in Section <ref> and the collection of families we study throughout the remainder of the paper are introduced in Subsection <ref>. In Section <ref>, we propose new combinatorial techniques to obtain upper bounds for the 1-shot capacities of these families, and in Section <ref>, we establish lower bounds. Section <ref> shows that there is a strong separation between linear and non-linear capacities, solidifying the necessity of network decoding in this setting. Finally, Section <ref> is devoted to conclusions, a discussion of open problems, and possible future works.

§ PROBLEM STATEMENT AND MOTIVATION

We focus on the typical scenario studied within the context of network coding; see [1, 3, 30, 8, 15, 13, 14, 9, 22, 24, 28, 26, 27, 10, 20] among many others.
Namely, one source of information attempts to transmit information packets to a collection of terminals through a network of intermediate nodes. The packets are
elements of a finite alphabet $\mA$ and the network is acyclic and delay-free.
We are interested in solving the multicast problem (that is, each terminal demands all packets)
under the assumption that an omniscient adversary acts on the network edges according to some restrictions.
These concepts will be formalized later
in the paper; see Section <ref>.
The goal of this section is to illustrate
the motivation behind our paper through an example.

Consider the single-source, two-terminal network $\mN$ depicted in Figure <ref>. We want to compute the number of alphabet packets that the source $S$ can transmit to the terminal $T$ in a single transmission round, called the 1-shot capacity.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.6of K] (V1) $V_1$;

[nnode,below=0.6of K] (V2) $V_2$;

[nnode,right=of K] (V3) $V_3$;

[nnode,right=of V3] (V4) $V_4$;

[vertex,right=3of V1 ] (T1) $T_1$;

[vertex,right=3of V2] (T2) $T_2$;

[edge,bend left=15] (S1)  to node[fill=white, inner sep=3pt]$e_1$ (V1);

[edge,bend right=15] (S1)  to node[fill=white, inner sep=3pt]$e_2$ (V1);

[edge,bend left=15] (S1) to  node[fill=white, inner sep=3pt]$e_3$ (V2);

[edge,bend right=15] (S1) to  node[fill=white, inner sep=3pt]$e_4$ (V2);

[edge,bend left=0] (V1) to  node[fill=white, inner sep=3pt]$e_6$ (V3);

[edge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{10}$ (T1);

[edge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{11}$ (T2);

[edge,bend left=0] (V1)  to node[fill=white, inner sep=3pt]$e_{5}$ (T1);

[edge,bend left=0] (V2)  to node[fill=white, inner sep=3pt]$e_{8}$ (T2);

[edge,bend left=0] (V2) to  node[fill=white, inner sep=3pt]$e_7$ (V3);

[edge,bend left=0] (V3) to  node[fill=white, inner sep=3pt]$e_{9}$ (V4);

An example of a network.

If no adversary acts on the network,
then the traditional cut-set bounds
are sharp, if the network alphabet is sufficiently large; see [1, 15, 14]. Since the (edge) min-cut
between $S$ and any $T \in \{T_1,T_2\}$ is 2, no more than 2 packets can be sent in a single transmission round. Furthermore, a strategy that achieves this bound is obtained by routing packet 1 across paths
$e_1 \to e_5$ and $e_4 \to e_8$,
and packet 2
across paths
$e_2 \to e_6 \to e_9 \to e_{10}$ and $e_3 \to e_7 \to e_9 \to e_{11}$.

This paper focuses on an adversarial model. That is,
a malicious “outside actor” can corrupt up to $t$ information packets
sent via the edges.
Note that the
term adversary has no cryptographic meaning in our setting and it simply models
the situation where any pattern of $t$ errors needs to be corrected.

Now suppose that the network $\mN$
is vulnerable, with an adversary able to change the value of up to $t=1$ of the
network edges.
Figure <ref> represents the same network as Figure <ref>, but with vulnerable (dashed) edges.
This scenario has been extensively investigated within network coding with possibly multiple terminals and multiple sources; see for instance [5, 20, 30, 3, 22, 13]. In particular, it follows from the Network Singleton Bound of [3, 30, 20] that
the network has capacity 0, meaning that the largest unambiguous code has size 1 (the terminology will be formalized later).

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.6of K] (V1) $V_1$;

[nnode,below=0.6of K] (V2) $V_2$;

[nnode,right=of K] (V3) $V_3$;

[nnode,right=of V3] (V4) $V_4$;

[vertex,right=3of V1 ] (T1) $T_1$;

[vertex,right=3of V2] (T2) $T_2$;

[ddedge,bend left=15] (S1)  to node[fill=white, inner sep=3pt]$e_1$ (V1);

[ddedge,bend right=15] (S1)  to node[fill=white, inner sep=3pt]$e_2$ (V1);

[ddedge,bend left=15] (S1) to  node[fill=white, inner sep=3pt]$e_3$ (V2);

[ddedge,bend right=15] (S1) to  node[fill=white, inner sep=3pt]$e_4$ (V2);

[ddedge,bend left=0] (V1) to  node[fill=white, inner sep=3pt]$e_6$ (V3);

[ddedge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{10}$ (T1);

[ddedge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{11}$ (T2);

[ddedge,bend left=0] (V1)  to node[fill=white, inner sep=3pt]$e_{5}$ (T1);

[ddedge,bend left=0] (V2)  to node[fill=white, inner sep=3pt]$e_{8}$ (T2);

[ddedge,bend left=0] (V2) to  node[fill=white, inner sep=3pt]$e_7$ (V3);

[ddedge,bend left=0] (V3) to  node[fill=white, inner sep=3pt]$e_{9}$ (V4);

The network of Figure <ref>, where all edges are vulnerable (dashed).

We recall that in the case of a network with multiple sources, multiple terminals, and an adversary able to corrupt up to $t$ of the network edges, the capacity region was computed in [5, 20, 18]. In the scenario just described, a capacity-achieving scheme can be obtained by combining linear network coding with rank-metric end-to-end coding.
We will comment on this again in Theorem <ref>.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.6of K] (V1) $V_1$;

[nnode,below=0.6of K] (V2) $V_2$;

[nnode,right=of K] (V3) $V_3$;

[nnode,right=of V3] (V4) $V_4$;

[vertex,right=3of V1 ] (T1) $T_1$;

[vertex,right=3of V2] (T2) $T_2$;

[ddedge,bend left=15] (S1)  to node[fill=white, inner sep=3pt]$e_1$ (V1);

[ddedge,bend right=15] (S1)  to node[fill=white, inner sep=3pt]$e_2$ (V1);

[ddedge,bend left=15] (S1) to  node[fill=white, inner sep=3pt]$e_3$ (V2);

[ddedge,bend right=15] (S1) to  node[fill=white, inner sep=3pt]$e_4$ (V2);

[ddedge,bend left=0] (V1) to  node[fill=white, inner sep=3pt]$e_6$ (V3);

[edge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{10}$ (T1);

[edge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{11}$ (T2);

[edge,bend left=0] (V1)  to node[fill=white, inner sep=3pt]$e_{5}$ (T1);

[edge,bend left=0] (V2)  to node[fill=white, inner sep=3pt]$e_{8}$ (T2);

[ddedge,bend left=0] (V2) to  node[fill=white, inner sep=3pt]$e_7$ (V3);

[ddedge,bend left=0] (V3) to  node[fill=white, inner sep=3pt]$e_{9}$ (V4);

The network of Figure <ref>, where only the dashed edges are vulnerable.

We now turn to the scenario that motivates this paper. The network remains vulnerable, but this time the adversary can only corrupt at most one of the dashed edges in Figure <ref>; the solid edges are not vulnerable.
Our main question is the same (what is the largest number of alphabet packets that can be transmitted?), but the answer is less obvious/known than before. By restricting the adversary to operate on a proper subset of the edges, one expects the capacity to increase with respect to the “unrestricted” situation. Therefore a natural question is whether the rate of one packet in a single channel use can be achieved.
As we will show in Theorem <ref>,
this is not possible: instead, the partially vulnerable network has capacity $\log_{|\mA|} (|\mA|-1)$,
where $\mA$ denotes the network alphabet.
As we will see, capacity can be achieved by making nodes $V_1$, $V_2$ and $V_3$ partially
decode received information
(which explains the title of our paper).
This is in sharp contrast with the case of an unrestricted adversary, where capacity can be achieved with end-to-end encoding/decoding.

The goal of this paper is to develop the theoretical framework needed to study networks that are partially vulnerable to adversarial noise, comparing results and strategies
with those currently available in contexts that are to date much better understood.

§ CHANNELS AND NETWORKS

In this section we include some preliminary definitions and results that will be needed throughout the entire paper. This will also allow us to establish the notation and to state the problems we will investigate in rigorous mathematical language.
This section is divided into two subsections. The first is devoted to arbitrary (adversarial) channels, while in the second we focus our attention on communication networks and their capacities.

§.§ Adversarial Channels

In our treatment, we will use the definition of (adversarial) channels proposed in [20], based on the notion of fan-out sets.
This concept essentially dates back to Shannon's fundamental paper on the zero-error capacity of a channel [21].
Under this approach, a channel is fully specified by the collection of symbols $y$ that can be received when a given symbol $x$ is transmitted. Considering transition probabilities does not make sense in this model since the noise is assumed to be of an “adversarial” nature. The latter assumption conveniently models all those scenarios where any error pattern of a given type must be corrected
and no positive probability of unsuccessful decoding is tolerated.
This is the scenario considered (often implicitly) in standard network coding references such as [22, 30, 3, 13] among many others.
We will briefly consider a probabilistic regime in Subsection <ref> with the goal of forming intuition about certain information theory phenomena we will observe.

A (discrete, adversarial) channel is a map
$\Omega: \mX \to 2^{\mY} \setminus \{\emptyset\}$, where $\mX$ and $\mY$ are finite non-empty sets called the input and output alphabets respectively.
The notation for such a channel is $\Omega: \mX \dashrightarrow \mY$. We say that $\Omega$ is  deterministic if $|\Omega(x)|=1$ for all $x \in \mX$.
We call $\Omega(x)$ the fan-out set of $x$.

Note that a deterministic channel $\Omega: \mX \dashrightarrow \mY$ can be naturally identified with a function $\mX \to \mY$, which we denote by $\Omega$ as well.

A (outer) code for a channel $\Omega: \mX \dashrightarrow \mY$ is a non-empty subset $\mC \subseteq \mX$. We say that $\mC$ is
unambiguous if $\Omega(x) \cap \Omega(x') =\emptyset$
for all $x, x' \in \mC$ with $x \neq x'$.

The base-two logarithm of the largest size of an unambiguous code for a given channel is its 1-shot capacity. In the graph theory representation of channels proposed by Shannon in [21], the 1-shot capacity coincides with the base-two logarithm of the largest cardinality of an independent set in the corresponding graph. We refer to <cit.>
for a more detailed discussion.

The ($1$-shot) capacity of a channel $\Omega:\mX \dashrightarrow \mY$ is the real number

$$\CC_1(\Omega)=\max\left\{\log_2 |\mC| \; : \; \mC \subseteq \mX \mbox{ is an unambiguous code for $\Omega$}\right\}.$$

We give an example to illustrate the previous definitions.

Let $\mX=\mY=\{0,1,2,3,4,5,6,7\}$. Define a channel $\Omega: \mX \dto \mY$ by setting

\begin{cases}
\{0,2\}  & \text{if} \ \ x = 0, \\
\{0,1,4,6\}  & \text{if} \ \ x = 1, \\
\{2,3,5\}  & \text{if} \ \ x = 2, \\
\{2,3,4,7\}  & \text{if} \ \ x = 3,
\end{cases}
\qquad  \qquad
\Omega(x)=
\begin{cases}
\{2,3,4,6\}  & \text{if} \ \ x = 4, \\
\{0,1,5\}  & \text{if} \ \ x = 5, \\
\{6\}  & \text{if} \ \ x = 6, \\
\{0,1,5,7\}  & \text{if} \ \ x = 7. \\
\end{cases}$$

Clearly, $\Omega$ is not deterministic. It can be checked that the only unambigious code for $\Omega$ of size 3 is $\mC=\{3,5,6\}$, and that there are no unambiguous codes of size 4. Therefore we have $\CC_1(\Omega)=\log_2 3$.

In this paper we focus solely on the
1-shot capacity of
While other capacity notions can be considered as well (e.g., the zero-error capacity), in the networking context these are significantly more technical to treat
than the 1-shot capacity, especially when focusing on restricted noise. We therefore omit them
in this first paper on network decoding and leave them as a future research direction; see Section <ref>.

We next describe how channels can be compared and combined with each other, referring to [20] for a more complete treatment.

Let $\Omega_1,\Omega_2 : \mX \dashrightarrow \mY$ be channels.
We say that $\Omega_1$ is finer
than $\Omega_2$ (or that $\Omega_2$ is coarser than $\Omega_1$) if $\Omega_1(x) \subseteq \Omega_2(x)$ for all $x \in \mX$.
The notation is $\Omega_1 \le \Omega_2$.

Finer channels have larger capacity, as the following simple result states.

Let $\Omega_1,\Omega_2 : \mX \dashrightarrow \mY$ be channels with $\Omega_1 \le \Omega_2$. We have $\CC_1(\Omega_1) \ge \CC_1(\Omega_2)$.

Channels with compatible output/input alphabets can be concatenated with each other via the following construction.

Let $\Omega_1:\mX_1 \dashrightarrow \mY_1$ and $\Omega_2:\mX_2 \dashrightarrow \mY_2$
be channels, with $\mY_1 \subseteq \mX_2$.
The concatenation of
$\Omega_1$ and $\Omega_2$ is the channel
$\Omega_1 \blacktriangleright \Omega_2 : \mX_1 \dashrightarrow \mY_2$ defined by

$$(\Omega_1 \blacktriangleright \Omega_2)(x):= \bigcup_{y \in \Omega_1(x)} \Omega_2(y).$$

The concatenation of channels is associative in the following precise sense.

Let $\Omega_i:\mX_i \dashrightarrow \mY_i$ be channels, for $i \in \{1,2,3\}$,
with $\mY_i \subseteq \mX_{i+1}$ for
$i \in \{1,2\}$. We have
$(\Omega_1 \blacktriangleright \Omega_2) \blacktriangleright \Omega_3 =
\Omega_1 \blacktriangleright (\Omega_2 \blacktriangleright \Omega_3)$.

The previous result allows us to
write expressions such as $\Omega_1 \blacktriangleright \Omega_2 \blacktriangleright \Omega_3$
without parentheses, when all concatenations are defined.

We conclude this subsection with a
of the data processing inequality from classical information theory; see e.g. <cit.>.

Let $\Omega_1:\mX_1 \dashrightarrow \mY_1$ and $\Omega_2:\mX_2 \dashrightarrow \mY_2$
be channels, with $\mY_1 \subseteq \mX_2$.
We have $\CC_1(\Omega_1 \blacktriangleright \Omega_2) \le \min\{\CC_1(\Omega_1), \,
\CC_1(\Omega_2)\}$.

§.§ Networks and Their Capacities

In this subsection we formally define
communication networks, network codes, and the channels they induce.
Our approach is inspired by [20], even though the notation used in this paper differs slightly. We omit some of the details and refer the interested reader directly to [20].

A (single-source) network  is a 4-tuple $\mN=(\mV,\mE, S, \bfT)$ where:

* $(\mV,\mE)$ is a finite, directed, acyclic multigraph,

* $S \in \mV$ is the source,

* ${\bf T} \subseteq \mV$ is the set of terminals or sinks,

Note that we allow multiple parallel directed edges. We also assume that the following hold.

* $|{\bf T}| \ge 1$, $S \notin  {\bf T}$.

*  For any $T \in {\bf T}$, there exists a directed path from $S$ to $T$.

* The source does not have incoming edges, and terminals do not have outgoing edges.

* For every vertex $V \in \mV \setminus (\{S\} \cup \bfT)$, there exists a directed path from
$S$ to $V$ and a directed path from $V$ to $T$ for some $T \in {\bf T}$.

The elements of $\mV$ are called vertices or nodes. The elements of
$\mV \setminus (\{S\} \cup {\bf T})$ are called intermediate nodes.
A (network) alphabet is a finite set $\mA$ with $|\mA| \ge 2$.
The elements of $\mA$ are called symbols or packets. We say that $\mN$ is a single-terminal network if $|\bfT| = 1$.

The network alphabet is interpreted as the set of symbols that can be sent over the edges of the network.

Throughout the paper, $\mN=(\mV,\mE,S,{\bf T})$ will always denote a network and $\mA$ an alphabet, as in Definition <ref>, unless otherwise stated. We let

be the minimum cardinality of an edge-cut (a set of edges that cuts the connection) between vertices $V,V' \in \mV$. We denote the
set of incoming and outgoing edges of $V \in \mV$ by $\inn(V)$ and $\out(V)$, respectively, and their cardinalities by $\degin(V)$ and $\degout(V)$.
These cardinalities are called the in-degree and out-degree of the vertex $V$, respectively.

The following concepts will be crucial in our approach.

The edges of a network $\mN=(\mV,\mE, S, \bfT)$ can be partially ordered as follows. For $e,e' \in \mE$, we say that $e$ precedes $e'$ if
there exists a directed path in $\mN$ that starts with $e$ and ends with $e'$. The notation is
$e \preccurlyeq e'$.

Following the notation of Definition <ref>, it is well known in graph theory that
the  partial order on $\mE$ can be extended to a (not necessarily unique) total order. By definition, such an extension $\le$ satisfies the following property:
$e \preccurlyeq e'$ implies  $e \le e'$.
Throughout the paper we will assume that such an order extension has been fixed in the various networks and we denote it by $\le$ (none of the results of this paper depend on the particular choice of the total order).
Moreover, we illustrate the chosen total order via the labeling of the edges; see, for example, Figure <ref>.

In our model, the intermediate nodes of a network process incoming packets according to prescribed functions. We do not assume any restrictions on these functions. In particular, even when $\mA$ is a linear space over a given finite field, we do not require the functions to be linear over the underlying field.
This is in strong contrast with the most common approach taken in the context of network coding; see, for instance,
[26, 31, 8, 23, 7, 15]. In fact, as we will argue in Section <ref>,
using non-linear network codes (e.g. decoding at intermediate nodes) is often needed to achieve capacity in the scenarios studied in this paper.

Let $\mN=(\mV,\mE, S, \bfT)$ be a network and $\mA$ an alphabet. A network code for  $(\mN,\mA)$ is a family $\mF=\{\mF_V \st V \in \mV \setminus (\{S\} \cup {\bf T})\}$ of functions,
$$\mF_V : \mA^{\degin(V)} \to \mA^{\degout(V)} \quad \mbox{for all $V \in \mV \setminus (\{S\} \cup {\bf T})$}.$$

A network code $\mF$ fully specifies how the intermediate nodes of a network process information packets. Note that the interpretation of each function $\mF_V$ is unique precisely thanks to the choice of the total order $\le$; see Notation <ref>.

Consider the network depicted in Figure <ref>, consisting of one source, one terminal, and one intermediate node. The edges are ordered according to their indices.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=*0.5 of S1] (K) ;

[nnode,right=of K] (V) $V$;

[vertex,right=*0.5 of V3] (T) $T$;

[edge,bend left=25] (S1)  to node[fill=white, inner sep=3pt]$e_1$ (V);

[edge,bend right=25] (S1)  to node[fill=white, inner sep=3pt]$e_3$ (V);

[edge,bend right=0] (S1)  to node[fill=white, inner sep=3pt]$e_2$ (V);

[edge,bend left=0] (V)  to node[fill=white, inner sep=3pt]$e_{4}$ (T);

Network for Example <ref>.

The way vertex $V$ processes information is fully specified by a function $\mF_V:\mA^3 \to \mA$, thanks to the choice of the total order.
For example, if $\mA=\F_5$ and $\mF_V(x_1,x_2,x_3)=x_1+2x_2+3x_3$
for all $(x_1,x_2,x_3) \in \mA^3$, then vertex $V$ sends over edge $e_4$ the field element obtained by summing the field element collected on edge $e_1$ with twice the field element collected on edge $e_2$ and three times the field element collected on edge $e_3$.

This paper focuses on networks $\mN=(\mV,\mE, S, \bfT)$ affected by potentially restricted adversarial noise. More precisely, we assume that at most $t$ of the alphabet symbols on a given edge set $\mU \subseteq \mE$ can be changed into any other alphabet symbols. We are interested in computing the largest number of packets that can be multicasted to all terminals in a single channel use.
As already mentioned,
the notion of error probability does not make sense in this context, since the noise is adversarial in nature.
We can make the described problem
rigorous with the aid of the following notation, which connects networks and network codes to the notion of (adversarial) channels introduced in
Subsection <ref>.

Let $\mN=(\mV,\mE, S, \bfT)$ be a network, $\mA$ an alphabet, $T \in \bd{T}$ a terminal, $\mF$ a network code for $(\mN,\mA)$, $\mU \subseteq \mE$ an edge set, and $t \ge 0$ an integer. We denote by

$$\Omega[\mN, \mA, \mF, S \to T,\mU,t] : \mA^{\degout(S)} \dashrightarrow \mA^{\degin(T)}$$

the channel representing the transfer from $S$ to terminal $T \in \bd{T}$, when the network code $\mF$ is used by the vertices and at most $t$ packets from the edges in $\mU$ are corrupted. In this context, we call $t$ the adversarial power.

The following example illustrates how to formally describe the channel introduced in Notation <ref>.

Let $\mN$ be the network in Figure <ref> and $\mA$ be an alphabet. We consider an adversary capable of corrupting up to one of the dashed edges, that is, one of the edges in $\mU =\{e_1,e_2,e_3\}$.
Let $\mF_{V_1}: \mA \to \mA$ be the identity function and let $\mF_{V_2}: \mA \to \mA$ be a function returning a constant value $a \in \mA$.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.5of K] (V1) $V_1$;

[nnode,below=0.5of K] (V2) $V_2$;

[vertex,right=of K] (T) $T$;

[ddedge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_1$ (V1);

[ddedge,bend left=0] (S1) to  node[sloped,fill=white, inner sep=1pt]$e_2$ (T);

[ddedge,bend right=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_3$ (V2);

[ddedge,bend right=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_3$ (V2);

[edge,bend left=0] (V1)  to node[sloped,fill=white, inner sep=1pt]$e_4$ (T);

[edge,bend left=0] (V2)  to node[sloped,fill=white, inner sep=1pt]$e_{5}$ (T);

Network for Example <ref>.

This scenario is fully modeled by the channel
$\Omega[\mN, \mA, \mF, S \to T,\mU,1] : \mA^{3} \dashrightarrow \mA^{2}$,
which we now describe.
For $x=(x_1,x_2,x_3) \in \mA^3$, we have that
$\Omega[\mN, \mA, \mF, S \to T,\mU,1](x)$  is the set of all alphabet vectors $y=(y_1,y_2,a) \in \mA^3$ for which
$\dH((y_1,y_2),(x_1,x_2)) \le 1$, where $\dH$ denotes the Hamming distance; see [16].

We are finally ready to give a rigorous definition for the 1-shot capacity of a network. This is the main quantity we are concerned with in this paper.

Let $\mN=(\mV,\mE, S, \bfT)$ be a network, $\mA$ an alphabet,
$\mU \subseteq \mE$ an edge set,
and $t \ge 0$ an integer.
The (1-shot) capacity
of $(\mN,\mA,\mU,t)$
is the largest
real number $\kappa$ for which there exists an outer code
$$\mC \subseteq \mA^{\degout(S)}$$

and a network code $\mF$ for $(\mN,\mA)$
with $\kappa=\log_{|\mA|}(|\mC|)$ such that
$\mC$ is unambiguous for each channel
$\Omega[\mN,\mA,\mF,S \to T,\mU,t]$, $T \in \bd{T}$. The notation for this largest $\kappa$ is

The elements of the outer code $\mC$
are called codewords.

The following bound, which is not sharp in general, is an immediate consequence of the definitions.

Following the notations of Definition <ref> and Definition <ref>, we have

$$\CC_1(\mN,\mA,\mU,t) \le \, \min_T \, \max_\mF \, \CC_1(\Omega[\mN,\mA,\mF,S \to T, \mU,t]),$$

where the minimum is taken over all network terminals $T \in \bfT$ and the maximum is taken over all network codes $\mF$ for $(\mN,\mA)$.

The main goal of this paper is to initiate the study of the quantity $\CC_1(\mN,\mA,\mU,t)$ for an arbitrary tuple $(\mN,\mA,\mU,t)$,
where $t \ge 0$ is an integer, $\mA$ is an alphabet and $\mU$ is a proper subset of the edges of the network $\mN$.

The main difference between this work and previous work in the same field lies precisely in the restriction of the noise to the set $\mU$. Recall moreover that when all edges are vulnerable, i.e., when $\mE=\mU$,
the problem
of computing $\CC_1(\mN,\mA,\mE,t)$
can be completely solved
by combining cut-set bounds
with linear network coding and rank-metric codes (for the achievability).
More precisely, the following hold.

Let $\mN=(\mV,\mE, S, \bfT)$ be a network, $\mA$ an alphabet,
and $t \ge 0$ an integer.
Let $\mu=\min_{T \in \bfT} \mincut_{\mN}(S,T)$.
Suppose that $\mA=\F_{q^m}$,
with $m \ge \mu$ and $q$ sufficiently large ($q \ge |{\bf T}|-1$ suffices).

$$\CC_1(\mN,\mA,\mE,t) = \max\{0, \, \mu-2t\}.$$

Moreover, it has been proven in [22] that the capacity value $\max\{0, \, \mu-2t\}$ can be attained by taking as a network code
$\mF$ a collection of $\F_q$-linear functions. In the case of an adversary having access to only a proper subset of the network edges, the generalization of Theorem <ref> can be derived and is stated as follows.

Let $\mN=(\mV,\mE, S, \bfT)$ be a network, $\mA$ an alphabet, $\mU \subseteq \mE$,
and $t \ge 0$ an integer.
We have

\begin{equation*}
\CC_1(\mN,\mA,\mU,t) \le \min_{T \in \bfT} \, \min_{\mE'} \left(
|\mE'\setminus \mU| + \max\{0,|\mE' \cap \mU|-2t\} \right),
\end{equation*}

where $\mE' \subseteq \mE$ ranges over edge-cuts between $S$ and $T$.

Next, we give an example to illustrate Definition <ref> that also makes use of the Generalized Network Singleton Bound of Theorem <ref>.

Consider the network $\mN$ depicted in Figure <ref>. We will show that
We choose the network code to consist of identity functions $\mF_{V_1}$ and $\mF_{V_2}$. Let $\mC$ be the $3$-times repetition code, that is,
$\mC=\{(x,x,x) \mid x \in \mA\}.$ Since at most $1$ symbol from the edges of $\mU$ is corrupted, it can easily be seen that $\mC$ is unambiguous for the channel $\Omega[\mN,\mA,\mF,S \to T,\mU,1]$. Since $|\mC|=|\mA|$, this shows that $\CC_1(\mN,\mA,\mU,t) \ge 1$. Choosing $\mE'=\{e_1,e_2,e_3\}$ in Theorem <ref>, we have $\CC_1(\mN,\mA,\mU,t) \le 1$, yielding the desired result.

§ THE CURIOUS CASE OF THE DIAMOND NETWORK

This section is devoted to the smallest example of network that illustrates the problem we focus on in this paper. We call it the Diamond Network, due to its shape, and denote it by $\mathfrak{A}_1$. The choice for the notation will become clear in Subsection <ref>, where we will introduce a family of networks (Family <ref>)
of which the Diamond Network is the “first” member.
The Diamond Network is depicted in Figure <ref>.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.35of K] (V1) $V_1$;

[nnode,below=0.35of K] (V2) $V_2$;

[vertex,right=of K] (T) $T$;

[edge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_1$ (V1);

[edge,bend left=15] (S1) to  node[sloped,fill=white, inner sep=1pt]$e_2$ (V2);

[edge,bend right=15] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_3$ (V2);

[edge,bend left=0] (V1)  to node[sloped,fill=white, inner sep=1pt]$e_4$ (T);

[edge,bend left=0] (V2)  to node[sloped,fill=white, inner sep=1pt]$e_{5}$ (T);

The Diamond Network $\mathfrak{A}_1$.

§.§ The Capacity of the Diamond Network

We are interested in computing the capacity of the Diamond Network $\mathfrak{A}_1$ of Figure <ref> when $\mA$ is an arbitrary alphabet,
$\mU=\{e_1,e_2,e_3\}$ is the set of vulnerable edges, and
Previously, the best known upper bound for the capacity of $\mathfrak{A}_1$ in this context was

\begin{equation} \label{boundDN}
\CC_1(\mathfrak{A}_1,\mA,\mU,1) \le 1,
\end{equation}

which follows from Theorem <ref>. It was however shown in the preliminary work [2] that the upper bound
in (<ref>) is not tight, regardless of the choice of alphabet $\mA$.
More precisely, the following hold.

For the Diamond Network $\mathfrak{A}_1$ of Figure <ref>, any alphabet $\mA$, and $\mU=\{e_1,e_2,e_3\}$, we have

$$\CC_1(\mathfrak{A}_1,\mA,\mU,1) = \log_{|\mA|} \, (|\mA|-1).$$

An intuitive idea of why the capacity of the Diamond Network is strictly less than one can be seen by considering that information arriving at the terminal through $e_4$ is completely useless without information arriving through $e_5$. The opposite is also true. Thus, we must have some cooperation between the two different “routes” in order to achieve a positive capacity. Unfortunately, because $V_2$ has one more incoming than outgoing edge, the cooperation implicitly suggested by the Generalized Network Singleton Bound of Theorem <ref> is impossible: a repetition code sent across $e_1$, $e_2$, and $e_3$ will fall short of guaranteed correction at the terminal. Cooperation is still possible, but it will come at a cost. To see achievability of Theorem <ref>, consider sending a repetition code across $e_1$, $e_2$, and $e_3$. Intermediate node $V_1$ forwards its received symbol; $V_2$ forwards if the two incoming symbols match, and sends a special reserved “alarm” symbol if they do not. The terminal looks to see whether the alarm symbol was sent across $e_5$. If so, it trusts $e_4$. If not, it trusts $e_5$. The (necessary) sacrifice of one alphabet symbol to be used as an alarm, or locator of the adversary, results in a rate of $\log_{|\mA|} (|\mA|-1)$. A proof that this is the best rate possible was first presented in [2], and the result is also shown in a new, more general way in Section <ref>.

Interestingly, when we add an additional edge to the Diamond Network, resulting in the so-called Mirrored Diamond Network $\mathfrak{D}_1$ of Figure <ref>, the Generalized Network Singleton Bound of Theorem <ref> becomes tight (with the
analogous adversarial action). More precisely, the following holds. It should be noted that the case of adding an extra incoming edge to $V_2$ of Figure <ref> is covered by Corollary <ref>.

For the Mirrored Diamond Network $\mathfrak{D}_1$ of Figure <ref>, any network alphabet $\mA$, and $\mU=\{e_1,e_2,e_3,e_4\}$, we have

$$\CC_1(\mathfrak{D}_1,\mA,\mU,1) = 1.$$

By Theorem <ref>, the previous result may be shown by simply exhibiting an explicit scheme achieving the upper bound of 1. We send a repetition code across $e_1$, $e_2$, $e_3$, and $e_4$. Each of $V_1$ and $V_2$ forwards if the two incoming symbols match, and sends a reserved alarm symbol if they do not. The terminal trusts the edge without the alarm symbol; if both send the alarm symbol, the terminal decodes to that symbol. Notice that we again make use of an alarm symbol, but that this symbol could also be sent as easily as any other alphabet symbol. This marks a striking difference from the alarm symbol used in the achievability of the Diamond Network capacity, which is instead sacrificed.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=*1.3 of S1] (K) ;

[nnode,above=0.45of K] (V1) $V_1$;

[nnode,below=0.45of K] (V2) $V_2$;

[vertex,right=of K] (T) $T$;

[edge,bend left=15] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_1$ (V1);

[edge,bend right=15] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_2$ (V1);

[edge,bend left=15] (S1) to  node[sloped,fill=white, inner sep=1pt]$e_3$ (V2);

[edge,bend right=15] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_4$ (V2);

[edge,bend left=0] (V1)  to node[sloped,fill=white, inner sep=1pt]$e_4$ (T);

[edge,bend left=0] (V2)  to node[sloped,fill=white, inner sep=1pt]$e_{5}$ (T);

The Mirrored Diamond Network $\mathfrak{D}_1$.

The example of the Mirrored Diamond Network of Figure <ref> indicates that the bottleneck vertex $V_2$ of the Diamond Network of Figure <ref> does not tell the whole story about whether the Network Singleton Bound is achievable. Instead, something more subtle is occurring with the manner in which information “streams” are split within the network. One may naturally wonder about the impact of adding additional edges to $V_1$ and/or $V_2$; we leave an exploration of a variety of such families to later sections. We next look at the scenario of random noise to build further intuition.

§.§ Information Theory Intuition

Partial information-theoretic intuition for the fact that the Generalized Network Singleton Bound of Theorem <ref> cannot be achieved in some cases when an adversary is restricted to a particular portion of the network can be seen even in the case of random noise (rather than adversarial). In this subsection, we will briefly consider the standard information-theoretic definition of capacity. That is, capacity will be defined as the supremum of rates for which an asymptotically vanishing decoding error probability (as opposed to zero error) is achievable.
We do not include all the fundamental information theory definitions, instead referring the reader to e.g. [4] for more details.

Consider a unicast network with a single terminal and one intermediate node as illustrated in Figure <ref>. Suppose that the first three edges of the network experience random, binary symmetric noise. That is, in standard information theory notation and terminology, each dashed edge indicates a Binary Symmetric Channel with transition probability $p$, denoted BSC($p$), while the two edges from the intermediate node to the terminal are noiseless.
In the sequel, we also let

denote the entropy function associated with the transition probability $p$.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[nnode,right=*0.8 of S1] (V1) $V$;

[vertex,right=*0.6 of K] (T) $T$;

[ddedge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_2$ (V1);

[ddedge,bend left=25] (S1) to  node[sloped,fill=white, inner sep=1pt]$e_1$ (V1);

[ddedge,bend right=25] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_3$ (V1);

[edge,bend left=15] (V1)  to node[sloped,fill=white, inner sep=1pt]$e_4$ (T);

[edge,bend right=15] (V1)  to node[sloped,fill=white, inner sep=1pt]$e_{5}$ (T);

Dashed edges act as BSC($p$)s. The capacity of each is then $1-H(p)$, while solid edges each have capacity $1$.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[nnode,right=of S1] (V1) $V$;

[vertex,right=*0.6 of K] (T) $T$;

[edge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$(3-3H(p))$ (V1);

[edge,bend left=0] (V1)  to node[sloped,fill=white, inner sep=1pt]$2$ (T);

The capacity of each (collapsed) edge is labeled.

A network with multi-edges, along with its simplified version with collapsed multi-edges labeled with their capacities.

Each of the multi-edge-sets $\{e_1,e_2,e_3\}$ and $\{e_4,e_5\}$ can then be considered as collapsed to a single edge of capacity $3(1-H(p))$ and $2$, respectively (see Figure <ref>). Recall that the Max-Flow Min-Cut Theorem (see e.g. <cit.>)
states that the capacity of the network is equal to the minimum over all edge-cuts of the network of the sum of the capacities of the edges in the cut. Thus, the capacity of our network is equal to $\min\{2,3-3H(p)\}$.

Next, we split the intermediate node into two nodes, as in Figure <ref>. Again making use of the Max-Flow Min-Cut Theorem, the new network's capacity is equal to
One can easily determine that this value is upper bounded by the capacity of the network in Figure <ref> for all $0\leq p\leq 0.5$. Furthermore, when $0< H(p) < 0.5$ (i.e., when $p$ is positive and less than approximately $0.11$), this bound is strict. In other words, splitting the intermediate node reduces capacity for an interval of small transition probabilities.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.25of K] (V1) $V_1$;

[nnode,below=0.25of K] (V2) $V_2$;

[vertex,right=of K] (T) $T$;

[ddedge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_1$ (V1);

[ddedge,bend left=15] (S1) to  node[sloped,fill=white, inner sep=1pt]$e_2$ (V2);

[ddedge,bend right=15] (S1)  to node[sloped,fill=white, inner sep=1pt]$e_3$ (V2);

[edge,bend left=0] (V1)  to node[sloped,fill=white, inner sep=1pt]$e_4$ (T);

[edge,bend left=0] (V2)  to node[sloped,fill=white, inner sep=1pt]$e_{5}$ (T);

Vertex $V$ of Figure <ref> is split into two intermediate nodes.

As a first natural generalization, suppose the network of Figure <ref> had $n+1$ edges from source to the intermediate node, $n$ edges from intermediate node to terminal, and that the (extension of the) network shown in Figure <ref> peeled off just a single edge from each layer, resulting in $\degin(V_1)=\degout(V_1)=1$, $\degin(V_2)=n-1$, and $\degout(V_2)=n-2$. Then the capacity gap between the first and second networks would be non-zero for all $0<H(p)<1/(n-1)$. This gap is illustrated for $n \in \{3,5,7\}$ in Figure <ref>. Denote by “Scenario 1” the original network for the given value of $n$, and by “Scenario 2” the corresponding network with split intermediate node. In Section <ref> we return to this generalization with adversarial as opposed to random noise; there, it is termed Family <ref>.

[legend style=at=(0.6,0.93), anchor = north west,
legend cell align=left,
ylabel=Network capacity,
xmin=0, xmax=0.5,
ymin=0, ymax=7,
xtick=0,0.11,0.2,0.3, 0.4, 0.5,
grid style=dashed,
every axis plot/.append style=thick, yticklabel style=/pgf/number format/fixed
[color=red,style=ultra thick]
coordinates  ( 0.0, 2 )
( 0.01, 2.0 )
( 0.02, 2.0 )
( 0.03, 2.0 )
( 0.04, 2.0 )
( 0.05, 2.0 )
( 0.06, 2.0 )
( 0.07, 1.902229047 )
( 0.08, 1.793462429 )
( 0.09, 1.690590549 )
( 0.1, 1.593013219 )
( 0.11, 1.500252126 )
( 0.12, 1.411917404 )
( 0.13, 1.327685445 )
( 0.14, 1.247283565 )
( 0.15, 1.170479086 )
( 0.16, 1.097071336 )
( 0.17, 1.026885664 )
( 0.18, 0.959768863 )
( 0.19, 0.89558562 )
( 0.2, 0.834215715 )
( 0.21, 0.77555178 )
( 0.22, 0.719497491 )
( 0.23, 0.665966089 )
( 0.24, 0.614879162 )
( 0.25, 0.566165627 )
( 0.26, 0.519760883 )
( 0.27, 0.475606091 )
( 0.28, 0.433647568 )
( 0.29, 0.393836261 )
( 0.3, 0.356127302 )
( 0.31, 0.320479625 )
( 0.32, 0.286855627 )
( 0.33, 0.255220882 )
( 0.34, 0.225543885 )
( 0.35000000000000003, 0.197795834 )
( 0.36, 0.171950432 )
( 0.37, 0.147983722 )
( 0.38, 0.125873933 )
( 0.39, 0.105601354 )
( 0.4, 0.087148217 )
( 0.41000000000000003, 0.070498594 )
( 0.42, 0.055638315 )
( 0.43, 0.042554888 )
( 0.44, 0.031237436 )
( 0.45, 0.021676638 )
( 0.46, 0.013864684 )
( 0.47000000000000003, 0.007795234 )
( 0.48, 0.003463392 )
( 0.49, 0.000865675 )
( 0.5, 0.0 )
[color=green,dashed,style=ultra thick]
coordinates ( 0.0, 2 )
( 0.01, 1.919206864 )
( 0.02, 1.858559457 )
( 0.03, 1.805608142 )
( 0.04, 1.757707811 )
( 0.05, 1.713603043 )
( 0.06, 1.672555081 )
( 0.07, 1.634076349 )
( 0.08, 1.59782081 )
( 0.09, 1.563530183 )
( 0.1, 1.531004406 )
( 0.11, 1.500084042 )
( 0.12, 1.411917404 )
( 0.13, 1.327685445 )
( 0.14, 1.247283565 )
( 0.15, 1.170479086 )
( 0.16, 1.097071336 )
( 0.17, 1.026885664 )
( 0.18, 0.959768863 )
( 0.19, 0.89558562 )
( 0.2, 0.834215715 )
( 0.21, 0.77555178 )
( 0.22, 0.719497491 )
( 0.23, 0.665966089 )
( 0.24, 0.614879162 )
( 0.25, 0.566165627 )
( 0.26, 0.519760883 )
( 0.27, 0.475606091 )
( 0.28, 0.433647568 )
( 0.29, 0.393836261 )
( 0.3, 0.356127302 )
( 0.31, 0.320479625 )
( 0.32, 0.286855627 )
( 0.33, 0.255220882 )
( 0.34, 0.225543885 )
( 0.35000000000000003, 0.197795834 )
( 0.36, 0.171950432 )
( 0.37, 0.147983722 )
( 0.38, 0.125873933 )
( 0.39, 0.105601354 )
( 0.4, 0.087148217 )
( 0.41000000000000003, 0.070498594 )
( 0.42, 0.055638315 )
( 0.43, 0.042554888 )
( 0.44, 0.031237436 )
( 0.45, 0.021676638 )
( 0.46, 0.013864684 )
( 0.47000000000000003, 0.007795234 )
( 0.48, 0.003463392 )
( 0.49, 0.000865675 )
( 0.5, 0.0 )

[color=blue,style=ultra thick]
( 0.0, 4 )
( 0.01, 4.0 )
( 0.02, 4.0 )
( 0.03, 4.0 )
( 0.04, 3.788539055 )
( 0.05, 3.568015214 )
( 0.06, 3.362775404 )
( 0.07, 3.170381745 )
( 0.08, 2.989104049 )
( 0.09, 2.817650915 )
( 0.1, 2.655022032 )
( 0.11, 2.500420209 )
( 0.12, 2.353195674 )
( 0.13, 2.212809075 )
( 0.14, 2.078805942 )
( 0.15, 1.950798476 )
( 0.16, 1.828452227 )
( 0.17, 1.711476106 )
( 0.18, 1.599614771 )
( 0.19, 1.492642701 )
( 0.2, 1.390359526 )
( 0.21, 1.2925863 )
( 0.22, 1.199162485 )
( 0.23, 1.109943482 )
( 0.24, 1.024798603 )
( 0.25, 0.943609378 )
( 0.26, 0.866268138 )
( 0.27, 0.792676819 )
( 0.28, 0.722745947 )
( 0.29, 0.656393768 )
( 0.3, 0.593545504 )
( 0.31, 0.534132708 )
( 0.32, 0.478092711 )
( 0.33, 0.425368136 )
( 0.34, 0.375906475 )
( 0.35000000000000003, 0.329659723 )
( 0.36, 0.286584054 )
( 0.37, 0.246639537 )
( 0.38, 0.209789889 )
( 0.39, 0.176002257 )
( 0.4, 0.145247028 )
( 0.41000000000000003, 0.117497656 )
( 0.42, 0.092730525 )
( 0.43, 0.070924814 )
( 0.44, 0.052062394 )
( 0.45, 0.03612773 )
( 0.46, 0.023107806 )
( 0.47000000000000003, 0.012992057 )
( 0.48, 0.00577232 )
( 0.49, 0.001442791 )
( 0.5, 0.0 )

[color=cyan,dashed,style=ultra thick]
coordinates ( 0.0, 4 )
( 0.01, 3.919206864 )
( 0.02, 3.858559457 )
( 0.03, 3.805608142 )
( 0.04, 3.757707811 )
( 0.05, 3.568015214 )
( 0.06, 3.362775404 )
( 0.07, 3.170381745 )
( 0.08, 2.989104049 )
( 0.09, 2.817650915 )
( 0.1, 2.655022032 )
( 0.11, 2.500420209 )
( 0.12, 2.353195674 )
( 0.13, 2.212809075 )
( 0.14, 2.078805942 )
( 0.15, 1.950798476 )
( 0.16, 1.828452227 )
( 0.17, 1.711476106 )
( 0.18, 1.599614771 )
( 0.19, 1.492642701 )
( 0.2, 1.390359526 )
( 0.21, 1.2925863 )
( 0.22, 1.199162485 )
( 0.23, 1.109943482 )
( 0.24, 1.024798603 )
( 0.25, 0.943609378 )
( 0.26, 0.866268138 )
( 0.27, 0.792676819 )
( 0.28, 0.722745947 )
( 0.29, 0.656393768 )
( 0.3, 0.593545504 )
( 0.31, 0.534132708 )
( 0.32, 0.478092711 )
( 0.33, 0.425368136 )
( 0.34, 0.375906475 )
( 0.35000000000000003, 0.329659723 )
( 0.36, 0.286584054 )
( 0.37, 0.246639537 )
( 0.38, 0.209789889 )
( 0.39, 0.176002257 )
( 0.4, 0.145247028 )
( 0.41000000000000003, 0.117497656 )
( 0.42, 0.092730525 )
( 0.43, 0.070924814 )
( 0.44, 0.052062394 )
( 0.45, 0.03612773 )
( 0.46, 0.023107806 )
( 0.47000000000000003, 0.012992057 )
( 0.48, 0.00577232 )
( 0.49, 0.001442791 )
( 0.5, 0.0 )

[color=magenta,style=ultra thick]
coordinates ( 0.0, 6 )
( 0.01, 6.0 )
( 0.02, 6.0 )
( 0.03, 5.639256995 )
( 0.04, 5.303954676 )
( 0.05, 4.9952213 )
( 0.06, 4.707885566 )
( 0.07, 4.438534444 )
( 0.08, 4.184745669 )
( 0.09, 3.944711281 )
( 0.1, 3.717030845 )
( 0.11, 3.500588293 )
( 0.12, 3.294473943 )
( 0.13, 3.097932705 )
( 0.14, 2.910328319 )
( 0.15, 2.731117867 )
( 0.16, 2.559833118 )
( 0.17, 2.396066549 )
( 0.18, 2.23946068 )
( 0.19, 2.089699781 )
( 0.2, 1.946503336 )
( 0.21, 1.80962082 )
( 0.22, 1.678827479 )
( 0.23, 1.553920875 )
( 0.24, 1.434718044 )
( 0.25, 1.321053129 )
( 0.26, 1.212775393 )
( 0.27, 1.109747547 )
( 0.28, 1.011844326 )
( 0.29, 0.918951276 )
( 0.3, 0.830963705 )
( 0.31, 0.747785791 )
( 0.32, 0.669329796 )
( 0.33, 0.595515391 )
( 0.34, 0.526269065 )
( 0.35000000000000003, 0.461523612 )
( 0.36, 0.401217675 )
( 0.37, 0.345295351 )
( 0.38, 0.293705844 )
( 0.39, 0.24640316 )
( 0.4, 0.203345839 )
( 0.41000000000000003, 0.164496719 )
( 0.42, 0.129822735 )
( 0.43, 0.09929474 )
( 0.44, 0.072887351 )
( 0.45, 0.050578822 )
( 0.46, 0.032350928 )
( 0.47000000000000003, 0.01818888 )
( 0.48, 0.008081248 )
( 0.49, 0.002019908 )
( 0.5, 0.0 )

[color=orange,dashed,style=ultra thick]
coordinates ( 0.0, 6 )
( 0.01, 5.919206864 )
( 0.02, 5.858559457 )
( 0.03, 5.639256995 )
( 0.04, 5.303954676 )
( 0.05, 4.9952213 )
( 0.06, 4.707885566 )
( 0.07, 4.438534444 )
( 0.08, 4.184745669 )
( 0.09, 3.944711281 )
( 0.1, 3.717030845 )
( 0.11, 3.500588293 )
( 0.12, 3.294473943 )
( 0.13, 3.097932705 )
( 0.14, 2.910328319 )
( 0.15, 2.731117867 )
( 0.16, 2.559833118 )
( 0.17, 2.396066549 )
( 0.18, 2.23946068 )
( 0.19, 2.089699781 )
( 0.2, 1.946503336 )
( 0.21, 1.80962082 )
( 0.22, 1.678827479 )
( 0.23, 1.553920875 )
( 0.24, 1.434718044 )
( 0.25, 1.321053129 )
( 0.26, 1.212775393 )
( 0.27, 1.109747547 )
( 0.28, 1.011844326 )
( 0.29, 0.918951276 )
( 0.3, 0.830963705 )
( 0.31, 0.747785791 )
( 0.32, 0.669329796 )
( 0.33, 0.595515391 )
( 0.34, 0.526269065 )
( 0.35000000000000003, 0.461523612 )
( 0.36, 0.401217675 )
( 0.37, 0.345295351 )
( 0.38, 0.293705844 )
( 0.39, 0.24640316 )
( 0.4, 0.203345839 )
( 0.41000000000000003, 0.164496719 )
( 0.42, 0.129822735 )
( 0.43, 0.09929474 )
( 0.44, 0.072887351 )
( 0.45, 0.050578822 )
( 0.46, 0.032350928 )
( 0.47000000000000003, 0.01818888 )
( 0.48, 0.008081248 )
( 0.49, 0.002019908 )
( 0.5, 0.0 )
Scenario 1, $n=3$, Scenario 2, $n=3$,Scenario 1, $n=5$,Scenario 2, $n=5$,Scenario 1, $n=7$,Scenario 2, $n=7$

Capacity gaps between the first generalized networks for $n \in \{3,5,7\}$.

A second possible generalization is as follows: suppose the network of Figure <ref> had $3n$ edges from source to intermediate node, and $2n$ edges from intermediate node to terminal, and that the network of Figure <ref> peeled off $n$ edges from each layer so that $\degin(V_1)=\degout(V_1)=n$, $\degin(V_2)=2n$, and $\degout(V_2)=n$. Interestingly, the capacity gap between the first and second networks would be non-zero for all $0<H(p)<0.5$, regardless of the value of $n$. This is illustrated for $n \in \{3,5,7\}$ in Figure <ref>. Denote by “Scenario 1” the original network for the given value of $n$, and by “Scenario 2” the corresponding network with split intermediate node. In Section <ref> we return to this generalization with adversarial as opposed to random noise; there, it is termed Family <ref>.

[legend style=at=(0.6,0.93), anchor = north west,
legend cell align=left,
ylabel=Network capacity,
xmin=0, xmax=0.5,
ymin=0, ymax=16,
xtick=0,0.11,0.2,0.3, 0.4, 0.5,
grid style=dashed,
every axis plot/.append style=thick, yticklabel style=/pgf/number format/fixed
[color=red,style=ultra thick]
coordinates  ( 0.0, 6 )
( 0.01, 6.0 )
( 0.02, 6.0 )
( 0.03, 6.0 )
( 0.04, 6.0 )
( 0.05, 6.0 )
( 0.06, 6.0 )
( 0.07, 5.706687142 )
( 0.08, 5.380387288 )
( 0.09, 5.071771646 )
( 0.1, 4.779039658 )
( 0.11, 4.500756377 )
( 0.12, 4.235752212 )
( 0.13, 3.983056335 )
( 0.14, 3.741850695 )
( 0.15, 3.511437258 )
( 0.16, 3.291214008 )
( 0.17, 3.080656991 )
( 0.18, 2.879306588 )
( 0.19, 2.686756861 )
( 0.2, 2.502647146 )
( 0.21, 2.326655341 )
( 0.22, 2.158492473 )
( 0.23, 1.997898268 )
( 0.24, 1.844637486 )
( 0.25, 1.69849688 )
( 0.26, 1.559282648 )
( 0.27, 1.426818274 )
( 0.28, 1.300942705 )
( 0.29, 1.181508783 )
( 0.3, 1.068381907 )
( 0.31, 0.961438875 )
( 0.32, 0.86056688 )
( 0.33, 0.765662645 )
( 0.34, 0.676631655 )
( 0.35000000000000003, 0.593387502 )
( 0.36, 0.515851297 )
( 0.37, 0.443951166 )
( 0.38, 0.3776218 )
( 0.39, 0.316804063 )
( 0.4, 0.26144465 )
( 0.41000000000000003, 0.211495781 )
( 0.42, 0.166914945 )
( 0.43, 0.127664665 )
( 0.44, 0.093712309 )
( 0.45, 0.065029914 )
( 0.46, 0.041594051 )
( 0.47000000000000003, 0.023385703 )
( 0.48, 0.010390176 )
( 0.49, 0.002597024 )
( 0.5, 0.0 )
[color=green,dashed,style=ultra thick]
( 0.0, 6 )
( 0.01, 5.757620592 )
( 0.02, 5.575678372 )
( 0.03, 5.416824427 )
( 0.04, 5.273123433 )
( 0.05, 5.140809129 )
( 0.06, 5.017665243 )
( 0.07, 4.902229047 )
( 0.08, 4.793462429 )
( 0.09, 4.690590549 )
( 0.1, 4.593013219 )
( 0.11, 4.500252126 )
( 0.12, 4.235752212 )
( 0.13, 3.983056335 )
( 0.14, 3.741850695 )
( 0.15, 3.511437258 )
( 0.16, 3.291214008 )
( 0.17, 3.080656991 )
( 0.18, 2.879306588 )
( 0.19, 2.686756861 )
( 0.2, 2.502647146 )
( 0.21, 2.326655341 )
( 0.22, 2.158492473 )
( 0.23, 1.997898268 )
( 0.24, 1.844637486 )
( 0.25, 1.69849688 )
( 0.26, 1.559282648 )
( 0.27, 1.426818274 )
( 0.28, 1.300942705 )
( 0.29, 1.181508783 )
( 0.3, 1.068381907 )
( 0.31, 0.961438875 )
( 0.32, 0.86056688 )
( 0.33, 0.765662645 )
( 0.34, 0.676631655 )
( 0.35000000000000003, 0.593387502 )
( 0.36, 0.515851297 )
( 0.37, 0.443951166 )
( 0.38, 0.3776218 )
( 0.39, 0.316804063 )
( 0.4, 0.26144465 )
( 0.41000000000000003, 0.211495781 )
( 0.42, 0.166914945 )
( 0.43, 0.127664665 )
( 0.44, 0.093712309 )
( 0.45, 0.065029914 )
( 0.46, 0.041594051 )
( 0.47000000000000003, 0.023385703 )
( 0.48, 0.010390176 )
( 0.49, 0.002597024 )
( 0.5, 0.0 )

[color=blue,style=ultra thick]

( 0.0, 10 )
( 0.01, 10.0 )
( 0.02, 10.0 )
( 0.03, 10.0 )
( 0.04, 10.0 )
( 0.05, 10.0 )
( 0.06, 10.0 )
( 0.07, 9.511145236 )
( 0.08, 8.967312147 )
( 0.09, 8.452952744 )
( 0.1, 7.965066096 )
( 0.11, 7.501260628 )
( 0.12, 7.059587021 )
( 0.13, 6.638427225 )
( 0.14, 6.236417825 )
( 0.15, 5.852395429 )
( 0.16, 5.48535668 )
( 0.17, 5.134428319 )
( 0.18, 4.798844314 )
( 0.19, 4.477928102 )
( 0.2, 4.171078577 )
( 0.21, 3.877758901 )
( 0.22, 3.597487456 )
( 0.23, 3.329830447 )
( 0.24, 3.074395809 )
( 0.25, 2.830828133 )
( 0.26, 2.598804413 )
( 0.27, 2.378030457 )
( 0.28, 2.168237842 )
( 0.29, 1.969181305 )
( 0.3, 1.780636512 )
( 0.31, 1.602398124 )
( 0.32, 1.434278134 )
( 0.33, 1.276104408 )
( 0.34, 1.127719425 )
( 0.35000000000000003, 0.988979169 )
( 0.36, 0.859752161 )
( 0.37, 0.73991861 )
( 0.38, 0.629369667 )
( 0.39, 0.528006772 )
( 0.4, 0.435741083 )
( 0.41000000000000003, 0.352492969 )
( 0.42, 0.278191574 )
( 0.43, 0.212774442 )
( 0.44, 0.156187182 )
( 0.45, 0.10838319 )
( 0.46, 0.069323418 )
( 0.47000000000000003, 0.038976171 )
( 0.48, 0.01731696 )
( 0.49, 0.004328374 )
( 0.5, 0.0 )

[color=cyan,dashed,style=ultra thick]
( 0.0, 10 )
( 0.01, 9.596034321 )
( 0.02, 9.292797287 )
( 0.03, 9.028040711 )
( 0.04, 8.788539055 )
( 0.05, 8.568015214 )
( 0.06, 8.362775404 )
( 0.07, 8.170381745 )
( 0.08, 7.989104049 )
( 0.09, 7.817650915 )
( 0.1, 7.655022032 )
( 0.11, 7.500420209 )
( 0.12, 7.059587021 )
( 0.13, 6.638427225 )
( 0.14, 6.236417825 )
( 0.15, 5.852395429 )
( 0.16, 5.48535668 )
( 0.17, 5.134428319 )
( 0.18, 4.798844314 )
( 0.19, 4.477928102 )
( 0.2, 4.171078577 )
( 0.21, 3.877758901 )
( 0.22, 3.597487456 )
( 0.23, 3.329830447 )
( 0.24, 3.074395809 )
( 0.25, 2.830828133 )
( 0.26, 2.598804413 )
( 0.27, 2.378030457 )
( 0.28, 2.168237842 )
( 0.29, 1.969181305 )
( 0.3, 1.780636512 )
( 0.31, 1.602398124 )
( 0.32, 1.434278134 )
( 0.33, 1.276104408 )
( 0.34, 1.127719425 )
( 0.35000000000000003, 0.988979169 )
( 0.36, 0.859752161 )
( 0.37, 0.73991861 )
( 0.38, 0.629369667 )
( 0.39, 0.528006772 )
( 0.4, 0.435741083 )
( 0.41000000000000003, 0.352492969 )
( 0.42, 0.278191574 )
( 0.43, 0.212774442 )
( 0.44, 0.156187182 )
( 0.45, 0.10838319 )
( 0.46, 0.069323418 )
( 0.47000000000000003, 0.038976171 )
( 0.48, 0.01731696 )
( 0.49, 0.004328374 )
( 0.5, 0.0 )

[color=magenta,style=ultra thick]
( 0.0, 14 )
( 0.01, 14.0 )
( 0.02, 14.0 )
( 0.03, 14.0 )
( 0.04, 14.0 )
( 0.05, 14.0 )
( 0.06, 14.0 )
( 0.07, 13.31560333 )
( 0.08, 12.55423701 )
( 0.09, 11.83413384 )
( 0.1, 11.15109253 )
( 0.11, 10.50176488 )
( 0.12, 9.883421829 )
( 0.13, 9.293798114 )
( 0.14, 8.730984956 )
( 0.15, 8.193353601 )
( 0.16, 7.679499353 )
( 0.17, 7.188199646 )
( 0.18, 6.71838204 )
( 0.19, 6.269099342 )
( 0.2, 5.839510007 )
( 0.21, 5.428862461 )
( 0.22, 5.036482438 )
( 0.23, 4.661762626 )
( 0.24, 4.304154133 )
( 0.25, 3.963159386 )
( 0.26, 3.638326178 )
( 0.27, 3.32924264 )
( 0.28, 3.035532978 )
( 0.29, 2.756853827 )
( 0.3, 2.492891116 )
( 0.31, 2.243357374 )
( 0.32, 2.007989388 )
( 0.33, 1.786546172 )
( 0.34, 1.578807196 )
( 0.35000000000000003, 1.384570837 )
( 0.36, 1.203653026 )
( 0.37, 1.035886054 )
( 0.38, 0.881117533 )
( 0.39, 0.739209481 )
( 0.4, 0.610037516 )
( 0.41000000000000003, 0.493490156 )
( 0.42, 0.389468204 )
( 0.43, 0.297884219 )
( 0.44, 0.218662054 )
( 0.45, 0.151736466 )
( 0.46, 0.097052785 )
( 0.47000000000000003, 0.05456664 )
( 0.48, 0.024243744 )
( 0.49, 0.006059723 )
( 0.5, 0.0 )

[color=orange,dashed,style=ultra thick]
( 0.0, 14 )
( 0.01, 13.43444805 )
( 0.02, 13.0099162 )
( 0.03, 12.639257 )
( 0.04, 12.30395468 )
( 0.05, 11.9952213 )
( 0.06, 11.70788557 )
( 0.07, 11.43853444 )
( 0.08, 11.18474567 )
( 0.09, 10.94471128 )
( 0.1, 10.71703084 )
( 0.11, 10.50058829 )
( 0.12, 9.883421829 )
( 0.13, 9.293798114 )
( 0.14, 8.730984956 )
( 0.15, 8.193353601 )
( 0.16, 7.679499353 )
( 0.17, 7.188199646 )
( 0.18, 6.71838204 )
( 0.19, 6.269099342 )
( 0.2, 5.839510007 )
( 0.21, 5.428862461 )
( 0.22, 5.036482438 )
( 0.23, 4.661762626 )
( 0.24, 4.304154133 )
( 0.25, 3.963159386 )
( 0.26, 3.638326178 )
( 0.27, 3.32924264 )
( 0.28, 3.035532978 )
( 0.29, 2.756853827 )
( 0.3, 2.492891116 )
( 0.31, 2.243357374 )
( 0.32, 2.007989388 )
( 0.33, 1.786546172 )
( 0.34, 1.578807196 )
( 0.35000000000000003, 1.384570837 )
( 0.36, 1.203653026 )
( 0.37, 1.035886054 )
( 0.38, 0.881117533 )
( 0.39, 0.739209481 )
( 0.4, 0.610037516 )
( 0.41000000000000003, 0.493490156 )
( 0.42, 0.389468204 )
( 0.43, 0.297884219 )
( 0.44, 0.218662054 )
( 0.45, 0.151736466 )
( 0.46, 0.097052785 )
( 0.47000000000000003, 0.05456664 )
( 0.48, 0.024243744 )
( 0.49, 0.006059723 )
( 0.5, 0.0 )
Scenario 1, $n=3$, Scenario 2, $n=3$,Scenario 1, $n=5$,Scenario 2, $n=5$,Scenario 1, $n=7$,Scenario 2, $n=7$

Capacity gaps between the second generalized networks for $n \in \{3,5,7\}$.

In both generalizations, we see that the intermediate node split in Example <ref> prevents edges $\{e_{1},e_{2},e_{3}\}$ from cooperating to send messages when the BSC transition probability is small: in the random noise scenario, the difference is due to a lower-capacity mixed-vulnerability edge-cut being present in the split network. This gap is mirrored by the gap in the 1-shot capacity we observe in adversarial networks with restricted adversaries, though the reason for the gap differs. In the case of a restricted adversary on these two networks who may corrupt up to one vulnerable edge (with no random noise), the Generalized Network Singleton Bound of Theorem <ref> is achievable for the network in Scenario 1, while it is not achievable for the network in Scenario 2 (see Theorem <ref>). For higher adversarial power, as for higher transition probability in the case of random noise, the two have matching capacities. In the case of adversarial noise, the difference in capacities for limited adversarial power is due to something beyond edge-cut differences, which are already baked into the Generalized Network Singleton Bound. Capacities with restricted adversaries are no longer additive, and so we must preserve the split structure by looking beyond both the Max-Flow Min-Cut Theorem and the Generalized Network Singleton Bound in order to establish improved upper bounds on capacity.

§ NETWORKS WITH TWO AND THREE LEVELS

In this section we focus on families of networks having 2 or 3 levels, a property which is defined formally below. Throughout this section, we assume basic graph theory knowledge; see e.g. [25]. We show that one can upper bound the capacity of a special class of 3-level networks by the capacity of a corresponding 2-level network. We then define five families of 2-level networks, which will be key players of this paper and whose capacities will be computed or estimated in later sections.

In Section <ref> we will show how the results of this section can be “ported” to arbitrary networks using a general method that
describes the information transfer from one edge-set to another; see in particular the Double-Cut-Set Bound of Theorem <ref>.
All of this will also allow us to
compute the capacity of the network
that opened the paper.

§.§ $m$-Level Networks

Let $\mN=(\mV,\mE,S,\mathbf{T})$ be a network and let $V,V' \in \mV$. We say that $V'$ covers $V$ if
$(V,V') \in \mE$.
We call $\mN$ an $m$-level network
if $\mV$ can be partitioned into $m+1$ sets $\mV_{0},\ldots,\mV_{m}$ such that $\mV_{0}=\{S\}$, $\mV_{m}=\mathbf{T}$, and each node in $\mV_{k}$,  for $k\in \{1,...,m-1\}$,
is only covered by elements of
$\mV_{k+1}$ and only covers elements of $\mV_{k-1}$. We call $\mV_k$ the $k$-th layer of $\mN$.

Notice that in an $m$-level network, any path from $S$ to any $T\in \mathbf{T}$ is of length $m$.
Moreover, the value of $m$ and the layers $\mV_k$, for $k \in \{0,...,m\}$,
in Definition <ref> are uniquely determined by the network $\mN$.
Many of the results of this paper rely on  particular classes of 2-level and 3-level networks, which we now define.

A 2-level network is
if it has a single terminal.
A 3-level network is
if it has
a single terminal,
each intermediate node at
distance 1 from the source has in-degree equal to 1, and each intermediate node at distance 1 from the terminal has out-degree equal to 1.

In order to denote 2- and 3-level networks more compactly, we will utilize (simplified) adjacency matrices of the bipartite subgraphs induced by subsequent node layers. First we present the most general notation for an $m$-level network, then discuss the particular cases of 2- and 3-level networks.

Let $\mN_m=(\mV,\mE,S,\bfT)$ be an $m$-level network and let $\mV_0,...,\mV_m$ be as in Definition <ref> (the subscript in $\mN_m$ has the sole function of stressing the number of levels).
Fix an enumeration of the elements of each $\mV_k$, $k \in \{0,...,m\}$.
We denote by $\smash{M^{m,k}}$ the matrix representing the graph induced by the nodes in layers $k-1$ and $k$ of $\mN_m$, for $k\in \{1,...,m\}$.
Specifically, $\smash{M^{m,k}}$ has dimensions $\smash{|\mV_{k-1}|\times |\mV_{k}|}$, and $\smash{M^{m,k}_{ij}=\ell}$ if and only if there are $\ell$ edges from node $i$ of $\mV_{k-1}$ to node $j$ of $\mV_{k}$. We can then denote the network by $\smash{(M^{m,1},M^{m,2},\ldots,M^{m,m})}$. It is easy to check that $\mN_m$ is uniquely determined by this representation.

In a 2-level network, we have two adjacency matrices $\smash{M^{2,1}}$ and $\smash{M^{2,2}}$, and in a 3-level network we have three adjacency matrices $\smash{M^{3,1}}$ and $\smash{M^{3,2}}$, and $\smash{M^{3,3}}$. Notice that in a simple 3-level network, $\smash{M^{3,1}}$ and $\smash{M^{3,3}}$ will always be all-ones vectors, and so we may drop them from the notation. With a slight abuse of notation, we will denote $\smash{M^{2,2}}$ as a row vector in a simple 2-level network (instead of as a column vector).

We give two examples to illustrate the previous notation.

Consider the Diamond Network of Section <ref>; see Figure <ref>. Following Notation <ref>, we may represent this network as $\smash{([1,2],[1,1]^\top)}$. Because the network is simple, we may abuse notation and simplify this to $\smash{([1,2],[1,1])}$. Similarly, the Mirrored Diamond Network (see Figure <ref>) may be represented as $\smash{([2,2],[1,1])}$.

Consider the 3-level network shown in Figure <ref>. Following Notation <ref>, we may represent this network as

\[
\left(\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1
\end{bmatrix},
\begin{bmatrix}
1 & 1 & 0 & 0  \\
1 & 1 & 0 & 0  \\
1 & 1 & 0 & 0  \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1  \\
0 & 0 & 1 & 1
\end{bmatrix},
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 1
\end{bmatrix}\right)

More simply, the simple 3-level network may be represented using only the center matrix.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=1.2of K] (V1) $V_1$;

[nnode,above=0.7of K] (V2) $V_2$;

[nnode,above=0.3of K] (V3) $V_3$;

[nnode,below=0of K] (V4) $V_4$;

[nnode,below=0.4of K] (V5) $V_5$;

[nnode,below=0.8of K] (V6) $V_6$;

[vertex,right=3.5of S1] (T) $T$;

[nnode,right=1.3of V1 ] (V7) $V_7$;

[nnode,right=1.3of V3] (V8) $V_8$;

[nnode,right=1.3of V4] (V9) $V_9$;

[nnode,right=1.3of V6] (V10) $V_{10}$;

[ddedge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=0pt] (V1);

[ddedge,bend right=0] (S1)  to node[sloped,fill=white, inner sep=0pt] (V2);

[ddedge,bend left=0] (S1) to  node[sloped,fill=white, inner sep=0pt] (V3);

[ddedge,bend right=0] (S1) to  node[sloped,fill=white, inner sep=0pt] (V4);

[ddedge,bend right=0] (S1) to  node[sloped,fill=white, inner sep=0pt] (V5);

[ddedge,bend right=0] (S1) to  node[sloped,fill=white, inner sep=0pt] (V6);

[edge,bend left=0] (V1) to  node (V7);

[edge,bend left=0] (V1) to  node (V8);

[edge,bend left=0] (V2) to  node (V7);

[edge,bend left=0] (V2) to  node (V8);

[edge,bend left=0] (V3) to  node (V7);

[edge,bend left=0] (V3) to  node (V8);

[edge,bend left=0] (V4) to  node (V7);

[edge,bend left=0] (V4) to  node (V8);

[edge,bend right=0] (V5) to  node (V9);

[edge,bend right=0] (V5) to  node (V10);

[edge,bend right=0] (V6) to  node (V9);

[edge,bend right=0] (V6) to  node (V10);

[edge,bend left=0] (V7) to  node (T);

[edge,bend left=0] (V8) to  node (T);

[edge,bend left=0] (V9) to  node (T);

[edge,bend left=0] (V10) to  node (T);

Network for Examples <ref> and <ref>.

§.§ Reduction from 3- to 2-Level Networks

In this subsection we describe a procedure to obtain a simple 2-level network from a simple 3-level network. In Section <ref> we will show that, under certain assumptions, the capacity of any network can be upper bounded by the capacity of a simple 3-level network constructed from it. Using the procedure described in this subsection, we will be able to upper bound
the capacity of an arbitrary network with that of an induced simple 2-level network (obtaining sharp bounds in some cases).

Let $\mN_3$ be a simple 3-level network
defined by matrix $\smash{M^{3,2}}$, along with all-ones matrices $\smash{M^{3,1}}$ and $\smash{M^{3,3}}$ (see Notation <ref>).
We construct a simple
2-level network $\mN_2$, defined via $\smash{M^{2,1}}$ and $\smash{M^{2,2}}$ as follows. Consider the bipartite graph $\smash{G^{3,2}}$ corresponding to adjacency matrix $\smash{M^{3,2}}$; if $\smash{G^{3,2}}$ has $\ell$ connected components, then let $\smash{M^{2,1}}$ and $\smash{M^{2,2}}$ both have dimensions $1\times \ell$ (where we are considering the simplified representation for a simple 2-level network; see Example <ref>). Let $\smash{M^{2,1}_{1i}=a}$ if and only if the $i$th connected component of $\smash{G^{3,2}}$ has $a$ vertices in $\mV_{1}$, and let $\smash{M^{2,2}_{1i}=b}$ if and only if the $i$th connected component of $\smash{G^{3,2}}$ has $b$ vertices in $\mV_{2}$.
Observe that the sum of the entries of $\smash{M^{2,1}}$ is equal to the sum of the entries of $\smash{M^{3,1}}$, and similarly with $\smash{M^{2,2}}$ and $\smash{M^{3,3}}$.

We call the network $\mN_2$ constructed above
the 2-level network associated with the 3-level network $\mN_3$.

Consider the network of Figure <ref>. The corresponding 2-level network is depicted in Figure <ref>.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.5of K] (V1) $V_1$;
[nnode,below=0.5of K] (V2) $V_2$;

[vertex,right=2of S1] (T) $T$;

[ddedge,bend left=10] (S1)  to node[sloped,fill=white, inner sep=0pt]$e_2$ (V1);
[ddedge,bend right=10] (S1)  to node[sloped,fill=white, inner sep=0pt]$e_3$ (V1);
[ddedge,bend left=30] (S1) to  node[sloped,fill=white, inner sep=0pt]$e_1$ (V1);
[ddedge,bend right=30] (S1) to  node[sloped,fill=white, inner sep=0pt]$e_4$ (V1);

[edge,bend right=15] (V1) to  node[sloped,fill=white, inner sep=0pt]$e_8$ (T);
[edge,bend left=15] (V1) to  node[sloped,fill=white, inner sep=0pt]$e_7$ (T);

[ddedge,bend right=15] (S1) to  node[sloped,fill=white, inner sep=0pt]$e_6$ (V2);
[ddedge,bend left=15] (S1) to  node[sloped, fill=white, inner sep=0pt]$e_5$ (V2);

[edge,bend right=15] (V2) to  node[sloped,fill=white, inner sep=0pt]$e_{10}$ (T);
[edge,bend left=15] (V2) to  node[sloped,fill=white, inner sep=0pt]$e_9$ (T);

The simple 2-level network corresponding to the (simple, 3-level) network
of Example <ref>.

While this deterministic process results in a unique simple 2-level network given a simple 3-level network, there may be multiple 3-level networks that result in the same 2-level network.
This however does not affect the following statement, which gives an upper bound for the capacity of a 3-level network
in terms of the capacity of the corresponding 2-level network, when the vulnerable edges are in both cases those directly connected with the source. While the argument
extends to more generalized choices of the vulnerable edges, in this paper we concentrate on this simplified scenario for ease of exposition.

Let $\mN_3$ be a simple 3-level network, and let $\mN_2$ be the simple 2-level network associated to it.
Let $\mU_3$ and $\mU_2$ be the set of edges directly connected to the sources of $\mN_3$ and $\mN_2$, respectively. Then for all network alphabets $\mA$ and for all $t \ge 0$ we have

\[\CC_1(\mN_3,\mA,\mU_3,t)\leq \CC_1(\mN_2,\mA,\mU_2,t).\]

Consider the network of Figure <ref> and
the corresponding 2-level network in Figure <ref>.
Suppose that the vulnerable edges in both networks are those
directly connected to the source,
and in both cases we allow up to $t$ corrupted edges.
Then Theorem <ref> implies that the capacity of the network
of Figure <ref>
is upper bounded by the capacity of the network of Figure <ref>.

Let $\mC_3$ be an outer code and $\mF_3$ be a network code for $(\mN_3,\mA)$ such that $\mC_3$ is unambiguous for the channel $\Omega[\mN_3,\mA,\mF_3,S \to T,\mU_3,t]$.

Let $\smash{M^{3,2}}$ be the matrix defining $\smash{\mN_3}$, and let $\smash{G^{3,2}}$ denote the bipartite graph with (simplified) adjacency matrix $\smash{M^{3,2}}$. Let $\smash{V^3_{ij}}$ denote the $j$th node in the right part of the $i$th connected component of $\smash{G^{3,2}}$, and let $\smash{\mF_{V^3_{ij}}}$ denote the function at $\smash{V^3_{ij}}$ defined by $\smash{\mF_3}$. Let the neighborhood of $\smash{V^3_{ij}}$ in $\smash{G^{3,2}}$ contain the (ordered) set of vertices
\[\smash{V^3_{ij1},\, V^3_{ij2}, \, \ldots,\, V^3_{ij\degin(V^3_{ij})}},\]
where $\smash{\degin(V^3_{ij})}$ is the in-degree of $\smash{V^3_{ij}}$. Then, for each $\smash{1\leq k\leq \degin(V^3_{ij})}$, denote the network code function at $\smash{V^3_{ijk}}$ by $\smash{\mF_{V^3_{ijk}}}$.
Notice that every $\smash{\mF_{V^3_{ijk}}}$ is a function with domain $\mA$ and codomain $\mA^{\degout(V^3_{ijk})}$, while each function  $\smash{\mF_{V^3_{ij}}}$ has domain $\mA^{\degin(V^3_{ij})}$ and codomain $\mA$.
Note that every node in the left part of $\smash{G^{3,2}}$ has a label $V^{3}_{ijk}$ for some $i$ and $j$ due to assumption <ref> of Definition <ref>. Each such node can have multiple labels $\smash{V^3_{ijk}}$ and $\smash{V^3_{ij'k'}}$ where $(j,k)\neq (j',k')$; of course, we stipulate that

We claim there exists $\mF_2$ such that $\mC_3$ is also unambiguous for $\Omega[\mN_2,\mA,\mF_2,S \to T,\mU_2,t]$. Indeed, define $\mF_2$ for each intermediate node $V_i$ in $\mN_2$ that corresponds to connected component $i$ of $G^{3,2}$ as an appropriate composition of functions at nodes in $\mV_1$ and $\mV_2$ of the 3-level network. More technically, we define $\mF_{V_i}$ as follows (here the product symbols denote the Cartesian product):

\begin{align*}
\mF_{V_i} : \mA^{\degin(V_i)} &\to \mA^{\degout(V_i)},\\
x&\mapsto \prod_{j=1}^{\degout(V_i)}
\mF_{V^3_{ij}}\left(\prod_{k=1}^{\degin(V^3_{ij})} \mF_{V^3_{ijk}}(x_{ijk})\vert_{V_{ij}^3}\right),
\end{align*}

where $x_{ijk}$ is the coordinate of the vector $x$ corresponding to node $\smash{V^{3}_{ijk}}$ in the left part of the $i$th connected component of $\smash{G^{3,2}}$, and  $\smash{\mF_{V^3_{ijk}}(x_{ijk})\vert_{V_{ij}^3}}$ is the restriction of $\smash{\mF_{V^3_{ijk}}(x_{ijk})}$ to the coordinate corresponding to $\smash{V_{ij}^3}$.

We claim that the fan-out set of any $x\in \mC_3$ over the channel $\Omega[\mN_2,\mA,\mF_2,S \to T,\mU_2,t]$ is exactly equal to the fan-out set of $x$ over the channel $\Omega[\mN_3,\mA,\mF_3,S \to T,\mU_3,t]$. This follows directly from the definitions of $\mF_2$ and $\mF_3$, and the fact that both networks are corrupted in up to $t$ positions from their first layers.
Suppose then, by way of contradiction, that $\mC_3$ is not unambiguous for $\Omega[\mN_2,\mA,\mF_2,S \to T,\mU_2,t]$.  That is, there exist $x,x'\in \mC_3$ such that $x\neq x'$ but the intersection of the fan-out sets of $x$ and $x'$ is nonempty. Then $\mC_3$ was not unambiguous for $\Omega[\mN_3,\mA,\mF_3,S \to T,\mU_3,t]$ to begin with. We conclude that $\mC_3$ is unambiguous for $\Omega[\mN_2,\mA,\mF_2,S \to T,\mU_2,t]$.

The proof above contains rather heavy notation and terminology. We therefore illustrate it with an example.

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=1.2of K] (V1) $V_{111}^3$;

[nnode,above=0.7of K] (V2) $V_{112}^3$;

[nnode,above=0.3of K] (V3) $V_{113}^3$;

[nnode,below=0of K] (V4) $V_{114}^3$;

[nnode,below=0.4of K] (V5) $V_{211}^3$;

[nnode,below=0.8of K] (V6) $V_{212}^3$;

[vertex,right=3.5of S1] (T) $T$;

[nnode,right=1.3of V1 ] (V7) $V_{11}^3$;

[nnode,right=1.3of V3] (V8) $V_{12}^3$;

[nnode,right=1.3of V4] (V9) $V_{21}^3$;

[nnode,right=1.3of V6] (V10) $V_{22}^3$;

[ddedge,bend left=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$x_{111}$ (V1);

[ddedge,bend right=0] (S1)  to node[sloped,fill=white, inner sep=1pt]$x_{112}$ (V2);

[ddedge,bend left=0] (S1) to  node[sloped,fill=white, inner sep=1pt]$x_{113}$ (V3);

[ddedge,bend right=0] (S1) to  node[sloped,fill=white, inner sep=1pt]$x_{114}$ (V4);

[ddedge,bend right=0] (S1) to  node[sloped,fill=white, inner sep=1pt]$x_{211}$ (V5);

[ddedge,bend right=0] (S1) to  node[sloped,fill=white, inner sep=1pt]$x_{212}$ (V6);

[edge,bend left=0] (V1) to  node (V7);

[edge,bend left=0] (V1) to  node (V8);

[edge,bend left=0] (V2) to  node (V7);

[edge,bend left=0] (V2) to  node (V8);

[edge,bend left=0] (V3) to  node (V7);

[edge,bend left=0] (V3) to  node (V8);

[edge,bend left=0] (V4) to  node (V7);

[edge,bend left=0] (V4) to  node (V8);

[edge,bend right=0] (V5) to  node (V9);

[edge,bend right=0] (V5) to  node (V10);

[edge,bend right=0] (V6) to  node (V9);

[edge,bend right=0] (V6) to  node (V10);

[edge,bend left=0] (V7) to  node (T);

[edge,bend left=0] (V8) to  node (T);

[edge,bend left=0] (V9) to  node (T);

[edge,bend left=0] (V10) to  node (T);

Network for Example <ref>.

Consider the labeling of vertices in Figure <ref> of Network $\mN_3$. Suppose the capacity is achieved by a network code
\, \mF_{V_{112}^3},
\, \mF_{V_{113}^3},
\, \mF_{V_{114}^3},
\, \mF_{V_{211}^3},
\, \mF_{V_{211}^3},
\, \mF_{V_{11}^3},
\, \mF_{V_{12}^3},
\, \mF_{V_{21}^3},
\, \mF_{V_{22}^3}\}$$
for $(\mN_3,\mA)$ and by an outer code $\mC_3\subseteq \mA^6$ unambiguous for the channel $\Omega[\mN_3,\mA,\mF_3,S \to T,\mU_3,t]$. Let $x=(x_{111},x_{112},x_{113},x_{114},x_{211},x_{212}) \in \mC_3$ and consider the scheme in Figure <ref>. The way functions $\mF_{V_1}$ and $\mF_{V_2}$ are defined in the proof of Theorem <ref> gives that the alphabet symbols

\begin{gather*}
\mF_{V_{11}^3}\big(\mF_{V_{111}^3}(x_{111})\vert_{V_{11}^3},\mF_{V_{112}^3}(x_{112})\vert_{V_{11}^3},\mF_{V_{113}^3}(x_{113})\vert_{V_{11}^3},\mF_{V_{114}^3}(x_{114})\vert_{V_{11}^3}\big), \\
\mF_{V_{12}^3}\big(\mF_{V_{111}^3}(x_{111})\vert_{V_{12}^3},\mF_{V_{112}^3}(x_{112})\vert_{V_{12}^3},\mF_{V_{113}^3}(x_{113})\vert_{V_{12}^3},\mF_{V_{114}^3}(x_{114})\vert_{V_{12}^3}\big), \\
\mF_{V_{21}^3}\big(\mF_{V_{211}^3}(x_{211})\vert_{V_{21}^3},\mF_{V_{212}^3}(x_{212})\vert_{V_{21}^3}\big), \mbox{ and } \\
\mF_{V_{22}^3}\big(\mF_{V_{211}^3}(x_{211})\vert_{V_{22}^3},\mF_{V_{212}^3}(x_{212})\vert_{V_{22}^3}\big)
\end{gather*}

are carried over the edges $e_7$, $e_8$, $e_9$ and $e_{10}$ respectively in Figure <ref>. Observe that the the fan-out set of any $x\in \mC_3$ over the channel $\Omega[\mN_2,\mA,\mF_2,S \to T,\mU_2,t]$ is exactly equal to the fan-out set of $x$ over the channel $\Omega[\mN_3,\mA,\mF_3,S \to T,\mU_3,t]$, as desired.

§.§ Some Families of Simple 2-Level Networks

In this section, we introduce five families of simple 2-level networks. Thanks to Theorem <ref>,
any upper bound for the capacities of these translates into an upper bound for the capacities of a 3-level networks associated with them; see Definition <ref>.
The five families of networks introduced in this subsection should be regarded as the “building blocks” of the theory developed in this paper,
since in Section <ref>
we will argue how to use them to obtain upper bounds for the capacities of larger networks.

We focus our attention on the scenario where the adversary acts on the edges directly connected to the source $S$, which we denote by $\mU_S$ throughout this section.
The families we introduce will be studied in detail in later sections, but are collected here for preparation and ease of reference. Each family is parametrized by a positive integer (denoted by $t$ or $s$ for reasons that will become clear below).

Define the simple 2-level networks

$$\mathfrak{A}_t=([t,2t],[t,t]), \quad t \ge 1.$$

Note that they reduce to
the Diamond Network of Section <ref> for $t=1$. The Generalized Network Singleton Bound of Theorem <ref> reads
$\CC_1(\mathfrak{A}_t,\mA,\mU_S,t) \le t$
for any alphabet $\mA$. Results related to this family can be found in Theorem <ref> and Proposition <ref>.

Define the simple 2-level networks
$$\mathfrak{B}_s=([1,s+1],[1,s]), \quad s \ge 1.$$

The case where $s=1$ yields the Diamond Network of Section <ref>. The Generalized Network Singleton Bound of Theorem <ref> for $t=1$
$\CC_1(\mathfrak{B}_s,\mA,\mU_S,1) \le s$
for any alphabet $\mA$. Note that for this family we will always take $t=1$, which explains our choice of using a different index, $s$, for the family members. Results related to this family can be found in Theorem <ref> and Corollary <ref>.

Define the simple 2-level networks
$$\mathfrak{C}_t=([t,t+1],[t,t]), \quad t \ge 2.$$

The case $t=1$ is covered in $\mathfrak{A}_1$ of Family <ref> and thus formally excluded here for a reason we will explain in Remark <ref>. The Generalized Network Singleton Bound of Theorem <ref>
$\CC_1(\mathfrak{C}_t,\mA,\mU_S,t) \le 1$
for any alphabet $\mA$. Our result related to this family can be found in Theorem <ref>.

Define the simple 2-level networks
$$\mathfrak{D}_t=([2t,2t],[1,1]), \quad t \ge 1.$$

The case where $t=1$ yields the Mirrored Diamond Network of Section <ref>. The Generalized Network Singleton Bound of Theorem <ref>
$\CC_1(\mathfrak{D}_t,\mA,\mU_S,t) \le 1$
for any alphabet $\mA$. Results related to this family can be found in Theorems <ref> and <ref>.

Define the simple 2-level networks
$$\mathfrak{E}_t=([t,t+1],[1,1]), \quad t \ge 1.$$

The case where $t=1$ yields the Diamond Network of Section <ref>.
The Generalized Network Singleton Bound of Theorem <ref>
$\CC_1(\mathfrak{E}_t,\mA,\mU_S,t) \le 1$
for any alphabet $\mA$. Results related to this family can be found in Theorems <ref> and <ref>.

As we will see, the results of this section and of the next show that the Generalized Network Singleton Bound of Theorem <ref>
is never sharp for Families <ref>, <ref>, and <ref>, no matter what the alphabet is.
The bound is, however, sharp for Families <ref> and <ref> under the assumption that the alphabet is a sufficiently large finite field, as we will show in Section <ref>.

§ SIMPLE 2-LEVEL NETWORKS: UPPER BOUNDS

In this section we present upper bounds on the capacity of simple 2-level networks based on a variety of techniques.
We then apply these bounds to the
families introduced in Subsection <ref>. We start by establishing the notation that we will follow in the sequel.

Throughout this section, $n \ge 2$ is an integer and
is a simple 2-level network; see Definition <ref>.
We denote by $\mU_S \subseteq \mE$ the set of edges directly connected to the source $S$ and let  $\mA$ be a network alphabet.
We denote the intermediate nodes of $\mN$ by $V_1,\ldots,V_n$, which correspond to the structural parameters $a_1, \ldots, a_n$ and
$b_1, \ldots, b_n$.
If $\mF$ is a network code for $(\mN,\mA)$,
then we simply write $\mF_i$ for $\smash{\mF_{V_i}}$.
Observe moreover that the network code $\mF$ can be “globally” interpreted as a function

$$\mF: \mA^{a_1+\ldots +a_n} \to \mA^{b_1+\ldots +b_n},$$

although of course allowed functions $\mF$ are restricted by the topology of the underlying 2-level network.

We start by spelling out the Generalized Network Singleton Bound of Theorem <ref> specifically for simple 2-level networks.

Following Notation <ref>, for all $t \ge 0$ we have

\[\CC_1(\mN,\mA,\mU_S,t) \leq
\min_{P_1\sqcup P_2=\{1,\ldots,n\}}\left(\sum_{i\in P_1} b_i+\max\left\{0,\sum_{i\in P_2} a_i - 2t\right\}\right),\]

where the minimum is taken over all 2-partitions $P_1, P_2$ of the set $\{1,\ldots,n\}$.

The upper bounds we derive in this section use a “mix” of projection and packing arguments. We therefore continue by reminding the reader of the notions of the Hamming metric ball and shell.

Given an outer code $\smash{\mC \subseteq \mA^{a_1+a_2+\ldots+a_n}}$, we let $\smash{\pi_i(\mC)}$ be the projection of $\mC$ onto the $a_i$ coordinates corresponding to the edges to intermediate node $V_{i}$ of the simple 2-level network $\mN$. For example, $\smash{\pi_1(\mC)}$ is the projection onto the first $a_1$ coordinates of the codeword. Moreover, for a given $x \in \mC$, we denote by $B^\HH_t(x)$ the Hamming ball of radius $t$ with center $x$, and by $S^\HH_t(x)$ the shell of that ball. In symbols,

$$B^\HH_t(x)=\{y \in \mA^{a_1+a_2+\ldots+a_n} \st d^\HH(x,y) \le t\}, \qquad S^\HH_t(x)=\{y \in B^\HH_t(x) \st d^\HH(x,y) = t\},$$

where $d^\HH$ denotes the usual Hamming distance.

The next observation focuses on the case $n=2$ to illustrate an idea that will be generalized immediately after in Remark <ref> below.

If $n=2$, then for all $t \ge 0$
an outer code $\mC \subseteq \mA^{a_1+a_2}$ is unambiguous for the channel $\Omega[\mN,\mA,\mF,S\to T,\mU_S,t]$ if and only if

$$\mF(x+e)=(\mF_1(\pi_1(x+e)), \mF_2(\pi_2(x+e))) \neq (\mF'_1(\pi_1(x'+e')), \mF_2(\pi_2(x'+e'))) =\mF(x'+e')$$
for all
$x,x' \in \mC$ with $x \neq x'$ and for all $e,e' \in \mA^{a_1+a_2}$ of Hamming weight at most $t$.
Therefore via a packing argument
we obtain

\begin{equation}
\label{eqn:packing_2}
\sum_{x \in \mC} |\mF\left(B^\HH_t(x)\right)| \le {|\mA|}^{b_1+b_2}.
\end{equation}

We will work towards extending the packing bound idea outlined in Remark <ref> to higher numbers of intermediate nodes using the properties of simple 2-level networks. We start with
the following result.

Following Notation <ref>, suppose $n=2$ and $b_1 \ge a_1$.
Let $t \ge 0$ and suppose that $\mC \subseteq \mA^{a_1+a_2}$ is unambiguous for the channel $\Omega[\mN,\mA,\mF,S\to T,\mU_S,t]$. Let $\mF'_1:\mA^{a_1} \to \mA^{b_1}$ be any injective map. Then $\mC$ is unambiguous for the channel $\Omega[\mN,\mA,\{\mF_1',\mF_2\},S\to T,\mU_S,t]$ as well.

Let $\mF=\{\mF_1,\mF_2\}$ and $\mF'=\{\mF'_1,\mF_2\}$. Towards a contradiction and using Remark <ref>, suppose that
there are $x,x' \in \mC$ with $x \neq x'$ and $e,e' \in \mA^{a_1+a_2}$ of Hamming weight at most $t$ with $\mF'(x+e)=\mF'(x'+e')$. This implies

$$(\mF'_1(\pi_1(x+e)), \mF_2(\pi_2(x+e)))=
(\mF'_1(\pi_1(x'+e')), \mF_2(\pi_2(x'+e'))).$$

Since $\mF'_1$ is injective, we have
$\pi_1(x+e) = \pi_1(x'+e')$ and thus

$$(\mF_1(\pi_1(x+e)), \mF_2(\pi_2(x+e)))=
(\mF_1(\pi_1(x'+e')), \mF_2(\pi_2(x'+e'))).$$

That is,
$\mF(x+e)=\mF(x'+e')$, a contradiction.

Lemma <ref> extends easily to an arbitrary number of intermediate nodes, showing that whenever $b_i \ge a_i$ for some $i$, without loss of generality we can assume $b_i=a_i$ and take the corresponding function $\mF_i$ to be the identity (ignoring extraneous outgoing edges). In other words, the capacity obtained by maximizing over all possible choices of $\mF$ is the same as the capacity obtained by maximizing over the $\mF$'s where $\mF_i$ is equal to the identity whenever $b_i \ge a_i$ (again, where some edges can be disregarded). This will simplify the analysis of the network families we study. In particular,
we can reduce the study of a
simple 2-level network $\mN=([a_1,...,a_n],[b_1,...,b_n])$
as in Notation <ref> to the study of

where, up to a permutation of the vertices and edges,

\begin{equation*}
r=\max\{i \st a_i \le b_i \mbox{ for all } 1 \le i \le r\}.
\end{equation*}

The next result combines the observation
of Remark <ref> with a packing argument to derive an upper bound on the capacity of certain simple 2-level networks.

Following Notation <ref>,
suppose that $a_i \le b_i$ for all $1\leq i \leq r$. Let $t \ge 0$ and let $\mC$ be an unambigious code for $\Omega[\mN,\mA,\mF,S \to T,\mU_S,t]$. Then

$$\sum_{\substack{t_1,\ldots,t_r \ge 0 \\ t_1+\ldots+t_r \le t}} \, \prod_{i=1}^r\binom{a_i}{t_i}(|\mA|-1)^{t_i} \, \sum_{x \in \mC} \, \prod_{j=r+1}^n \left|\mF_j\left(B^\HH_{t-(t_1+\ldots+t_r)}(\pi_j(x))\right)\right| \le |\mA|^{b_1+b_2+\ldots +b_n}.$$

Let $\mF=\{\mF_1,\ldots,\mF_r,\ldots,\mF_n\}$ be a network code for $(\mN,\mA)$, where the first $r$ functions correspond to the pairs $(a_1,b_1),\ldots,(a_r,b_r)$. By Lemma <ref>, we shall assume without loss of generality that $\mF_i$
is an injective map for $1 \le i \le r.$ By Remark <ref>, we can assume them to be identity by ignoring the extraneous outgoing edges. For $x \in \mC$, we have

$$B^\HH_t(x) = \bigsqcup_{t_1+\ldots +t_n \le t} \left[ S^\HH_{t_1}(\pi_1(x)) \times \cdots \times
S^\HH_{t_n}(\pi_n(x)) \right],$$

where $\sqcup$ emphasizes that the union is disjoint. Then,

\begin{align*}
\mF(B^\HH_t(x)) &= \bigcup_{t_1+\ldots +t_n \le t} \mF \left[S^\HH_{t_1}(\pi_1(x)) \times \cdots \times
S^\HH_{t_n}(\pi_n(x)) \right]\\
&= \bigcup_{t_1+\ldots +t_n \le t} \left[S^\HH_{t_1}(\pi_1(x)) \times \cdots \times
S^\HH_{t_r}(\pi_r(x)) \times \mF_{r+1}(S^\HH_{t_{r+1}}(\pi_{r+1}(x)) \times \cdots \times \mF_{n}(S^\HH_{t_{n}}(\pi_{n}(x)) \right]\\
&= \bigcup_{t_1 + \ldots +t_r \le t} \  \bigcup_{t_{r+1}+\ldots+t_n\le t - (t_1 + \ldots +t_r)}  \Bigl[ S^\HH_{t_1}(\pi_1(x)) \times \cdots \times S^\HH_{t_r}(\pi_r(x)) \, \times \\ & \qquad \qquad
\qquad
\times \mF_{r+1}(S^\HH_{t_{r+1}}(\pi_{r+1}(x))
\times \cdots \times  \mF_{n}(S^\HH_{t_{n}}(\pi_{n}(x))\Bigr].
\end{align*}

The first union in the last equality is disjoint due to $\mF_1,\ldots,\mF_r$ being the identity and the fact that we are considering the shells.

\begin{align*}
\mF(B^\HH_t(x)) &= \bigsqcup_{t_1+\ldots+t_r \le t} \Bigl[S^\HH_{t_1}(\pi_1(x)) \times \cdots \times S^\HH_{t_r}(\pi_r(x)) \times \\ &
\qquad \qquad \qquad
\bigcup_{t_{r+1}+\ldots+t_n \le t - (t_1 + \ldots + t_r)}\biggl( \mF_{r+1}(S^\HH_{t_{r+1}}(\pi_{r+1}(x))
\times \cdots \times \mF_{n}(S^\HH_{t_{n}}(\pi_{n}(x))\biggr)\Bigr].
\end{align*}

By taking cardinalities in the previous identity
we obtain

\[
|\mF(B^\HH_t(x))|= \sum_{ t_1 + \ldots +t_r \le t} \, \prod_{i=1}^r\binom{a_i}{t_i}(|\mA|-1)^{t_i} \prod_{j=r+1}^n |\mF_j(B^\HH_{t-(t_1 + \ldots + t_r)}(\pi_j(x)))|,\]

where the terms in the second product come from considering that all shells up to the shell of radius $t-(t_1 + \ldots + t_r)$ will be included for each projection. Summing over $x \in \mC$, exchanging summations, and using the same argument as in (<ref>), we obtain the desired result.

In this paper, we
are mainly interested in the case $(n,r)=(2,1)$ of the previous result.
For convenience of the reader, we state this as a corollary of Theorem <ref>.

Following Notation <ref>, suppose $n=2$ and $a_1\le b_1$.
Let $t \ge 1$ and let
$\mC$ be an unambiguous code for the channel $\Omega[\mN,\mA,\mF,S \to T,\mU_S,t]$. Then

\binom{a_1}{t_1}(|\mA|-1)^{t_1} \sum_{x \in \mC} \left|\mF_2\left(B^\HH_{t-t_1}(\pi_2(x)))\right)\right| \le |\mA|^{b_1+b_2}.$$

We next apply the bound of Theorem <ref> (in the form of Corollary <ref>) to some of the network families
introduced in Subsection <ref>.
With some additional information, Theorem <ref> gives us that the Generalized Network Singleton Bound of Corollary <ref> is in general not achievable, no matter what the network alphabet $\mA$ is. This is in strong contrast with what is commonly observed in classical coding theory, where the Singleton bound is always the sharpest (and in fact sharp) when the alphabet is sufficiently large.

Let $\mathfrak{B}_s=(\mV,\mE,S,\{T\})$ be a member of
Family <ref>. Let $\mA$ be any network alphabet and let $\mU_S$ be the  set of edges of $\mathfrak{B}_s$ directly connected to $S$.
We have

$$\CC_1(\mathfrak{B}_s,\mA,\mU_S,1) <s.$$

In particular, the Generalized Network Singleton Bound of Corollary <ref> is not met.

Let $\mF$ be a network code for the pair $(\mathfrak{B}_s,\mA)$ and let
$q:=|\mA|$ to simplify the notation.
Suppose that $\mC$ is an unambiguous code for the channel
$\Omega[\mathfrak{B}_s,\mA,\mF,S \to T,\mU_S,1]$. We want to show that $|\mC|<q^s$.
Corollary <ref> gives

\begin{equation} \label{touse}
(q-1) \cdot |\mC| + \sum_{x \in \mC} \left|\mF_2\left(B^\HH_1(\pi_2(x))\right)\right| \le q^{s+1}.
\end{equation}

Suppose towards a contradiction that $|\mC|=q^s$.
We claim that there exists a codeword $x \in \mC$ for which the cardinality of

$$\left\{\mF_2(\pi_2(z)) \st \dH(\pi_2(x),\pi_2(z))\leq 1,\ z\in \mA^{s+2}\right\}$$

is at least 2. To see this, we start by observing that $\mF_2$ restricted to ${\pi_2(\mC)}$ must be injective, as otherwise the fan-out sets of at least two codewords would intersect non-trivially, making $\mC$ ambiguous for the channel $\Omega[\mathfrak{B}_s,\mA,\mF,S \to T,\mU_S,1]$.
Therefore it is now enough to show that $B^\HH_1(\pi_2(x)) \cap B^\HH_1(\pi_2(y)) \neq \emptyset$ for some distinct $x,y\in\mC$,
which would imply that the cardinality of one among

$$\left\{\mF_2(\pi_2(z)) \st \dH(\pi_2(x),\pi_2(z))\leq 1,\ z\in \mA^{s+2}\right\}, \ \left\{\mF_2(\pi_2(z)) \st \dH(\pi_2(y),\pi_2(z))\leq 1,\ z\in \mA^{s+2}\right\}$$

is at least 2, since $\mF_2(\pi_2(x)) \neq \mF_2(\pi_2(y))$.
Observe that $|B^\HH_1(\pi_2(x))| = (s+1)(q-1)+1$ for any $x \in \mC,$ and that
$$\sum_{x \in \mC} |B^\HH_1(\pi_2(x))| = q^s(s+1)(q-1)+q^s = q^{s+1}(s+1) - sq^s > q^{s+1}= |\mA^{a_2}|,$$
where we use the fact that $q > 1$. If $B^\HH_1(\pi_2(x)) \cap B^\HH_1(\pi_2(y)) = \emptyset$ for all distinct $x,y\in\mC$, then $\sum_{x \in \mC} |B^\HH_1(\pi_2(x))| \le |\mA^{a_2}|$, a contradiction. Therefore
$$B^\HH_1(\pi_2(x)) \cap B^\HH_1(\pi_2(y)) \neq \emptyset,$$
proving our claim.
We finally combine the said claim with the inequality in (<ref>), obtaining

$$q|\mC|+1=(q-1)|\mC| + 2 +(|\mC|-1)  \le (q-1) \, |\mC| + \sum_{x \in \mC} |\mF_2(B^\HH_1(\pi_2(x)))| \le q^{s+1}.$$
In particular, $|\mC| < q^s$, establishing the theorem.

While we cannot compute the exact capacity of the networks of Family <ref>, preliminary experimental results and case-by-case analyses seem to indicate that

\begin{equation} \label{ourc}
\CC_1(\mathfrak{B}_s,\mA,\mU_S,1) = \log_{|\mA|} \left(\frac{|\mA|^s + |\mA|}{2}-1\right),
\end{equation}

which would be consistent
with Corollary <ref>.
At the time of writing this paper
proving (or disproving) the equality in (<ref>) remains an open problem.

Notice that Theorem <ref> uses a packing argument “downstream” of the intermediate nodes in a simple 2-level network. Next, we work toward an upper bound on capacity that utilizes a packing argument “upstream” of the intermediate nodes.
Later we will show that the packing argument “upstream” acts similarly to the Hamming Bound from classical coding theory and can sometimes give better results in the networking context.

We start with the following lemma, which will be the starting point for the Second Packing Bound below.

We follow Notation <ref>
and let $t \ge 0$ be an integer.
Let $\mC$ be an outer code for $(\mN,\mA)$.  Then $\mC$ is unambiguous
for the channel $\Omega[\mN,\mA,\mF,S\to T,\mU_S,t]$
if and only if $\mF^{-1}(\mF(B^\HH_t(x))) \cap \mF^{-1}(\mF(B^\HH_t(x'))) = \emptyset$ for all distinct $x,x' \in \mC$.

Suppose $\mF^{-1}(\mF(B^\HH_t(x))) \cap \mF^{-1}(\mF(B^\HH_t(x'))) \neq \emptyset$ for some distinct $x,x'\in\mC$, and let $y$ lie in that intersection. This implies
$$\mF(y) \in \mF(B^\HH_t(x)) \cap \mF(B^\HH_t(x')) = \Omega(x) \cap \Omega(x').$$
In other words, $\mC$ is not unambiguous for the channel $\Omega[\mN,\mA,\mF,S\to T,\mU_S,t]$. For the other direction, it is straightforward to see that disjointness of the preimages implies disjointness of the fan-out sets.

Following the notation of
Lemma <ref>, for $n=2$
and an unambiguous $\mC$ for the channel $\Omega[\mN,\mA,\mF,S\to T,\mU_S,t]$ we obtain the “packing” result

$$\sum_{x \in \mC} |\mF^{-1}(\mF(B^\HH_t(x)))| \le |\mA|^{a_1 + a_2}.$$

By extending this idea to more than two intermediate nodes, one obtains the following upper bound.

Following Notation <ref>,
suppose that $a_i \le b_i$ for $1\leq i \leq r$. Let $t \ge 0$ and let $\mC$ be an unambigious code for $\Omega[\mN,\mA,\mF,S \to T,\mU_S,t]$. Then

$$\sum_{\substack{t_1,\ldots,t_r \ge 0 \\ t_1+\ldots+t_r \le t}}\prod_{i=1}^r\binom{a_i}{t_i}(|\mA|-1)^{t_i} \sum_{x \in \mC} \prod_{j=r+1}^n |\mF_j^{-1}(\mF_j(B^\HH_{t-(t_1+\ldots+t_r)}(\pi_j(x))))| \le |\mA|^{a_1+a_2+\cdots a_n}.$$

The proof of the previous result follows from similar steps to those in the proof of Theorem <ref>, and we omit it here.
As we did for the case of
Theorem <ref>,
we also spell out the case $(n,r)=(2,1)$ for Theorem <ref>.

Following Notation <ref>, suppose $n=2$ and $a_1\le b_1$.
Let $t \ge 1$ and let
$\mC$ be an unambiguous code for the channel $\Omega[\mN,\mA,\mF,S \to T,\mU_S,t]$. Then

$$\sum_{t_1=0}^t \binom{a_1}{t_1}(|\mA|-1)^{t_1} \sum_{x \in \mC} |\mF_2^{-1}(\mF_2(B^\HH_{t-t_1}(\pi_2(x))))| \le |\mA|^{a_1 + a_2}.$$

Although Theorem <ref> acts similarly to
the Hamming Bound from classical coding theory, we find it significantly more difficult to apply than our
Theorem <ref>
in the networking context.
The reason behind this lies in the fact that, in general,

\begin{equation} \label{nono}\mF^{-1}(\mF(B^\HH_t(x))) \neq \mF_1^{-1}(\mF_1(\pi_1(B^\HH_t(x)))) \times  \mF_2^{-1}(\mF_2(\pi_2(B^\HH_t(x)))).
\end{equation}

This makes it challenging to evaluate the quantities in the statement of
Theorem <ref>, even in the case $n=2$ (Corollary <ref>).
We give an example to illustrate the inequality in (<ref>).

Consider the Diamond Network $\mathfrak{A}_1$ with $\mA=\F_3$; see Section <ref> and Subsection <ref>. We know from Theorem <ref>
that its capacity is $\log_3 2$.
A capacity-achieving pair $(\mF,\mC)$
is given by $\mC=\{(1,1,1),(2,2,2)\}$ and $\mF=\{\mF_1,\mF_2\}$, where
$\mF_1(a) = a$ for all $a \in \mA$
\begin{cases}
1  & \text{if} \ \ x = y = 1 \\
2  & \text{if} \ \ x = y = 2 \\
0  & \text{otherwise.} \\
\end{cases}$$

\begin{align*}
\mF^{-1}(\mF(B^\HH_1((1,1,1))))
&=\mF^{-1}(\{(0,1),(1,1),(2,1),(1,0)\}) \\
&\neq \mF_1^{-1}(\{0,1,2\}) \times \mF_2^{-1}(\{0,1\})\\
&=\mF_1^{-1}(\mF_1(B^\HH_1(1)))\times \mF_2^{-1}(\mF_2(B^\HH_1(1,1))).
\end{align*}

We next present an upper bound on the capacity of the networks of Family <ref>,
showing that the Generalized Network Singleton Bound
of Corollary <ref> is not met for this family, no matter what the alphabet size is.
Notice that the number of indices
$i$ for which
$a_{i}\leq b_{i}$
for a network
of Family <ref>
is 0 whenever $t>1$.
In particular, the strategy behind the proofs of Theorems <ref> and <ref>
is of no help in this case.

Let $\mathfrak{E}_t=(\mV,\mE,S,\{T\})$ be a member of
Family <ref>. Let $\mA$ be any network alphabet and let $\mU_S$ be the  set of edges of $\mathfrak{E}_t$ directly connected to $S$.
We have

$$\CC_1(\mathfrak{E}_t,\mA,\mU_S,t) <1.$$

In particular, the Generalized Network Singleton Bound of Corollary <ref> is not met.

Let $q:=|\mA|$.
Suppose by way of contradiction that there exists an unambiguous code $\mC$ of size $q$ for $\Omega[\mathfrak{E}_{t},\mA,\mF,S \to T,\mU_S,t]$, for some network code  $\mF=\{\mF_{1},\mF_{2}\}$.  Since $\mC$ is unambiguous, it must be the case that $\mC$ has minimum distance equal to at least $2t+1$, making $\mC$ an MDS code of length and minumum distance $2t+1$.
Thus, $\pi_1(\mC)$ must contain $q$ distinct elements. We also observe that the restriction of $\mF_1$ to $\pi_1(\mC)$ must be injective, since otherwise the intersection of fan-out sets would be nonempty for some pair of codewords in $\mC$. Therefore we have that $\mF_1(\pi_1(\mC))=\mA$.

Putting all of the above together, we conclude that there must exist $x, y \in \mC$ and $e\in \mA^{2t+1}$ such that $x\neq y$, $\mF_1(\pi_1(x))=\mF_1(\pi_1(e))$, and $d^H(\pi_1(e),\pi_1(y))\le t-1$. We thus have

\begin{align*}
x'&:=(x_1,\ldots,x_t,x_{t+1},y_{t+2},y_{t+3},\ldots,y_{2t+1}) \in B^\HH_t(x),\\
y'&:=(e_1,\ldots,e_t,x_{t+1},y_{t+2},y_{t+3},\ldots,y_{2t+1}) \in B^\HH_t(y).  \end{align*}

Finally, observe that $(\mF_1(\pi_1(x')),\mF_2(\pi_2(x')))=(\mF_1(\pi_1(y')),\mF_2(\pi_2(y')))\in \Omega(x)\cap \Omega(y)$, a contradiction.

We now turn
to the networks of Family <ref>, which are probably the most natural generalization of the Diamond Network of Section <ref>.
We show that none of the members of
Family <ref> meet the Generalized Network Singleton Bound of Corollary <ref> with equality, no matter what the underlying alphabet is.

Let $\mathfrak{A}_t=(\mV,\mE,S,\{T\})$ be a member of
Family <ref>. Let $\mA$ be any network alphabet and let $\mU_S$ be the  set of edges of $\mathfrak{A}_t$ directly connected to $S$.
We have

$$\CC_1(\mathfrak{A}_t,\mA,\mU_S,t) <t.$$

In particular, the Generalized Network Singleton Bound of Corollary <ref> is not met.

Let $q:=|\mA|$. Towards a contradiction, assume that
the rate $t$ is achievable. That is, there exists an unambiguous code $\mC$ of size $q^t$ for $\Omega[\mathfrak{A}_{t},\mA,\mF,S \to T,\mU_S,t]$, where $\mF=\{\mF_{1},\mF_{2}\}$ is a network code for $(\mathfrak{A}_t,\mA)$. Note that $|\pi_2(\mC)|=|\mC|$ and that the restriction of
$\mF_2$ to $\pi_2(\mC)$
is injective, as otherwise
the intersection of fan-out sets would be nonempty for some pair of codewords in $\mC$, as one can easily check.

We claim that there must exist two distinct codewords $x,y \in \mC$ such that $B^\HH_t(\pi_2(x)) \cap B^\HH_t(\pi_2(y)) \neq \emptyset$.
Observe that

\begin{align}
\sum_{x \in \mC} |B^\HH_t(\pi_2(x))| &= q^t\left(\sum_{k=0}^t \binom{2t}{k}(q-1)^k\right) \nonumber \\
&> q^t\left(\sum_{k=0}^t \binom{t}{k}(q-1)^k\right) \nonumber \\
&= q^{2t}, \label{eqn:factorial}
\end{align}

where Equation (<ref>) follows from the Binomial Theorem. If $B^\HH_t(\pi_2(x)) \cap B^\HH_t(\pi_2(y)) = \emptyset$ for all distinct $x,y\in\mC$, then we would have
$$\sum_{x \in \mC} |B^\HH_t(\pi_2(x))| = \left| \bigcup_{x \in \mC} B_t^\HH(\pi_2(x)) \right| \le q^{2t}.$$
Therefore it must be the case that some such intersection is nonempty.
In other words, there exist some distinct $x,y\in \mC$ and $e \in \mA^{2t}$ such that $e \in B^\HH_t(\pi_2(x)) \cap B^\HH_t(\pi_2(y))$.

By the fact that the restriction of
$\mF_2$ to $\pi_2(\mC)$
is injective and its codomain has size $q^t=|\pi_2(\mC)|$,
the restriction of
$\mF_2$ to $\pi_2(\mC)$
must be surjective as well.
$\mF_2(e) = \mF_2(\pi_2(a))$ for some $a \in \mC$.
If $a=x$, then $\mF_2(e)=\mF_2(\pi_2(x))$ and we have $(\mF_1(\pi_1(y)),\mF_2(e))=(\mF_1(\pi_1(y)),\mF_2(\pi_2(x))) \in \Omega(x) \cap \Omega(y)$, the intersection of the fan-out sets, which is a contradiction to $\mC$ being unambiguous. A similar argument holds if $a=y$. Otherwise, we still have $(\mF_1(\pi_1(x)),\mF_2(\pi_2(a))) \in \Omega(x) \cap \Omega(a),$ a contradiction. We conclude that there cannot be an unambiguous code of size $q^t$.

We conclude this section by mentioning that the networks of both Family <ref> and Family <ref> do achieve the Generalized Network Singleton Bound of Corollary <ref>: both capacities will be examined in the next section.

§ SIMPLE 2-LEVEL NETWORKS: LOWER BOUNDS

We devote this section to
deriving lower bounds
on the capacity of simple
2-level networks.
In connection with Theorem <ref>,
we note that a rate may be achievable for a simple 2-level network and yet not achievable for every corresponding simple 3-level network.
We start by establishing the notation for this section.

Throughout this section we follow Notation <ref>.
In particular, we work with simple 2-level networks
$\mN=(\mV,\mE,S,\{T\})=([a_1,a_2,\ldots,a_n],[b_1,b_2,\ldots,b_n])$, denoting by $\mU_S$ the set of edges directly connected to the source $S$.
For any $t \ge 1$, we partition the vertices of such a network into the following (disjoint and possibly empty) sets:

\begin{align*}
I_{1}(\mN,t)&=\{i \st a_i\geq b_i+2t\},\\
I_{2}(\mN,t)&=\{i \st a_i\leq b_i\},\\
I_{3}(\mN,t)&=\{i \st b_i + 1\leq a_i \leq b_i+2t-1\}.
\end{align*}

Suppose that $\mA$ is a sufficiently large finite field.
Let $t \ge 1$ and define the set $\Tilde{I}_{3}(\mN,t) =\{i \in I_{3}(\mN,t) \st a_i > 2t\}$.

\begin{equation*}
\CC_1(\mN,\mA,\mU_S,t)\geq \sum_{i \in I_1(\mN,t)} b_i + \max\left\{X,Y \right\},
\end{equation*}

\begin{align*}
X &= \sum_{i\in \Tilde{I}_3(\mN,t)} (a_i-2t) + \max\left\{0,\left(\sum_{i\in I_2(\mN,t)} a_i\right) - 2t\right\}, \\
Y &= \max\left\{0,\left(\sum_{i\in I_2(\mN,t)} a_i + \sum_{i\in I_3(\mN,t)} b_i\right)- 2t\right\}.
\end{align*}

We will construct a network code $\mF = \{\mF_1,\ldots,\mF_n\}$ for $(\mN,\mA)$ and an unambiguous outer code in various steps, indicating how each intermediate node operates. The alphabet $\mA$ should be
a large enough finite field
that admits MDS codes with parameters as described below.

For each $i \in I_1(\mN,t)$, let $\mF_i$ be a minimum distance decoder for an MDS code with parameters $\left[b_i+2t,\ b_i,\ 2t+1\right]$ that is sent along the first $b_i +2t$ edges incoming to $V_i$. The source sends arbitrary symbols along the extraneous $a_i - (b_i+2t)$ edges and these will be disregarded by $V_i$. Via the intermediate nodes indexed by $I_1(\mN,t)$, we have thus achieved $\sum_{i\in I_{1}(\mN,t)} b_i$ information symbols decodable by the terminal.

In the remainder of the proof we will show that either an extra $X$ symbols or an extra $Y$ symbols (i.e., an extra $\max\{X,Y\}$ symbols in general) can be successfully transmitted. We show how the two quantities $X$ and $Y$ can be achieved separately, so that we may choose the better option of the two and achieve the result.

* For each $i \in \Tilde{I}_3(\mN,t)$, let $\mF_i$ be a minimum distance decoder for an MDS code with parameters $\left[a_i,\ a_i-2t,\ 2t+1\right]$ that sends its output across the first $a_i -2t$ outgoing edges from $V_i$. Arbitrary symbols are sent along the remaining outgoing edges and they will be ignored at the destination. We disregard all intermediate nodes with indices from the set $I_3(\mN,t)\setminus \Tilde{I}_3(\mN,t)$ as they will not contribute to the lower bound  in this scheme.
The symbols sent through the vertices indexed by ${I_2}(\mN,t)$ will be globally encoded via an
MDS code with parameters

$$\left[\sum_{i\in I_{2}(\mN,t)} a_i,\ \left(\sum_{i\in I_{2}(\mN,t)} a_i\right) - 2t,\ 2t+1\right].$$

The intermediate nodes indexed by ${I_2}(\mN,t)$
will simply forward the incoming symbols along the first $a_i$ outgoing edges, sending arbitrary symbols along the other $b_i - a_i$ outgoing edges. Symbols sent on these outgoing edges will be disregarded at the destination. If $\sum_{i\in I_{2}(\mN,t)} a_i \leq 2t$, we instead ignore the vertices indexed by $I_2(\mN,t)$ in this scheme. In conclusion, via the intermediate nodes indexed by $I_2(\mN,t)\cup I_3(\mN,t)$, we have added $X$ information symbols decodable by the terminal.

* For $i \in I_2(\mN,t) \cup I_3(\mN,t)$, let each $\mF_i$ simply forward up to $b_i$ received symbols as follows. If $i\in I_2(\mN,t)$, then $a_i$ symbols will be forwarded along the first $a_i$ outgoing edges and arbitrary symbols will be sent along the other $b_i - a_i$ outgoing edges. These edges will be disregarded at the destination. If $i\in I_3(\mN,t)$, then $b_i$ symbols sent over the first $b_i$ edges incoming to $V_i$ will be forwarded. The source $S$ will send arbitrary symbols along the other $a_i - b_i$ incoming edges, which will however be ignored. At the concatenation of all (non-arbitrary) coordinates to an intermediate node with index in $I_2(\mN,t)\cup I_3(\mN,t)$, the outer code will be an MDS code with parameters

$$\left[\sum_{i\in I_{2}(\mN,t)} a_i + \sum_{i\in I_{3}(\mN,t)} b_i,\ \left(\sum_{i\in I_{2}(\mN,t)} a_i + \sum_{i\in I_{3}(\mN,t)} b_i\right) -2t ,\ 2t+1\right].$$

The MDS code is then decoded at the terminal. If $\sum_{i\in I_{2}(\mN,t)} a_i + \sum_{i\in I_{3}(\mN,t)} b_i \leq 2t$, we ignore the coordinates corresponding to $I_2(\mN,t)\cup I_3(\mN,t)$ in this scheme.
In conclusion, via the intermediate nodes in $I_2(\mN,t)\cup I_3(\mN,t)$ we have added $Y$ information symbols decodable at the terminal.

This concludes the proof.

We note that
Theorem <ref> does not always yield a positive value, even for networks where the capacity is positive. For example,
for the member
Family <ref>, Theorem <ref> gives a lower bound of 0 for the capacity. However, the following result shows that $\CC_1(\mathfrak{A}_2,\mA,\mU_S,2)$ is, in fact, positive.

Let $\mathfrak{A}_t=(\mV,\mE,S,\{T\})$ be a member of
Family <ref>. Let $\mA$ be any network alphabet and let $\mU_S$ be the  set of edges of $\mathfrak{A}_t$ directly connected to $S$.
We have

$$\CC_1(\mathfrak{A}_2,\mA,\mU_S,2) \ge 1.$$

Fix two distinct alphabet symbols $*, *'\in \mA$.
The source $S$ encodes each element of $\mA$ using a six-times repetition code. Vertex $V_1$
simply forwards the received symbols, while vertex $V_2$ proceeds as follows.
If, on the four incoming edges, an alphabet symbol appears at least three times, $V_2$ forwards that symbol on both outgoing edges.
Otherwise $V_2$ outputs $*$ on one edge, and $*'$ on the other. At destination, if the incoming symbols from $V_{2}$ match, then the terminal $T$ decodes to that symbol. Otherwise, it decodes to the alphabet symbol sent from $V_{1}$. All symbols from $\mA$ can be sent with this scheme, including $*$ and $*'$, giving a capacity of at least $1$.

We also give the following less sophisticated lower bound on the capacity of simple 2-level networks. The idea behind the proof is to construct a subnetwork of the original one where a lower bound for the capacity can be easily established.

Suppose that $\mA$ is a sufficiently large finite field.
For all $t \ge 0$ we have

\begin{equation} \label{albe}
\CC_1(\mN,\mA,\mU_S,t) \ge  \max\left\{0, \, \sum_{i=1}^n\min\{a_i,b_i\} -2t\right\}.
\end{equation}

We will construct a network $\mN'=(\mV,\mE',S,\{T\})$ such that
$$\CC_1(\mN,\mA,\mU_S,t) \ge \CC_1(\mN',\mA,\mU'_S,t),$$

where $\mU'_S$ is the set of edges directly connected to $S$ in the new network $\mN'$.
For $i \in I_2(\mN,t)$, remove the first $b_i - a_i$ outgoing edges from $V_i.$ Similarly, for each $i \in \{1,\ldots,n\} \setminus I_2(\mN,t)$, remove the first $a_i-b_i$

incoming edges to $V_i$. Denote the new network obtained in this way by $\mN'$ and observe that all intermediate nodes $V_i'$ in $\mN'$ have $\degin(V_i')=\degout(V_i')$. This implies that $I_2(\mN',t)=\{1,\ldots,n\}.$ Since removing edges cannot increase the capacity (technically, this is a consequence of Proposition <ref>), we have $\CC_1(\mN,\mA,\mU_S,t) \ge \CC_1(\mN',\mA,\mU_S,t).$ We will give a coding scheme for $\mN'$ that achieves the right-hand side of (<ref>) to conclude the proof.
Consider the edge-cut

$$\mE'= \bigcup_{i=1}^{n} \inn(V_{i}').$$

By the definition of $\mN'$, we have $|\mE'| = \sum_{i=1}^n\min\{a_i,b_i\}$.
Since the left-hand side of (<ref>) is always non-negative, we shall assume
$|\mE'| > 2t$ without loss of generality.
Under this assumption, we will prove that the rate
$|\mE'| -2t$
is achievable.

We choose the outer code $\mC$ to be an MDS code with parameters $[|\mE'|,|\mE'|-2t,2t+1]$ over the finite field $\mA$. All of the intermediate nodes forward incoming packets
(the number of outgoing edges will now allow this). The terminal receives a codeword of length $|\mE'|$ and decodes it according to the chosen MDS code.

The lower bound of Theorem <ref>
is larger than the one of Proposition <ref>, and it can be
strictly larger.
For example, consider the simple 2-level network $\mN=([2,5,6],[2,2,2])$. By the Generalized Network Singleton Bound of Corollary <ref>, we have  $\CC_1(\mN,\mA,\mU_S,2) \le 4$. Theorem <ref> gives a lower bound of $3$ for $\CC_1(\mN,\mA,\mU_S,2)$, while Proposition <ref> gives a lower bound of 2 for the same quantity.

As an application of  Theorem <ref> we provide a family of simple 2-level networks where
the Generalized Network Singleton Bound of Corollary <ref> is always met with equality.

Suppose that $\mA$ is a sufficiently large finite field.
Let $t \ge 0$ and suppose that
$I_3(\mN,t) = \emptyset$. Then the Generalized Network Singleton Bound of Corollary <ref> is achievable.

Since $I_3(\mN,t) = \emptyset$, $\Tilde{I}_3(\mN,t)$ as defined in Theorem <ref> is also empty. Therefore Theorem <ref> gives

\begin{equation}
\label{eqn:eql-sb}
\CC_1(\mN,\mA,\mU_S,t)\geq \sum_{i\in I_{1}(\mN,t)}b_i+\max\left\{0,\left(\sum_{i\in I_{2}(\mN,t)} a_i\right) -2t\right\}.
\end{equation}

Choosing $P_1 = I_1(\mN,t)$ and $P_2 = I_2(\mN,t)$ in Corollary <ref> gives us that the Generalized Network Singleton (upper) Bound is equal to the right-hand side of (<ref>).

We include an example illustrating how Corollary <ref> is applied in practice.

Take $\mN=([12,8,2,2,1],[5,2,4,3,1])$ and let $\mA$ be a sufficiently large finite field. We want to compute
We have $I_1(\mN,3) = \{1,2\}$, $I_2(\mN,t) = \{3,4,5\}$, and $I_3(\mN,t)=\emptyset$. The intermediate nodes indexed by $i \in I_1(\mN,3)$ use local MDS decoders of dimension $b_i$ to retrieve $\sum_{i\in I_{1}(\mN,t)}b_i$ information symbols. That is, $V_1$ uses an $[11,5,7]$ MDS decoder and $V_2$ uses an $[8,2,7]$ MDS decoder. The intermediate nodes indexed by $I_2(\mN,3)$ are supposed to cooperate with each other and can be seen as one intermediate node with $5$ incoming and $8$ outgoing edges.

In the notation of the proof of Corollary <ref>, we have $\sum_{i\in I_{2}(\mN,t)} a_i < 2t$. In this case,
the vertices indexed by $I_{2}(\mN,t)$ are disregarded.
In total, the Generalized Network Singleton Bound of Corollary $\ref{cor:sing}$, whose value is 7, is met with equality.

We finally turn to the networks of Families <ref> and <ref>, which we did not treat in Section <ref>.
The next two results compute
the capacities of these families and prove, in particular, that the Generalized Network Singleton Bound of Corollary <ref>
is attained.
This, along with the upper bounds of Section <ref> for the families <ref>,<ref> and <ref>, demonstrates that emptiness of $I_3(\mN,t)$ is far from a complete characterization of the Generalized Network Singleton Bound achievability (i.e., Corollary <ref> is not biconditional); see Remark <ref>.

Let $\mathfrak{C}_t=(\mV,\mE,S,\{T\})$ be a member of
Family <ref>. Let $\mA$ be any network alphabet and let $\mU_S$ be the  set of edges of $\mathfrak{C}_t$ directly connected to $S$. We have

$$\CC_1(\mathfrak{C}_t,\mA,\mU_S,t) = 1.$$
In particular, the Generalized Network Singleton Bound of Corollary <ref> is met with equality.

We let $q:=|\mA|$ for ease of notation (but note that $q$ does not need to be a prime power). We will construct
a network code $\mF=\{\mF_1,\mF_2\}$
for $(\mN,\mA)$ and an unambiguous outer code $\mC$ for the channel $\Omega[\mathfrak{C}_{t},\mA,S \to T,\mU_S,t]$ of size $q$.
Recall that $t \ge 2$ by the very definition of Family <ref>.

Case 1: $q=t=2$.  Let $\mA = \{a,b\}.$ Encode each element of $\mA$ using a 5-times repetition code. It can be checked that the pair $(\mC,\mF)$ achieves the desired capacity, where $\mC=\{(a,a,a,a,a),(b,b,b,b,b)\}$ and $\mF=\{\mF_1,\mF_2\}$ is defined as follows.
$\mF_1(v) = v$ for all $v \in \mA^2$
\begin{cases}
(a,a)  & \text{if} \ \ w = (a,a,a), \\
(b,b)  & \text{if} \ \ w = (b,b,b), \\
(a,b)  & \text{if} \ \ w \in S^\HH_{1}(a,a,a), \\
(b,a)  & \text{if} \ \ w \in S^\HH_{1}(b,b,b). \\
\end{cases}$$

Case 2: $\max\{q,t\} \ge 3$.  Encode each element of $\mA$ using a $2t+1$-times repetition code, so that the codewords of $\mC$ are given by $c_{1},c_{2},\ldots,c_{q}$. The intermediate function $\mF_1$ simply forwards its received symbols.

We will next define the function $\mF_2$. Notice that there are $q\left(\lfloor t/2 \rfloor+1\right)$ shells $S^\HH_{i}(\pi_{2}(c_{j}))$ for $i\in \{ 0,1,\ldots, \lfloor t/2 \rfloor\}$ and $j\in \{1,\ldots,q\}$. Define
$$D= \mA^{t+1}\setminus \bigcup_{j\in \{1,\ldots,q\}}B^\HH_{\lfloor t/2 \rfloor}(\pi_{2}(c_{j})),$$

where $\pi_2$ is defined in Notation <ref>.
That is, $D$ is the set of words that do not belong to any ball of radius $\lfloor t/2 \rfloor$ centered at the projection of a codeword, so that the union of $D$ with the collection of the shells described above is all of $\mA^{t+1}$. Let $q':=q\left(\lfloor t/2 \rfloor+1\right)+1$. Since $\max\{q,t\} \ge 3$,
we have

\begin{equation*}
\end{equation*}

Therefore, we may define $\mF_2$ to be such that the sets $D$ and $S^\HH_{i}(\pi_{2}(c_{j}))$ for $i\in \{ 0,1,\ldots, \lfloor {t/2} \rfloor\}$ and $j\in \{1,\ldots, q\}$ each map to a single, distinct element of $\mA^{t}$.

Decoding at the terminal is accomplished as follows. Suppose that the terminal receives the pair $(x,y)\in \mA^{t} \times \mA^{t}$. First, the set $\mF_2^{-1}(y)$ is computed. If $\mF_2^{-1}(y) = D$, then the terminal decodes to the majority of the coordinates in $x$,

this is guaranteed to be the transmitted symbol based on how $D$ was defined. If $\mF_2^{-1}(y) =\pi_{2}(c_{j})$ for some $j$, the terminal decodes to the repeated symbol in $c_j$.
Finally, if $\mF_2^{-1}(y) = S^\HH_{i}(\pi_{2}(c_{j}))$ for $i\in \{1,\ldots, \lfloor t/2 \rfloor\}$, then it is not clear to the decoder if $i$ symbols were corrupted incoming to $V_{2}$ (and up to $t-i$ symbols to $V_{1}$), or if at least $(t+1)-i$ symbols were corrupted from $V_{2}$ (and up to $i-1$ to $V_{1}$). To differentiate the possibilities, the terminal looks to $x$. If at least $i$ of the symbols of $x$ are consistent with $c_{j}$, then we must be in the first scenario (recall $i\leq \lfloor t/2\rfloor$), so the terminal decodes to $c_{j}$. Otherwise, at most $i-1$ symbols were changed to $V_{1}$, and hence the majority of the symbols in $x$ will correspond to the transmitted codeword. In this case, the terminal decodes to the majority of symbols in $x$.

We propose an example that illustrates the scheme in the proof of Theorem <ref>.

We will show that $\CC_1(\mathfrak{C}_4,\mA,\mU_S,4) = 1$ when $|\mA|=2$; see Family <ref> for the notation. Let $\mA=\{a,b\}$. Following the proof of Theorem <ref>, we consider the repetition code that has the codewords $c_1=(a,a,a,a,a,a,a,a,a)$ and $c_2=(b,b,b,b,b,b,b,b,b)$. Observe that $D=\emptyset$. We illustrate the decoding of $c_1$ case-by-case. Since the alphabet size is equal to 2, the analysis of the $\binom{9}{4}$ possible actions of the adversary can be reduced to the following 5 basic cases (which also cover the favorable scenario where the adversary might not use their full power).

* $(a,a,a,a,a,a,a,a,a)$ is changed into $(a,a,a,a,a,b,b,b,b)$ by the adversary. Since we have $(a,b,b,b,b) \in S_1(\pi_2(c_2))$ and none of the coordinates of $(a,a,a,a)$ is $b$, the terminal decodes to $c_1$.

* $(a,a,a,a,a,a,a,a,a)$ is changed into $(a,a,a,b,a,a,b,b,b)$ by the adversary. Since we have $(a,a,b,b,b) \in S_2(\pi_2(c_2))$ and only one of the coordinates of $(a,a,a,b)$ is $b$, the terminal decodes to $c_1$.

* $(a,a,a,a,a,a,a,a,a)$ is changed into $(a,a,b,b,a,a,a,b,b)$ by the adversary. Since we have $(a,a,a,b,b) \in S_2(\pi_2(c_1))$ and at least 2 of the coordinates of $(a,a,b,b)$ is $a$, the terminal decodes to $c_1$.

* $(a,a,a,a,a,a,a,a,a)$ is changed into $(a,b,b,b,a,a,a,a,b)$ by the adversary. Since we have $(a,a,a,a,b) \in S_1(\pi_2(c_1))$ and least 1 of the coordinates of $(a,b,b,b)$ is $a$, the terminal decodes to $c_1$.

* $(a,a,a,a,a,a,a,a,a)$ is changed into $(b,b,b,b,a,a,a,a,a)$ by the adversary. Since we have $(a,a,a,a,a) = \pi_2(c_1)$, the terminal decodes to $c_1$.

This shows that, no matter what the action of the adversary is, one alphabet symbol can always be transmitted unambiguously.

The reason for excluding the case $t=1$ in the Definition of Family <ref> is the non-achievability of the Generalized Network Singleton Bound of Corollary <ref> given in Theorem <ref>. It should be noted that since that case is already studied, excluding it from Family <ref> makes sense to exhibit a family of networks which achieve Corollary <ref> as proven in Theorem <ref>.

We now turn to the networks of Family <ref>, the only family introduced in Subsection <ref> that we have not yet considered.

Let $\mathfrak{D}_t=(\mV,\mE,S,\{T\})$ be a member of
Family <ref>. Let $\mA$ be any network alphabet and let $\mU_S$ be the  set of edges of $\mathfrak{D}_t$ directly connected to $S$. We have
$$\CC_1(\mathfrak{D}_t,\mA,\mU_S,t)= 1.$$
In particular, the Generalized Network Singleton Bound of Corollary <ref> is met with equality.

Fix an alphabet symbol $* \in \mA$.
The source $S$ encodes each element of $\mA$ using a $4t$-times repetition code.
The vertices $V_1$ and $V_2$ implement a majority-vote decoder each, unless
two symbols occur an equal number of times over the incoming edges. In that case, the vertices output $*$. At the destination, if the incoming symbols match, then the terminal decodes to that symbol. Otherwise, it decodes to the alphabet symbol that is not equal to $*$. All symbols from $\mA$ can be sent with this scheme, including $*$, giving a capacity of at least $1$ and establishing the theorem.

Let $\mN = ([a_1,a_2],[b_1,b_2])$ a simple 2-level network with $n=2$ intermediate nodes. Let $\mA$ be a sufficiently large finite field.

Size of $I_3(\mN,t)$     Corollary <ref> is met     Corollary <ref> is not met
0      always      never (Corollary <ref>)

1     $\mathfrak{C}_2$ (Theorem <ref> )     $\mathfrak{A}_2$ (Theorem <ref>)

2     $\mathfrak{D}_2$ (Theorem <ref>)      $\mathfrak{E}_2$ (Theorem <ref> )

On the 1-shot capacity of simple 2-level networks with 2 intermediate nodes.

We present Table <ref> to illustrate that the size of $I_3(N,t)$ cannot be considered as a criterion for the achievability of the Generalized Network Singleton Bound of Corollary <ref>.

§ THE DOUBLE-CUT-SET BOUND AND APPLICATIONS

In this section we illustrate how the results on 2-level and 3-level networks derived throughout the paper can be combined with each other and applied to study an arbitrarily large and complex network $\mN$.

We already stressed in Section <ref>
that known cut-set bounds are not sharp in general when considering a restricted adversary (whereas they are sharp, under certain assumptions, when the adversary is not restricted; see Theorem <ref>).

The main idea behind the approach taken in this section is to consider pairs of edge-cuts, rather than a single one, and study the “information flow” between the two. This allows one to better capture the adversary's restrictions and to incorporate them into explicit upper bounds for the capacity of the underlying network $\mN$.
All of this leads to our Double-Cut-Set Bound below; see Theorem <ref>. In turn,
Theorem <ref> can be used to derive an upper bound for the capacity of $\mN$ in terms of the capacity of an induced 3-level network.
This brings the study of 3-level networks and their reduction to 2-level networks into the game; see Sections <ref> and <ref>.

A concrete application of the machinery developed in this section will be illustrated later in Example <ref>, where we will go back to our opening example of Section <ref>
and rigorously compute its capacity.
Another network is studied in Example <ref>.

We begin by introducing supplementary definitions and notation specific to this section.

Let $\mN=(\mV,\mE,\mS,\bfT)$ be a
network and let $\mE_1, \mE_2 \subseteq \mE$ be non-empty edge sets. We say that $\mE_1$ precedes $\mE_2$ if every path from $S$ to an edge of $\mE_2$
contains an edge of $\mE_1$.
In this situation, for $e \in \mE_2$ and $e' \in \mE_1$, we say that $e'$ is an immediate predecessor of $e$ in $\mE_1$ if $e' \preccurlyeq e$ and there is no $e'' \in \mE_1$ with $e' \preccurlyeq e'' \preccurlyeq e$ and $e' \neq e''$.

We illustrate the previous notions with an example.

Consider the network $\mN$ and the edge sets $\mE_1$ and $\mE_2$ in Figure <ref> below. Then $\mE_1$ precedes $\mE_2$.
We have $e_2 \preccurlyeq e_{10}$ and $e_9 \preccurlyeq e_{10}$. Moreover,
$e_9$ is an immediate predecessor of $e_{10}$ in $\mE_1$, while $e_2$ is not.

[blue, line width=1.5pt] (1,2) .. controls (2,1) .. (2,-0) ;

[blue, line width=1.5pt] (6.3,1) – (7.3,-1) ;

[red, line width=1.5pt] (9.5,2.5) .. controls (9.2,1) .. (10,0);

vertex/.style = shape=circle,draw,inner sep=0pt,minimum size=1.9em
nnode/.style = shape=circle,fill=myg,draw,inner sep=0pt,minimum
edge/.style = ->,> = stealth
dedge/.style = densely dotted,->,> = stealth
ddedge/.style = dashed,->,> = stealth

[vertex] (S1) $S$;

[shape=coordinate,right=of S1] (K) ;

[nnode,above=0.6of K] (V1) $V_1$;

[nnode,below=0.6of K] (V2) $V_2$;

[nnode,right=of K] (V3) $V_3$;

[nnode,right=of V3] (V4) $V_4$;

[vertex,right=3of V1 ] (T1) $T_1$;

[vertex,right=3of V2] (T2) $T_2$;

[ddedge,bend left=15] (S1)  to node[fill=white, inner sep=3pt]$e_1$ (V1);

[ddedge,bend right=15] (S1)  to node[fill=white, inner sep=3pt]$e_2$ (V1);

[ddedge,bend left=15] (S1) to  node[fill=white, inner sep=3pt]$e_3$ (V2);

[ddedge,bend right=15] (S1) to  node[fill=white, inner sep=3pt]$e_4$ (V2);

[ddedge,bend left=0] (V1) to  node[fill=white, inner sep=3pt]$e_6$ (V3);

[edge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{10}$ (T1);

[edge,bend left=0] (V4)  to node[fill=white, inner sep=3pt]$e_{11}$ (T2);

[edge,bend left=0] (V1)  to node[fill=white, inner sep=3pt]$e_{5}$ (T1);

[edge,bend left=0] (V2)  to node[fill=white, inner sep=3pt]$e_{8}$ (T2);

[ddedge,bend left=0] (V2) to  node[fill=white, inner sep=3pt]$e_7$ (V3);

[ddedge,bend left=0] (V3) to  node[fill=white, inner sep=3pt]$e_{9}$ (V4);

[text=blue] (E1) at (2.3,0.0) $\mE_1$;
[text=blue] (E11) at (7.6,-1) $\mE_1$;

[text=red] (E2) at (10.3,0.1) $\mE_2$;

Network $\mN$ for Examples <ref>, <ref>, and  <ref>.

The following notion of channel will be crucial in our approach. It was formally defined in [20] using a recursive procedure.

Let $\mN$, $\mE_1$ and $\mE_2$ be as in Definition <ref>. If $\mA$ is a network alphabet, $\mF$ is a network code for $(\mN,\mA)$, $\mU \subseteq \mE$, and $t \ge 0$, then we denote by

\begin{equation} \label{chtd}
\Omega[\mN,\mA,\mF,\mE_1 \to \mE_2,\mU \cap \mE_1,t]: \mA^{|\mE_1|} \dashrightarrow \mA^{|\mE_2|}
\end{equation}