Minimum of two submodular functions

Question

Let $V$ be a finite set, and denote with $2^V$ the corresponding power set. Consider two (non-monotone) submodular function $f:2^V\rightarrow \mathbb{R}_{\geq 0}$ and $g:2^V\rightarrow \mathbb{R}_{\geq 0}$. Consider the function $$ H: 2^V \rightarrow \mathbb{R}_{\geq 0} : U \mapsto \min (f(U), g(U)). $$ Is the function $H$ also a submodular function?

Answer 1

If you try it out with any two distinct nonzero modular functions you'll see that their minimum is not submodular. Requiring that they are not monotone doesn't really changes things. Consider the following where $V=\{a,b\}$.

$$ \begin{array}{c|c|c|c|c} & \emptyset & \{a\} &\{b\} &\{a,b\}\\ \hline f & 0 & 0 & 2 & 1 \\ \hline g & 0 & 2 & 0 & 1 \\ \hline h & 0 & 0 & 0 & 1 \end{array} $$ In this example, $f$ and $g$ are simple non monotone submodular functions. However, $$ h(\emptyset) + h(\{a,b\}) \not\le h(\{a\}) + h(\{b\}) $$