Skip to main content
14 of 20
Rollback to Revision 11

Does there exist at least two sets whose union gives the universe in a certain intersection-closed family of sets?

[Crossposted at math.stackexchange].

Originally I posted a more complicated version of this question. I decided to edit and put it in this simplified form, because I think that if we can answer this question then maybe we can answer the original one too.

Let $\mathcal{F}$ be a family of $n$ finite sets. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is intersection-closed ($\mathcal{F}$ must contain $A \cap B$ for any $A,B \in \mathcal{F}$);
  2. every element in $U(\mathcal{F})$ belongs to at least $\lceil (n-1)/2 \rceil$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).

Is it possible to prove that, for any possible choice of $\mathcal{F}$, there exist $A, B \in \mathcal{F}$ such that $A \cup B = U(\mathcal{F})$?

Maybe a sketch of a possible approach could be starting from the power set $\mathcal{P}(U(\mathcal{F}))$, then try to remove an intersection irreducible set to obtain another intersection-closed family, and show that we cannot do that without removing all intersection irreducible sets of the same size. Alternatively, start from an intersection-closed family without any $A,B$ such that $A \cup B = U(\mathcal{F})$, then show that if we add sets still without such $A, B$, then condition $2$ keeps being unsatisfied.