Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 12 1 i Solution Created 2026-10-03 Updated 2026-10-14
For and a rank- uniform set family , let be its lower shadow. Count pairs with , and . Every contributes pairs, whereas each shadow member lies in at most rank- sets. ThusThis is the Local LYM inequality. Complementation gives the upper-shadow form for .
To deduce the LYM inequality, let be an antichain, its rank- part, and all rank- sets containing some member of . For ,The union is disjoint because an antichain member cannot contain a smaller member; every other set of contains a rank- superset of its smaller witnessing member. Apply the upper local inequality and put :Since and , summing givesThus the deduction uses the local inequality explicitly, rather than quoting a separate maximal-chain argument.
Let , the largest rank size. The LYM sum is at least , proving the Sperner theorem bound. If , equality forces all its members onto ranks with binomial coefficient . For even , there is only the middle rank, so the family is that whole rank.
For , only ranks are possible, each of size . Let . Antichainness gives , and local LYM gives . Since the two antichain parts together have size , equality must hold. The inclusion graph between these ranks is -regular on each side. Its edges from already number , so equality leaves no edge from to the complementary upper vertices.
The graph is connected: exchanging one element between two -sets joins them through their -element union, and successive exchanges connect all lower vertices; every upper vertex has a lower neighbour. Consequently is either empty or the entire upper rank. This connectedness of adjacent-level incidence in a Boolean lattice excludes mixed extremizers. HenceThere is one choice for even and two for odd . For , the sole maximum family is , agreeing with this description.