# Supermodular function

If $p:2^V \to {\mathbb R} \cup \{-\infty\}$ is a set function on a finite ground set V, and $X,Y \subseteq V$, then we define the following two inequalities:

• supermodular inequality: $p(X)+p(Y) \leq p(X \cap Y)+p(X \cup Y)$
• negamodular inequality: $p(X)+p(Y) \leq p(X \setminus Y)+p(Y \setminus X)$

We can define several classes of set functions based on where these inequalities hold:

• p is (fully) supermodular if the supermodular inequality holds for every $X,Y \subseteq V$. In other words, p is supermodular if and only if -p is a submodular function.
• p is negamodular if the negamodular inequality holds for every $X,Y \subseteq V$.
• p is skew-supermodular if for every $X,Y \subseteq V$ either the supermodular or the negamodular inequality holds.
• p is intersecting supermodular if the supermodular inequality holds for every $X,Y \subseteq V$ for which $X \cap Y \neq \emptyset$.
• p is crossing supermodular if the supermodular inequality holds for every $X,Y \subseteq V$ for which $X \cap Y \neq \emptyset$ and $X \cup Y \neq V$. We can similarly define crossing negamodular functions, too.

See Frank and Király [1] for a survey on covering problems related to supermodular functions.

## References

1. A. Frank, T.Király, A Survey on Covering Supermodular Functions, in: Research Trends in Combinatorial Optimization, W. Cook, L. Lovász and J. Vygen, eds, Springer (2009), 87-126. DOI link.