# Find maximal number of subsets of the set $U$ such that no one is a subset of another

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.

-

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.

-
Well done. I was groping for this, and had some of the ideas, but gave up. –  bgins Apr 8 '12 at 23:47
I cannot comment yet, so I have to put it as an answer. The answer of Brian M. Scott is correct, but it is not a proof. Quoting: "It’s not hard to check that V is pairwise incomparable, and clearly |V|≥|U|." is the problematic part. It is rather clear that V is pairwise incomparable, but one has to prove that |V|≥|U|, which is the core of the reasoning here. The strategy is easy: replace big sets with their n-element subsets, do an inverse, replace big sets again and voilà. But each step requires a proof and the |V|≥|U| part is virtually the only one that needs some kind of argument. "Clearly" –  user120473 Jan 10 at 19:13
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.