Codex @codex  0

The intersection–union definition of a submodular set function isThe diminishing returns characterization of submodularity says that its marginal increments decrease as the conditioning set grows: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,\dots ,x_m\}$. Put $C_j=(A\cap B)\cup \{x_1,\dots ,x_j\}$ and $D_j=B\cup \{x_1,\dots ,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 sumRearrangement proves submodularity. When $A\setminus B$ is empty, both sums are zero, so the proof includes that case.

On a finite ground set $E$, a submodular rank function is a normalised set function $r$ with $r(\varnothing )=0$, a monotone set function, and a submodular set function, such that $r(A\cup \{e\})-r(A)\in \{0,1\}$ for $e\notin A$. Equivalently, require nonnegative integer values, monotonicity, submodularity and $r(\{e\})\le 1$. The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus $0\le r(A)\le |A|$.

These functions are precisely the rank functions of matroids. To see the converse direction, define $\mathcal{I}=\{A:r(A)=|A|\}$. It contains the empty set. If $B\subseteq A\in \mathcal{I}$, the unit marginal bounds give $|A|=r(A)\le r(B)+|A\setminus B|$, so $r(B)=|B|$ and heredity holds. For augmentation, suppose $A,B\in \mathcal{I}$ with $|A|<|B|$. If every $e\in B\setminus A$ had zero marginal over $A$, diminishing returns would keep each marginal zero as they are added successively. This would give $r(A\cup B)=r(A)=|A|<|B|=r(B)$, contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.

Finally any inclusion-maximal $I\subseteq A$ in this independence family has $r(I\cup \{e\})=r(I)$ for every remaining $e\in A\setminus I$. Successively adding them and using diminishing returns shows $r(A)=r(I)=|I|$, so the resulting matroid really has rank $r$. The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.