# Does $\sum_{|S| \text{ even}} f(S) \le \sum_{|T| \text{ even}} f(T)$ hold for all nondecreasing submodular functions f?

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.

• thanks Fedor for pointing out my typo. Also thanks to Hao for your counterexample for n = 3. Sep 1, 2022 at 8:36

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