Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Why do you feel so strongly about typing the non-standard $\{1,2...n\}$ instead of the standard $\{1,2,\ldots,n\}$? (After I did that bit of minor copy-editing, you changed it back within a few seconds.) – Michael Hardy Aug 12 '12 at 3:54
:) Appreciate your moderation. I was adding an extra sentence in an edit, and looks like we both edited with a momentary time gap. – user23600 Aug 12 '12 at 3:59
Edited, $|A_i|>0$ – user23600 Aug 12 '12 at 10:35
In the disjoint case, in order to check sub-modularity, we have to define $f(\emptyset)$. – Davide Giraudo Aug 12 '12 at 11:25
Edited it as $f(\varnothing)=0$. – user23600 Aug 12 '12 at 14:42
up vote 0 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.