Submodular function

Dependencies:

1. Set function

$f: 2^{\Omega} \to \mathbb{R}$ be a function. Then $f$ is submodular iff it satisfies one of the following equivalent conditions:

1. $\forall Y \subseteq \Omega, \forall X \subseteq Y, \forall Z \in \Omega \setminus Y,$ $f(Z \mid X) \ge f(Z \mid Y)$.
2. $\forall P \subseteq \Omega, \forall Q \subseteq \Omega,$ $f(P) + f(Q) \ge f(P \cup Q) + f(P \cap Q)$.

Proof of equivalence of definitions

Definition 1 implies definition 2 if we let $Y = P$, $X = P \cap Q$ and $Z = Q - P$.

Definition 2 implies definition 1 if we let $P = X \cup Z$ and $Q = Y$.

Dependency for:

1. Sum of submodular functions is submodular
2. A set function is additive iff it is submodular and supermodular iff it is subadditive and superadditive.
3. A submodular function is also a subadditive function
4. Matroid: rank is submodular
5. Matroid: weighted rank is submodular
6. EF1 and EFX

Info:

• Depth: 3
• Number of transitive dependencies: 3

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function