<p>Higher-order discrete derivatives of set functions are explored in <a href="http://rutcor.rutgers.edu/pub/rrr/reports2003/44_2003.ps" rel="nofollow">Submodularity, supermodularity and higher-order monotonicities of pseudo-boolean functions</a>. 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-02T16:56:22.113Z
2012-04-05T17:58:12.663Z
2012-04-05T17:58:12.663Z
Yuval Filmus
<p>There is a <a href="http://arxiv.org/pdf/1107.5559.pdf">complete characterization of coverage functions</a> 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.</p>

<p>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$. </p>

<p>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$.</p>

<p>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)</p>

<p>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. </p>

CC BY-SA 3.0
2012-04-02T15:08:10.027Z
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
CC BY-SA 3.0
2012-04-02T04:32:13.567Z
2012-04-02T05:12:59.040Z
2012-04-02T05:12:59.040Z
Ashwinkumar B V
<p>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). $$</p>

<p>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.</p>

<blockquote>
  <p>Is this property known?</p>
</blockquote>

<h3>Background</h3>

<p>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.</p>

<p>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.</p>

<ds.algorithms><approximation-algorithms><submodularity>
Strengthenings of submodularity
Yuval Filmus
# Strengthenings of submodularity

(Asked by: username_0 on 2012-04-02)

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.

**Tags:** ds.algorithms, approximation-algorithms, submodularity


---

## 2 answers

### Answer by username_1 on 2012-04-02. Score: 13 | Accepted answer

There is a [complete characterization of coverage functions](http://arxiv.org/pdf/1107.5559.pdf) 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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_0 on 2012-04-02. Score: 7

Higher-order discrete derivatives of set functions are explored in [Submodularity, supermodularity and higher-order monotonicities of pseudo-boolean functions](http://rutcor.rutgers.edu/pub/rrr/reports2003/44_2003.ps). 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.


---

