Skip to main content
added 238 characters in body
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).

Is it possible to prove or disprove that, for any possible choice of $\mathcal{F}$, there exist $A, B, C \in \mathcal{F}$ such that $A \cap B \cap C = \emptyset$? In case they must exist, is it possible to get a lower bound for the number of such unordered triplets?

Note that if we consider couples instead of triplets, it is possible to build counterexamples where there does not exist any $A, B \in \mathcal{F}$ such that $A \cap B = \emptyset$ (see here).

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).

Is it possible to prove or disprove that, for any possible choice of $\mathcal{F}$, there exist $A, B, C \in \mathcal{F}$ such that $A \cap B \cap C = \emptyset$? In case they must exist, is it possible to get a lower bound for the number of such unordered triplets?

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).

Is it possible to prove or disprove that, for any possible choice of $\mathcal{F}$, there exist $A, B, C \in \mathcal{F}$ such that $A \cap B \cap C = \emptyset$? In case they must exist, is it possible to get a lower bound for the number of such unordered triplets?

Note that if we consider couples instead of triplets, it is possible to build counterexamples where there does not exist any $A, B \in \mathcal{F}$ such that $A \cap B = \emptyset$ (see here).

Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23

Number of disjoint set triplets in a union-closed family

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).

Is it possible to prove or disprove that, for any possible choice of $\mathcal{F}$, there exist $A, B, C \in \mathcal{F}$ such that $A \cap B \cap C = \emptyset$? In case they must exist, is it possible to get a lower bound for the number of such unordered triplets?