Skip to main content
Does -> Do, while this is on the front page
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Does Do 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 slightly 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 we can answer the original one too.

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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

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 slightly 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 we can answer the original one too.

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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

Do 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 slightly 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 we can answer the original one too.

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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

Rollback to Revision 17
Source Link

[Crossposted at math.stackexchange].

Originally I posted a slightly 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. 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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

[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.

[Crossposted at math.stackexchange].

Originally I posted a slightly 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 we can answer the original one too.

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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

Rollback to Revision 16
Source Link

[Crossposted at math.stackexchange].

Originally I posted a slightly 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. 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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

[Crossposted at math.stackexchange].

Originally I posted a slightly 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 we can answer the original one too.

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 intersection-closed ($\mathcal{F}$ must contain at least one instance of $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 modifying set multiplicites as needed by requirement $2$, 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.

[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.

Rollback to Revision 15
Source Link
Loading
Rollback to Revision 14
Source Link
Loading
Rollback to Revision 13
Source Link
Loading
Rollback to Revision 11
Source Link
Loading
Rollback to Revision 10
Source Link
Loading
deleted 45 characters in body
Source Link
Loading
Restricted the family to a plain set instead of a multiset
Source Link
Loading
added 3 characters in body
Source Link
Loading
added 217 characters in body
Source Link
Loading
added 56 characters in body
Source Link
Loading
added 300 characters in body
Source Link
Loading
Simplified the original question
Source Link
Loading
added 139 characters in body
Source Link
Loading
deleted 249 characters in body
Source Link
Loading
added 249 characters in body
Source Link
Loading
Clarified what intersection-closed is meant for a "multiset" family.
Source Link
Loading
Source Link
Loading