3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Roman Bruckner Jan 28 '14 at 9:07
  • $\begingroup$ 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$. $\endgroup$ – dan Jan 28 '14 at 15:52
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.