# Are all (non-constant) symmetric submodular functions non-monotone?

I am trying to show (if possible) that symmetric submodular functions are non-monotone (excluding constant sub-modular functions).

Recall that a submodular function $f : 2^{\Omega} \rightarrow R$ is such that for $A,B \subset \Omega$, $f(A)+f(B) \geq f(A\cup B) + f(A \cap B)$, and that a symmetric submodular function satisfies $f(A) = f(\Omega \setminus A)$. A monotone function satisfies $f(A) \leq f(B)$ whenever $A \subseteq B$.

A classic example of a symmetric submodular function that is non-monotone is the graph cut function.

Is it possible to show just from the above definitions that any symmetric submodular function (that is not constant) is non-monotone?

• If I din't miss anything, choosing $\Omega = \{a,b\}$ and mapping $\{a\}\mapsto 1$, $\{b\}\mapsto 1$, $\{a,b\}\mapsto 1.5$ seems to be a counterexample to your claim. – Roman Bruckner Jan 28 '14 at 9:07
• Thanks for the reply. The issue with this counter example depends on how $f(\emptyset)$ is defined. I usually see it defined to be $f(\emptyset)=0$, in which case the above would not be a counter example, since $f(\emptyset) \neq f(\{a,b\})$, i.e., $f$ is not symmetric. Here, of course, I use that $\Omega \setminus \Omega = \emptyset$. – dan Jan 28 '14 at 15:52

Given any set $\Omega$, and a symmetric, monotone map $f\colon 2^\Omega\to R$. By symmetry, we have $f(\Omega) = f(\Omega\setminus\Omega) = f(\emptyset)$. Moreover, given any subset $A\subseteq \Omega$, monotony yields $f(\emptyset)\le f(A)\le f(\Omega)$, hence $f$ is constant.