# Submodular function

Let $LaTeX: N$ be a finite set and let $LaTeX: f$ be a function on the subsets of $LaTeX: N$ into $LaTeX: \mathbb{R}$. Then, $LaTeX: f$ is submodular if it satisfies:
$LaTeX: f(S \lor T) \le f(S) + f(T) - f(S \land T) \mbox{ for } S, T \subset N.$
Example: $LaTeX: \textstyle N=\{0,1\}^n$ (binary n-vectors) and $LaTeX: \textstyle f(S) = \sum_{x \in S} \sum_{j=1}^{n} x_j.$ Instance: $LaTeX: \textstyle n=2,$ $LaTeX: \textstyle S=\{(0,1), (1,1)\},$ $LaTeX: \textstyle T=\{(1,0),(1,1)\}.$ Then, $LaTeX: \textstyle f(S \lor T) = 4,$ $LaTeX: \textstyle f(S)=3,$ $LaTeX: \textstyle f(T)=3,$ $LaTeX: \textstyle \mbox{and } f(S \land T) = 2.$ (The linearity of Sum makes the inequality hold with inequality.)