1
$\begingroup$

By the hypercube I mean the lattice formed by all n-bit strings ordered by pointwise inequality. For example, $000 \leq 110$, $010 \leq 110$, $110$ and $001$ are not comparable. Further we have the meet and join operations $\wedge$ and $\vee$ that take the pointwise max and min. For example $010 \wedge 110 = 010$ and $001 \vee 100 = 101$. A submodular measure $\mu$ is a function from the hypercube to nonnegative reals satisfying $\mu(x) + \mu(y) \geq \mu(x \wedge y) + \mu(x \vee y)$ for all $x$ and $y$.

My question is, what is a minimal set of $(x,y)$ such that if the inequality above holds for these $(x,y)$ then it holds for all $(x,y)$ (and hence $\mu$ is submodular)?

The question comes out of mere curiousity (I want to understand submodularity in a more intuitive way) - I first guessed it suffices to check all pairs of elements of same rank. I'm still not sure whether that's true. If $x$ and $y$ are comparable, then the inequality is vacuous by itself.

$\endgroup$

1 Answer 1

3
$\begingroup$

These submodular measures on the hypercube are the same as non-negative submodular set functions. A minimal set of inequalities is $$ f(x+e_j)+f(x+e_j)\geq f(x)+f(x+e_i+e_j) $$ over all $x\in\{0,1\}^n$ and $1\leq i < j\leq n$ such that $x_i=x_j=0$. I'm using $e_i$ to denote the bit-string that is $1$ exactly at $i$. These inequalities are the third equivalent definition listed on the Wikipedia page. To see these are a minimal set, given $z\in\{0,1\}^n$ and all $1\leq I< J\leq n$ with $z_I=z_J=0$ we can define $$ f(x)=\begin{cases} n^2+2-(\sum x_i)^2&\text{ if $x=z$ or $x=z+e_I+e_J$}\\ n^2-(\sum x_i)^2 &\text{ otherwise} \end{cases}$$ for all bit-strings $x$.

Then $f(x+e_j)+f(x+e_j)-f(x)-f(x+e_i+e_j)$ is non-negative except when $(x,i,j)=(z,I,J)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.