Are there subsets of every size in a union-closed family?

49 Views Asked by At

Let $X$ be a finite set with at least one element and $\eta\subseteq\mathcal{P}(X)$ a union-closed collection of subsets of $X$ such that $$X=\bigcup_{A\in\eta}A$$ $$\forall x,y\in X\text{ there exists }A\in\eta\text{ such that }A\text{ contains one of them but not the other}$$ $$\emptyset\notin\eta$$ and let $q=\min_{A\in\eta}|A|$

Is it true that for every $q\le k\le|X|$ there exists $A\in\eta$ such that $|A|=k$ ? It is obviously true for $k=q$ and $k=|X|$, and I also know it to be true for $k=|X|-1$. I'm trying to use a similar argument with $$k_{min}=\min\{\,k\;:\;\nexists A\in\eta\;\;\text{with}\;\;|A|=k\,\}$$ $$k_{max}=\max\{\,k\;:\;\nexists A\in\eta\;\;\text{with}\;\;|A|=k\,\}$$ because then for every $q\le k<k_{min}$ and $k_{max}<k\le|X|$ there exists an $A\in\eta$ with $|A|=k$ and then contradicting the minimality/maximality, but the proof seems elusive. There might be a nice, simple counterexample but I can't find it.

If it were false, I would like to know how you came up with a counterexample and if a weaker result, like $k_{min}=k_{max}$ or $k_{max}-k_{min}\le q$, could be possible.

Thanks!

1

There are 1 best solutions below

3
On BEST ANSWER

A convoluted counterexample: Let $n$ be some large even integer, say $n\geq 100$. Let $A = 2^{[n]} \setminus \{\emptyset\}$. Let $X$ be the set $$ X = \{ x_1,\ldots, x_n, y_1,\ldots, y_n \} .$$ Let $\eta$ be the following set of subsets of $X$: For any $B\in A$, let $$ \{ y_i \mid i\in B \} \cup \{x_i \mid i\in B\} $$ be included in $\eta$. Also, for all $z\in X$, let $X\setminus \{z\}$ be included in $\eta$. Let no other sets be included in $\eta$. The inclusion of the sets $X\setminus \{z\}$ means that any two elements are separated by a set in $\eta$. Also, the union of any two sets in $\eta$ is again in $\eta$. Moreover, $\eta$ contains sets of size $2,4,\ldots, 2n-2, 2n-1,2n$. Notice that the only set of odd size that $\eta$ contains are the sets $X\setminus \{z\}$ of size $2n-1$. The family $\eta$ does not contains sets of size $3,5,...2n-3$.