Skip to main content
MathOverflow

Return to Question

typo for the RHS
Source Link
Colin Tan
Colin Tan
  • 331
  • 4
  • 12

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{ even}} f(T)?$$$$\sum_{|S| \text{ even}} f(S) \le \sum_{|T| \text{ odd}} f(T)?$$ Here $|S|$ is the cardinality of $S$, as usual.

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{ even}} f(T)?$$ Here $|S|$ is the cardinality of $S$, as usual.

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.

Source Link
Colin Tan
Colin Tan
  • 331
  • 4
  • 12

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{ even}} f(T)?$$ Here $|S|$ is the cardinality of $S$, as usual.