Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 109 / 1

Proceed by mathematical induction on $n$. The cases $n=0,1$ are immediate. Given a symmetric chain decomposition of a Boolean lattice $\mathcal{P}([n-1])$, consider one of its chainsIt produces the two chainsand, when nonempty,The first runs from rank $r$ to rank $n-r$, and the second from rank $r+1$ to rank $n-1-r$; both endpoint ranks sum to $n$. They are disjoint and together contain the old chain both without and with $n$. Doing this for every old chain partitions $\mathcal{P}([n])$ into symmetric chains.

Choose symmetric chain decompositions of $\mathcal{P}(X_1)$ and $\mathcal{P}(X_2)$. Their Cartesian products partition $\mathcal{P}(X)$ into grids $C_1\times C_2$. Within one grid, two members in the same row differ only in $X_1$, and two in the same column differ only in $X_2$. The hypothesis on $\mathcal{F}$ therefore permits at most one member in each row and each column. Hence

Because $n_1$ and $n_2$ are even, both symmetric chains have odd length and are centred at ranks $n_1/2$ and $n_2/2$. The grid contains exactly $\min \{|C_1|,|C_2|\}$ points whose two ranks sum to $n/2$: they lie on its central antidiagonal. Thus the bound for $\mathcal{F}$ in each grid is the number of rank-$n/2$ subsets in that grid. Summing over all grids gives