# Submodularity Proof

For a fixed set $T$ and for sets $A_i ,\forall i \in \left \{ 1,2,\dots,n \right \}$ , I define $f(A_i)=\frac{|A_i|+|T|}{|A_i\cup T|}$, where $|A_i|$ is the cardinality of set $A_i$. Is $f(A_i)$ submodular, i.e, is $$f(A_i)+f(A_j)\geq f(A_i\cup A_j)+f(A_i\cap A_j), \forall i,j \in \left \{ 1,2,\dots,n \right \} ?$$

Is $f(A_i)$ submodular in a sub-case when $A_i \cap A_j=\varnothing,\forall i,j$ and $|A_i\cap T|>0,\forall A_i$ ? If the above is proved directly, the sub-case also follows.

• Why are you using $[1,2,\ldots,n]$ and not $\{1,2,\ldots,n\}$? The former is commonly used to denote the interval of real numbers so you have infinitely many sets, where as the second notation is for the integers $1$ to $n$ - which is what I think you mean. Mar 21, 2012 at 22:38
• I made the correction. Thanks. That's right- for integers 1 to n.
– user23600
Mar 21, 2012 at 22:42

It's not. Let $A$ be $\{1,\dots,N\}$, $B$ be $\{1,N+1,N+2,\dots,2N\}$, and $T$ be just $\{1\}$, for $N$ large. Then $f(A)$, $f(B)$ and $f(A \cup B)$ are close to $1$, while $f(A \cap B) = 2$.

A brute-force computation shows that the inequality is true for $A \cap B = \emptyset$. Let $k = |(A \backslash B) \cap T|$, $m = |(B \backslash A) \cap T|$, $n = |T \backslash (A \cup B)$, $r = |A \backslash (B \cup T)|$, $s = |B \backslash (A \cup T)|$. Since for all $X$

$$f(X) = \frac{|X| + |T|}{|X \cup T|} = 1 + \frac{|X \cap T|}{|X \cup T|},$$

all we have to prove is

$$\frac{k}{k + m + n + r} + \frac{m}{k + m + n + s} \ge \frac{k + m}{k + m + n + r + s},$$

which is obviously true, with inequality iff $r = s = 0$. It is a bit more tedious to make the computations in the general case and derive possible counterexamples, such as $(T, A, B) := (V, V \cup W, V \cup X)$ where $V, W, X$ are arbitrary disjoint, non-empty finite sets.

• What do you mean by: considering, $|A \cap \overline{B} \cap T|$, $|A \cap \overline{B} \cap \overline{T}|$, ... individually and everything is fine?
– user23600
Aug 11, 2012 at 19:09

We notice that $$f(A_i)=\frac{|A_i|+|B|-|A_i\cap B|}{|A_i\cup B|}+\frac{|A_i\cap B|}{|A_i\cup B|}=1+\frac{|A_i\cap B|}{|A_i\cup B|},$$ so actually the question is whether the function $$g\colon A\mapsto \frac{|A\cap B|}{|A\cup B|}$$ is submodular.

• Take $$A_1:=\{1,\dots,n\}$$, $$A_2=\{n,\dots,2n-1\}$$ and $$B=\{n\}$$. We have $$g(A_1)=\frac 1n=g(A_2),g(A_1\cup A_2)=\frac 1{2n-1},g(A_1\cap A_2)=g(B)=1,$$ so just pick $$n$$ such that $$\frac 2n<\frac 1{2n-1}+1$$.

• However, when $$A_1$$ and $$A_2$$ are disjoint, we have $$g(A_1\cup A_2)=\frac{|A_1\cap B|+|A_2\cap B|}{|A_1\cup B|+|A_2\cup B|}=\frac{|A_1\cap B|}{|A_1\cup B|+|A_2\cup B|}+\frac{|A_2\cap B|}{|A_1\cup B|+|A_2\cup B|},$$ and we conclude using the inequalities $$|A_1\cup B|+|A_2\cup B|\geq |A_j\cup B|$$, $$j\in \{1,2\}$$.

• This is a simple and elegant proof showing supermodularity in the disjoint case, and submodularity for the given choice of $n$, otherwise.
– user23600
Aug 14, 2012 at 12:34