0
$\begingroup$

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 minimal 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}$. In this question I gave proofs that for $0 \le m \le 2$ there must exist at least one abundant element.

Let $\mathcal{G}^\star(X) = \{G \in \mathcal{G} : X \in G\}$ and $\mathcal{G}^{\star\star}(\mathcal{I}) = \cap_{X \in \mathcal{I}} \space \mathcal{G}^\star(X)$.

QUESTION: Is it possible to build an example union-closed family $\mathcal{F}$ for which $m \ge 3$, and there does NOT exist three disjoint sub-families $\mathcal{F}_1, \mathcal{F}_2, \mathcal{F}_3 \subset \mathcal{F}$ such that $\mathcal{G}^{\star\star}(\mathcal{F}_1) \cup \mathcal{G}^{\star\star}(\mathcal{F}_2) \cup \mathcal{G}^{\star\star}(\mathcal{F}_3) = \mathcal{G}$, $\mathcal{G}^{\star\star}(\mathcal{F}_i) \cap \mathcal{G}^{\star\star}(\mathcal{F}_j) \not= \mathcal{G}^{\star\star}(\mathcal{F}_1),\mathcal{G}^{\star\star}(\mathcal{F}_2),\mathcal{G}^{\star\star}(\mathcal{F}_3)$, $1 \le i \lt j \le 3$, and $|\mathcal{G}^{\star\star}(\mathcal{F}_1)|+|\mathcal{G}^{\star\star}(\mathcal{F}_2)|+|\mathcal{G}^{\star\star}(\mathcal{F}_3)|+(|\mathcal{G}^{\star\star}(\mathcal{F}_1)||\mathcal{G}^{\star\star}(\mathcal{F}_2)||\mathcal{G}^{\star\star}(\mathcal{F}_3)|)^{1/3} \ge n$ ?

A possibility could be to try to extend the example in the linked question, where the family was generated by a Fano plane, and for any two non-empty sets $X,Y \in \mathcal{F}$ we have $\mathcal{G}^\star(X) \cup \mathcal{G}^\star(Y) \not= \mathcal{G}$, i.e. find a family such that for any three non-empty sets $X,Y,Z \in \mathcal{F}$ we have $\mathcal{G}^\star(X) \cup \mathcal{G}^\star(Y) \cup \mathcal{G}^\star(Z) \not= \mathcal{G}$.

On the other hand, using this method it is possible to show that a family with the requirements (removing "NOT" in the question) must have abundant elements.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .