Binary initial segment 2026-10-06
An initial segment of the binary order on the discrete cube contains the vertices whose integer encodings are . It is a down-set, so its internal edges and two-dimensional cube faces can be counted at their unique upper vertices by and .
Harper theorem implies the Kruskal-Katona theorem Created 2026-10-06 Updated 2026-10-07
Adjoin all lower levels to a uniform set family before applying Harper theorem. Its remaining neighbourhood contribution is the upper shadow, so lexicographic initial segments minimize upper shadows. Complementation and reversal of coordinates turn this into colexicographic order minimizing the lower shadow, giving the Kruskal-Katona theorem.
Equality in Harper theorem need not make a down-set a cube-automorphic image of a simplicial initial segment. In , take all sets of size at most one and the four two-element sets forming a four-cycle. This family has size nine and closed graph neighbourhood size fifteen, just like the size-nine simplicial order on the discrete cube initial segment. The induced degree of a vertex distributions differ, so they cannot be related by a graph automorphism.
Past exam of the mathematics course of the University of Cambridge 2008 ii Paper 1 16G Solution Created 2026-09-24 Updated 2026-09-24