Consider a union-closed family $\mathcal{F} = \{A_1, \dotsc ,A_n\}$ of $n$ finite sets, $n$ odd, $n \ge 3$, $A_i \neq \emptyset$, $i=1,\dotsc,n$.

Let $h=\frac{n+1}{2}$. We have that:

$$\bigcup_{1 \le i_1 \lt \ldots \lt i_h \le n} A_{i_1} \cap \ldots \cap A_{i_h} = \bigcap_{1 \le i_1 \lt \ldots \lt i_h \le n} A_{i_1} \cup \ldots \cup A_{i_h}. \tag{1}\label{1}$$

This is because the LHS contains all elements that are in at least $h$ of the $A_i$ and the RHS contains all elements that are in at least $n-h+1$ of the $A_i$ (because for each element that does not belong to the RHS we can find $h$ $A_i$ that do not contain it and thus it is in maximum $n-h$ of the $A_i$) and note that in our case $h=n-h+1$.

Let $B_k = A_{i_{k,1}} \cup \dotsb \cup A_{i_{k,h}}$, $B_k \neq U(\mathcal{F})$, $1 \le i_{k,1} \lt \dotsb \lt i_{k,h} \le n$, $1 \le k \le n$.

Let's choose $1 \le i_{1,1} \lt \dotsb \lt i_{1,h} \le n$ and $1 \le i_{2,1} \lt \dotsb \lt i_{2,h} \le n$ to form $B_1$ and $B_2$, $B_1 \neq B_2$. Since $B_k \neq U(\mathcal{F})$ then $A_i \neq U(\mathcal{F})$ and $B_1$ and $B_2$ must share at least two sets $C_1 = A_{i_{1,u_1}} = A_{i_{2,z_1}}$ and $C_2 = A_{i_{1,u_2}} = A_{i_{2,z_2}}$ in the respective unions expressions $B_1 = A_{i_{1,1}} \cup \dotsb \cup A_{i_{1,h}}$ and $B_2 = A_{i_{2,1}} \cup \dotsb \cup A_{i_{2,h}}$, because $2h-(n-1) = 2$. Therefore $B_1 \cap B_2 \neq \emptyset$.

Likewise, we choose three sets $B_1$, $B_2$, $B_3$, all different. $B_1$ and $B_2$ share at least two sets $C_1$ and $C_2$ in the respective union expressions, as in the above paragraph with only two sets $B_1$ and $B_2$. If one of these sets has an element in common with one of $A_{i_{3,1}}, \dotsc, A_{i_{3,h}}$ then $B_1 \cap B_2 \cap B_3 \neq \emptyset$. Otherwise all unions of the form $C_j \cup A_{i_{3,l}}$ are in $\mathcal{F}$, and it is easy to see that they must be all different, otherwise we would have $C_1 = C_2$ and/or $A_{i_{3,l}} = A_{i_{3,m}}$. Therefore there are $2h = n+1$ such unions, which added to $C_1, C_2, A_{i_{3,1}}, \ldots, A_{i_{3,h}}$, give $n+1+2+h \gt n$, absurd. Therefore $B_1 \cap B_2 \cap B_3 \neq \emptyset$.

Now choose four sets $B_1$, $B_2$, $B_3$, $B_4$ like above. The four unions are formed in total by $4h=2n+2$ sets selected among $n-1$, thus $A_1, \dotsc ,A_n$ appear on average $2\frac{n+1}{n-1} > 2$ times in $B_1$, $B_2$, $B_3$, $B_4$. Therefore there must be at least one set $A_t$ belonging to three of the $B_1$, $B_2$, $B_3$, $B_4$. Letting $C_1 = A_t$ and reasoning like before we have that, assuming $C_1 \not\subset B_4$ and $C_1 \cap A_{i_{4,1}} = \emptyset, \dotsc, C_1 \cap A_{i_{4,h}} = \emptyset$, the sets $C_1, A_{i_{4,1}}, \dotsc, A_{i_{4,h}}$ generate $h$ different unions $C_1 \cup A_{i_{4,1}}, \dotsc, C_1 \cup A_{i_{4,h}}$, in turn different from $C_1, A_{i_{4,1}}, \dotsc, A_{i_{4,h}}$, for a total of $h+1+h = n+2 > n$, absurd. Therefore $B_1 \cap B_2 \cap B_3 \cap B_4 \neq \emptyset$.

