# Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions

Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\rightarrow \mathbb{R}$ and for every $S, T \subseteq \Omega$ we have that $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$.

We also have that $f$ and $g$ are non-negative: $f(.) \geq 0$

And are monotone increasing: $f(S) \leq f(T)$, for all sets $S \subseteq T$

I just wonder is there a way we can prove that $fg$ is submodular (or not)?

-

## 1 Answer

Counter example:

$\Omega = \{a,b\}$. $f(\phi)=0$, $f(\{a\})=1$, $f)\{b\})=2$, $f(\{a,b\}) = 3$.

Multiply $f$ with itself. The result is not submodular.

-
Thanks polkjh for the comment, it's been a while. I found from the Exercise 3.32 (b), page 119, S.Boyd's Convex Optimization book that the 2 functions must be 1 increasing and 1 decreasing to make the product function submodular. In this case, since they're both increasing, we can definitely build up a counter example like you did to show that the product is not submodular –  HuyNA Mar 4 '13 at 23:52
@HuyNA One increasing and one decreasing look sufficient, but I think the condition is too strong. It might be possible to get a weaker condition for product being submodular, though I have no idea yet how. Anyway, thanks for pointing that out! –  polkjh Mar 5 '13 at 4:00