Suppose $f$ is a submodular set function on a universe $U$ of size $n$.

For $k \in \{0,\ldots,n\}$, let $$ F(k) = \operatorname*{\mathbb{E}}_{X \in \binom{U}{k}} f(X), $$ where $\binom{U}{k}$ is the set of all subsets of $U$ of size $k$.

We are interested in proving the following inequality: $$ F(k) \geq \frac{k}{n} F(n) + \frac{n-k}{n} F(0). $$ One can prove this inequality by induction on $k$ (or even directly, if we're careful), but this doesn't explain why the inequality holds. Instead, we will use some form of term rewriting.

Submodularity directly implies the following inequality, for $k \in \{1,\ldots,n-1\}$: $$ F(k) \geq \frac{1}{2} F(k+1) + \frac{1}{2} F(k-1). $$ Imagine applying this inequality over and over again, in an arbitrary way. Here is an example for $n = 3$ and $k = 2$: $$ \begin{align*} F(2) &\geq \frac{1}{2} F(3) + \frac{1}{2} F(1) \\ &\geq \frac{1}{2} F(3) + \frac{1}{4} F(2) + \frac{1}{4} F(0) \\ &\geq \frac{5}{8} F(3) + \frac{1}{8} F(1) + \frac{1}{4} F(0) \\ &\geq \frac{5}{8} F(3) + \frac{1}{16} F(2) + \frac{5}{16} F(0) \\ &\geq \cdots \\ &\geq \frac{2}{3} F(3) + \frac{1}{3} F(0). \end{align*} $$ The dots hide infinitely many steps.

There is a way to make this argument completely rigorous. One can cook up some potential function that increases whenever one applies any instance of submodulary (for example, the expectation of squared cardinality). Taking the consequence of $F(k)$ maximizing this potential, it's easy to see that we get an inequality of the form $$ F(k) \geq \alpha F(n) + \beta F(0). $$ If $f$ is any modular function then there is equality. Taking $f = 1$ we find that $\alpha + \beta = 1$, and taking $f(X) = |X|$ we determine $\alpha = k/n$.

This argument extends to prove more interesting inequalities on submodular functions.

Does this sort of reasoning look familiar?

  • $\begingroup$ What is the question here? $\endgroup$ May 9, 2012 at 0:09
  • $\begingroup$ I am looking for input from people familiar with term rewriting. It might be, for example, that a similar argument appears in some paper. Perhaps the argument can be put more succinctly in their terminology. $\endgroup$ May 9, 2012 at 1:33


Your Answer

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