Residual of submodular function is submodular

Dependencies:

1. Set function
2. Submodular function
3. /sets-and-relations/de-morgan-laws

Let $f$ be a real-valued submodular set function over $\Omega$. Let $S \subseteq \Omega$ and define the function $g$ over $\Omega \setminus S$ as $g(X) = f(X \mid S) = f(X \cup S) - f(S)$. Then $g$ is also submodular.

Proof

Let $P, Q \subseteq \Omega \setminus S$. Then \begin{align} & g(P) + g(Q) \\ &= f(P \cup S) + f(Q \cup S) - 2f(S) \\ &≥ f((P \cup S) \cup (Q \cup S)) + f((P \cup S) \cap (Q \cap S)) - 2f(S) \\ &= f((P \cup Q) \cup S) + f((P \cap Q) \cup S) - 2f(S) \tag{by De Morgan's law} \\ &= g(P \cup Q) + g(P \cap Q). \end{align} Hence, $g$ is submodular.

Dependency for:

1. PROPm implies PROP1

Info:

• Depth: 4
• Number of transitive dependencies: 5

Transitive dependencies:

1. /sets-and-relations/countable-set
2. /sets-and-relations/de-morgan-laws
3. σ-algebra
4. Set function
5. Submodular function