# How to read 'max min' and 'min max'?

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this graph has capacity $c_e$. Pick two arbitrary vertices from $G$ and label them $s$ and $t$ respectively.

Now, we'll let $P*$ be the set of $s-t$ paths in the graph, and let $C*$ be the set of $s-t$ cuts -- meaning, $C*$ refers to the subset of edges in $G$ that constitute all possible $s-t$ cuts.

Demonstrate that the following equality is true:

$\max_{P\in P*} \min_{e \in P}c_e = \min_{C \in C*}\max_{e \in C}c_e$

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

• At heart, this is not a question about network flows but about understanding mathematical notation. One may argue it should therefore be migrated to Mathematics, but I think the connection to CS is apparent. – Raphael Mar 30 '16 at 20:56

I'm frankly not even sure whether the above equation is meant to involve a multiplication.

No, not at all. We have nesting here:

$\max_{X \in \mathcal{X}}\ ( \min_{x \in X} x)$

is the largest minimum of all $X$. Similarly -- but the other way around -- for $\min \max$. This is very similar to nested quantifiers $\forall$ and $\exists$.

Let, for instance, $\mathcal{X} = \{ \{1,2\}, \{3,4\} \}$. Then, the following equalities hold:

1. $\min_{X \in \mathcal{X}} \min_{x \in X} x = 1$.
2. $\min_{X \in \mathcal{X}} \max_{x \in X} x = 2$.
3. $\max_{X \in \mathcal{X}} \min_{x \in X} x = 3$.
4. $\max_{X \in \mathcal{X}} \max_{x \in X} x = 4$.

Play around with the example by adding more sets to $\mathcal{X}$, more values to the individual sets, and quantify over $f(x)$ instead of just $x$ for different $f$, in order to get a feeling for this.

If you are inclined to algorithmic thinking, do a quick implementation; you'll see how these operators nest more clearly with types, and examples are faster to compute. For instance, the second example would be

Xs.map { X => X.max }.min