Minimum of submodular function over family of subsets
Let and are two lattices. If is a submodular function and is a function with the property that if and , then and . defined as is submodular.
Let , note since and , we have and .
This is quite useful, for starters, it proves that we can create a monotone submodular function from any submodular function.
Let be a submodular function, then defined as are monotone and submodular.
A practical application is to generalize the cut function. Consider for a directed graph graph . We would define to be the set of out going edges from to . is a submodular function. An alternate definition for is the minimum number of edges to be removed so there is no path from to .
A simple generalization is when we only care about . We can define to be the minimum number of edges to be removed so there is no path from to . Amazingly(or not not surprisingly, depending on your intuition), is also a submodular function by invoking the next theorem, which is a direct corollary of our first theorem.
Let be a submodular function, then defined as is submodular.