Submodular function, square of which is also submodular?

Question

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?

Answer 1

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.