# 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?

• The property that you listed about submodular composed with concave is incorrect. To see this, take $f$ to be a cut function and $g(S) = \sqrt{f(S)}$. You can show that $g(S)$ is not submodular. This property was listed on the wikipedia page for submodular functions for quite some time, but it was incorrect. Recently removed. May 6, 2019 at 16:58

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.