A Possible Mistake in Lovasz's "Submodular functions and convexity"

56 Views Asked by At

The possible mistake appears in Lovász L. (1983) Submodular functions and convexity. In: Bachem A., Korte B., Grötschel M. (eds) Mathematical Programming The State of the Art. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-68874-4_10.

This a pdf of the paper and below is a screenshot where I believe there is a mistake. enter image description here

Following the text, modular functions (2) are set functions $f : 2^E \rightarrow \mathbb{R}$ such that $f(X \cap Y) + f(X \cup Y) = f(X) + f(Y)$.

Lovasz claims that modular functions satsify the following property (3).
$f(X) = \sum_{x\in X} f(\{x\}) + f(\emptyset)$

I tried to prove it, but I think it's just false. Consider the following equality, which holds for modular functions. $f(\{x\} \cup \{y\}) + f(\{x\} \cap \{y\}) = f(\{x\}) + f(\{y\})$

If $x \neq y$, this implies $f(\{x, y\}) + f(\emptyset) = f(\{x\}) + f(\{y\})$ and then $f(\{x, y\}) = f(\{x\}) + f(\{y\}) - f(\emptyset)$

Then Lovasz can only be correct if $f(\emptyset) = 0$ for every modular function, which is not true. Am I missing something here or is this a genuine error in the paper?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes I think this is a typo. The correct claim would be:

$$ f(X) = f(\emptyset) + \sum_{x\in X} (f(\{x\}) - f(\emptyset)) $$

It's common in the literature to assume $f(\emptyset)=0$ (sometimes referred to being normalized), so it's easy to see how that might have been overlooked.