= Solution
On a finite <ground set> $E$, a \b[<submodular rank function>] is a <set function> $r:2^E\to\mathbb R$ with the following properties:
$$
\begin{aligned}
&r(\varnothing)=0,\\
&A\subseteq B\Longrightarrow r(A)\leq r(B),\\
&r(A)+r(B)\geq r(A\cup B)+r(A\cap B),\\
&r(A\cup\{e\})-r(A)\in\{0,1\}\quad(e\notin A).
\end{aligned}
$$
These are normalization, monotonicity, <submodularity>, and unit <integer> increments. In particular its values are nonnegative <integers> with $r(A)\leq|A|$. Equivalently, one can require an integer-valued normalized monotone submodular function with $r(\{e\})\leq1$: diminishing returns then bounds every marginal increment by one. A general real-valued submodular function need not be a <matroid> rank.
Back to article page
