# Proving that some intersection of $5$ (or more) unions is non-empty for a union-closed family of sets

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.

• 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? Jan 26, 2022 at 17:32
• @LSpice thank you for correcting, I have edited the question and I hope it is clearer now. Jan 26, 2022 at 18:33

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.