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.
 A: Correction, 15 June 2022. As noted in the comment by user120473 below, there was a significant gap in the argument given in my original answer; this only just came to my attention, and I have rewritten the answer to repair that gap.
Say that two subsets of $U$ are incomparable if neither is a subset of the other. Let $\mathscr{U}$ be any pairwise incomparable family of subsets of $U$. For any set $X$ and $k\in\Bbb N$ let $[X]^k$ be the family of subsets of $X$ of cardinality $k$.
Let $\mathscr{V}_0=\mathscr{U}$. Given $\mathscr{V}_k$ for some $k\in\Bbb N$, let $m_k=\max\{|V|:V\in\mathscr{V}_k\}$, and if $m_k>n$, construct $\mathscr{V}_{k+1}$ as follows. Let $\mathscr{M}_k=\{V\in\mathscr{V}_k:|V|=m_k\}$. Let $$\mathscr{P}_k=\{\langle V,S\rangle:V\in\mathscr{M}_k\text{ and }S\in[V]^{m_k-1}\}\,;$$ clearly $|\mathscr{P}_k|=m_k|\mathscr{M}_k|$. On the other hand, each $S\in\bigcup_{V\in\mathscr{M}_k}[V]^{m_k-1}$ is a subset of at most $$|U\setminus S|=2n-m_k+1$$ members of $\mathscr{M}_k$, so
$$m_k|\mathscr{M}_k|=|\mathscr{P}_k|\le(2n-m_k+1)\left|\bigcup_{V\in\mathscr{M}_k}[V]^{m_k-1}\right|\,,$$
and hence
$$\frac{\left|\bigcup_{V\in\mathscr{M}_k}[V]^{m_k-1}\right|}{|\mathscr{M}_k|}\ge\frac{m_k}{2n-m_k+1}\ge\frac{n+1}n>1\,,$$
since $m_k\ge n+1$. Thus, $\left|\bigcup_{V\in\mathscr{M}_k}[V]^{m_k-1}\right|>|\mathscr{M}_k|$.
Let $\mathscr{V}_{k+1}=(\mathscr{V}_k\setminus\mathscr{M}_k)\cup\bigcup_{V\in\mathscr{M}_k}[V]^{m_k-1}$. Clearly $|\mathscr{V}_{k+1}|>|\mathscr{V}_k|$, and I claim that $\mathscr{V}_{k+1}$ is a pairwise incomparable family. Clearly $\mathscr{V}_k^+\setminus\mathscr{M}_k$ and $\bigcup_{V\in\mathscr{M}_k}[V]^{m_k-1}$ are both pairwise incomparable. Suppose now that $V_0\in\mathscr{V}_k\setminus\mathscr{M}_k$ and $S\in[V]^{m_k-1}$ for some $V\in\mathscr{M}_k$. Then $V_0\setminus S\supseteq V_0\setminus V\ne\varnothing$, so $V_0\nsubseteq S$. And $|V_0|\le m_k-1=|S|$, so $|V_0\cap S|<|S|$, and therefore $S\nsubseteq V_0$, and $V_0$ and $S$ are incomparable.
Finally, $n\le m_{k+1}<m_k$, so there must be some $\ell\in\Bbb N$ such that $m_\ell\le n$; let $\mathscr{V}=\mathscr{V}_\ell$. Then $|\mathscr{V}|>|\mathscr{U}|$ unless $\ell=0$, in which case $|\mathscr{V}|=|\mathscr{U}|$. Let $\mathscr{W}=\{U\setminus V:V\in\mathscr{V}\}$; $\mathscr{W}$ is pairwise incompatible, $|\mathscr{W}|=|\mathscr{V}|$, and $|W|\ge n$ for each $W\in\mathscr{W}$. Thus, we can repeat the argument used to get $\mathscr{V}$ from $\mathscr{U}$ to get a pairwise incomparable family $\mathscr{X}$ such that $|\mathscr{X}|\ge|\mathscr{W}|=|\mathscr{V}|\ge|\mathscr{U}|$, and $\mathscr{X}\subseteq[U]^n$. But then $|\mathscr{U}|\le|\mathscr{X}|\le\left|[U]^n\right|=\binom{2n}n$, so $\binom{2n}n$ is indeed an upper bound on the size of any family of pairwise incomparable subsets of $U$. And since $[U]^n$ is itself a pairwise incomparable family of cardinality $\binom{2n}n$, this upper bound is sharp.
A: 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.
A: The answer: $\binom{2n}{n}$.
To show it's a lower bound: obviously if $A$ is the collection of all subsets of size $n$, then it satisfies the condition, and $A$ has $\binom{2n}{n}$ elements.
To show it's an upper bound: suppose $A$ is such a collection.  Now consider the set of all maximal chains of subsets of $U$ (e.g. $\{ \emptyset, \{ 3 \}, \{ 1, 3 \}, \{ 1, 3, 4 \}, \{ 1, 2, 3, 4 \} \}$ is a maximal chain of subsets of $\{ 1, 2, 3, 4 \})$.  This set of maximal chains has cardinality $(2n)!$ since it's easy to put it in bijection with the set of orderings of the elements of $U$, by associating a maximal chain with the sequence in which elements are added to the elements of the chain.  Similarly, any subset $X$ of $U$ with $k$ elements is in $k! (2n-k)!$ of these maximal chains: considering the equivalent ordering of elements of $U$, we can choose the first $k$ elements in any order from $X$, and then the last $2n-k$ elements in any order from $U \setminus X$.  Finally, note that no two distinct elements of $A$ can be in the same maximal chain, by the hypothesis that neither is a subset of the other.  Putting these observations together, we conclude:
\begin{equation*}
(2n)! \ge \sum_{X \in A} |X|! (2n - |X|)! \ge |A| \cdot \left( \mathrm{min}_{0 \le k \le 2n} ~ k! (2n-k)! \right) .
\end{equation*}
Therefore,
\begin{equation*}
|A| \le \frac{(2n)!}{\mathrm{min}_{0 \le k \le 2n} ~ k! (2n-k)!} =
\mathrm{max}_{0 \le k \le 2n} \frac{(2n)!} {k! (2n-k)!} =
\mathrm{max}_{0 \le k \le 2n} \binom{2n}{k} = \binom{2n}{n}.
\end{equation*}
Actually, it's trivial to generalize this proof to $U$ of any size $n$ (whether even or odd), in which case the answer is $\binom{n}{\lfloor n/2 \rfloor}$.  (Though this proof does leave open the question of whether it's possible to achieve the upper bound in the case $n$ is odd, using a mixture of subsets of sizes $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$.)
