# Submodular monotone 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, for any $S,T\subseteq E : f(T)\leq f(S) + \sum_{e_i\in T-S}(f(S\cup\{e_i\})-f(S))$ where $f$ is a submodular monotone function . I've tried induction but got no where.

-

## 1 Answer

Consider $f(S \cup \{e_i\})+f(S \cup \{e_j\} ), e_i,e_j \in T-S$. It is obvious that $e_i,e_j \notin S$. So, $$f(S \cup \{e_i\})+f(S \cup \{e_j\} ) \geq f(S \cup \{e_i,e_j\})+f(S)$$ Extending it to three terms, $f(S \cup \{e_i\})+f(S \cup \{e_j\} )+f(S \cup \{e_k\}) \geq f(S\cup\{e_i,e_j\})+f(S\cup \{e_k\}) + f(S) \geq f(S \cup\{e_i,e_j,e_k\}) +2f(S)$

Suppose $|T-S| = n$. Then, $$\sum_{i \in T-S} f(S\cup \{e_i\}) \geq f(S \cup \{\cup e_i\}) + (n-1)f(S)$$ $$\sum_{i \in T-S} (f(S\cup \{e_i\})-f(S)) \geq f(S \cup \{\cup_{i\in T-S} e_i\}) -f(S)$$ $$f(S)+\sum_{i \in T-S} (f(S\cup \{e_i\})-f(S)) \geq f(S \cup \{\cup_{i\in T-S} e_i\})$$ Note that $$f(S \cup \{\cup_{i\in T-S} e_i\}) = f(S\cup T)$$

$$f(S)+\sum_{i \in T-S} (f(S\cup \{e_i\})-f(S)) \geq f(S \cup T)\geq f(T)$$

There you go!!

-
Sorry, computer broke :) Thanks for your answer – Shmoopy Dec 11 '12 at 18:54