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.



Submodular measures on the hypercube
These submodular measures on the hypercube are the same as
non-negative [submodular set
functions](http://en.wikipedia.org/wiki/Submodular_function). 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)$.


