Combinatorics – Maximal Number of Subsets with No Subset Relation

Question

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.

Answer 1

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.