If the longest chain in a partial order is of length n, then the partial order can be written as a _____ of n antichains.

GATE 1991 · Discrete Mathematics · Partial Order · medium

Answer: union (a partial order with longest chain length n is a union of n antichains)

1. Define Mirsky rank layers: Define rank(x) = length of longest chain with x as maximum. Layer k = {x : rank(x) = k} is an antichain: if x <= y and rank(x) = rank(y), the chain through x to y would be longer, contradicting maximality. Ranks run from 1 to n.
2. State the decomposition as a union: The n Mirsky layers are disjoint and together cover all elements of P. So the partial order is written as a UNION of n antichains.