0

Let's say I have 10 finite sets $X_1, X_2, ..., X_{10}$.
Given the values $|X_i|,$ for $i=1,2,..,10$ and $|X_i \cap X_j|$ for $i\not= j$ and $i,j=1,2,...,10$,
what is the best estimation of the cardinality of $$|X_1 \cap X_2 \cap ... \cap X_{10}|$$ that I can get (without knowing the elements of the 10 sets $X_i$)?

My guess is that the only thing that I can assume with accuracy is that $$|X_1 \cap X_2 \cap ... \cap X_{10}| \leq min_{i,j}(|X_i \cap X_j|), \text{ with } i\not=j \text{ and }i,j=1,...,10.$$ Can I do any better?

All the Best,

Luca

Luca
  • 1,616
  • It's possible to get sets such that $|X_i| = 9$ and $|X_i \cap X_j| = 8$ for every $i, j$ but such that $X_1 \cap \ldots \cap X_{10} = \emptyset$: just choose $X_i= { 1, 2, \ldots, i-1, i+1, \ldots, 10}$, for example. – Connor Harris Jul 11 '19 at 14:23
  • @ConnorHarris : First, thanks for your comment. I think I didn't explain well what I want to do, sorry! What I wish to achieve is the most accurate calculation possible of the cardinality of all the 10 sets. I only know the cardinality of each of the 10 sets, and the intersection of each two of them. Without knowing their elements. – Luca Jul 11 '19 at 14:36
  • 1
    Right, I'm giving a case where the all the sets and their pairwise intersections have very large cardinality but the intersection of all the sets is empty, which means that any lower bound on the size of the overall intersection is likely not to be very good. – Connor Harris Jul 11 '19 at 14:38

1 Answers1

1

You need more information to get an accurate count of the intersection, otherwise all you can say is what you have said

$$|X_1 \cap X_2 \cap ... \cap X_{10}| \leq min_{i,j}(|X_i \cap X_j|), \text{ with } i\not=j \text{ and }i,j=1,...,10.$$

Note that even in the simple case of three sets, we have

$$ |A\cup B\cup C|= |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

Thus with the given information and without knowing $$ |A\cup B\cup C|$$ we can not find $$ |A\cap B\cap C|$$

Mohammad Riazi-Kermani
  • 68,728