I was studying sub modular functions and was trying to prove the equivalence of different definitions of sub modular functions.

Consider this first definition:

$$ \forall A \subseteq B , s \notin B, F(A \cup \{s\}) - F(A) \geq F(B \cup \{ s \}) -F(B)$$

I was trying to show that the following was equivalent:

$$\forall A,B \subseteq V : F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$

I've been told that its suppose to be a simple exercise but I've had a hard time starting such a proof. Intuitively, I feel that the correct thing might be to use exclusion-inclusion rule for sets, but wasn't sure how to. Also, are sub modular functions suppose to be linear? Because without a property like that I cannot think of how to a expand such an expression like:

$$F(A \cup \{s\})$$


$$ F(A \cup B) $$

Maybe someone can start off the proof so that I can try finishing it off? Or maybe provide the first direction of the implication so that I can do the other? I feel I might not know enough of the properties of sub modular function so to start this. Or maybe provide a list of properties I should be considering using?

I usually provide more of my thoughts but I am a little stuck because I don't know what rules I am allowed to use to expand any of the terms in the equations.


I think I got one direction of the equivalence. The goal is to show:

$$ \forall A \subseteq B , s \notin B, F(A \cup \{s\}) - F(A) \geq F(B \cup \{ s \}) -F(B) $$

$$\iff \forall A,B \subseteq V : F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$

I think I got the following implication ($\Leftarrow$).

The key step is the following definition:

Let $C \subseteq B$ and $s \notin B$ and define $A = C \cup \{s\}$. Then:

$$F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$


$$ F(C \cup \{s\}) + F(B) \geq F(C \cup \{s\} \cup B) + F((C \cup \{s\}) \cap B) $$

After some algebra and some re-arranging we get:

$$ F(C \cup \{s\}) + F(B) \geq F(C \cup B \cup \{s\}) + F((C \cap B) \cup (\{s\} \cap B)) $$

Notice that since $C \subseteq B$ then $C \cup B = C$ and similarly, $C \cap B = C$ is true. Also notice that since $s$ is defined to not be in B, then the intersection of $s$ and $B$ is the empty set i.e. $B \cap \{ s \} = \emptyset$. Hence:

$$ F(C \cup \{s\}) + F(B) \geq F(B \cup \{s\}) + F((C \cap B) \cup (\{s\} \cap B)) $$

$$ F(C \cup \{s\}) + F(B) \geq F(B \cup \{s\}) + F(C \cup (\emptyset)) $$

$$ F(C \cup \{s\}) + F(B) \geq F(B \cup \{s\}) + F(C) $$

Now, after re-arranging some more terms we get the desired implication:

$$ F(C \cup \{s\}) - F(C) \geq F(B \cup \{s\}) - F(B) $$

where $C \subseteq B$ and $s \notin B$.

However, I am still missing the other direction to complete the if and only if.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.