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.