8
$\begingroup$

[Now crossposted at math.stackexchange.]

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 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}$.

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). This is because every non-abundant element belongs to at most $\lceil n/2 \rceil - 1$ sets of $\mathcal{F}$, therefore there exist $n - \lceil n/2 \rceil + 1$ sets that do not contain it. On the other hand, every abundant element belongs to at least $\lceil n/2 \rceil$ sets of $\mathcal{F}$, therefore every union of $n - \lceil n/2 \rceil + 1$ sets must contain it.

We can consider the case when there exists a non-empty set $A$ in $\mathcal{F}$ which is a subset of $|\mathcal{G}|-m$ sets in $\mathcal{G}$, but no set in $\mathcal{F}$ is a subset of $|\mathcal{G}|-m+1$ sets in $\mathcal{G}$. I think it can be proven that for $0 \le m \le 2$ there must exist at least one abundant element. The proofs exploit the fact that the sets in $\mathcal{G}$ that do not have $A$ as subset must share some of the other sets in $\mathcal{F}$ as subsets. For example for $m=1$ the shared subsets are at least $\lfloor (n+1)/2 \rfloor$, for $m = 2$ it can be shown that they are at least $|\mathcal{G}|+1$.

Proof for $m=1$: By definition of $\mathcal{G}$ and $A$, when $m=1$ there is one and only one set in $\mathcal{G}$ that does not include $A$. This set is the union of at least $\lceil(n+1)/2\rceil$ sets in $\mathcal{F}$. If no element is abundant, and $\emptyset \in \mathcal{F}$, then there are at least $\lceil(n-1)/2\rceil$ non-empty sets with empty intersection with $A$. It is easy to see that the unions of one of these sets and $A$ are all different and different from the operands, therefore we get in total $\lceil(n-1)/2\rceil \times 1 + \lceil(n-1)/2\rceil + 1 + 1 = n + 1 > n$ sets (where the last $+1$ is for $\emptyset$), absurd. If no element is abundant, and $\emptyset \not\in \mathcal{F}$, then there are at least $\lceil(n+1)/2\rceil$ non-empty sets with empty intersection with $A$. The unions of one of these sets and $A$ are all different and different from the operands, therefore we get in total $\lceil(n+1)/2\rceil \times 1 + \lceil(n+1)/2\rceil + 1 = n + 2 > n$ sets, absurd. Therefore there is at least one abundant element in $A$.

Proof for $m=2$: By definition of $\mathcal{G}$ and $A$, when $m=2$ there are exactly two sets in $\mathcal{G}$ that do not include $A$. Let them be $G_1$ and $G_2$. They are the union of at least $\lceil(n+1)/2\rceil$ sets in $\mathcal{F}$. Since $\mathcal{G}$ is minimal, $G_1$ and $G_2$ are also the union of at least $\lceil(n-1)/2\rceil$ sets in $\mathcal{F} \setminus (\mathcal{G} \cup \{ U(\mathcal{F}), A \})$ and $G_1$,$G_2$ respectively, where $U(\mathcal{F})$ is the union of all sets in $\mathcal{F}$ (the universe). The size of $\mathcal{F} \setminus (\mathcal{G} \cup \{ U(\mathcal{F}), A \})$ is $n - |\mathcal{G}| - 2$, therefore there are at least $|\mathcal{G}|+1 \le 2\lceil(n-1)/2\rceil -(n - |\mathcal{G}| - 2)$ sets of $\mathcal{F}$ that are included in both $G_1$ and $G_2$. If no element is abundant, then there are at least $|\mathcal{G}|$ non-empty subsets of $G_1$ and $G_2$, with empty intersection with $A$. It is easy to see that the unions of one of these sets and $A$ are all different and different from the operands. The number of those unions is $|\mathcal{G}|$. None of them can be equal to $G_1$ or $G_2$ otherwise $A$ would be a subset of one or both of them and we would fall back in the case $m=1$ or $m=0$. They could be equal to $U(\mathcal{F})$ or be a set in $\mathcal{G} \setminus \{G_1, G_2\}$. But $|U(\mathcal{F}) \cup (\mathcal{G} \setminus \{G_1, G_2\})| = |\mathcal{G}| - 1$, therefore there exists a non-empty set $F_1 \in \mathcal{F}$, $F_1 \not= U(\mathcal{F})$, $F_1 \not\in \mathcal{G}$, such that $F_1 \not\subseteq G_1$ and $F_1 \not\subseteq G_2$, otherwise again $A$ would be a subset of $G_1$ and/or $G_2$, and we would fall back in the case $m=1$ or $m=0$. Then we can replace $\mathcal{F} \setminus (\mathcal{G} \cup \{ U(\mathcal{F}), A \})$ with $\mathcal{F} \setminus (\mathcal{G} \cup \{ U(\mathcal{F}), A, F_1 \})$ above to deduce that there are at least $|\mathcal{G}|+1$ non-empty subsets of both $G_1$ and $G_2$, with empty intersection with $A$, and continue indefinitely with the same step, absurd. Therefore there is at least one abundant element in $A$.

Now the case $m=3$. Extending this answer I obtained as an example the following family depicted through its Hasse diagram (lattice) ordered by inclusion ($0$ is the empty set):

Example Hasse diagram for the case m=3

