# Lipshitz Constant of the convex extension of a submodular function

The title says it all :)

Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function $g:[0,1]^n\rightarrow\mathbb{R}$, which agrees with $f$ wherever it is defined (the integral points of the hypercube).

One such way of calculating an extension is given here: http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture21-22.pdf

My question is what is the relationship between the Lipshitz constant of $f$ and $g$?

Quite obviously, they don't have to be equal, and it might depend on the way which we define the extension.

For example, let's say that $n=1$, and that $f(0)=0$, $f(1)=1$. Then $g(x)=x$ and $g(x)=x^2$ are both valid convex extensions, but one has a Lipshitz constant of 1 (as does $x$), and the other has a Lipshitz constant of 2.

Thanks, Guy

-