{'fraction_non_alphanumeric': 0.05440586285116036, 'fraction_numerical': 0.010329785377770023, 'mean_word_length': 3.838905775075988, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Max-Flow Min-Cut Theorem with Applications in Small Worlds and Dual Radio Networks

Intrigued by the capacity of random networks, we start by proving a max-flow min-cut theorem that is applicable to any random graph obeying a suitably defined independence-in-cut property. We then show that this property is satisfied by relevant classes, including small world topologies, which are pervasive in both man-made and natural networks, and wireless networks of dual devices, which exploit multiple radio interfaces to enhance the connectivity of the network. In both cases, we are able to apply our theorem and derive max-flow min-cut bounds for network information flow.


I. INTRODUCTION
In the quest for the fundamental limits of communication networks, whose topology is typically described by graphs, the connection between the maximum information flow and the minimum cut of the network plays a singular and prominent role. In the case where the network has one or more independent sources of information but only one sink, it is known that the transmitted information behaves like water in pipes and the capacity can be obtained by classical network flow methods. Specifically, the capacity of this network will then follow from the well-known Ford-Fulkerson max-flow min-cut theorem [4], which asserts that the maximal amount of a flow (provided by the network) is equal to the capacity of a minimal cut, i.e. a nontrivial partition of the graph node set V into two parts such that the sum of the capacities of the edges connecting the two parts (the cut capacity) is minimum. Provided there is only a single sink, routing offers an optimal solution for transporting messages both when they are statistically independent [5] and when they are generated by correlated sources [6].
Max-flow min-cut arguments are useful also in the case of multicast networks, in which a single source broadcasts a number of messages to a set of sinks. This network capacity problem was solved in [7], where it is shown that applying coding operations at intermediate nodes (i.e. network coding) is necessary to achieve the max-flow/min-cut bound of a general network.
A converse proof for this problem, known as the network information flow problem, was provided by [8], whereas linear network codes were proposed and discussed in [9] and [10].
When the topology of the network is modeled by a randomly constructed graph, the natural goal is a probabilistic characterization of the minimum cut, which in the spirit of the network information flow literature [7] we shall sometimes call (admittedly with some abuse) the capacity of the random network. Although some capacity results of this flavor are available for particular instances, most notably for Erdös-Rényi graphs and random geometric graphs [11], the problem remains open for many relevant classes of random graphs. Motivated by this observation, we make the following contributions: • A Max-flow Min-cut Theorem: We introduce the independence-in-cut property, which is satisfied by large classes of random graphs, and derive inner and outer bounds for the minimum cut of any network that possesses this basic property. In contrast with [11], our approach is based on Hoeffding's inequality, which allows us to prove a theorem that is valid for a larger class of networks.
• Capacity Bounds for Small-World Networks: Based on the aforementioned max-flow mincut theorem, we are able to characterize the max-flow min-cut capacity of Small-World networks with shortcuts and with rewiring [12]. Our results show, somewhat surprisingly, that, up to a constant factor, a rewiring rule that preserves the independence-in-cut property does not affect the capacity of large small-world networks.
• Capacity Bounds for Dual Radio Networks: We are able to apply our theorem also to wireless network models in which some of the nodes are able to establish both short-range and long-range connections by means of dual radio interfaces. The capacity bounds thus obtained shed some light on the potential gains of this technology.
Our motivation to consider small-world networks, i.e. graphs with high clustering coefficients and small average path length, stems from their proven ability to capture fundamental properties of relevant phenomena and structures in sociology, biology, statistical physics and man-made networks. Beyond well-known examples such as Milgram's "six degrees of separation" [13] between any two people in the United States and the Hollywood graph with links between actors, small-world structures appear in such diverse networks as the U.S. electric power grid, the nervous system of the nematode worm Caenorhabditis elegans [14], food webs [15], telephone call graphs [16], and, most strikingly, the World Wide Web [17]. The term small-world graph itself was coined by Watts and Strogatz, who in their seminal paper [12] defined a class of models which interpolate between regular lattices and random Erdös-Rényi graphs by adding shortcuts or rewiring edges with a certain probability p (see Figures 1 and 2). The most striking feature of these models is that for increasing values of p the average shortest-path length diminishes sharply, whereas the clustering coefficient, defined as the expected value of the number of links between the neighbors of a node divided by the total number of links that could exist between them, remains practically constant during this transition. Since small-world graphs were first proposed as models for complex networks [12] and [18], most contributions have focused essentially on connectivity parameters such as the degree distribution, the clustering coefficient or the shortest path length between two nodes (see e.g. [19]). In spite of its arguable relevance -particularly where communication networks are concerned -the capacity of small-world networks has, to the best of our knowledge, not yet been studied in depth by the scientific community.
The second class of networks addressed in this paper is motivated by the fact that wireless interfaces become standard commodities and communication devices with multiple radio interfaces appear in various products. Thus, it is only natural to ask whether the aforementioned devices can lead to substantial performance gains in wireless communication networks. Promising examples include [20], where multiple radios are used to provide better performance and greater functionality for users, and [21], where it is shown that using radio hierarchies can reduce power consumption. This growing interest in wireless systems with multiple radios (for example, a Bluetooth interface and an IEEE 802.11 wi-fi card) motivates us to study the impact of dual radio devices on the capacity of wireless networks.
The rest of the paper is organized as follows. Section II states the problem and proves our main theorem. The results for small-world networks and dual radio networks then follow in Section III and Section IV, respectively. The paper concludes with Section V.

II. MAIN RESULT
Consider a graph G = (V, E), where V represents the set of nodes of the graph and E the set of edges connecting these nodes. In the rest of the paper, we assume that the edges in the graph represent communication links with unitary capacity.
Definition 1: Consider a graph G = (V, E) with |V | = n, a source s, a set T of terminals and a set R of relay nodes such that V = {s} ∪ R ∪ T . Let t be a terminal node, i.e. t ∈ T and let N be the number of relay nodes, i.e. N = |R| = n − 1 − |T |. A s-t-cut of size x in the graph G is a partition of the set of relay nodes R into two sets V k and V k such that |V k | = x The edges crossing the cut are given by The following definition describes the capacity of a cut as the sum of the capacities of the edges crossing the cut.
Definition 2: Consider a graph G = (V, E) and a s-t-cut of size x, with the corresponding sets V x and V x . The capacity of the cut, denoted by C x , is given by C where C ij denotes the capacity of the link between nodes i and j.
In the spirit of [4], we will refer to the value of the minimum s-t-cut as the s-t-capacity, denoted by C s;t . In the case of multiple terminals, denoting by T the set of terminals, the s-T -capacity, denoted by C s;T , is the minimum of the s-t-capacities over all terminals, i.e. C s;T = min t∈T C s;t .

Definition 3:
We say that a graph G has the independence-in-cut property if, for every cut i.e. all the variables in the sum are independent random variables.
Notice that, based on this definition, a graph with the independence-in-cut property is not necessarily a graph in which all the edges in the graph are independent random variables. An example of this is the case of Dual Radio Networks, discussed in detail in Section IV, where we shall show that, although there is dependency between some edges, we have that, given a cut, all the edges crossing it are independent random variables. This observation is valid for every cut.
In our approach, we make use of the independence-in-cut property to compute bounds on the probability that the capacity of a cut is close to its expected value. In fact, we shall view a cut as the sum of random variables. Given the independence-in-cut property, these variables are independent, which allows us to provide the desired bounds. If these variables are not independent, i.e. if the edges that cross a given cut are not independent random variables, the computation of these bounds becomes extremely difficult, since we are required to bound the sum of correlated random variables, irrespective of the correlation structure.
Capacity bounds for Erdös-Rényi graphs and random geometric graphs are the main focus of [11]. The bounds were derived specifically for each of the models, using Chernoff techniques.
This limits the analysis to the case of networks with independent and identically distributed edges. We shall use some of the techniques presented in [11], but instead of Chernoff bounds our approach exploits Hoeffding's inequality [22] to derive a more general result. The resulting theorem is true for any network that verifies the independence-in-cut property -edges are not required to be identically distributed.
Our main result is given by the following theorem. P(i ↔ j) and ǫ = d ln(n−2) λ 2 (n−2) with 1 < d < λ 2 (n−2) ln(n−2) . The s-T -capacity, C s;T , verifies To be able to prove Theorem 1, we first need to state and prove a few auxiliary results. We start by presenting a useful inequality.
Lemma 1 (Hoeffding's inequality, from [22]): For X 1 , X 2 , . . . , X m independent random variables with P(X i ∈ [a i , b i ]) = 1, ∀i ∈ {1, 2, . . . , m}, if we define S = X 1 + X 2 + · · · + X m , then First, we determine an upper bound on the probability that the capacity of a cut takes a value much smaller than its expected value.

Lemma 2:
Consider the single-source single-terminal case. For ǫ > 0 and N ≥ 2, we have (1) To compute the desired upper bound, we shall use the Hoeffding's inequality (Lemma 1). We where (a) follows from setting λ = min i,j:P(i↔j)>0 Moreover, from (1), (2) Now, because the graph G has the independence-in-cut property, C x can be viewed as the sum of N + x(N − x) independent Bernoulli distributed random variables. Therefore, we can apply Lemma 1 to (2), with m = N + x(N − x) and t = ǫλ, and we get For simplicity, we consider only the case of edges with unitary capacity.
Using the previous result, we obtain another useful inequality.
Proof: By Lemma 2, we have that P(A x ) ≤ e −2(N +x(N −x))ǫ 2 λ 2 . Notice that, for each x ∈ {0, ..., N}, there are N x cuts in which one of the partitions consists of x nodes and the source. Therefore, we can write We have that where we use the following arguments: (b) follows from substituting β by e −2ǫ 2 λ 2 N . Now, using Corollary 1, we can bound the global minimum cut of G s .
Applying Corollary 1 concludes the proof.
We are now ready to prove Theorem 1.
Proof of Theorem 1: Replacing ǫ in Corollary 2 by the expression d ln(n−2) Using once again the fact that (y Therefore, we have that where we used the following arguments: Using the bounds we have already constructed for the single-source single-terminal case, we can easily obtain bounds for the single-source multiple-terminals case. Since C s;T = min By Theorem 4, we have that P(C s; . Now, to compute the upper bound on P(C s;T ≥ (1 + ǫ)c min ), let C * be a cut such that E(C * ) = c min . Notice that, by definition, any cut is greater or equal to C s;T , in particular the (4) Define δ as the number of random variables that define the cut C * , i.e. δ is the number of edges that possibly cross the cut C * . Because λ = min i,j:P(i↔j)>0 and, from (4), (5) Because the graph G has the independence-in-cut property, C * can be viewed as the sum of δ independent and bounded random variables (more precisely, all the variables belong to the interval [0, 1]). Thus, noticing that E(C * ) = c min and applying Hoeffding's inequality (Lemma 1) with m = δ, S = C * and t = ǫλ, we have that .
Since x ∈ {0, . . . , N}, we have that the number of random variables that define a cut is at least N, and this is true for every cut. Thus, the same holds for the cut C * , which implies that δ ≥ N.
and thus, from (5), we get P(C s;

A. Classes of Small-World Networks
We start by giving rigorous definitions for the classes of small-world networks under consideration. All the models in this paper are consider to be unweighted graphs containing no self-loops or multiple edges. First, we require a precise notion of distance in a ring.
Definition 4: Consider a set of n nodes connected by edges that form a ring (see Fig. 3, left plot). The ring distance between two nodes is defined as the minimum number of hops from one node to the other. If we number the nodes in clockwise direction, starting from any node, then the ring distance between nodes i and j is given by d(i, j) = min{|i − j|, n − |i − j|}.
For simplicity, we refer to d(i, j) as the distance between i and j. Next, we define a kconnected ring lattice, which serves as basis for the small-world models used in this paper.

Definition 5:
A k-connected ring lattice (see Fig. 3) is a graph L = (V L , E L ) with nodes V L and edges E L , in which all nodes in V L are placed on a ring and are connected to all the nodes within distance k 2 . Notice that in a k-connected ring lattice, all the nodes have degree k. We are now ready to define the small-world models under consideration. To obtain a small-world network with rewiring, we proceed as follows. Let E R = E L be the initial set of edges. Each edge e ∈ E L is removed from the set E R with probability 1 − p, where p is called the probability of rewiring. Each edge e / ∈ E L is then added to the set E R with probability pk n−k−1 . After considering all possible edges connecting nodes in V L , the resulting small-world network is specified by the graph (V L , E R ).
This model is a variant of the small-world network with rewiring in [12] in which all the edges can be viewed as independent random variables, thus satisfying the independence-in-cut property. Finding max-flow min-cut bounds for the original construction is intractable due to the complex dependencies between randomly rewired edges. To ensure the key property of constant average number of edges per node, as in [12], our definition attributes weight pk n−k−1 to the edges that are not in the initial lattice. The expected number of edges per node in an instance of the model is thus given by (1 − p)k + pk n−k−1 (n − k − 1) = k.

B. Capacity Bounds for Small-World Networks
We shall now use Theorem 1 to prove capacity bounds for the aforementioned small-world models. We start with a useful lemma. Proof: We start by splitting G into two subgraphs: a k-connected ring lattice L with weights w 1 and a graph F with nodes V L and all remaining edges of weight w 2 . Clearly, the value of a cut in G is the sum of the values of the same cut in L and in F . Moreover, both in L and in F , the global minimum cut is a cut in which one of the partitions consists of one node (any other partition increases the number of outgoing edges). Since each node in L has k edges of weight w 1 and each node in F has the remaining n − 1 − k edges of weight w 2 , the result follows.
The following theorem gives upper and lower bounds on the capacity of Small-World Networks with Shortcuts.
Proof: Consider a Small-World Network with Shortcuts G SWS = (V, E). Let G w be a fully-connected weighted simple graph with set of nodes V . If we assign to each edge e = (i, j) in G w the weight w e = P{i and j are connected in the Small-World with Shortcuts}, we have that the expected value of a cut in G SWS is the value of the same cut in G w . Therefore, since c min = min C∈C E(C), we have that c min is the value of the minimum cut in the graph G w . Notice that the weights are assigned as follows: • The weight of the edges in the initial lattice of a Small-World Network with Shortcuts is one (because they are not removed); • The weight of the remaining edges is p, (i.e. the probability that an edge is added).
Therefore, G w is a graph in the conditions of Lemma 3, with w 1 = 1 and w 2 = p. Hence, the global minimum cut in G w is given by k + (n − 1 − k)p, which is equivalent to C min = k+(n−1−k)p. Moreover, the minimum edge weight is p, i.e. λ = p. Therefore, using Theorem 1, the bounds for the s-T -capacity of a Small-World Network with Shortcuts follow. To conclude the proof, it just remains to notice that lim n→∞ ǫ = lim n→∞ d ln(n − 2) p 2 (n − 2) = 0.
We are also able to obtain a similar result for the case of rewiring, as previously defined.
Theorem 3: The s-T -capacity of a Small-World Network with Rewiring with parameters n, p and k, denoted by C SWR s;T , satisfies the following inequalities: , ∀n ≥ n 0 for some a > 0 and is given by 1 − p and the weight of the remaining edges is given by pk n−k−1 . Notice that G w is a graph in the conditions of Lemma 3, with w 1 = 1 − p and w 2 = pk n−k−1 . Therefore, the global minimum cut in G w , is given by k(1 − p) + (n − 1 − k) pk n−k−1 = k, which, using similar arguments to those in the proof of Theorem 2, is equivalent to c min = k.
We have that there are only two different probability values: 1 − p and pk n−k−1 . Therefore, λ = min 1 − p, pk n − k − 1 . Notice also that all the edges are independent random variables (by the definition of the model). Hence, using Theorem 1, we can obtain the sought bounds. We Therefore, we have that, if p ≤ 1 − k n−1 , then λ = pk n−k−1 , else λ = 1 − p. In the latter, we have that ǫ = d ln(n−2) (1−p) 2 (n−2) and, therefore, lim Now, let us consider the case p ≥ 1 − k n−1 . We have that λ = pk n−k−1 and, therefore, It is clear that, if the value of k does not depend on n, the value of ǫ will diverge. So we need to analyze the behavior of ǫ when k is a function of n.
Recall that k is the number of initial neighbors in the k-connected ring lattice. Thus, k/n represents the fraction of nodes in the network to which each node is initially connected. Let us consider the case of k n ≥ 1 ln a (n) , ∀n ≥ n 0 for some a > 0 and n 0 ∈ N (notice this includes the case of k n constant). In the following, all inequalities are considered to be for n ≥ n 0 . We have that where (a) follows from the fact that k ≥ n ln b (n) . We have that lim n→∞ d ln b+1 (n)/p 2 n = 0. Thus, using inequality (6), we have that lim n→∞ ǫ = 0. Now let us consider the case of k n ≤ b n , ∀n ≥ n 1 , for some b > 0 and n 1 ∈ N (notice that this is equivalent to k ≤ b and, therefore, includes the case where k does not depend on n). In the following, all inequalities are considered to be for n ≥ n 1 . We have that where (a) follows from the fact that k ≤ b.

IV. DUAL RADIO NETWORKS
This section is devoted to the probabilistic characterization of the max-flow min-cut capacity of dual radio networks, which we model as follows. Let E L be the set of edges created in this step. Finally, the set of edges of a DRN is defined by The main result of this section is given by the following theorem.

Remark 3:
The bounds for the capacity of Dual Radio Networks are centered around (n−2)µ, with µ = πr 2 S +πp 2 (r 2 L −r 2 S ), where p represents the fraction of nodes with two different wireless interfaces. Thus, since lim n→∞ ǫ = 0, we can say that in the limit of large networks the capacity of Dual Radio Networks grows quadratically with the number of nodes with two wireless interfaces.
Before presenting the proof of Theorem 4, we need to state and prove some auxiliary results.

Lemma 4:
The probability of two nodes being connected in an instance of a Dual Radio Network is given by µ = πr 2 S + πp 2 (r 2 L − r 2 S ). Proof: First, we calculate the probability that a node Y is connected to node X, given the position of X. This probability is given by Using the notation P (A|X) = P X (A) and d(X, Y) = D, we have the following: where (a) follows from the fact that for any two events A and B, P(A ∪ B) = P(A) + P(B) −

P(A ∩ B), and (b) is justified by noting that
The events {D ≤ r L } and {X ∈ V L } are independent, and the same is true for the events {D ≤ r L } and {Y ∈ V L }. Because the set of nodes V L is formed by nodes selected at random and in an independent fashion, we have that the events {X ∈ V L } and {Y ∈ V L } are independent. Therefore, Using analogous arguments, we have that Noticing that the events {X ∈ V L } and {Y ∈ V L } are independent of the position of X, we Because the nodes are placed on a torus, we have that P X (D ≤ ρ) = πρ 2 , with ρ ≤ 1/ √ π.
Noticing that P(X ∈ V L ) = P(Y ∈ V L ) = p, we have that: Let pos(X) be the random variable that represents the position of node X. The final result The next result shows that the Dual Radio Network model possesses the independence-in-cut property. It is a non-trivial example of a large class of networks whose edges are not independent random variables. Consider three nodes, X 1 , X 2 and X 3 . Suppose that the position of X 1 is known and that this node is connected both to X 2 and X 3 . It follows that the positions of X 2 and X 3 are constrained by the position of X 1 , and thus P( However, as the next result shows, the edges across a given cut in a Dual Radio Network are independent random variables.
Lemma 5: A Dual Radio Network exhibits the independence-in-cut property.
Proof: We will start by showing that the outgoing edges of a node X are independent random variables, when conditioned on the position of X. This means that {X ↔ Y 1 }, {X ↔ Y 2 }, . . . , {X ↔ Y n−1 } are mutually independent conditioned on the fact that the position of node X is fixed i.e. X = x). Without loss of generality, we may write: where we exploited the fact that the position of X is fixed. Now, notice that none of the events {Y 2 ↔ x}, . . . , {Y n−1 ↔ x} affects the event {Y 1 ↔ x}, because we do not have information about the existence of connection between Y 1 and any of the Y i . Therefore, where we used the following arguments: • (a) follows from the fact that outgoing edges of a node are independent, as we have already demonstrated; • (b) follows from the property that two nodes are connected with probability is µ, thus • (c) follows from the fact that µ zα (1 − µ) 1−zα does not depend on the position of X.
This reasoning shows that the outgoing edges of any given node are independent. Using similar arguments, we can also prove that the incoming edges of any given node are also independent.
Recall that a cut C k is of the form C k = i∈V k With independent outgoing edges and incoming edges for any given node and knowing that edges with no node in common are also independent, we have that all the edges that cross the cut are independent random variables, which clearly satisfies the definition of the independence-in-cut property.
We are now ready to prove Theorem 4.
Proof of Theorem 4: We start by calculating the minimum expected value of a cut in an instance of a Dual Radio Network. Consider a s-t-cut of size k, C k = Therefore, we have that c min = min   (9), it is crucial that the probability of two nodes being connected is independent of the position of the nodes, which means that all nodes have to have the same coverage area. The fact that, in the wrap-around case, Dual Radio Networks have the independence-in-cut property was crucial for obtaining the bounds for the capacity of these networks. In the following, we will provide bounds on the capacity of Dual Radio Networks based on a non-wrap-around square by analyzing networks that are similar to Dual Radio Networks, but where all the nodes obtain the same coverage area, by increasing (or decreasing) their radio range.
Proof: The main idea of the proof is to consider the situation of nodes adjusting their transmitting range so that all the nodes have the same coverage area 2 . In a Dual Radio Network based on the unit square with an Euclidean metric, nodes closer to the border have lower coverage area than nodes in the center of the square. More precisely, we have that the corner nodes have the minimum coverage area from all the nodes. Using arguments similar to those used to prove Lemma 4, namely Equality (8), we have that P(X ↔ Y|X is a corner node) = π 4 r 2 S + π 4 p 2 (r 2 L − r 2 S ).
Consider the situation where all nodes adjust their communication range such that ∀X, P(X ↔ Y|X = x) = π 4 r 2 S + π 4 p 2 (r 2 L − r 2 S ) = µ ′ and let C ′ s;T be the s-T -capacity of this network. This means that all nodes (except the corner ones) have to reduce their transmitting power (for both wireless communication technologies). In this case, we have that the probability of two nodes being connected does not depend on the position, thus the proof of Lemma 5 holds and, therefore, this network has the independence-in-cut property. Moreover, if C k is a cut of size k, we have that E(C k ) = (N +x(N −x))µ ′ , since E(C ij ) = P(i ↔ j) = µ ′ , i, j. Therefore, c min = (n−2)µ ′ and, by Theorem 1, P(C ′ s;T ≤ (1 − ǫ ′ )(n − 2)µ ′ ) = O α n 2d , with ǫ ′ = d ln(n−2) µ ′2 (n−2) . Notice that, with µ = πr 2 S + πp 2 (r 2 L − r 2 S ) and ǫ = d ln(n−2) µ 2 (n−2) , we have that µ ′ = µ 4 and, thus, ǫ ′ = 4ǫ. Thus, we have that P C ′ s;T ≤ (1 − 4ǫ)(n − 2) In a Dual Radio Network, it is clear that many nodes will have an higher coverage area, which can only lead to an increase of capacity. Thus, we have that C ′ s;T ≤ C DRN * s;T . Therefore, if C DRN * Thus, from (10), we have that P C DRN * s;T ≤ (1 − 4ǫ)(n − 2) µ 4 = O α n 2d . Now, to compute the upper bound on P C DRN * s;T ≥ (1 + ǫ)(n − 2)µ , we will use the same approach as before, but now with some increasing their transmitting power. Consider the situation where all the nodes adjust their communication range such that ∀X, P(X ↔ Y|X = x) = π 4 r 2 S + π 4 p 2 (r 2 L − r 2 S ) = µ and let C ′′ s;T be the s-T -capacity of this network. This means that the nodes closer to the border of the unit square will increase their transmitting power (for both technologies). As before, in this situation we have that the network has the independence-in-cut property and, with c min = (n − 2)µ, we can use Theorem 1 and we get with ǫ = d ln(n−2) µ 2 (n−2) . In the real situation, many nodes will have a lower transmitting power, which can only lead to a decrease in the capacity. Therefore, C ′′ s;T ≥ C DRN * s;T . Therefore, if C DRN * s;T ≥ (1+ǫ)(n−2)µ, then C ′′ s;T ≥ (1+ǫ)(n−2)µ, which implies that P C DRN * s;T ≥ (1 + ǫ)(n − 2)µ ≤ P C ′′ s;T ≥ (1 + ǫ)(n − 2)µ . Thus, by (11), we have that P C DRN * s;T To conclude the proof of the theorem, just notice that lim n→∞ ǫ = lim n→∞ d ln(n − 2) µ 2 (n − 2) = 0.

V. CONCLUSIONS
After defining the property of independence-in-cut for the edges of random graphs, we proved a general theorem that provides upper and lower bounds for the max-flow min-cut capacity of any graph satisfying this property. This theorem is not only of some interest by itself, but also proves to be a valuable tool in determining capacity bounds for small-world graphs and dual radio models, whose importance stems from their arguably compelling applications. Perhaps the most striking conclusions to be drawn from our results are that (a) rewiring satisfying the independence-in-cut property does not change the capacity of a small-world network up to a constant factor and that (b) the capacity of dual radio networks grows quadratically with the fraction of dual radio devices, thus indicating that a small percentage of such devices is sufficient to improve significantly the maximum information flow in the network. p=0 p=0.1 p=0.9