An upper bound on the size of antichain

Question

Let $P$ be a collections of subsets of the set {1,2, ..., n} such that $P$ is an anti-chain and cardinality of sets in $P$ is strictly less than $k$, where $1 \leq k \leq n$? Can we get an upper bound on the cardinality of $P$ in terms of $k$?

Answer 1

Let $\mathcal{P}$ be an anti-chain over the universe $[n]:= \{1, \ldots, n\}$, and let $a_t$ denote the number of elements in it of cardinality $t$. Suppose further that for some $k \in [n]$, $a_t = 0$ for all $t \geq k$.

If $k > \lfloor\frac{n}{2} \rfloor$, then Sperner's bound is optimal. Consider the anti-chain of sets of size $\lfloor\frac{n}{2} \rfloor$ in $[n]$.

Otherwise, by the Lubell–Yamamoto–Meshalkin inequality, \begin{align} \sum_{t = 0}^{n} \frac{a_t}{\binom{n}{t}} \leq 1. \end{align} For the anti-chain in question, this translates to \begin{align} \sum_{t = 0}^{k-1} \frac{a_t}{\binom{n}{t}} \leq 1. \end{align} From this and the monotonicity of the binomial coefficient below the halfway point, it follows that \begin{align} \sum_{t = 0}^{k-1} \frac{a_t}{\binom{n}{k-1}} \leq 1. \end{align} Hence, the total number of elements in $\mathcal{P}$ cannot exceed $\binom{n}{k-1}$. This bound is seen to be optimal by considering the set of all $(k-1)$-sets in $[n]$.