# Strengthenings of submodularity

A set-function $f$ is monotone submodular if for all $A,B$, $$f(A) + f(B) \geq f(A \cup B) + f(A \cap B).$$

A stronger property is $$\begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\f(A\cup B) + f(B\cup C) + f(A\cup C) + f(A \cap B \cap C). \end{multline*}$$ Taking $C = A\cup B$, this property implies monotone submodularity.

Is this property known?

### Background

This property came up while trying to characterize coverage functions. Given some weighted universe $U$ (all weights are non-negative) and a family $X$ of subsets of $U$, the coverage function $f(S)$ is defined for $S \subseteq X$ as the total weight of elements covered by sets in $S$. The function $f$ is always monotone and submodular. The converse isn't true.

The property in question implies that $f$ is a coverage function in the case $|X| = 3$. Similar, more complicated properties work for larger $X$. All these properties are satisfied by coverage functions, so this is a complete characterization.

There is a complete characterization of coverage functions in terms of such equations. For |X|>3 there are more equations than the ones pointed. Each of these equations can be thought as a constraint on discrete $k^{th}$ derivative.

Monotone increase function if and only if first order discrete derivative is +ve. i.e. $f(B)-f(A)\ge 0$ when $A\subseteq B$.

Submodularity if and only if second order discrete derivative is -ve. i.e. $(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$.

Similarly if you have conditions on the next $n$ derivatives you get coverage functions. (I think the signs need to be +ve for even order derivative and -ve for odd order derivative)

Something similar was already known in probability. A coverage function can also be thought as a probability measure (upto a scaling constant). The only reference I was able to dig up was page 439 from Feller's book on probability.

• Thanks for the reference! The condition of the discrete derivative is slightly different, as you only consider adding one element at a time. Monotonicity is rather $f(A \cup \{x\}) \geq f(A)$ and submodularity is $f(A \cup \{x\}) + f(A \cup \{y\}) \geq f(A \cup \{x,y\}) + f(A)$. The latter is in fact equivalent to the usual condition only when none of $A,B$ is a subset of the other. So my third-order property (which requires the previous ones in full generality) doesn't appear in the paper. – Yuval Filmus Apr 2 '12 at 15:08

Higher-order discrete derivatives of set functions are explored in Submodularity, supermodularity and higher-order monotonicities of pseudo-boolean functions. According to them, the strict third-order discrete derivative condition is $$\begin{multline*} f(A \cap B) + f(A \cap C) + f(B \cap C) + f((A \cap B) \cup (A \cap C) \cup (B \cap C)) \geq \\ f(A \cap (B \cup C)) + f(B \cap (A \cup C)) + f(C \cap (A \cup B)) + f(A \cap B \cap C). \end{multline*}$$ The "aggregate" condition is mentioned in the paper "A characterization of a cone of pseudo-boolean functions via supermodularity-type inequalities" by Cramma, Hammer and Holtzman (inequality (4)), which is part of the rare collection "Quantitative Methoden in den Wirtschaftswissenschaften". This condition should be the same as mine.

Edit: The actual condition that Cramma, Hammer and Holtzman give is $$\begin{multline*} f(A) + f(B) + f(C) + f(A \cap B \cap C) \geq \\ f(A \cup B \cup C) + f(A \cap B) + f(A \cap C) + f(B \cap C). \end{multline*}$$ If you put $C = \varnothing$, you get submodularity.