1
$\begingroup$

For a fixed set $B$ and for sets $A_i ,\forall i \in \left \{ 1,2,\dots,n \right \}$ , I define $f(A_i)=\frac{|A_i \cap B|}{2|A_i|-|A_i\cap B|}$, where $|A_i|>0$ 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), \quad \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$ , $f(\varnothing)=0$ and $|A_i\cap B|>0,\forall A_i$ ? If the above is proved directly, the sub-case also follows.

  • 1
    Edited it as $f(\varnothing)=0$.2012-08-12

1 Answers 1

0

It seems, barring miscomputation, that $f$ is not submodular: take $B=\{2\}$, $A_1:=\{1,2\}$, $A_2=\{2,3\}$. Then $f(A_1\cup A_2)=\frac{1}{2\cdot 3-1}=\frac 15,\quad f(A_1\cap A_2)=\frac 1{2-1}=1,$ $f(A_1)=f(A_2)=\frac 1{2\cdot 2-1}=\frac 13.$ Hence $f(A_1\cup A_2)+f(A_1\cap A_2)=\frac 65\geq\frac 23=f(A_1)+f(A_2).$ But when $A_1$ and $A_2$ are disjoint it's the case, since \begin{align}f(A_1\cup A_2)&=\frac{|A_1\cap B|+|A_2\cap B|}{2|A_1|+2|A_2|-|A_1\cap B|-|A_2\cap B|}\\ &=\frac{|A_1\cap B|}{2|A_1|+2|A_2|-|A_1\cap B|-|A_2\cap B|}+\frac{|A_2\cap B|}{2|A_1|+2|A_2|-|A_1\cap B|-|A_2\cap B|}. \end{align} Since $2|A_j|-|A_j\cap B|\geq 0$, we get the result.