Take the 2-minute tour ×
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.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.