Now I wanted to push that a little further for $5$ sets $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, but while I can make it work for specific examples, I cannot get a general proof that it must be always $B_1 \cap B_2 \cap B_3 \cap B_4 \cap B_5 \neq \emptyset$.

Can someone help with the case $5$ (or even more) sets?

Edit 2022-01-26

I have seen now that for $j \neq k$ it must be $A_{i_{k,1}} \neq B_j , \dotsc , A_{i_{k,h}} \neq B_j$, otherwise $B_j \subset B_k$ and therefore $B_k$ could be removed from the intersection that would have fewer sets. But since $A_{i_{k,1}} \neq B_j , \dotsc , A_{i_{k,h}} \neq B_j$ for $j \neq k$, it follows that $A_{i_{k,1}} , \dotsc , A_{i_{k,h}}$ can be chosen in less than $n$ sets, or more precisely in $n-1-(q-1)$ where $q$ is the number of $B_i$ sets ($q=5$ in the question case). Since there are fewer choices for the $A_i$, there will be more "overlapping" for the $B_i$ union expressions, but I am not sure if it might help.

  • $\begingroup$ What does "$B_1$ and $B_2$ share at least two sets that we can call $C_1$ and $C_2$" mean? That is, what does it mean for two sets to share sets? $\endgroup$
    – LSpice
    Jan 26, 2022 at 17:32
  • 1
    $\begingroup$ @LSpice thank you for correcting, I have edited the question and I hope it is clearer now. $\endgroup$ Jan 26, 2022 at 18:33

1 Answer 1


Each of the $5$ unions $B_k = A_{i_{k,1}} \cup \dotsb \cup A_{i_{k,h}}$, $k=1,\dotsc,5$ cannot contain another of them i.e. $B_k \not\subseteq B_j$ for $k \neq j$ otherwise we can simplify $B_1 \cap B_2 \cap B_3 \cap B_4 \cap B_5$ to get an intersection with less than $5$ sets. Therefore $A_{i_{k,l}} \neq B_j$ for $k \neq j$, $l = 1, \dotsc, h$ and then the $A_{i_{k,l}}$ can be chosen among $n-1-4 = n-5$ sets (having removed $U(\mathcal{F})$ and all $B_j$ with $j \neq k$).

The total number of occurrences, in the $B_k$ union expressions, of $A_1,\dotsc,A_n$, $A_i \neq B_1,B_2,B_3,B_4,B_5$, $A_i \neq U(\mathcal{F})$, $i=1,\dotsc,n$, will be at least $5(\frac{n+1}{2}-1)$. The $-1$ accounts for the worst case when there always exist one $A_{i_{k,l}} = B_k$ in the union expression of $B_k$. The minimum average occurrence for the $A_i \neq B_1,B_2,B_3,B_4,B_5$, $A_i \neq U(\mathcal{F})$, $i=1,\dotsc,n$ will then be $\frac{5}{2}\frac{n-1}{n-6}$.

$\frac{5}{2}\frac{n-1}{n-6} > 3$ for $6 < n < 31$ therefore when $n < 31$ there will be at least one $A_i$ occurring in at least $4$ of the union expressions for the $B_k$. Now either $A_i$ belongs to all $B_1,B_2,B_3,B_4,B_5$, or otherwise we can apply the same reasoning for the case of four union expressions $B_1,B_2,B_3,B_4$ (see the question). In any case $B_1 \cap B_2 \cap B_3 \cap B_4 \cap B_5 \neq \emptyset$.

