= Solution
\b[The <LYM inequality>.] For an <antichain> $\mathcal F$ in the <Boolean lattice>,
$$
\boxed{\sum_{F\in\mathcal F}\binom n{|F|}^{-1}\leq1.}
$$
To prove this by <double counting>, generate a <maximal chain in a Boolean lattice> from a <permutation> $\pi$ of $[n]$: its members are the first $j$ entries of $\pi$, for $0\leq j\leq n$. A particular $j$-set belongs to exactly $j!(n-j)!$ of the $n!$ resulting <maximal chains in a Boolean lattice>. Each such <maximal chain in a Boolean lattice> meets the <antichain> at most once. Counting pairs consisting of a member of $\mathcal F$ and a <permutation> whose associated <maximal chain in a Boolean lattice> contains it gives
$$
\sum_{F\in\mathcal F}|F|!(n-|F|)!\leq n!.
$$
Division by $n!$ proves the <LYM inequality>, including the empty <antichain> and the levels containing $\varnothing$ or $[n]$.
\b[A <symmetric chain decomposition of a Boolean lattice>.] A <symmetric chain> has one set at every size from $k$ to $n-k$, with consecutive members related by inclusion. Start with the single <symmetric chain> containing $\varnothing$ when $n=0$. Given a <symmetric chain>
$$
A_k\subset A_{k+1}\subset\cdots\subset A_{n-k}
$$
in a <symmetric chain decomposition of a Boolean lattice> on $[n]$, let $x=n+1$ and replace its two copies in the larger <Boolean lattice> by
$$
A_k\subset\cdots\subset A_{n-k}\subset A_{n-k}\cup\{x\},
$$
and, when it is nonempty, by
$$
A_k\cup\{x\}\subset\cdots\subset A_{n-k-1}\cup\{x\}.
$$
The endpoint sizes of the first <symmetric chain> sum to $n+1$; those of the second <symmetric chain> also sum to $n+1$. These <symmetric chains> partition the original <symmetric chain> together with its copy containing $x$. Thus this construction inductively partitions the entire <Boolean lattice> into <symmetric chains>. Each <symmetric chain> contains exactly one set of size $\lfloor n/2\rfloor$, so the number of <symmetric chains> is
$$
\boxed{\binom n{\lfloor n/2\rfloor}.}
$$
\b[The proposed sum bound for <cross-intersecting families> is false.] Take $n=3$ and
$$
\mathcal A=\mathcal B=\bigl\{\{1,2\},\{1,3\},\{2,3\}\bigr\}.
$$
Both are <antichains>, and any member of one meets any member of the other. Nevertheless,
$$
\boxed{|\mathcal A|+|\mathcal B|=6>3=\binom3{\lfloor3/2\rfloor}.}
$$
The hypothesis permits the two <antichains> to coincide. Even if distinct <antichains> were wanted, taking $\mathcal B=\{\{1,2\},\{1,3\}\}$ gives $5>3$.
Back to article page
