# Submodular functions

A few definitions:

A Submodular function $f:2^E \rightarrow R$ is a function that satisfies the following two equivalent definitions:

• for every $S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T)$
• for every $S,T\subseteq E$ with $S\subseteq T$ and for every $x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T)$

A monotone submodular function is a submodular functions such that for every $S,T \subseteq E$ with $S\subseteq T : f(T)\geq f(S)$ . We also define $f(\emptyset) = 0$.

Show that $\sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S)$ where $e_i\in S$ for all i, where f is a monotone submodular function.

-

The formula $\sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S)$ is certainly false.If $f$ is a (monotone) submodular function, then $f+c$ with $c \in \mathbb R$ is also a (monotone) submodular function. So you would have $\sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) + c$ for arbitrary $c \in \mathbb R$, which is obviously not true.

However, it's easy to prove $\sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) - f(\emptyset)$. Simply note that $f(S)-f(S-\{e_i\}) \leq f(S-U)-f(S-U-\{e_i\})$ for $e_i\notin U$. So the sum is bounded by a telescope sum: $$\sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq \\ (f(S)-f(S-\{e_1\}))+(f(S-\{e_1\}))-f(S-\{e_1, e_2\})+\ldots+(f(S-\cup_{i=1}^{n-1} \{e_i\})-f(S-\cup_{i=1}^n \{e_i\}))\\ =f(S)-f(S-\cup_{i=1}^n \{e_i\}) \leq f(S) - f(\emptyset)$$ Only the last step of replacing $f(S-\cup_{i=1}^n \{e_i\})$ by $f(\emptyset)$ requires monotony.

-
Sorry, forgot to mention that f(empty_set) = 0. You're right of course. –  Shmoopy Dec 10 '12 at 9:24

Fix a set $E$ with monotone submodular function $f$. Note that $\tilde{f}(I) := f(I) + \lambda$ also will be a monotone submodular function, for any $\lambda \in \mathbb{R}$, since loosely speaking the same number of $\tilde{f}$'s appear on each side of all inequalities.

With that for $n = 1$ our desired inequality just reads $f(S - e_1) \geqslant 0$, but by our analysis this can be taken to be arbitrary, in particular negative.

So perhaps you want some further hypothesis?

-