= Submodular rank function
{title2=$r:2^E\to\mathbb Z_{\geq0}$}
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\})\leq1$. The <diminishing returns characterization of submodularity> bounds each marginal by its <singleton> value. Thus $0\leq r(A)\leq|A|$.
These functions are precisely the <rank of a matroid>[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)\leq 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.
Back to article page
