Largest collection of subsets of $\{1,2,\ldots,n\}$ such that no set is a subset of another.

169 Views Asked by At

Given a set $U$ of $n$ elements, consider a collection $\mathcal{C}$ of subsets of $U$ such that for all $A,B \in \mathcal{C}$, $A \not\subset B$ and $B \not\subset A$.

What is the largest possible size (or a good upper bound) of $\mathcal{C}$.

2

There are 2 best solutions below

0
On BEST ANSWER

This is just Sperner's theorem, so the maximum is $${n\choose [{n\over 2}]}.$$

2
On

If we pick $k$ with $0\le k\le n$ and let $\mathcal C$ be all the size $k$ subsets of $U$ then $\mathcal C$ satisfies your condition.

Can we do better? What does the Lubell-Yamamoto-Meshalkin inequality tell us?