0
$\begingroup$

Let $f : 2^n \to \mathbb{R}$ be a nondecreasing submodular function, where $2^n$ is the powers of $\{1, \dots, n\}$. Here nondecreasing means that $f(S) \le f(T)$ for all $S \subseteq T$. And submodularity means that $f(S) + f(T) \ge f(S \cup T) + f(S \cap T)$ for all $S, T$.

Is it true that $$\sum_{|S| \text{ even}} f(S) \le \sum_{|T| \text{ odd}} f(T)?$$ Here $|S|$ is the cardinality of $S$, as usual.

$\endgroup$
1
  • $\begingroup$ thanks Fedor for pointing out my typo. Also thanks to Hao for your counterexample for n = 3. $\endgroup$
    – Colin Tan
    Sep 1, 2022 at 8:36

1 Answer 1

3
$\begingroup$

Assuming the inequality you would like to prove has the sum over odd subsets on the RHS, then you could consider the following counter-example for $n=3$: $f(\emptyset)=0$, $f(\{i\})=1$, $f(\{i, j\})=2$, and $f(\{1,2,3\})=2$. $f$ is non-decreasing and submodular, but the sum over even sets is $6$ and the sum over odd sets is only $5$.

To have the sum over odd sets on the LHS also would not work for $n=2$.

$\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.