For $n \ge 31$, let $t$ be the number of $A_i$ occurring in $3$ of the union expressions for the $B_k$. It must be $\frac{5\frac{n-1}{2}-3t}{n-6-t} \le 2$, which gives, for $n \ge 31$, $t \ge \frac{n+19}{2} \ge 20$. The $A_i$ occurring in $3$ of the $B_k$ can occur in ${5 \choose 3} = 10$ ways (the number of ways to choose $3$ of the $B_k$). We want to find $1 \le j \lt k \lt l \le 5$ such that there are as much as possible $A_i$ in the union expressions of $B_j, B_k, B_l$. In the worst case, they will be equally distributed among the ${5 \choose 3}$ combinations of $B_j, B_k, B_l$, but since $t \ge 20$ there will be at least $2 = \frac{20}{10}$ of the $A_i$, $C_1 = A_{i_1}, C_2 = A_{i_2}$, occurring in the same triplet of union expressions $B_j, B_k, B_l$. The other two $B_p$, $B_q$ unions $1 \le p \lt q \le 5$, $p,q \neq j,k,l$ will share $s = 2h - (n-6)=7$ of the $A_i$ sets in the respective union expressions. Let's call these sets $D_1, \dotsc, D_s$. If there exist a couple $C_u, C_v$ such that $C_u \cap D_v \neq \emptyset$, we are done ($B_1 \cap B_2 \cap B_3 \cap B_4 \cap B_5 \neq \emptyset$), otherwise it is easy to see that the unions of one of $C_1, C_2$ and one of $D_1, \dotsc, D_s$ will be all different between themselves and from $C_1, C_2, D_1, \dotsc, D_s$. The number of such unions is $2s$, and they cannot be in the union expressions of $B_p$ and/or $B_q$, otherwise either $C_1$ or $C_2$ would belong to $B_p$ and/or $B_q$, therefore belonging to $4$ or $5$ of the $B_k$, which we have already shown leading to $B_1 \cap B_2 \cap B_3 \cap B_4 \cap B_5 \neq \emptyset$ (see the $n < 31$ case above). On the other hand, if neither $C_1$ nor $C_2$ belong to $B_p$ or $B_q$, we can recompute the number of $A_i$ shared by the union expressions of $B_p$ and $B_q$ as $s' = 2h - (n-6-2s) = 2s+2h-n+6 = 3s > s$ and reiterating the same reasoning, recomputing the number of sets shared by the union expressions of $B_p$ and $B_q$ again, we would have $s'' > s'$ and so on without limit, therefore there must exist a couple $C_u, C_v$ such that $C_u \cap D_v \neq \emptyset$ and then $B_1 \cap B_2 \cap B_3 \cap B_4 \cap B_5 \neq \emptyset$ always.

(Edit 2022-02-04: The above argument can probably be simplified because we just need one $C_1 = A_{i_1}$ occurring in three $B_k$ to make it work, and it exists for all $n > 6$ because $\frac{5}{2}\frac{n-1}{n-6}>2$. I think it works also with six $B_k$ unions because $\frac{6}{2}\frac{n-1}{n-7}>3$: in this case we have one $C_1 = A_{i_1}$ occurring in four $B_k$. However, for the case of seven $B_k$, we have $\frac{7}{2}\frac{n-1}{n-8}>4$ only for $n < 57$).

All the above should be rewritten in a more detailed and formal way, but I think (I hope) it is correct.

Now, extending the above for $B_1,B_2,B_3,B_4,B_5,B_6$ unions or more does not seem easy. Maybe it worked for $5$ because $3$ (the number of $B_j$, $B_k$, $B_l$) and $2$ (the number of $B_p$, $B_q$) are near to $5/2$. So it seems one should try to divide the $B_k$ into two groups of about the same number each. Intuitively, if we write the unions one below the other aligning vertically the same $A_i$, since the unions use $\frac{n+1}{2}$ sets, then the $A_i$ occur on about half of the positions horizontally, therefore they must occur about half of the times vertically too.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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