The set $U$ contains $2n$ elements. Let's select $k$ subsets such that no one is a subset of another. Which $k$ is maximal?
I heard that the maximum is reached when all of the $k$ subsets have cardinality $n$. But can't prove it.
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|
Say that two subsets of $U$ are incomparable if neither is a subset of the other, and say that a subset of $U$ is large if it has more than $n$ elements. Let $\mathscr{U}$ be any pairwise incomparable family of subsets of $U$. For any set $X$ let $[X]^n$ be the family of subsets of $X$ of cardinality $n$. Let $$\mathscr{V}=\{S\in\mathscr{U}:|S|\le n\}\cup\bigcup\left\{[S]^n:S\in\mathscr{U}\text{ and }|S|>n\right\}\;;$$ in case that’s a little opaque, $\mathscr{V}$ is simply the result of replacing each large member of $\mathscr{U}$ by its $n$-element subsets. It’s not hard to check that $\mathscr{V}$ is pairwise incomparable, and clearly $|\mathscr{V}|\ge|\mathscr{U}|$. Now let $\mathscr{W}=\{U\setminus V:V\in\mathscr{V}\}$; $\mathscr{W}$ is pairwise incomparable, $|\mathscr{W}|=|\mathscr{V}|$, and $|W|\ge n$ for each $W\in\mathscr{W}$. Repeat the process used to go from $\mathscr{U}$ to $\mathscr{V}$: let $$\mathscr{X}=\Big(\mathscr{W}\cap[U]^n\Big)\cup\bigcup\left\{[W]^n:W\in\mathscr{W}\setminus[U]^n\right\}\;.$$ Then $|\mathscr{X}|\ge|\mathscr{W}|\ge|\mathscr{U}|$, and $\mathscr{X}\subseteq[U]^n$, so $|\mathscr{U}|\le\left|[U]^n\right|=\dbinom{2n}n$, so $\dbinom{2n}n$ is indeed an upper bound on the size of any family of pairwise incomparable subsets of $U$. Since $[U]^n$ is a pairwise incomparable family of cardinality $\dbinom{2n}n$, this upper bound is sharp. |
|||
|
|
There are ${2n\choose m}$ subsets of $U$ of size $m$; these add to $2^{2n}$ over $0\le m\le 2n$ as we know. If we choose all subsets of the same size, $m$, then none is a subset of another; call this collection of subsets $U_m$. But $|U_m|={2n\choose m}$ attains its maximum at the middle binomial coefficient, when $m=n$. It only remains to check whether another system of non-uniformly sized subsets of $U$ can be larger. As a partial result, note that we cannot add any other subset $S$ of $U$ to $U_m$, for if $|S|>m$, $S$ contains an $m$-element subset, while if $|S|<m$, it is contained in one. |
|||
|
|
