Bounds on chain size for union-closed families

23 Views Asked by At

Let $X$ be a finite set with at least one element and let $\eta$ be a family of subsets of $X$ such that $$A\cup B\in\eta\text{ for every }A,B\in\eta$$ $$X=\bigcup_{A\in\eta}A$$ $$\text{For every }x,y\in X\text{ there exists }A\in\eta\text{ which contains one but not the other}$$ Now, for any $A\in\eta$ define $$u_A=\{\,B\in\eta\;:\; B<A\,\}$$ $$u^A=\{\,B\in\eta\;:\; A<B\,\}$$

where $A<B$ is short for $A\subseteq B$ and $A\ne B$. The question is how big/small can $|u_A|+|u^A|$ be in terms of $|X|$ and $|\eta|$ ?

Obviously $|u_A|+|u^A|\le|\eta|-1$ and this is best possible (when $\eta$ is totally ordered and when $A=X$) but how small can it be? If $u_A$ is small then $A$ is small too, and then $u^A$ is big, and viceversa. This is why I expect at least a very bad bound like $$|u_A|+|u^A|\ge|X|$$ I suspect the size of $A$ might play a role in the bound. For example, if $X=\{1,2,\dots,N\}$ and $\eta=\mathcal{P}(X)$ then $|u_A|+|u^A|$ is the lowest when $|A|=N/2$.

Also for any set $B\in\eta\setminus(u_A\cup u^A)$ we have $A\cup B\in u^A$ so $|\eta\setminus(u_A\cup u^A)|$ and $|u^A|$ should be of similar size, bearing in mind the cancellations $A\cup B=A\cup C$

That said, I can't rigorously prove any of this.

Thanks!

1

There are 1 best solutions below

1
On

I found an easy proof for the lower bound $$|u^A|+|u_A|\ge |X|-1$$ Let $\eta_A=\{A\}\cup u^A\cup u_A$. Then $\eta_A$ satisfies the same properties as $\eta$, most importantly that $\eta_A$ "separates" points (i.e for any two $x,y\in X$ there exists $B\in\eta_A$ which contains one but not the other). Now because of this I know that $|\eta_A|=1+|u_A|+|u^A|\ge|X|$

The same example of the link proves that this bound is best possible in terms of $|X|$