0
$\begingroup$

I have the following problem emerged. Let's say we have $l$ finite sets $A_1, A_2, \ldots, A_l$ with cardinality of $n_1, n_2, \ldots\, n_l$, respectively. We know that $| A_i \cap A_j | \le a_{ij}$ (ibvously, $a_{ij}=a_{ji}$).

What could be a lower bound on $\left|\bigcup_{k=1}^l A_k \right|$?

The bound I would be satisfied with should be easy (polynomial) to compute and thus could be rough (but better than just maximum of $n_i$).

Some notes

From inclusion-exclusion principle we know exact expresion for that: $$ \left|\bigcup_{k=1}^l A_k\right| = \sum_{k=1}^l (-1)^{k+1} \left( \sum_{1 \le i_1 < i_2 < \ldots < i_k \le l} \left| A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_k} \right| \right) $$ but it is an exponintioal computation and we don't know all the intersections anyway.

In the real problem I am facing,there are the following values $$ n_i = w_i \binom{n-w_i}{k-1}, \\ a_{ij} = \delta \binom{n-w_i-w_j+\delta}{k-1}, \\ w_i, n, k, \delta \mbox{ are some natural numbers.} $$ But it's getting more messy to work with these expressions.

UPD. The question could be re-phrased like the following.

Find an easy computable function $\beta(l; a_{ij})$ such that for every $l$, $A_j$ and $a_{ij} = a_{ji}$ it holds $$ \left|\bigcup_{k=1}^l A_k\right| \ge \beta(l; a_{ij}) $$

$\endgroup$
  • $\begingroup$ You do not need to find the exact cardinality but rather (I am guessing) the greatest lower bound. If it is just a lower bound try $0$. ;) To get the smallest possible value the sets must overlap as much as possible. Suppose the sets are ordered so that $n_{1} \leq n_{2} \leq \cdots$. Work out a cases; say up to $3$ or $4$ sets. Then try induction on the number of sets. $\endgroup$ – Jay May 2 '14 at 15:08
  • $\begingroup$ Haha, no, $0$ is too rough :) $\endgroup$ – Yauhen Yakimenka May 2 '14 at 15:33
1
$\begingroup$

By Bonferroni's inequalities, the terms in the inclusion-exclusion sum alternately under- and over-estimate the final value. You should be fine with just: $$ \lvert A_1 \cup A_2 \cup \ldots \cup A_n \rvert \ge \sum_i \lvert A_i \rvert - \sum_{i < j} \lvert A_i \cap A_j \rvert \ge \sum_i \lvert A_i \rvert - \sum_{i < j} a_{ij} $$ This bound can be attained, when the intersections in threes are empty.

$\endgroup$
  • $\begingroup$ Well, this seems to be a good bound. Let me check if it is not too rough for my problem. $\endgroup$ – Yauhen Yakimenka May 2 '14 at 15:55
  • $\begingroup$ Well, I tried to generate some random sets and this bound is always giving negative number in RHS :( (which at least means that this situation is highly probably). So basically this bound is worse than just $\max n_j$ O_o $\endgroup$ – Yauhen Yakimenka May 2 '14 at 17:45
1
$\begingroup$

A greedy estimate:

Supposing for $1<k\le l$, $$ \left| A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_k} \right|= \begin{cases} 0 & \text{if k is odd}\\ b_{(k,\{i_1,i_2,\dots i_k\})}:=\min\{a_{i_pi_q} | p,q \in \{1,2,\dots k\}\} & \text{if k is even} \end{cases} $$

By inclusion-exclusion,$$\left|\bigcup_{i=1}^l A_j\right|=\sum_{i=1}^{l}n_{l}-\sum_{j=1}^{\lfloor \frac{l}{2}\rfloor}\left( \sum_{S_{2j}\subset [l]}b_{(2j,S_{2j})}\right)$$

This makes sense only if the RHS$>0$.

$\endgroup$
  • $\begingroup$ Could you explain why the second sum in right-hand side is iterated over $j$ only and not all the combinations of 3 out of $l$? And why does it has minus in front of sum? And what about the terms for $k=5,7,\ldots$? $\endgroup$ – Yauhen Yakimenka May 2 '14 at 15:45
  • $\begingroup$ @jjauhien: The second sum in the RHS is iterated over even numbers starting from two. By construction, odd intersections are made null so they do not contribute in the sum (all of them have positive sign in the inclusion-exclusion sum) and even intersections are maximized (all of them have negative sign in the inclusion-exclusion sum). $\endgroup$ – talegari May 2 '14 at 16:11
  • $\begingroup$ Shouldn't it be like the following then? $$ \left|\bigcup_{j=1}^l A_j\right| \ge \sum_{i=1}^{l} n_i - \sum_{j=1}^{\lfloor \frac{l}{2}\rfloor} \binom{l}{2j} b_{2j} $$ where $b_k = \min \{a_{ij} ~|~ i<j\}$ now. $\endgroup$ – Yauhen Yakimenka May 2 '14 at 16:23
  • $\begingroup$ @jjauhien: Yes, I have fixed it now. Slightly, better than the one you have suggested. $\endgroup$ – talegari May 2 '14 at 16:29
  • $\begingroup$ From the first look I would say that calculating over all the $S_{2j}$, $j=1,2,\ldots,\lfloor l/2 \rfloor$ would make calculation exponential... I will re-check it now. $\endgroup$ – Yauhen Yakimenka May 2 '14 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.