Submodular function

Let V be a finite ground set. A set function $$b:2^V \to {\mathbb R} \cup \{\infty\}$$ is (fully) submodular if $$b(X)+b(Y) \geq b(X \cap Y)+b(X \cup Y)$$ for every $$X,Y \subseteq V$$ . In other words, b is submodular if and only if -b is a supermodular function.

Intersecting and crossing submodular set functions can be defined similarly as their supermodular counterparts:

• p is intersecting submodular if the submodular inequality holds for every $$X,Y \subseteq V$$ for which $$X \cap Y \neq \emptyset$$ .
• p is crossing submodular if the submodular inequality holds for every $$X,Y \subseteq V$$ for which $$X \cap Y \neq \emptyset$$ and $$X \cup Y \neq V$$ .
• p is posimodular if -p is negamodular.