Submodularity Proof

Question

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.

Answer 1

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$.

Answer 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.

Answer 3

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\}$.