1. Dilworth's Theorem

1.1 Definition. The width of a partially ordered set $P$ is the cardinality of the largest antichain. (For example, a chain has width 1.)

Observation. If $P$ is the union of $n$ chains, then $P$ has width at most $n$.

1.2 Theorem (R. P. Dilworth) Let $P$ be a finite partially ordered set of width $n$. Then $P$ is a union of $n$ chains.

This is a kind of minimax theorem, in that it shows that the maximum size of an antichain in $P$ is the minimum number of chains whose union is $P$. There are a number of combinatorial consequences. Here is one:

Let $\rho$ be a binary relation between finite sets $A$ and $B$, i.e., $\rho \subseteq A \times B$. A matching of $A$ into $B$ is a one-to-one function $f:A\rightarrow B$ such that for all $a \in A$, $a \rho f(a)$.

1.3 Corollary (P. Hall's matching theorem) Given $\rho$, a necessary and sufficient condition for the existence of a matching of $A$ into $B$ is that for each $k=1,2,\dots$,

(*) any $k$ elements of $A$ are related to at least $k$ elements of $B$, in the sense that each of these elements of $B$ is related to at least one of the $k$ elements of $A$.

(In the proof, the disjoint union of $A$ and $B$ is made into a partially ordered set by declaring $a < b$ when $a \rho b$.)

1.4 Definition Let $A _ 1,\dots, A _ n$ be subsets of a finite set. A system of distinct representatives (SDR) for the $A _ i$ is a set of distinct elements $a _ 1,\dots, a _ n$ with $a _ i \in A _ i$.

An obvious necessary condition for the existence of an SDR is (*) For each $k \leq n$, the union of any $k$ of the $A _ i$ has at least $k$ elements.

1.5 Corollary (P. Hall's theorem on distinct representatives) The condition (*) is a necessary and sufficient condition for the existence of an SDR.

Recall that subsets $A _ 1,\dots, A _ n$ of a set $S$ form a partition of $S$ if the $A _ i$ are pairwise disjoint and have union $S$. The $A _ i$ are called the blocks of the partition.

We say that a partition is an equipartition if all its blocks have the same cardinality.

1.6 Corollary (Equipartition theorem) Two equipartions of a finite set $S$, each with the same number of blocks, have a system of common representatives (SCR)--in other words, one set of elements that constitutes a system of distinct representatives for both of the two equipartitions.