And the following table lists for all sets in $\mathcal{G}$ the sets in $\mathcal{F}$ which are subsets of them, with a $1$ if included, $0$ if not included. The set number is shown with digits written vertically:

    00000000001111111111222222222233333333334
    01234567890123456789012345678901234567890
    -----------------------------------------
G1: 11111111111111111110000000001001000000000
G2: 11111111111111111110000000001000100000000
G3: 11111111111111111110000000001000010000000
G4: 11111111110000000001111111110100001000000
G5: 11111111110000000001111111110100000100000
G6: 11111111110000000001111111110100000010000
G7: 10000000001111111111111111110010000001000
G8: 10000000001111111111111111110010000000100
G9: 10000000001111111111111111110010000000010

(if you want to experiment, I have written a python script to build the above table and graph; the input lists all inclusions in the family).

If we take $A = F_1$ we have $21$ "shared" sets in $\mathcal{F}$ which are included in $G_7$, $G_8$ and $G_9$.

MY QUESTION: is it possible to build an example for $m=3$ where, for any $A$ as defined above, the sets in $\mathcal{G}$ that do not have $A$ as subset share less than $|\mathcal{G}|$ of the other sets in $\mathcal{F}$ as subsets? Is it possible to determine the minimum number of shared subsets?

Some thoughts:

The logical and of any two columns of the table must belong to the table too. Supposing that there does not exist an example as required by the question, we can formulate this conjecture which is equivalent to the problem here, but with weaker hypotheses.

In case all elements of the family belong to exactly $\lfloor (n-1)/2 \rfloor$ sets in $\mathcal{F}$ then the size of $\mathcal{G}$ is equal to the number of elements and every $0$ (respectively $1$) in the table built like in the above means the element corresponding to the row belongs (respectively do not belong) to the set represented by the column. Then the case $m=1$ means that the smallest set in $\mathcal{F}$ is a singleton set, while the case $m=2$ means that the smallest set in $\mathcal{F}$ has two elements. Both cases easily imply there exists an abundant element. However in general that is not true for a smallest set with three elements (see this example).

Without using more than in $m = 2$ the union-closed property, we cannot prove that there is some "overlapping" of the three rows not including $A$, when $n$ is large enough (see here and here).

For a particular case of $m$, and $\emptyset \in \mathcal{F}$, the equation $(|\mathcal{G}|-m)(n-|\mathcal{G}|-2) \ge |\mathcal{G}|\lfloor(n-3)/2\rfloor$ must be satisfied. This implies that when $m = 2$, $n \ge 20$ (and in fact the example here has $n=29$), when $m = 3$, $n \ge 32$ (and in fact the example in this question has $n=41$), when $m = 4$, $n \ge 44$.

$\endgroup$

1 Answer 1

1
$\begingroup$

Thanks to this answer to a related question, I was able to build an example where there is not even one couple of non-empty sets $A, B$ such that $A \in G$ or $B \in G$ for all $G \in \mathcal{G}$.

The example is built by taking the union-closed family generated by the lines in the Fano plane with the addition of the empty set, then adding in the corresponding lattice a $14$-element chain between each atom (a Fano plane line) and $0$ (the empty set).

The resulting lattice $L$ can then be converted back to a union-closed family by setting $\mathcal{F} = \{S_x :\, x\in L\}$ and $S_x=\{y\in L\, :\, y\not\geq x,\, y \not= a \land b\}$, i.e. $y$ must be meet-irreducible (see here).

$\mathcal{F}$ has $135$ sets and $105$ elements. The number of elements could be reduced to $35$ by replacing the $14$-element chains with something similar to a power set.

This is a picture of its Hasse diagram (lattice):

enter image description here

And the following table lists for all sets in $\mathcal{G}$ the sets in $\mathcal{F}$ which are subsets of them, with a $1$ if included, $0$ if not included. The set number is shown with digits written vertically:

    000000000000000000000000000000100000000000000100000000000000100000000000000100000000000000100000000000000111111111111111111111111111111
    000000000011111911111222222222023333333333444044444445555555055566666666667077777777788888088888999999999000001111111122222233311222323
    012345678901234956789012345678090123456789012134567890123456278901234567890312345678901234456789012345678567890123456901256701378384294
    ---------------------------------------------------------------------------------------------------------------------------------------
G1: 111111111111111111111111111111111111111111111100000000000000011111111111111100000000000000000000000000000011010010100010000000010000000
G2: 111111111111111111111111111111100000000000000011111111111111100000000000000000000000000000011111111111111110100101001000000100001000000
G3: 111111111111111100000000000000011111111111111100000000000000000000000000000011111111111111111111111111111101001100000001100000100100000
G4: 111111111111111100000000000000000000000000000011111111111111111111111111111111111111111111100000000000000000111000000000011010000010000
G5: 100000000000000011111111111111111111111111111111111111111111100000000000000011111111111111100000000000000000000011010101001000000001000
G6: 100000000000000011111111111111100000000000000000000000000000011111111111111111111111111111111111111111111100000000111000000011100000100
G7: 100000000000000000000000000000011111111111111111111111111111111111111111111100000000000000011111111111111100000000000110110101000000010

There isn't any couple of columns (excluding the empty set column) without two zeroes in the same row.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .