1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Mar 21, 2012 at 22:38
  • 1
    $\begingroup$ I made the correction. Thanks. That's right- for integers 1 to n. $\endgroup$
    – user23600
    Mar 21, 2012 at 22:42

3 Answers 3

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

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

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

You must log in to answer this question.