Return to Question

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.

(I have posted a corrected version of this question. The limit $\lceil n/2 \rceil$ must be replaced with $\lceil (n+1)/2 \rceil$.)

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subset \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.