Theory of partially-ordered sets (posets) — sets equipped with a binary relation ≤ that is reflexive, antisymmetric and transitive. Central concepts: chains (totally-ordered subsets), antichains (mutually-incomparable subsets), lattices…
order-theory
Dilworth: width(P) = min chain cover
Dilworth 1950 (Ann. Math. 51:161) — the minimum number of totally-ordered chains needed to partition a finite poset P equals the maximum…
Birkhoff: finite distributive lattice ↔ J(P) of down-sets of join-irreducibles
Birkhoff 1937 representation theorem — every finite distributive lattice L is isomorphic to the lattice of down-sets of its subposet of…
Poset / lattice foundations: reflexive-antisymmetric-transitive ≤ and join/meet
A partially-ordered set (P, ≤) is a set P with a binary relation ≤ satisfying reflexivity x ≤ x, antisymmetry x ≤ y ∧ y ≤ x ⇒ x = y, and…
Sperner: width(2^[n]) = C(n, ⌊n/2⌋) exact
Sperner 1928 (Math. Z. 27:544) — the maximum antichain size of the Boolean lattice 2^[n] (power set of {1,...,n} ordered by inclusion) is…
Mirsky: height(2^[n]) = n+1 exact
Mirsky 1971 dual of Dilworth — the maximum chain length in 2^[n] is n+1, achieved by the full flag of successive single-element extensions…
Birkhoff down-set counts: |J(chain_3)|=4, |J(antichain_3)|=8, |J(V)|=5
Exact enumeration of down-sets J(P) for three canonical 3-element posets, demonstrating Birkhoff's representation in action. (1) Chain-3…