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?

Improve this question
$\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, 2014 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, 2014 at 15:52

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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