# Minimum of submodular function over family of subsets

Let $L$ and $L_{′}$ are two lattices. If $f:L→R$ is a submodular function and $P:L_{′}→2_{L}$ is a function with the property that if $X∈P(A)$ and $Y∈P(B)$, then $X∧Y∈P(A∧B)$ and $X∨Y∈P(A∨B)$. $f_{P}:L_{′}→R$ defined as $f_{P}(X)=Y∈P(X)min f(Y)$ is submodular.

Let $X_{∗}=argmin_{Y∈P(X)}f(Y)$, note since $X_{∗}∈P(X)$ and $Y_{∗}∈P(Y)$, we have $X_{∗}∨Y_{∗}∈P(X∨Y)$ and $X_{∗}∨Y_{∗}∈P(X∧Y)$. $f_{P}(X)+f_{P}(Y) =f(X_{∗})+f(Y_{∗})≥f(X_{∗}∨Y_{∗})+f(X_{∗}∧Y_{∗})≥f((X∨Y)_{∗})+f((X∧Y)_{∗})=f_{P}(X∨Y)+f_{P}(X∧Y) $

This is quite useful, for starters, it proves that we can create a monotone submodular function from any submodular function.

Let $f:2_{V}→R$ be a submodular function, then $f_{∗},f_{∗}:2_{V}→R$ defined as $f_{∗}(X)=min{f(Y)∣Y⊂X}f_{∗}(X)=min{f(Y)∣X⊂Y}$ are monotone and submodular.

A practical application is to generalize the cut function. Consider for a directed graph graph $G=(V,E)$. We would define $δ_{+}(A)$ to be the set of out going edges from $A$ to $V∖A$. $f=∣δ_{+}∣$ is a submodular function. An alternate definition for $f$ is the minimum number of edges to be removed so there is no path from $A$ to $V∖A$.

A simple generalization is when we only care about $T⊂V$. We can define $f_{T}(A)$ to be the minimum number of edges to be removed so there is no path from $A$ to $T∖A$. Amazingly(or not not surprisingly, depending on your intuition), $f_{T}$ is also a submodular function by invoking the next theorem, which is a direct corollary of our first theorem.

Let $f:2_{V}→R$ be a submodular function, then $f_{T}:2_{T}→R$ defined as $f_{T}(X)=min{f(Y)∣Y⊂X,T∖X⊂V∖Y}$ is submodular.