Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 109 4 ii Solution 2026-09-28
Fix and consider the tracesFor distinct , the hypothesis applied in both orders saysEquivalently, neither trace contains the other. Thus the traces are distinct and form an antichain in the Boolean lattice on the points of . By Sperner theorem,which is the required bound.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 109 4 i Solution 2026-09-28
Choose a Uniformly random maximal chain in a Boolean lattice. A fixed -element set lies on the chain with probability . Since an antichain meets any chain at most once, the expected number of its members on the chain is at most one:This is the Lubell--Yamamoto--Meshalkin inequality.
For the equality case, every maximal chain must meet . Suppose has size and is obtained from by exchanging one element. There is a maximal chain whose rank- member is , whose rank- member is , and whose rank- member is . Every lower member is contained in and every higher member contains , so antichainness excludes all of them. Equality forces . The graph of -subsets joined by one-element exchanges is connected, hence . Conversely, a full level clearly gives equality.
Since ,The equality characterization above leaves exactly either middle level. This proves Sperner theorem with its equality cases.