= Chain lower bound for a submodular set function
{title2=$f(U)\geq\sum_{x_j\in U}\bigl(f(P_j)-f(P_{j-1})\bigr)$}
Let $f$ be a <normalised set function> that is a <submodular set function>, and order a finite <subset> $T=\{x_1,\ldots,x_n\}$. Set $P_j=\{x_1,\ldots,x_j\}$ and $P_0=\varnothing$. Then the displayed inequality holds for every $U\subseteq T$, with equality for $U=T$. The right side is a <modular set function> lying below $f$ on the <power set> of $T$ and touching it at the top.
\b[Proof.] Reveal the elements of $U$ in the chosen order. Immediately before adding $x_j\in U$, the conditioning <set> is $U\cap P_{j-1}\subseteq P_{j-1}$. By <diminishing returns>, its <marginal increment> is at least $f(P_j)-f(P_{j-1})$. Sum and use $f(\varnothing)=0$. The same <telescoping sum> gives equality at $T$. The individual increments need not be nonnegative.
Back to article page
