Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 12 / 1 / ii / Solution

Proceed by induction on the ground-set size, starting with the one-element chain $\{\varnothing \}$ in the Boolean lattice on no coordinates. Suppose a symmetric chain decomposition of a Boolean lattice on $[n]$ has been constructed. Write one of its chains asOn adjoining the new coordinate $v=n+1$, replace its two copies byand, when nonempty,The first chain has endpoint ranks $r,n-r+1$, summing to $n+1$. The second has endpoint ranks $r+1,n-r$, also summing to $n+1$. Both are saturated chains, increasing rank by one at every step. If the original chain was a singleton, the second chain is omitted.

These new chains are disjoint: the first contains every old set without $v$ and just the last old set with $v$; the second contains precisely the remaining old sets with $v$. Thus together they cover both lifted copies of the old chain. Different old chains have disjoint copies, so performing this construction for each yields a partition of all subsets of $[n+1]$ into symmetric chains. This completes the induction and proves a symmetric chain partition exists for every $n$.