Submodular function, square of which is also submodular? A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions:


*

*for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $

*for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $


There is also a property:
$f:2^\Omega\rightarrow \mathbb{R}_+$ is a submodular function then $g:2^\Omega\rightarrow \mathbb{R}_+$ defined as $g(S)=\phi(f(S))$ where $\phi$ is a concave function, is also a submodular function.
We can show an example when a square of a submodular function is not submodular. 
I have a monotone submodular function $h:2^\Omega\rightarrow [0,1]$. Can we say a criteria on $h$, for which the square of this function is submodular? Can we say something about the form of $h$ or its properties, so that $h^2$ is submodular? 
 A: Let $K = \lvert \Omega \rvert$. For a simple example, consider
$$ h(X) = \sqrt{{\lvert X\rvert}{K}}$$
which is submodular, and its square $h^2(X) = \frac{\lvert X \rvert}{K}$ is also submodular. 
Assume that $h(X)$ is submodular. Then $h^2(X)$ is submodular iff for any $ X \subset Y \subseteq \Omega$ and  $j \in \Omega\setminus Y$:
\begin{align*}
h^2(j\cup X) - h^2(X) &\ge h^2(j\cup Y) - h^2(Y)
\end{align*}
which is equivalent to: 
\begin{align*}
\left(h(j\cup X) - h(X)\right)\left(h(j\cup X) + h(X)\right) &\ge \left(h(j\cup Y) - h(Y)\right)\left(h(j\cup Y) + h(Y)\right)
\end{align*}
which is also equivalent to 
$$ \frac{h(j \cup X) - h(X)}{h(j \cup Y) - h(Y)} \ge \frac{h(j\cup Y) + h(Y)}{h(j\cup X) + h(X)}.$$
I don't know if there is more to be said without giving more conditions on $h$ other than submodularity.
If $h$ is not monotone, we can get a nice sufficient condition out of this. Since we assume that $h(X)$ is submodular, we know that $h(j\cup X) - h(X) \ge h(j \cup Y) - h(Y)$. So it is sufficient to show that
$$ h(j\cup X) + h(X) \ge h(j\cup Y) + h(Y).$$
If $h$ is monotone, the inequality above is trivially false. 
