3
$\begingroup$

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.

3 Answers 3

6

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.

  • 0
    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"2014-01-10
2

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|, it is contained in one.

0

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$.)