A question about sizes of antichains

ceiling-and-floor-functionscombinatoricselementary-set-theoryextremal-combinatorics

Background

While working with antichains, set families and Sperner's theorem I came across an exercise which asked the following:

If $A_1,\dots,A_k$ are disjoint antichains of the set $\mathcal P([n])$, then
$$|A_1|+\dots+|A_k|\leq \sum_{i=-\lfloor \frac{k}{2}\rfloor}^{\lfloor \frac{k-1}{2}\rfloor}\binom{n}{\lfloor\frac{n+i}{2}\rfloor}.$$

Here $[n]$ denotes the set of the first $n$ positive integers.

My problem

I am completely stumped by this problem because of the floor functions in particular. I can't see what is the right hand side of the inequality counting.

I can see however a couple of things:

  • The amount on the left: $|A_1|+\dots+|A_k|$ is precisely the size of $\displaystyle \bigcup_{j=1}^k A_j$ because of the fact that the sets are disjoint.
  • I know that by Sperner's theorem, the size of an antichain is bounded by $\binom{n}{\lfloor\frac{n}{2}\rfloor}$. So the sum of the sizes is at most $k$ times such quantity. But I cannot compare $k\binom{n}{\lfloor\frac{n}{2}\rfloor}$ with the sum on the RHS.
  • I also know about a couple of results, Dilworth and Mirsky's theorems. But Mirksky's claim is that we need at least an amount of antichains equal to the number of elements in the longest chain to cover $\mathcal P([n])$. And we don't even know if our sets form a covering.

In Essence:

  • How can I interpret the sum on the right hand side of the inequality? Can it be written more easily? What is it counting?

Any hint, or indication on how to approach this problem will be kindly received.

Best Answer

The RHS is the sum of the sizes of the $k$ largest ranks of $2^{[n]}$, which is equal to the sum of the middle $k$ values of the $n^\text{th}$ row of Pascal's triangle. That is, in plain English, your inequality says

The union of any $k$ disjoint antichains in $2^{[n]}$ is at most as large as the union of the $k$ largest ranks in $2^{[n]}$.

This property is known as the $k$-Sperner property. When $k=1$, this is just the usual Sperner property of $2^{[n]}$.

It should be obvious how to obtain equality in your inequality; let $A_1$ be the set of subsets with cardinality $m:=\lfloor n/2\rfloor$, let $A_2$ be the sets with cardinality $m+1$, $A_3$ with size $m-1$, $A_4$ with size $m+2$, etc.

Now you should at least understand the intuition behind the question. Usually, you prove the Sperner property for $2^{[n]}$ by finding a series of "order matchings." Letting $P_i$ be the collection of subsets of $[n]$ with size $i$, order matchings are maps $f_i:P_i\to P_{i+1}$ which satisfy $S\subseteq f(S)$ for all $S\in P_i$ when $i<\lfloor n/2\rfloor$, and maps $f_i:P_{i+1}\to P_i$ which satisfy $f(S)\supseteq S$ for all $S\in P_{i+1}$ when $i\ge \lfloor n/2\rfloor$. Given an antichain $A$, by applying enough of these order-matchings to the elements of $A$, you get an injection from $A$ to the largest level of $2^{[n]}$. This same proof can be modified to when you have a disjoint collection of $k$ antichains, so get an injection from this union to the set of the $k$ largest levels of $2^{[n]}$.

Related Question