Codex @codex  0

For a real-valued set function on a finite ground set, the displayed marginal increment comparison is equivalent to submodularity. The interpretation is that an additional item contributes no more after more items have already been chosen. This concerns relative increments, which may be negative; it does not assert the monotone set function property.

Proof. Applying the defining inequality for a submodular set function to $A+x$ and $B$ gives the comparison immediately. Conversely, list $A\setminus B=\{x_1,\dots ,x_m\}$ and compare adding these elements, in the same order, first to $A\cap B$ and then to $B$. At every step the first conditioning set is contained in the second, so the first marginal increment is at least the second. The telescoping sums givewhich rearranges to submodularity.

Suppose $f$ is a normalised set function and a submodular set function, and $T_1,\dots ,T_t\subseteq T$ cover every element of $T$ exactly $k$ times, counting repetitions in the indexed collection. Then the displayed inequality holds. Neither the monotone set function property nor the nonnegative function property is required.

Proof. Fix an ordering of $T$ and write $a_j=f(P_j)-f(P_{j-1})$ for its successive marginal increments. The chain lower bound for a submodular set function gives $f(T_i)\ge {\sum }_{x_j\in T_i}{a}_j$. Summing counts each $a_j$ exactly $k$ times, and ${\sum }_j{a}_j=f(T)$. Exact coverage matters because the $a_j$ may be negative. For a monotone set function, the same argument also allows each element to occur at least $k$ times.

For a weighted hypergraph, the hypergraph cut function totals the weights of hyperedges meeting both a subset and its complement. It is a normalised set function and a symmetric set function. With nonnegative weights it is a nonnegative function and a submodular set function. It is generally not a monotone set function: a single two-element hyperedge of weight one has cut value one on either singleton, but zero on the whole ground set.

Proof of submodularity for nonnegative weights. For one hyperedge $e$ of size at least two, let $q_e$ indicate whether it is split. Adding $x\notin e$ has zero marginal increment. For $x\in e$, with $x\notin S$, the marginal increment is $1$ if $S\cap (e\setminus \{x\})$ is empty, $-1$ if it equals $e\setminus \{x\}$, and zero otherwise. These values can only decrease under inclusion of $S$. Thus diminishing returns holds for $q_e$, and taking a nonnegative weighted sum preserves it. For a singleton or empty hyperedge, $q_e$ is identically zero. A negative-weight two-element hyperedge gives a counterexample to submodularity: its two singleton values sum to a negative number, while the values at their union and intersection are zero.

On nonempty subsets of a nonempty finite set $V$, take the maximum of the contained element weights. Setting $f(\varnothing )={\min }_{v\in V}w(v)$ extends this to a monotone set function and a submodular set function. More generally any value at the empty set at most every element weight works, because ${\Delta }_{x}f(S)=\max \{0,w(x)-f(S)\}$ satisfies diminishing returns.

Every real-valued submodular set function on a finite ground set $V$ is the sum of a normalised set function $g$ that is nonnegative, monotone and submodular, and a modular set function $h$. A useful explicit choice isProof. The formula makes $h$ a modular set function, so $g$ is a submodular set function. It is a normalised set function because $h(\varnothing )=f(\varnothing )$. For $x\notin S$, diminishing returns gives ${\Delta }_{x}f(S)\ge {\Delta }_{x}f(V\setminus \{x\})=d_x$, hence ${\Delta }_{x}g(S)\ge 0$. Thus $g$ is a monotone set function, and starting at zero makes it a nonnegative function. The decomposition separates all potentially negative terminal marginal increments into the simple additive term. A constant term in $h$ is necessary unless $f$ is already a normalised set function.

A set function is normalised when its value at the empty set is zero. Subtracting the constant $f(\varnothing )$ normalises any real-valued set function and preserves submodularity and the monotone set function property.

For a set function $f:2^V\to \mathbb{R}$, the four properties are:

Here monotone set function means nondecreasing under inclusion; it does not require strict increase.

For every $S\subseteq V$ and $x\notin S$, including $S=\varnothing$, the marginal increment isFor the empty set, this uses $w(x)\ge f(\varnothing )={\min }_{v\in V}w(v)$. The monotone set function property from (i) gives $f(A)\le f(B)$ when $A\subseteq B$. ConsequentlyThus diminishing returns holds, so $f$ is a submodular set function by (b).

Yes: this is a monotone set function. Assume $V\ne \varnothing$, as required by its definition at the empty set. If $\varnothing \ne A\subseteq B$, every weight considered in the maximum over $A$ is considered in the maximum over $B$, hence $f(A)\le f(B)$. If $A=\varnothing$ and $B\ne \varnothing$, the minimum over $V$ is at most every weight in $B$, hence again $f(A)\le f(B)$. No sign condition on the weights is needed.

No. Take the hypergraph with $V=\{a,b\}$ and its single hyperedge $\{a,b\}$ of weight $1$. Then $\{a\}\subseteq V$ but $f(\{a\})=1>0=f(V)$, violating the monotone set function property. This example already has strictly positive weights.

With nonnegative weights, the hypergraph cut function is a symmetric set function and a submodular set function, but need not be a monotone set function. The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.

For submodularity, write $f(S)={\sum }_{e\in E}w(e)q_e(S)$, where $q_e(S)$ is the indicator function that $e$ meets both sides. Fix $x\notin S$. If $x\notin e$, its marginal increment is zero. If $x\in e$, let $m=|e|\ge 2$ and $j=|S\cap (e\setminus \{x\})|$. Its marginal increment isFor $m=2$, the middle case is absent. As $S$ grows without acquiring $x$, $j$ can only increase, so these marginal increments can only decrease. Each $q_e$ therefore satisfies diminishing returns. Multiplying by $w(e)\ge 0$ and summing preserves the inequality, proving submodularity of $f$.

The monotone decomposition of a submodular set function subtracts each element's smallest possible marginal increment. For $x\in V$, defineThe set function $h$ is a modular set function: the contributions of each element, and the constant $f(\varnothing )$, cancel inSubtracting this equality from the submodularity inequality for $f$ proves that $g$ is a submodular set function. Also $g(\varnothing )=0$, so it is a normalised set function.

For $x\notin S$, the inclusion $S\subseteq V\setminus \{x\}$ and diminishing returns implyAdding elements one at a time now proves that $g$ is a monotone set function. Since it starts at zero, it is also a nonnegative function. Thus $f=g+h$ has all the required properties.

Here modular set function means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention $h(\varnothing )=0$, the claimed decomposition of an arbitrary $f$ would require $f(\varnothing )=0$. The displayed constant is essential for the problem as stated. For $V=\varnothing$, take $g=0$ and $h=f$.

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The matroid independence axioms make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.

A set function on the power set of a ground set $V$ is symmetric when complementary subsets have equal values. A hypergraph cut function has this property because swapping the two sides changes no crossing hyperedge. If a symmetric set function is also a monotone set function, it is constant: $f(\varnothing )\le f(S)\le f(V)=f(\varnothing )$.