The theorem states the following:

In any network $(G, s, t, c)$ $(G$ is a directed graph, $s$ is the source, $t$ is the sink, $c$ are the capacities $)$ we have $\sup\{ v(f) : f$ is a feasible flow $\} = \min \{ c(S, T) : (S, T)$ is a cut }$

Moreover, the supremum is attained

The proof in the lecture notes is attached

enter image description here

The problem starts at "Repeating this for each edge, we find a subsequence of flows with $v(f_i) \rightarrow M$ such that $f_i(x,y)$ converges for each... "

If we choose $1$ edge, we can find this convergent subsequence, for example by finding a monotone sequence and using standard analysis results. But when we choose the second edge, how do we guarantee that the sequence of flows converges for both of the edges?

Thanks in advance


The trick is a standard analysis one:

Let $f_n(x_1y_1)$ and $f_n(x_2y_2)$ be two sequences. We can then find a subsequence $f_{k_n}(x_1y_1)$ which is convergent. Next, instead of looking at $f_n(x_2y_2)$, look at the subsequence $f_{k_n}(x_2y_2)$. This is bounded, thus it has a converegent subsequence $f_{l_n}(x_2y_2)$.

Now, since $f_{l_n}(x_1y_1)$ is a subsequence of $f_{k_n}(x_1y_1)$ it is convergent.

Note This is actually an argument about compatcness. In $\mathbb R^d$ a set is compact if it is closed and bounded. Thus by boundedness, the sequence $$(f_n(x_1y_1), f_n(x_2y_2),..., f_n(x_dy_d)$$ has a convergent subsequence in some closed ball in $\mathbb R^d$.

  • $\begingroup$ Oh, i see, thanks a lot! $\endgroup$ – asdf Dec 26 '17 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.