Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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!!

share|cite|improve this answer
Sorry, computer broke :) Thanks for your answer – Shmoopy Dec 11 '12 at 18:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.