# 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