# Conjecture about union-closed families of sets - attempt 3

Version 2 of the conjecture was disproved. In this version 3 of the conjecture I am adding a further requirement to obtain from $$\mathcal{H}$$ a "minimal" family $$\mathcal{G}$$.

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+1)/2 \rceil = n - \lceil n/2 \rceil + 1$$ of the sets in $$\mathcal{F}$$.

Let $$\mathcal{G} \subseteq \mathcal{H}$$ be the family of all sets in $$\mathcal{H}$$ which are not a proper superset of another set in $$\mathcal{H}$$. Note that the intersection of all sets in $$\mathcal{G}$$ is equal to the intersection of all sets in $$\mathcal{H}$$.

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

Note that the intersection of all sets in $$\mathcal{G}$$ gives the set of all elements of $$U(\mathcal{F})$$ that belong to at least $$\lceil n/2 \rceil$$ sets of $$\mathcal{F}$$ (so-called abundant elements, explanation here). The same is true for the intersection of all 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 the counterexample for version 2 of the conjecture (satisfied with $$| \mathcal{G} | - 1$$ sets). See also example 2 (it is this one), example 3 (similar to this one).

Counterexample. Start with an $$8$$-element Boolean algebra. Insert a $$5$$-element chain between each atom and $$0$$. Insert a $$2$$-element antichain between each dual atom and $$1$$. Call the resulting lattice $$\mathcal F$$.

Now $$|\mathcal F|=29$$, and $$\mathcal G$$ consists of the $$6$$ elements which were inserted just below $$1$$. No element except $$0$$ is contained in more than $$4$$ elements of $$\mathcal G$$.

• I don't want to waste your time, but do you feel it might be possible to build examples with $n$ sets and less than $n/2$ (or $n/4$) elements? Commented May 11 at 16:13
• I have no idea.
– bof
Commented May 11 at 18:57

For reference, I think I managed to build @bof example (software check here).

$$\mathcal{F}$$ is :

$$F_{1} = \{1, 2, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{2} = \{1, 2, 7, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{3} = \{1, 2, 7, 8, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{4} = \{1, 2, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{5} = \{1, 2, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{6} = \{1, 2, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{7} = \{3, 4, 7, 8, 9, 10, 11, 17, 18, 19, 20, 21\} \\ F_{8} = \{3, 4, 7, 8, 9, 10, 11, 12, 17, 18, 19, 20, 21\} \\ F_{9} = \{3, 4, 7, 8, 9, 10, 11, 12, 13, 17, 18, 19, 20, 21\} \\ F_{10} = \{3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21\} \\ F_{11} = \{3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21\} \\ F_{12} = \{3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{13} = \{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\} \\ F_{14} = \{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17\} \\ F_{15} = \{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18\} \\ F_{16} = \{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19\} \\ F_{17} = \{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20\} \\ F_{18} = \{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{19} = \{1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{20} = \{1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{21} = \{1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{22} = \{1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{23} = \{1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{24} = \{1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{25} = \{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{26} = \{1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{27} = \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F_{28} = \emptyset \\ F_{29} = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\}$$

$$\mathcal{G}$$ is:

$$G_{1} = \{1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ G_{2} = \{1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ G_{3} = \{1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ G_{4} = \{1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ G_{5} = \{1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ G_{6} = \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\}$$

The complement $$\mathcal{F}^c$$ intersection-closed family is:

$$F^c_{1} = \{3, 4, 5, 6, 7, 8, 9, 10, 11\} \\ F^c_{2} = \{3, 4, 5, 6, 8, 9, 10, 11\} \\ F^c_{3} = \{3, 4, 5, 6, 9, 10, 11\} \\ F^c_{4} = \{3, 4, 5, 6, 10, 11\} \\ F^c_{5} = \{3, 4, 5, 6, 11\} \\ F^c_{6} = \{3, 4, 5, 6\} \\ F^c_{7} = \{1, 2, 5, 6, 12, 13, 14, 15, 16\} \\ F^c_{8} = \{1, 2, 5, 6, 13, 14, 15, 16\} \\ F^c_{9} = \{1, 2, 5, 6, 14, 15, 16\} \\ F^c_{10} = \{1, 2, 5, 6, 15, 16\} \\ F^c_{11} = \{1, 2, 5, 6, 16\} \\ F^c_{12} = \{1, 2, 5, 6\} \\ F^c_{13} = \{1, 2, 3, 4, 17, 18, 19, 20, 21\} \\ F^c_{14} = \{1, 2, 3, 4, 18, 19, 20, 21\} \\ F^c_{15} = \{1, 2, 3, 4, 19, 20, 21\} \\ F^c_{16} = \{1, 2, 3, 4, 20, 21\} \\ F^c_{17} = \{1, 2, 3, 4, 21\} \\ F^c_{18} = \{1, 2, 3, 4\} \\ F^c_{19} = \{5, 6\} \\ F^c_{20} = \{6\} \\ F^c_{21} = \{5\} \\ F^c_{22} = \{3, 4\} \\ F^c_{23} = \{4\} \\ F^c_{24} = \{3\} \\ F^c_{25} = \{1, 2\} \\ F^c_{26} = \{2\} \\ F^c_{27} = \{1\} \\ F^c_{28} = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\} \\ F^c_{29} = \emptyset$$

• Wouldn't it be easier (on the reader too) to just list the complements of those sets? For that matter, it might be better to consider the whole problem in terms of intersection-closed families. Moreover, intersection-closed families seem to come up more often in practice, e.g., the subalgebras of a (general) algebra.
– bof
Commented May 12 at 1:01
• I have added the complement intersection-family and removed the three elements belonging to all sets except the empty set. Now the family is independent so I presume that the number of elements ($21$) is minimal for the given lattice. Commented May 13 at 13:30