Let $F=\{S_1,\dots,S_n\}$ be a family of finite sets and $G=\{T_1,\dots,T_m\}$ also be a family of finite sets. Define the union of $F$ and $G$ naturally as $F \cup G=\{S_1 \cup T_1, S_2 \cup T_1, \dots , S_n \cup T_1, \dots, S_1 \cup T_m, \dots, S_n \cup T_m\}$.

The maximum number of distinct elements in $F \cup G$ is $mn$, which occurs when all of the sets are disjoint. What is the minimum number of distinct elements in $F \cup G$?

  • 1
    $\begingroup$ Have you tried anything so far? $\endgroup$ – TomGrubb Nov 14 '17 at 4:17
  • $\begingroup$ ThomasGrubb, No, I have not thought too deeply about this. My real motive for asking the question is to see if there is any good material out there which addresses questions like this. $\endgroup$ – Craig Feinstein Nov 14 '17 at 4:20

The minimum is $1,$ which occurs when $S_i=\{1,2,3,\dots,n+m\}\setminus\{i\}$ for $i=1,2,3,\dots,n$ and $T_j=\{1,2,3,\dots,n+m\}\setminus\{n+j\}$ for $j=1,2,3,\dots,m;$ more generally, whenever the complements of all the sets are disjoint.


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.