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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .