\( \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\FF}{\mathbb{F}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \)

Blocking sets and the min-max principle

Blocking sets have one property useful when solving optimization problems. Suppose we have a finite set $E$ of elements, and real-valued function $f:E\to R$; we can treat $f(x)$ as the "weight" of element $x\in E$. Suppose further that we have some family $\A$ of subsets of $E$. The weight of a member $A\in \A$ is the maximum weight of its element, that is, $f(A)=\max\{f(x)\colon x\in A\}$. Given a family $\A$, our goal is to find the smallest weight of its member. This is a minimization problem. Using blocking sets we can turn it into a maximization problems as follows.
Theorem [Edmonds-Fulkerson 1979]: For every antichain $\A$, \[ \min_{A\in \A}\ \max_{x\in A}f(x)=\max_{B\in b(\A)}\ \min_{x\in B}f(x)\,. \]

Related literature:


Return to the home page of the 2nd edition