= Solution
The intersection–union definition of a <submodular set function> is
$$
f(A)+f(B)\geq f(A\cap B)+f(A\cup B)\qquad(A,B\subseteq V).
$$
The <diminishing returns characterization of submodularity> says that its <marginal increments> decrease as the conditioning <set> grows:
$$
\Delta_x f(A):=f(A\cup\{x\})-f(A)\geq f(B\cup\{x\})-f(B)=:\Delta_x f(B)
\quad(A\subseteq B,\ x\notin B).
$$
To obtain <diminishing returns> from <submodularity>, apply the intersection–union inequality to $A\cup\{x\}$ and $B$. Their <intersection> is $A$ and their <union> is $B\cup\{x\}$, giving exactly the displayed comparison.
Conversely, assume <diminishing returns>, and enumerate $A\setminus B=\{x_1,\ldots,x_m\}$. Put $C_j=(A\cap B)\cup\{x_1,\ldots,x_j\}$ and $D_j=B\cup\{x_1,\ldots,x_j\}$. Since $C_{j-1}\subseteq D_{j-1}$ and $x_j\notin D_{j-1}$, summing the <marginal increment> comparisons gives the <telescoping sum>
$$
f(A)-f(A\cap B)=\sum_{j=1}^m\Delta_{x_j}f(C_{j-1})
\geq\sum_{j=1}^m\Delta_{x_j}f(D_{j-1})=f(A\cup B)-f(B).
$$
Rearrangement proves <submodularity>. When $A\setminus B$ is empty, both sums are zero, so the proof includes that case.
Back to article page
